Digital Signature Algorithm (DSA) ist ein USA-Bundesregierungsstandard oder FIPS für Digitalunterschriften. Es wurde vom Nationalen Institut für Standards und Technologie (NIST) im August 1991 für den Gebrauch in ihrem Digital Signature Standard (DSS) vorgeschlagen, der in FIPS 186 angegeben ist, angenommen 1993. Eine geringe Revision wurde 1996 als FIPS 186-1 ausgegeben. Der Standard wurde weiter 2000 als FIPS 186-2 und wieder 2009 als FIPS 186-3 ausgebreitet.

DSA wird dadurch bedeckt, am 26. Juli 1991 abgelegt, und David W. Kravitz, einem ehemaligen NSA Angestellten zugeschrieben. Dieses Patent wurde in "Die Vereinigten Staaten von Amerika, wie vertreten, vom Sekretär des Handels, Washington, D.C gegeben." und der NIST hat dieses weltweit ohne Königtum Patent bereitgestellt. Dr Claus P. Schnorr behauptet, dass sein (ungültig) DSA bedeckt hat; dieser Anspruch wird diskutiert. DSA ist eine Variante des ElGamal Unterschrift-Schemas.

Schlüsselgeneration

Schlüsselgeneration hat zwei Phasen. Die erste Phase ist eine Wahl von Algorithmus-Rahmen, die zwischen verschiedenen Benutzern des Systems geteilt werden können, während die zweite Phase öffentliche und private Schlüssel für einen einzelnen Benutzer schätzt.

Parameter-Generation

• Wählen Sie eine genehmigte kryptografische Kuddelmuddel-Funktion H. Im ursprünglichen DSS war H immer SHA-1, aber die stärkeren SHA-2 Kuddelmuddel-Funktionen werden für den Gebrauch im aktuellen DSS genehmigt. Die Kuddelmuddel-Produktion kann zur Größe eines Schlüsselpaares gestutzt sein.
• Entscheiden Sie sich für eine Schlüssellänge L und N. Das ist das primäre Maß der kryptografischen Kraft des Schlüssels. Der ursprüngliche DSS hat L beschränkt, ein Vielfache 64 zwischen 512 und 1024 (einschließlich) zu sein. NIST 800-57 empfiehlt Längen von 2048 (oder 3072) für Schlüssel mit Sicherheitslebenszeiten, die sich außer 2010 (oder 2030) mit entsprechend längerem N ausstrecken. FIPS 186-3 gibt L und N Länge-Paare (1024,160), (2048,224), (2048,256), und (3072,256) an.
• Wählen Sie ein N-Bit erster q. N muss weniger sein als oder gleich der Kuddelmuddel-Produktionslänge.
• Wählen Sie ein L-Bit Hauptmodul p solch, dass p-1 ein Vielfache von q ist.
• Wählen Sie g, eine Zahl, deren multiplicative bestellen, modulo ist p q. Das kann durch das Setzen g = h mod p für einen willkürlichen h getan werden (1 < h < p1), und mit einem verschiedenen h noch einmal versuchend, wenn das Ergebnis als 1 herauskommt. Die meisten Wahlen von h werden zu einem verwendbaren g führen; allgemein wird h=2 verwendet.

Die Algorithmus-Rahmen (p, q, g) können zwischen verschiedenen Benutzern des Systems geteilt werden.

Schlüssel pro Benutzer

In Anbetracht einer Reihe von Rahmen schätzt die zweite Phase private und öffentliche Schlüssel für einen einzelnen Benutzer:

• Wählen Sie x durch eine zufällige Methode, wo 0 < x mod p.
• Öffentlicher Schlüssel ist (p, q, g, y). Privater Schlüssel ist x.

Dort bestehen Sie effiziente Algorithmen, für den modularen exponentiations h mod p und g mod p wie exponentiation durch das Quadrieren zu schätzen.

Das Unterzeichnen

Lassen Sie H die Hashing-Funktion und M die Nachricht sein:

• Erzeugen Sie einen zufälligen Wert pro Nachricht k wo 0 < k < q
• Berechnen Sie r = (g mod p) mod q
• Im unwahrscheinlichen Fall dass r = 0, fangen Sie wieder mit einem verschiedenen zufälligen k an
• Berechnen Sie s = (k (H (m) + x · r)) mod q
• Im unwahrscheinlichen Fall dass s = 0, fangen Sie wieder mit einem verschiedenen zufälligen k an
• Die Unterschrift ist (r, s)

Die ersten zwei Schritte belaufen sich auf das Schaffen eines neuen Schlüssels pro Benutzer. Der modulare exponentiation hier ist der am meisten rechenbetont teure Teil der Unterzeichnen-Operation, und es kann geschätzt werden, bevor das Nachrichtenkuddelmuddel bekannt ist.

Das Modulgegenteil k mod q ist der zweite teuerste Teil, und es kann auch geschätzt werden, bevor das Nachrichtenkuddelmuddel bekannt ist. Es kann mit dem verlängerten Euklidischen Algorithmus oder mit dem kleinen Lehrsatz von Fermat als k mod q geschätzt werden.

Das Überprüfen

• Weisen Sie die Unterschrift wenn 0 mod q zurück
• Berechnen Sie u1 = H (M) · w mod q
• Berechnen Sie u2 = r · w mod q
• Berechnen Sie v = ((g · y) mod p) mod q
• Die Unterschrift ist wenn v = r gültig

DSA ist dem Unterschrift-Schema von ElGamal ähnlich.

Genauigkeit des Algorithmus

Das Unterschrift-Schema ist im Sinn richtig, dass der verifier immer echte Unterschriften akzeptieren wird. Das kann wie folgt gezeigt werden:

Erstens, wenn g = h mod p hieraus folgt dass

g  h  1 (mod p) durch

Der kleine Lehrsatz von Fermat. Seitdem g> 1 und q ist erst, g muss Auftrag q haben.

Der Unterzeichner schätzt

:

So

:

\begin {richten }\aus

k & \equiv H (m) s^ {-1} +xrs^ {-1 }\\\

& \equiv H (m) w + xrw \pmod {q }\

\end {richten }\aus

</Mathematik>

Da g Auftrag q hat (mod p), haben wir

:\begin {richten }\aus

g^k & \equiv g^ {H (m) w} g^ {xrw }\\\

& \equiv g^ {H (m) w} y^ {rw }\\\

& \equiv G^ {u1} Y^ {u2} \pmod {p }\

\end {richten }\aus</Mathematik>

Schließlich folgt die Genauigkeit von DSA

aus:

r &= (G^k \mod p) \mod q \\

&= (G^ {u1} Y^ {u2} \mod p) \mod q \\

&= v

\end {richten} </Mathematik> {aus}

Empfindlichkeit

Mit DSA, dem Wärmegewicht, der Geheimhaltung und der Einzigartigkeit des zufälligen Unterschrift-Wertk ist kritisch. Es ist so kritisch, dass das Verletzen von irgendwelchen jener drei Voraussetzungen Ihren kompletten privaten Schlüssel zu einem Angreifer offenbaren kann. Das Verwenden desselben Werts zweimal (während sogar es k Geheimnis behält), einen voraussagbaren Wert verwendend, oder sogar einige Bit von k in jeder von mehreren Unterschriften durchlassend, ist genug, um DSA zu brechen.

Siehe auch

• Elliptische Kurve DSA
• Modularithmetik

Links

• FIPS-186, die erste Version der offiziellen DSA Spezifizierung.
• FIPS-186, Änderungsmitteilung Nr. 1, die erste Änderungsbenachrichtigung zur ersten Version der Spezifizierung.
• FIPS-186-1, die erste Revision zur offiziellen DSA Spezifizierung.
• FIPS-186-3, die dritte und aktuelle Revision zur offiziellen DSA Spezifizierung.
• FIPS-186-3-Billigung, Billigungsansage der dritten Revision zur offiziellen DSA Spezifizierung.
• Empfehlung für das Schlüsselmanagement - Teil 1: allgemein, NIST Spezielle Veröffentlichung 800-57, p. 62-63