Zum Inhalt springen

NTRUSign

aus Wikipedia, der freien Enzyklopädie

NTRUSign ist ein digitales Signaturverfahren, das 2003 entwickelt wurde.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Es basiert auf dem Goldreich-Goldwasser-Halewi-Signaturverfahren und ist der Nachfolger des unsicheren NSS-Verfahrens, wird aber ebenfalls als unsicher betrachtet.

Beschreibung des Verfahrens

Ebenso wie in NTRUEncrypt laufen auch NTRUSign die Berechnungen (mit Ausnahme der Division durch die Resultante) im Ring <math>R = \Z_q[X]/(X^N-1)</math> ab, wobei die Multiplikation „*“ eine zyklische Faltung modulo <math>q</math> ist: Das Produkt zweier Polynome <math>f = [f_0, f_1, \ldots, f_{N-1}]</math> und <math>g = [g_0, g_1, \ldots, g_{N-1}]</math> ist <math>f*g = \sum_{i+j \equiv k \mod N}f_i \cdot g_j \mod q</math>.

Es kann bei NTRUSign entweder das Standard- oder das transponierte Gitter zugrunde gelegt werden. Das transponierte Gitter hat den Vorteil, dass das Polynom <math>f'</math> nur Koeffizienten in {-1, 0, 1} enthält und sich dadurch schneller multiplizieren lässt.

Weiterhin kann der Parameter <math>B</math>, die Zahl sogenannter Perturbationen, gewählt werden. Es hat sich allerdings herausgestellt, dass 0 Perturbationen unsicher und mehr als eine nicht notwendig sind, daher ist <math>B</math> in der Praxis immer gleich 1.

Außerdem sind die Größen <math>N</math> (Anzahl Polynomkoeffizienten), <math>q</math> (Modulus), <math>d</math> (Anzahl Koeffizienten = −1), <math>\beta</math> (Normkorrekturfaktor) und <math>\mathcal{N}</math> (Normschranke) von Bedeutung.

Schlüsselerzeugung

Es werden <math>B</math> sogenannte Basen erzeugt. Jede davon besteht aus 3 Polynomen, die mit <math>f, f'</math> und <math>h</math> bezeichnet werden. Das Polynom <math>h</math> der ersten Basis bildet den öffentlichen Schlüssel, alle anderen Polynome sämtlicher Basen bilden zusammen den Privatschlüssel.

Basiserzeugung

Es wird hier die Variante nach Hoffstein et al.<ref>Hoffstein, Pipher, Silverman: An Introduction to mathematical Cryptography, Springer 2008, ISBN 978-0-387-77993-5</ref> beschrieben. Im EESS-Standard<ref name=EESS><templatestyles src="Webarchiv/styles.css" />{{#if:20120316123207 

      | {{#ifeq: 20120316123207 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20120316123207}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-03 02:06:06 InternetArchiveBot | 2019-05-03 02:06:06 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20120316123207}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-03 02:06:06 InternetArchiveBot | 2019-05-03 02:06:06 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-03 02:06:06 InternetArchiveBot | 2019-05-03 02:06:06 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }} (Memento{{#if: {{#if: 2019-05-03 02:06:06 InternetArchiveBot | 2019-05-03 02:06:06 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Archivierte Kopie | {{#invoke:WLink|getEscapedTitle|Archivierte Kopie}} | {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}} }}  
                 }}}}}}}}{{#if:2019-05-03 02:06:06 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20120316123207|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf}}
    || {{#if:  || }}
  }}{{#if: Archivierte Kopie
    | {{#if: {{#invoke:WLink|isBracketedLink|Archivierte Kopie}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} Efficient Embedded Security Standard</ref> findet die Invertierung der Polynome <math>f</math> und <math>g</math> nicht in <math>\R</math>, sondern in <math>\Z</math> statt. Dadurch kommt man zwar ohne Kommazahlen aus und erhält „bessere“ (normkleinere) Polynome F und G, muss aber zusätzlich eine aufwändige Resultantenberechnung durchführen.

Zur Generierung einer Basis <math>(f, f', h)</math> geht man wie folgt vor:

  1. Wahl eines zufälligen Polynoms <math>f</math>, dessen Koeffizienten in {-1, 0, 1} liegen und das modulo <math>q</math> invertierbar ist.
  2. Wahl eines zufälligen Polynoms <math>g</math>, dessen Koeffizienten in {-1, 0, 1} liegen und das modulo <math>q</math> invertierbar ist.
  3. Resultante <math>R_f</math> von <math>f</math> und ein Polynom <math>\rho_f</math> berechnen, so dass <math>\rho_f * f + \tau_f * (x^n-1) = R_f</math> für ein beliebiges Polynom <math>\tau_f</math> gilt. Dieser Schritt ist der rechenintensivste. Mildern kann man dies, indem man für mehrere Primzahlen <math>p_i</math> die Resultante modulo <math>p_i</math> berechnet und die Gesamtresultante aus den Moduli rekonstruiert. Zu Einzelheiten der Resultantenberechnung siehe Abschnitte 2.2.7.1 und 2.2.7.2 des EESS-Standards<ref name=EESS />.
  4. Resultante <math>R_g</math> von <math>g</math> und ein Polynom <math>\rho_g</math> berechnen, so dass <math>\rho_g * g+\tau_g * (x^n-1)=R_g</math> für ein beliebiges Polynom <math>\tau_g</math> gilt.
  5. Wenn <math>GGT(R_f,R_g)</math>≠1 ist, wieder bei Schritt 1 anfangen.
  6. Mittels des erweiterten euklidischen Algorithmus zwei Zahlen <math>S_f</math> und <math>S_g</math> ermitteln, so dass <math>S_f R_f+S_g R_g=1</math> gilt.
  7. <math>A(x)=qS_f\rho_f(x)</math> und <math>B(x)=-qS_g\rho_g(x)</math> setzen.
  8. Inverse <math>f^{-1}(x)=\rho_f(x)/R_f</math> und <math>g^{-1}(x)=\rho_g(x)/R_g</math> in <math>\R[x]/(x^N-1)</math> auf genügend viele Dezimalstellen berechnen.
  9. <math>C(x)=\lfloor 1/2(B(x)*f^-1(x)+A(x)*g^-1(x)) \rceil</math>. Anmerkung: <math>\lfloor</math> und <math>\rceil</math> sind Gaußklammern.
  10. <math>F(x)=B(x)-C(x)*f(x)</math> und <math>G(x)=A(x)-C(x)*g(x)</math>.
  11. <math>f_q</math> = die Inverse von <math>f</math> modulo <math>q</math>.
  12. Im Standardfall: <math>f'=F</math> und <math>h=g*f_q \mod q</math>
  13. Im transponierten Fall: <math>f'=g</math> und <math>h=F*f_q \mod q</math>

Signierung

Sei m die zu signierende Nachricht.

Für <math>i=B</math> bis 0 werden folgende Schritte ausgeführt:

  1. <math>(f, f', h)</math> = <math>i</math>-te Basis
  2. <math>x = \lfloor -\frac{1}{q}m_i*f'_i \rceil</math>
  3. <math>y = \lfloor \frac{1}{q}m_i*f_i \rceil</math>
  4. <math>s_i = x*f + y*f'</math>
  5. <math>m_i = si*(h_i-h_{i-1}) \mod q</math>
  6. <math>s = s + s_i</math>

<math>s</math> ist die Signatur.

Beachte: Unter bestimmten Umständen kann es vorkommen, dass die Signatur trotz gültigen Schlüssels ungültig ist. Es empfiehlt sich daher, die Signatur nach der Erzeugung zu überprüfen und ggf. nochmals zu signieren.

Signaturprüfung

Sei <math>m</math> die Nachricht, <math>h</math> der öffentliche Schlüssel und <math>s</math> die Signatur. Die Norm <math>||t||</math> eines Polynoms <math>t</math> sei durch <math>\inf_{0 \leq k<q} ||t+kq||_z</math> gegeben, wobei <math>||r||_z = \sum_{i=0}^{N-1}r_i^2 - \frac{1}{N}\sum_{i=0}^{N}r_i</math> ist (letztere wird als zentrierte Euklidische Norm bezeichnet).

Die Signatur wird dann wie folgt überprüft:

  1. <math>b = \sqrt{||s||^2 + \beta^2||s*h-m||^2}</math>
  2. Die Signatur ist gültig, wenn <math>b<\mathcal{N}</math> ist.

Bemerkung: Die Berechnung der Norm über die Definition ist ineffizient. Eine bessere Methode ist es, auf alle Polynomkoeffizienten eine Konstante zu addieren, so dass die zwei Koeffizienten mit dem größten Abstand gleich weit von <math>\frac{q}{2}</math> entfernt sind (jeweils modulo <math>q</math>). Die Norm ergibt sich dann durch die zentrierte Euklidnorm (s. o.) des so entstandenen Polynoms.

Effizienz

Um die Multiplikation zu beschleunigen, können die Parameter <math>f</math> und <math>g</math> so gewählt werden, dass viele Koeffizienten Null sind. Dazu wird ein Parameter <math>d</math> gewählt und bei der Wahl von <math>f</math> und <math>g</math> werden <math>d</math> Koeffizienten gleich 1, <math>d-1</math> Koeffizienten gleich −1 und der Rest gleich 0 gesetzt.

Die Prüfung mehrerer Signaturen lässt sich beschleunigen, indem man statt der einzelnen Normen die Norm der Summe der Signaturen überprüft. Die Parameter <math>N</math> und <math>\mathcal{N}</math> müssen dazu erhöht werden.

Sicherheit

Die mit dem Verfahren erstellten Signaturen verraten Informationen über den geheimen Schlüssel. Diese Tatsache wurde 2006 ausgenutzt, um das Verfahren anzugreifen: Ungefähr 400 Signaturen reichten aus, um den geheimen Schlüssel zu berechnen.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Das Verfahren wurde nach diesem Angriff angepasst, Perturbationen sollten das Berechnen des geheimen Schlüssels erheblich erschweren. Das verbesserte Verfahren wurde 2012 angegriffen, der geheime Schlüssel konnte aus mehreren Tausend Signaturen berechnet werden.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Einzelnachweise

<references />

Weblinks

| DEPATIS =US7308097B2 | WIPO = US7308097B2 | Google = US7308097B2 | #default =US7308097B2 }}}}{{#if:Digital signature and authentication method and apparatus2002-12-062007-12-11NTRU Cryptosystems IncJeffrey Hoffstein et Alläuft nach der 20-jährigen Spanne am 6. Dezember 2022 ab|:|.}}{{#if:Digital signature and authentication method and apparatus| Digital signature and authentication method and apparatus.}}{{#if:2002-12-06| Angemeldet am {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:2007-12-11NTRU Cryptosystems IncJeffrey Hoffstein et Al|,}}}}{{#if:2007-12-11|{{#if:2002-12-06| veröffentlicht am | Veröffentlicht am }}{{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:NTRU Cryptosystems IncJeffrey Hoffstein et Al|,}}}}{{#if:NTRU Cryptosystems Inc| Anmelder: NTRU Cryptosystems Inc{{#if:Jeffrey Hoffstein et Al|,}}}}{{#if:Jeffrey Hoffstein et Al| Erfinder: Jeffrey Hoffstein et Al}}{{#if:läuft nach der 20-jährigen Spanne am 6. Dezember 2022 ab| (läuft nach der 20-jährigen Spanne am 6. Dezember 2022 ab)}}{{#if:2002-12-062007-12-11NTRU Cryptosystems IncJeffrey Hoffstein et Alläuft nach der 20-jährigen Spanne am 6. Dezember 2022 ab|.}}‌}}{{#invoke:TemplatePar|match |template= Vorlage:Patent |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Patent}} |format= |preview=@@@ |1=Land= ABC+ |2=V-Nr= /^[0-9A-Z]+$/ |3=Titel= * |4=Erfinder= * |5=Anmelder= * |6=A-Datum= * |7=V-Datum= * |8=Typ= ASCII |9=Code= ASCII |10=Kommentar= * |11=KeinLink= ASCII |12=DB=ASCII }}

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=NTRUSign&oldid=2291382“