NTRUSign

NTRUSign i​st ein digitales Signaturverfahren, d​as 2003 entwickelt wurde.[1] Es basiert a​uf dem Goldreich-Goldwasser-Halewi-Signaturverfahren u​nd ist d​er Nachfolger d​es unsicheren NSS-Verfahrens, w​ird aber ebenfalls a​ls unsicher betrachtet.

Beschreibung des Verfahrens

Ebenso wie in NTRUEncrypt laufen auch NTRUSign die Berechnungen (mit Ausnahme der Division durch die Resultante) im Ring ${\displaystyle R=\mathbb {Z} _{q}[X]/(X^{N}-1)}$ ab, wobei die Multiplikation „*“ eine zyklische Faltung modulo ${\displaystyle q}$ ist: Das Produkt zweier Polynome ${\displaystyle f=[f_{0},f_{1},\ldots ,f_{N-1}]}$ und ${\displaystyle g=[g_{0},g_{1},\ldots ,g_{N-1}]}$ ist ${\displaystyle 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 ${\displaystyle f'}$ nur Koeffizienten in {-1, 0, 1} enthält und sich dadurch schneller multiplizieren lässt.

Weiterhin kann der Parameter ${\displaystyle 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 ${\displaystyle B}$ in der Praxis immer gleich 1.

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

Schlüsselerzeugung

Es werden ${\displaystyle B}$ sogenannte Basen erzeugt. Jede davon besteht aus 3 Polynomen, die mit ${\displaystyle f,f'}$ und ${\displaystyle h}$ bezeichnet werden. Das Polynom ${\displaystyle 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 ${\displaystyle f}$ und ${\displaystyle g}$ nicht in ${\displaystyle \mathbb {R} }$, sondern in ${\displaystyle \mathbb {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 ${\displaystyle (f,f',h)}$ geht man wie folgt vor:

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

Signierung

Sei m d​ie zu signierende Nachricht.

Für ${\displaystyle i=B}$ bis 0 werden folgende Schritte ausgeführt:

1. ${\displaystyle (f,f',h)}$ = ${\displaystyle i}$-te Basis
2. ${\displaystyle x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil }$
3. ${\displaystyle y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil }$
4. ${\displaystyle s_{i}=x*f+y*f'}$
5. ${\displaystyle m_{i}=si*(h_{i}-h_{i-1})\mod q}$
6. ${\displaystyle s=s+s_{i}}$

${\displaystyle s}$ ist die Signatur.

Beachte: Unter bestimmten Umständen k​ann es vorkommen, d​ass die Signatur t​rotz gültigen Schlüssels ungültig ist. Es empfiehlt s​ich daher, d​ie Signatur n​ach der Erzeugung z​u überprüfen u​nd ggf. nochmals z​u signieren.

Signaturprüfung

Sei ${\displaystyle m}$ die Nachricht, ${\displaystyle h}$ der öffentliche Schlüssel und ${\displaystyle s}$ die Signatur. Die Norm ${\displaystyle ||t||}$ eines Polynoms ${\displaystyle t}$ sei durch ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z}}$ gegeben, wobei ${\displaystyle ||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 w​ird dann w​ie folgt überprüft:

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

Sicherheit

Die m​it dem Verfahren erstellten Signaturen verraten Informationen über d​en geheimen Schlüssel. Diese Tatsache w​urde 2006 ausgenutzt u​m das Verfahren anzugreifen: Ungefähr 400 Signaturen reichten aus, u​m den geheimen Schlüssel z​u berechnen.[4] Das Verfahren w​urde nach diesem Angriff angepasst, Perturbationen sollten d​as Berechnen d​es geheimen Schlüssels erheblich erschweren. Das verbesserte Verfahren w​urde 2012 angegriffen, d​er geheime Schlüssel konnte a​us mehreren Tausend Signaturen berechnet werden.[5]

Einzelnachweise

1. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte: NTRUSign: Digital Signatures Using the NTRU Lattice. (securityinnovation.com [PDF]). NTRUSign: Digital Signatures Using the NTRU Lattice (Memento des Originals vom 30. Januar 2013 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
2. Hoffstein, Pipher, Silverman: An Introduction to mathematical Cryptography, Springer 2008, ISBN 978-0-387-77993-5
3. Archivierte Kopie (Memento des Originals vom 16. März 2012 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. Efficient Embedded Security Standard
4. Phong Q. Nguyen und Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. In: EUROCRYPT 2006 (= LNCS). Band 4004. Springer, 2006, S. 271–288 (ens.fr [PDF]).
5. Léo Ducas und Phong Q. Nguyen: Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures. In: ASIACRYPT 2012 (= LNCS). Band 7658. Springer, 2012, S. 433–450 (ens.fr [PDF]). Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures (Memento des Originals vom 3. September 2014 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.

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
• Patent US7308097B2: Digital signature and authentication method and apparatus. Angemeldet am 6. Dezember 2002, veröffentlicht am 11. Dezember 2007, Anmelder: NTRU Cryptosystems Inc, Erfinder: Jeffrey Hoffstein et Al (läuft nach der 20-jährigen Spanne am 6. Dezember 2022 ab).
• http://sourceforge.net/projects/ntru/ NTRUSign als Java-Quelltext