NTRUSign

NTRUSign ist ein digitales Signaturverfahren, das 2003 entwickelt wurde^[1]. Es basiert auf dem Goldreich-Goldwasser-Halewi-Signaturverfahren und ist der Nachfolger des unsicheren NSS-Verfahrens. Es ist mit NTRUEncrypt verwandt.

Beschreibung des Verfahrens

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

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

Weiterhin kann der Parameter B, 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 B in der Praxis immer gleich 1.

Außerdem sind die Größen N (Anzahl Polynomkoeffizienten), q (Modulus), d (Anzahl Koeffizienten = -1), β (Normkorrekturfaktor) und $\mathcal{N}$ (Normschranke) von Bedeutung.

Schlüsselerzeugung

Es werden B sogenannte Basen erzeugt. Jede davon besteht aus 3 Polynomen, die mit f,f' und h bezeichnet werden. Das Polynom h 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.^[2] beschrieben. Im EESS-Standard^[3] findet die Invertierung der Polynome f und g nicht in $\R$, sondern in $\Z$ 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 (f,f',h) geht man wie folgt vor:

1. Wahl eines zufälligen Polynoms f, dessen Koeffizienten in {-1, 0, 1} liegen und das modulo q invertierbar ist.
2. Wahl eines zufälligen Polynoms g, dessen Koeffizienten in {-1, 0, 1} liegen und das modulo q invertierbar ist.
3. Resultante R_f von f und ein Polynom ρ_f berechnen, so dass ρ_f * f + τ_f * (xⁿ − 1) = R_f für ein beliebiges Polynom τ_f gilt. Dieser Schritt ist der rechenintensivste. Mildern kann man dies, indem man für mehrere Primzahlen p_i die Resultante modulo p_i 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^[3].
4. Resultante R_g von g und ein Polynom ρ_g berechnen, so dass ρ_g * g + τ_g * (xⁿ − 1) = R_g für ein beliebiges Polynom τ_g gilt.
5. Wenn GGT(R_f,R_g)≠1 ist, wieder bei Schritt 1 anfangen.
6. Mittels des erweiterten euklidischen Algorithmus' zwei Zahlen S_f und S_g ermitteln, so dass S_fR_f + S_gR_g = 1 gilt.
7. A(x) = qS_fρ_f(x) und B(x) = − qS_gρ_g(x) setzen.
8. Inverse f ^{− 1}(x) = ρ_f(x) / R_f und g ^{− 1}(x) = ρ_g(x) / R_g in $\R[x]/(x^N-1)$ auf genügend viele Dezimalstellen berechnen.
9. $C(x)=\lfloor 1/2(B(x)*f^-1(x)+A(x)*g^-1(x)) \rceil$. Anmerkung: $\lfloor$ und $\rceil$ sind Gaußklammern.
10. F(x) = B(x) − C(x) * f(x) und G(x) = A(x) − C(x) * g(x).
11. f_q = die Inverse von f modulo q.
12. Im Standardfall: f' = F und $h=g*f_q \mod q$
13. Im transponierten Fall: f' = g und $h=F*f_q \mod q$

Signierung

Sei m die zu signierende Nachricht.

Für i = B bis 0 werden folgende Schritte ausgeführt:

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

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

Die Signatur wird dann wie folgt überprüft:

1. $b = \sqrt{||s||^2 + \beta^2||s*h-m||^2}$
2. Die Signatur ist gültig, wenn $b<\mathcal{N}$ 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 $\frac{q}{2}$ entfernt sind (jeweils modulo q). 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 f und g so gewählt werden, dass viele Koeffizienten Null sind. Dazu wird ein Parameter d gewählt und bei der Wahl von f und g werden d Koeffizienten gleich 1, d − 1 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 N und $\mathcal{N}$ müssen dazu erhöht werden.

Sicherheit

Da NTRUSign-Signaturen Informationen über den Privatschlüssel enthalten, kann ein Angreifer, der ausreichend viele Signaturen kennt, den Privatschlüssel ermitteln. Es darf deshalb mit einem Schlüsselpaar nur eine begrenzte Anzahl Signaturen erstellt werden. Die Autoren geben an, dass mit einer Perturbation über 10¹⁰ Signaturen erzeugt werden können, ohne den Schlüssel zu gefährden (ohne Perturbationen sind es nur 400^[4]). Zur Sicherheit wird aber empfohlen, schon nach 10 Mio. Signaturen den Schlüssel zu wechseln. Ist dies nicht praktikabel, kann bei der Schlüsselerzeugung auch die Anzahl Perturbationen und damit die Lebensdauer des Schlüssels erhöht werden.

Jede Signatur ist nicht nur für die signierte Nachricht, sondern auch für alle naheliegenden (im Sinne der zentrierten Euklidnorm) Nachrichten gültig. Deshalb (und aus Effizienzgründen) wird nicht die Nachricht selber, sondern ein Streuwert signiert.

Einzelnachweise

1. ↑ Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte: NTRUSign: Digital Signatures Using the NTRU Lattice. (http://www.securityinnovation.com/cryptolab/pdf/NTRUSign_RSA.pdf).
2. ↑ Hoffstein, Pipher, Silverman: An Introduction to mathematical Cryptography, Springer 2008, ISBN 978-0-387-77993-5
3. ↑ ^{a b} http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf Efficient Embedded Security Standard
4. ↑ Phong Q. Nguyen: A Note on the Security of NTRUSign. (http://eprint.iacr.org/2006/387.pdf).

Weblinks

• http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf Beschreibung des Algorithmus
• http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/NTRUSignParams-2005-08.pdf Ergänzungen, Optimierungen und Herleitung von Parametern
• http://www.freepatentsonline.com/7308097.pdf US-Softwarepatent auf NTRUSign, läuft nach der 20jährigen Spanne am 6. Dezember 2022 ab
• http://sourceforge.net/projects/ntru/ NTRUSign als Java-Quelltext