Loading AI tools
digitales Signaturverfahren Aus Wikipedia, der freien Enzyklopädie
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.
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.
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.
Es wird hier die Variante nach Hoffstein et al.[2] beschrieben. Im EESS-Standard[3] 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:
Sei m die zu signierende Nachricht.
Für bis 0 werden folgende Schritte ausgeführt:
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.
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:
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.
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.
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.[4] 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.[5]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.