Digitaler Signaturalgorithmus mit elliptischer Kurve

Elliptic Curve Digital Signature Algorithm (ECDSA) ist einAlgorithmusderdigitalen Signatur-Public-Key-Variante vonDSA. Es verwendetKryptographie auf elliptischen Kurven.

Einführung

Der Algorithmus wurde 1992 von Scott Vanstone als Reaktion auf eine Ausschreibung für digitale Signaturen des National Institute of Standards and Technology (NIST) vorgeschlagen. Vanstone gründete Certicom 1985 und sein Unternehmen besitzt die meisten Patente für elliptische Kurvenalgorithmen. Die Vorteile von ECDSA gegenüber DSA und RSA sind kürzere Schlüssellängen und schnellere Signatur- und Verschlüsselungsvorgänge.

ECDSA ist durch den ANSI X9.62-1998 Standard, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) definiert .

Algorithmus

Sei eine Formelkurve . Es ist eine elliptische Kurve auf einem endlichen Körper ganzer Zahlen modulo p mit p einer Primzahl und einem Punkt G der Kurve (sogenannter Basispunkt). Die Reihenfolge von G n , die kleinsten Ganzzahl , so dass nG gibt den Punkt im Unendlichen der Kurve und neutralen Elements der kommutativen Gruppe an den Punkten der Kurve . Damit alle ganzen Zahlen zwischen 1 und n-1 invertierbar modulo n sind, ist es zwingend erforderlich, dass der Ring ein Körper ist und daher n eine Primzahl ist (dies ist eine Folge des Satzes von Bézout). Daher bezeichnet im Folgenden die Notation, wenn eine ganze Zahl zwischen 1 und n-1 ist, die Umkehrung von im Feld . ja2=x3+beimx+b{\ displaystyle y ^ {2} = x ^ {3} + ax + b}Ö{\ Anzeigestil O}Z/nichtZ{\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}k-1 mod nicht{\ displaystyle k ^ {- 1} {\ text {mod}} n}k{\ Anzeigestil k}k{\ Anzeigestil k}Z/nichtZ{\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}

Vorbereitung der Schlüssel

• Wählen Sie eine ganze Zahl s zwischen und aus, die der private Schlüssel sein soll.1{\ Anzeigestil 1}nicht-1{\ Anzeigestil n-1}
• Berechnen Sie mit dem Element der elliptischen Kurve.Q=soG{\ Anzeigestil Q = sG}
• Der öffentliche Schlüssel ist Q und der private Schlüssel ist s .

Unterschrift

• Wähle zufällig eine Zahl k zwischen 1 und n -1
  • siehe FIPS 186-4 Anhang B5 für empfohlene Methoden zur Generierung dieser Nummer.
  • Sony hat bei der Sicherung der PS3 bei der Auswahl dieser Nummer nicht genügend Sorgfalt walten lassen, um den privaten Schlüssel zu finden
  • EdDSA verwendet eine deterministische Methode, um diese kryptografische Nonce zu berechnen
  • Für das Signieren von Kryptowährungstransaktionen verwenden einige Implementierungen eine Berechnung vom HMAC- Typ , um k . zu erhalten
• Berechnung (ich, j)=k G{\ displaystyle (i, ~ j) = k ~ G}
• Berechnen  ; Ja , gehe zum ersten Schrittx=ich mod nicht{\ displaystyle x = i ~ {\ bmod {~}} n}x=0{\ Anzeigestil x = 0}
• Berechnen Sie, wo H ( m ) das Ergebnis eines kryptografischen Hashs auf der zu signierenden Nachricht m ist, oft SHA-1 (NIST und ANSSI empfehlen, nicht mehr SHA-1, sondern SHA-256 oder SHA-512 zu verwenden , Ethereum verwendet Keccak- 256, eine Variante von SHA-3 )ja=k-1(H(ich)+sox) mod nicht{\ displaystyle y = k ^ {- 1} (H (m) + sx) ~ {\ bmod {~}} n}
• Also geh zum ersten Schrittja=0{\ Anzeigestil y = 0}
• Die Signatur ist das Paar ( x , y ).

Überprüfung

• Prüfen Sie, ob Q verschieden ist von (dem Punkt im Unendlichen) und dass Q tatsächlich zur elliptischen Kurve gehörtÖ{\ Anzeigestil O}
• Überprüfe, dass nQ liefertÖ{\ Anzeigestil O}
• Überprüfen Sie, ob x und y zwischen 1 und n -1 . liegen
• Berechnung (ich,j)=(H(ich)ja-1 mod nicht)G+(xja-1 mod nicht)Q{\ displaystyle (i, j) = (H (m) y ^ {- 1} ~ {\ bmod {~}} n) G + (xy ^ {- 1} ~ {\ bmod {~}} n) Q }
• Überprüfen Sie das .x=ich mod nicht{\ displaystyle x = i ~ {\ bmod {~}} n}

Demonstration

(H(ich)ja-1 mod nicht) G+(xja-1 mod nicht) Q{\ displaystyle \ left (H (m) y ^ {- 1} ~ {\ bmod {~}} n \ right) ~ G + {\ Big (} xy ^ {- 1} ~ {\ bmod {~}} n {\ Groß)} ~ Q}

=(H(ich)ja-1 mod nicht)G+(xja-1 mod nicht)so G{\ displaystyle = \ left (H (m) y ^ {- 1} ~ {\ bmod {~}} n \ right) G + {\ Big (} xy ^ {- 1} ~ {\ bmod {~}} n {\ Groß)} s ~ G}

=((H(ich)+sox)ja-1) mod nicht G{\ displaystyle = \ left ((H (m) + sx) y ^ {- 1} \ right) ~ {\ bmod {~}} n ~ G}

=((H(ich)+sox)k(H(ich)+sox)-1) mod nicht G{\ displaystyle = \ left (\ left (H (m) + sx \ right) k (H (m) + sx) ^ {- 1} \ right) ~ {\ bmod {~}} n ~ G}

=(k mod nicht) G{\ displaystyle = \ left (k ~ {\ bmod {~}} n \ right) ~ G} =k G{\ displaystyle = k ~ G} =(ich, j){\ displaystyle = (i, ~ j)}

Wenn also , wird die Signatur verifiziert. x=ich mod nicht{\ displaystyle x = i ~ {\ bmod {~}} n}

Sicherheit

Da alle bekannten Algorithmen zur Lösung des Problems des diskreten Logarithmus auf elliptischen Kurven in ( Baby-Step Giant-Step , Rho Pollards Algorithmus) sind, muss die Größe des Körpers daher ungefähr doppelt so groß sein wie der gewünschte Sicherheitsparameter. Für einen 128-Bit-Sicherheitsgrad (AES-128, RSA-3072) nehmen wir eine Kurve an einem Körper , wobei . Ö(nicht){\ displaystyle O ({\ sqrt {n}})}Fq{\ displaystyle \ mathbb {F} _ {q}}q≈2256{\ displaystyle q \ ca. 2 ^ {256}}

Integration

In der Praxis basiert ECDSA oft auf Kurven, die von Organisationen wie NIST oder Certicom empfohlen werden.

NIST empfiehlt beispielsweise fünfzehn verschiedene elliptische Kurven an zehn verschiedenen Körpern. Es werden fünf Kurven über fünf endliche Körper der Ordnung p prime empfohlen , genannt P-192, P-224, P-256, P-384, P-521, zehn Kurven über fünf endliche Körper der Form . Fp{\ displaystyle \ mathbb {F} _ {p}}F2ich{\ displaystyle \ mathbb {F} _ {2 ^ {m}}}

Die ANSSI empfiehlt die Verwendung der FRP256v1-Kurve, deren Parameter 2011 im Amtsblatt veröffentlicht wurden, und der P-256-Kurve, P-384, P-521, B-283, B-409 und B-571, definiert in FIPS 186 -2.

Hinweise und Referenzen

1. ANSI-Entwurf X9.62-1998
2. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
3. Artikel der BBC News Technology zur Sicherung der PS3
4. Engadget: Wert der Zufallszahl k, die zum Signieren von PS3-Software verwendet wird .
5. siehe deterministic_generate_k Funktion Ethereum Quellcode in Python
6. FIPS PUB 186-4, Digital Signature Standard (DSS)
7. Mitteilung über die vom französischen Staat festgelegten Parameter elliptischer Kurven, Amtsblatt Nr. 241 vom 16.10.2011 .
8. Allgemeine Sicherheitsreferenz, Anhang B1, „Kryptografische Mechanismen Regeln und Empfehlungen zur Auswahl und Dimensionierung von kryptografischen Mechanismen“.

Anhänge

Zum Thema passende Artikel

• EdDSA , eine weitere Signatur, die eine elliptische Kurve verwendet und auf der verdrehten Edwards-Kurve basiert
• Curve25519 , basierend auf edDSA und geschützt gegen fehlerhafte Pseudo-Zufallszahlengeneratoren

Externe Links

• "ECDSA, Schlüssel-Bitcoin-Technologie" (Version 15. März 2016 im Internetarchiv ) .