www.wikidata.de-de.nina.az

NTRUSign ist ein digitales Signaturverfahren das 2003 entwickelt wurde 1 Es basiert auf dem Goldreich Goldwasser Halewi

NTRUSign

NTRUSign ist ein digitales Signaturverfahren, das 2003 entwickelt wurde. 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 Bearbeiten

Ebenso wie in NTRUEncrypt laufen auch NTRUSign die Berechnungen (mit Ausnahme der Division durch die Resultante) im Ring ab, wobei die Multiplikation „*“ eine zyklische Faltung modulo ist: Das Produkt zweier Polynome und ist .

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

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

Außerdem sind die Größen (Anzahl Polynomkoeffizienten), (Modulus), (Anzahl Koeffizienten = −1), (Normkorrekturfaktor) und (Normschranke) von Bedeutung.

Schlüsselerzeugung Bearbeiten

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

Basiserzeugung Bearbeiten

Es wird hier die Variante nach Hoffstein et al. beschrieben. Im EESS-Standard findet die Invertierung der Polynome und nicht in , sondern in 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 geht man wie folgt vor:

  1. Wahl eines zufälligen Polynoms , dessen Koeffizienten in {-1, 0, 1} liegen und das modulo invertierbar ist.
  2. Wahl eines zufälligen Polynoms , dessen Koeffizienten in {-1, 0, 1} liegen und das modulo invertierbar ist.
  3. Resultante von und ein Polynom berechnen, so dass für ein beliebiges Polynom gilt. Dieser Schritt ist der rechenintensivste. Mildern kann man dies, indem man für mehrere Primzahlen die Resultante modulo 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.
  4. Resultante von und ein Polynom berechnen, so dass für ein beliebiges Polynom gilt.
  5. Wenn ≠1 ist, wieder bei Schritt 1 anfangen.
  6. Mittels des erweiterten euklidischen Algorithmus zwei Zahlen und ermitteln, so dass gilt.
  7. und setzen.
  8. Inverse und in auf genügend viele Dezimalstellen berechnen.
  9. . Anmerkung: und sind Gaußklammern.
  10. und .
  11. = die Inverse von modulo .
  12. Im Standardfall: und
  13. Im transponierten Fall: und

Signierung Bearbeiten

Sei m die zu signierende Nachricht.

Für bis 0 werden folgende Schritte ausgeführt:

  1. = -te Basis

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 Bearbeiten

Sei die Nachricht, der öffentliche Schlüssel und die Signatur. Die Norm eines Polynoms sei durch gegeben, wobei ist (letztere wird als zentrierte Euklidische Norm bezeichnet).

Die Signatur wird dann wie folgt überprüft:

  2. Die Signatur ist gültig, wenn 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 entfernt sind (jeweils modulo ). Die Norm ergibt sich dann durch die zentrierte Euklidnorm (s. o.) des so entstandenen Polynoms.

Effizienz Bearbeiten

Um die Multiplikation zu beschleunigen, können die Parameter und so gewählt werden, dass viele Koeffizienten Null sind. Dazu wird ein Parameter gewählt und bei der Wahl von und werden Koeffizienten gleich 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 und müssen dazu erhöht werden.

Sicherheit Bearbeiten

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. 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.

Einzelnachweise Bearbeiten

  1. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte: NTRUSign: Digital Signatures Using the NTRU Lattice. (securityinnovation.com [PDF]).
  2. Hoffstein, Pipher, Silverman: An Introduction to mathematical Cryptography, Springer 2008, ISBN 978-0-387-77993-5
  3. ↑ (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.@1@2Vorlage:Webachiv/IABot/grouper.ieee.org 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]).

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 wird aber ebenfalls als unsicher betrachtet Inhaltsverzeichnis 1 Beschreibung des Verfahrens 1 1 Schlusselerzeugung 1 1 1 Basiserzeugung 1 2 Signierung 1 3 Signaturprufung 1 4 Effizienz 1 5 Sicherheit 2 Einzelnachweise 3 WeblinksBeschreibung des Verfahrens BearbeitenEbenso wie in NTRUEncrypt laufen auch NTRUSign die Berechnungen mit Ausnahme der Division durch die Resultante im Ring R Z q X X N 1 displaystyle R mathbb Z q X X N 1 nbsp ab wobei die Multiplikation eine zyklische Faltung modulo q displaystyle q nbsp ist Das Produkt zweier Polynome f f 0 f 1 f N 1 displaystyle f f 0 f 1 ldots f N 1 nbsp und g g 0 g 1 g N 1 displaystyle g g 0 g 1 ldots g N 1 nbsp ist f g i j k mod N f i g j mod q displaystyle f g sum i j equiv k mod N f i cdot g j mod q nbsp Es kann bei NTRUSign entweder das Standard oder das transponierte Gitter zugrunde gelegt werden Das transponierte Gitter hat den Vorteil dass das Polynom f displaystyle f nbsp nur Koeffizienten in 1 0 1 enthalt und sich dadurch schneller multiplizieren lasst Weiterhin kann der Parameter B displaystyle B nbsp die Zahl sogenannter Perturbationen gewahlt werden Es hat sich allerdings herausgestellt dass 0 Perturbationen unsicher und mehr als eine nicht notwendig sind daher ist B displaystyle B nbsp in der Praxis immer gleich 1 Ausserdem sind die Grossen N displaystyle N nbsp Anzahl Polynomkoeffizienten q displaystyle q nbsp Modulus d displaystyle d nbsp Anzahl Koeffizienten 1 b displaystyle beta nbsp Normkorrekturfaktor und N displaystyle mathcal N nbsp Normschranke von Bedeutung Schlusselerzeugung Bearbeiten Es werden B displaystyle B nbsp sogenannte Basen erzeugt Jede davon besteht aus 3 Polynomen die mit f f displaystyle f f nbsp und h displaystyle h nbsp bezeichnet werden Das Polynom h displaystyle h nbsp der ersten Basis bildet den offentlichen Schlussel alle anderen Polynome samtlicher Basen bilden zusammen den Privatschlussel Basiserzeugung Bearbeiten Es wird hier die Variante nach Hoffstein et al 2 beschrieben Im EESS Standard 3 findet die Invertierung der Polynome f displaystyle f nbsp und g displaystyle g nbsp nicht in R displaystyle mathbb R nbsp sondern in Z displaystyle mathbb Z nbsp statt Dadurch kommt man zwar ohne Kommazahlen aus und erhalt bessere normkleinere Polynome F und G muss aber zusatzlich eine aufwandige Resultantenberechnung durchfuhren Zur Generierung einer Basis f f h displaystyle f f h nbsp geht man wie folgt vor Wahl eines zufalligen Polynoms f displaystyle f nbsp dessen Koeffizienten in 1 0 1 liegen und das modulo q displaystyle q nbsp invertierbar ist Wahl eines zufalligen Polynoms g displaystyle g nbsp dessen Koeffizienten in 1 0 1 liegen und das modulo q displaystyle q nbsp invertierbar ist Resultante R f displaystyle R f nbsp von f displaystyle f nbsp und ein Polynom r f displaystyle rho f nbsp berechnen so dass r f f t f x n 1 R f displaystyle rho f f tau f x n 1 R f nbsp fur ein beliebiges Polynom t f displaystyle tau f nbsp gilt Dieser Schritt ist der rechenintensivste Mildern kann man dies indem man fur mehrere Primzahlen p i displaystyle p i nbsp die Resultante modulo p i displaystyle p i nbsp 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 Resultante R g displaystyle R g nbsp von g displaystyle g nbsp und ein Polynom r g displaystyle rho g nbsp berechnen so dass r g g t g x n 1 R g displaystyle rho g g tau g x n 1 R g nbsp fur ein beliebiges Polynom t g displaystyle tau g nbsp gilt Wenn G G T R f R g displaystyle GGT R f R g nbsp 1 ist wieder bei Schritt 1 anfangen Mittels des erweiterten euklidischen Algorithmus zwei Zahlen S f displaystyle S f nbsp und S g displaystyle S g nbsp ermitteln so dass S f R f S g R g 1 displaystyle S f R f S g R g 1 nbsp gilt A x q S f r f x displaystyle A x qS f rho f x nbsp und B x q S g r g x displaystyle B x qS g rho g x nbsp setzen Inverse f 1 x r f x R f displaystyle f 1 x rho f x R f nbsp und g 1 x r g x R g displaystyle g 1 x rho g x R g nbsp in R x x N 1 displaystyle mathbb R x x N 1 nbsp auf genugend viele Dezimalstellen berechnen C x 1 2 B x f 1 x A x g 1 x displaystyle C x lfloor 1 2 B x f 1 x A x g 1 x rceil nbsp Anmerkung displaystyle lfloor nbsp und displaystyle rceil nbsp sind Gaussklammern F x B x C x f x displaystyle F x B x C x f x nbsp und G x A x C x g x displaystyle G x A x C x g x nbsp f q displaystyle f q nbsp die Inverse von f displaystyle f nbsp modulo q displaystyle q nbsp Im Standardfall f F displaystyle f F nbsp und h g f q mod q displaystyle h g f q mod q nbsp Im transponierten Fall f g displaystyle f g nbsp und h F f q mod q displaystyle h F f q mod q nbsp Signierung Bearbeiten Sei m die zu signierende Nachricht Fur i B displaystyle i B nbsp bis 0 werden folgende Schritte ausgefuhrt f f h displaystyle f f h nbsp i displaystyle i nbsp te Basis x 1 q m i f i displaystyle x lfloor frac 1 q m i f i rceil nbsp y 1 q m i f i displaystyle y lfloor frac 1 q m i f i rceil nbsp s i x f y f displaystyle s i x f y f nbsp m i s i h i h i 1 mod q displaystyle m i si h i h i 1 mod q nbsp s s s i displaystyle s s s i nbsp s displaystyle s nbsp ist die Signatur Beachte Unter bestimmten Umstanden kann es vorkommen dass die Signatur trotz gultigen Schlussels ungultig ist Es empfiehlt sich daher die Signatur nach der Erzeugung zu uberprufen und ggf nochmals zu signieren Signaturprufung Bearbeiten Sei m displaystyle m nbsp die Nachricht h displaystyle h nbsp der offentliche Schlussel und s displaystyle s nbsp die Signatur Die Norm t displaystyle t nbsp eines Polynoms t displaystyle t nbsp sei durch inf 0 k lt q t k q z displaystyle inf 0 leq k lt q t kq z nbsp gegeben wobei r z i 0 N 1 r i 2 1 N i 0 N r i displaystyle r z sum i 0 N 1 r i 2 frac 1 N sum i 0 N r i nbsp ist letztere wird als zentrierte Euklidische Norm bezeichnet Die Signatur wird dann wie folgt uberpruft b s 2 b 2 s h m 2 displaystyle b sqrt s 2 beta 2 s h m 2 nbsp Die Signatur ist gultig wenn b lt N displaystyle b lt mathcal N nbsp ist Bemerkung Die Berechnung der Norm uber die Definition ist ineffizient Eine bessere Methode ist es auf alle Polynomkoeffizienten eine Konstante zu addieren so dass die zwei Koeffizienten mit dem grossten Abstand gleich weit von q 2 displaystyle frac q 2 nbsp entfernt sind jeweils modulo q displaystyle q nbsp Die Norm ergibt sich dann durch die zentrierte Euklidnorm s o des so entstandenen Polynoms Effizienz Bearbeiten Um die Multiplikation zu beschleunigen konnen die Parameter f displaystyle f nbsp und g displaystyle g nbsp so gewahlt werden dass viele Koeffizienten Null sind Dazu wird ein Parameter d displaystyle d nbsp gewahlt und bei der Wahl von f displaystyle f nbsp und g displaystyle g nbsp werden d displaystyle d nbsp Koeffizienten gleich 1 d 1 displaystyle d 1 nbsp Koeffizienten gleich 1 und der Rest gleich 0 gesetzt Die Prufung mehrerer Signaturen lasst sich beschleunigen indem man statt der einzelnen Normen die Norm der Summe der Signaturen uberpruft Die Parameter N displaystyle N nbsp und N displaystyle mathcal N nbsp mussen dazu erhoht werden Sicherheit Bearbeiten Die mit dem Verfahren erstellten Signaturen verraten Informationen uber den geheimen Schlussel Diese Tatsache wurde 2006 ausgenutzt um das Verfahren anzugreifen Ungefahr 400 Signaturen reichten aus um den geheimen Schlussel zu berechnen 4 Das Verfahren wurde nach diesem Angriff angepasst Perturbationen sollten das Berechnen des geheimen Schlussels erheblich erschweren Das verbesserte Verfahren wurde 2012 angegriffen der geheime Schlussel konnte aus mehreren Tausend Signaturen berechnet werden 5 Einzelnachweise Bearbeiten Jeffrey Hoffstein Nick Howgrave Graham Jill Pipher Joseph H Silverman William Whyte NTRUSign Digital Signatures Using the NTRU Lattice securityinnovation com PDF Hoffstein Pipher Silverman An Introduction to mathematical Cryptography Springer 2008 ISBN 978 0 387 77993 5 a b Archivierte Kopie Memento des Originals vom 16 Marz 2012 im Internet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot grouper ieee org Efficient Embedded Security Standard 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 Leo 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 Weblinks Bearbeitenhttp grouper ieee org groups 1363 lattPK submissions EESS1v2 pdf Beschreibung des Algorithmus http grouper ieee org groups 1363 WorkingGroup presentations NTRUSignParams 2005 08 pdf Erganzungen Optimierungen und Herleitung von Parametern Patent US7308097B2 Digital signature and authentication method and apparatus Angemeldet am 6 Dezember 2002 veroffentlicht am 11 Dezember 2007 Anmelder NTRU Cryptosystems Inc Erfinder Jeffrey Hoffstein et Al lauft nach der 20 jahrigen Spanne am 6 Dezember 2022 ab http sourceforge net projects ntru NTRUSign als Java Quelltext Abgerufen von https de wikipedia org w index php title NTRUSign amp oldid 228996352