EdDSA - EdDSA

EdDSA

Allgemeines
Designer	Daniel J. Bernstein , Niels Duif, Tanja Lange , Peter Schwabe, Bo-Yin Yang et al.
Erstmals veröffentlicht	26. September 2011
Detail
Struktur	Kryptographie mit elliptischen Kurven

In der Public-Key-Kryptographie ist der Edwards-Curve Digital Signature Algorithm ( EdDSA ) ein digitales Signaturschema , das eine Variante der Schnorr-Signatur verwendet, die auf verdrehten Edwards-Kurven basiert . Es ist so konzipiert, dass es schneller ist als bestehende digitale Signaturschemata, ohne die Sicherheit zu beeinträchtigen. Es wurde von einem Team mit Daniel J. Bernstein , Niels Duif, Tanja Lange , Peter Schwabe und Bo-Yin Yang entwickelt. Die Referenzimplementierung ist Public-Domain-Software .

Zusammenfassung

Das Folgende ist eine vereinfachte Beschreibung von EdDSA, wobei Details der Codierung von ganzen Zahlen und Kurvenpunkten als Bitfolgen ignoriert werden; die vollständigen Details sind in den Papieren und RFC.

Ein EdDSA-Signaturschema ist eine Wahl:

• des endlichen Körpers über ungerader Primzahl ;${\displaystyle \mathbb{F} _{q}}$${\displaystyle q}$
• einer elliptischen Kurve, über deren Gruppe von rationalen Punkten eine Ordnung besteht , wobei eine große Primzahl ist und als Kofaktor bezeichnet wird;${\displaystyle E}$${\displaystyle \mathbb{F} _{q}}$${\displaystyle E(\mathbb{F}_{q})}$${\displaystyle \mathbb{F} _{q}}$${\displaystyle \#E(\mathbb{F}_{q})=2^{c}\ell}$${\displaystyle \ell}$${\displaystyle 2^{c}}$
• des Basispunktes mit Auftrag ; und${\displaystyle B\in E(\mathbb{F}_{q})}$${\displaystyle \ell}$
• der kryptografischen Hash-Funktion mit -Bit-Ausgaben, wobei Elemente von und Kurvenpunkte durch Bitfolgen dargestellt werden können.${\displaystyle H}$${\displaystyle 2b}$${\displaystyle 2^{b-1}>q}$${\displaystyle \mathbb{F} _{q}}$${\displaystyle E(\mathbb{F}_{q})}$${\displaystyle b}$

Diese Parameter sind allen Benutzern des EdDSA-Signaturschemas gemeinsam. Die Sicherheit des Systems EdDSA Signatur hängt entscheidend von der Wahl der Parameter für die willkürliche Wahl der Base ausnehmen punkt zum Beispiel Pollard-Rho-Methode für Logarithmen wird erwartet , dass etwa nehmen Kurve Ergänzungen , bevor es einen diskreten Logarithmen berechnen kann, so muss es sein groß genug, dass dies nicht durchführbar ist, und wird in der Regel auf mehr als 2 ²⁰⁰ geschätzt . Die Wahl der durch die Wahl beschränkt ist , da von dem Satz von Hasse , kann unterscheiden sich nicht von mehr als . Die Hash-Funktion wird in formalen Analysen der Sicherheit von EdDSA normalerweise als zufälliges Orakel modelliert . In der Variante HashEdDSA wird zusätzlich eine kollisionsresistente Hash-Funktion benötigt. ${\displaystyle {\sqrt {\ell\pi/4}}}$${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle q}$${\displaystyle \#E(\mathbb{F}_{q})=2^{c}\ell}$${\displaystyle q+1}$${\displaystyle 2{\sqrt {q}}}$${\displaystyle H}$${\displaystyle H'}$

Innerhalb eines EdDSA-Signaturschemas

Öffentlicher Schlüssel

Ein öffentlicher EdDSA-Schlüssel ist ein Kurvenpunkt , der in Bits codiert ist .${\displaystyle A\in E(\mathbb{F}_{q})}$${\displaystyle b}$

Unterschrift

Eine EdDSA-Signatur auf einer Nachricht durch einen öffentlichen Schlüssel ist das in Bits codierte Paar aus einem Kurvenpunkt und einer ganzen Zahl, die die folgende Verifikationsgleichung erfüllt. bezeichnet die Verkettung .${\displaystyle M}$${\displaystyle A}$${\displaystyle (R,S)}$${\displaystyle 2b}$${\displaystyle R\in E(\mathbb{F}_{q})}$${\displaystyle 0<S<\ell}$${\displaystyle \parallel}$

Privat Schlüssel

Ein privater EdDSA-Schlüssel ist ein -Bit-String, der gleichmäßig zufällig ausgewählt werden sollte. Der entsprechende öffentliche Schlüssel ist , wobei die niederwertigsten Bits in Little-Endian als ganze Zahl interpretiert werden. Die Signatur einer Nachricht ist wo für , und${\displaystyle b}$${\displaystyle k}$${\displaystyle A=sB}$${\displaystyle s=H_{0,\dots,b-1}(k)}$${\displaystyle b}$${\displaystyle H(k)}$${\displaystyle M}$${\displaystyle (R,S)}$${\displaystyle R=rB}$${\displaystyle r=H(H_{b,\dots,2b-1}(k)\parallel M)}$

$${\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell}}.}$$

Dies erfüllt die Verifikationsgleichung:

Ed25519

Ed25519 ist das EdDSA-Signaturschema, das SHA-512 (SHA-2) und Curve25519 verwendet, wobei

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/\mathbb{F} _{q}}$ist die verdrehte Edwards-Kurve

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$ und ${\displaystyle c=3}$
• ${\displaystyle B}$ist der eindeutige Punkt, dessen Koordinate ist und dessen Koordinate positiv ist. "positiv" wird in Bezug auf die Bitcodierung definiert: ${\displaystyle E(\mathbb{F}_{q})}$${\displaystyle y}$${\displaystyle 4/5}$${\displaystyle x}$
  
  • "positive" Koordinaten sind gerade Koordinaten (niederwertiges Bit wird gelöscht)
  • "negative" Koordinaten sind ungerade Koordinaten (niederwertiges Bit ist gesetzt)
• ${\displaystyle H}$ist SHA-512 , mit .${\displaystyle b=256}$

Die Kurve ist birational äquivalent zur Montgomery-Kurve, die als Curve25519 bekannt ist . Die Äquivalenz ist ${\displaystyle E(\mathbb{F}_{q})}$

Performance

Das ursprüngliche Team hat Ed25519 für die x86-64 Nehalem / Westmere- Prozessorfamilie optimiert . Die Verifizierung kann in Stapeln von 64 Signaturen durchgeführt werden, um einen noch höheren Durchsatz zu erzielen. Ed25519 soll eine Angriffsresistenz bieten, die mit hochwertigen symmetrischen 128-Bit- Chiffren vergleichbar ist . Öffentliche Schlüssel sind 256 Bit lang und Signaturen sind 512 Bit lang.

Sichere Codierung

Als Sicherheitsfunktionen verwendet Ed25519 keine Verzweigungsoperationen und Array-Indizierungsschritte, die von geheimen Daten abhängen, um viele Seitenkanalangriffe abzuwehren .

Wie andere auf diskretem Log basierende Signaturschemata verwendet EdDSA einen geheimen Wert, der als Nonce bezeichnet wird und für jede Signatur eindeutig ist. In den Signaturschemata DSA und ECDSA wird diese Nonce traditionell für jede Signatur zufällig generiert – und wenn der Zufallszahlengenerator beim Erstellen einer Signatur jemals kaputt und vorhersehbar ist, kann die Signatur den privaten Schlüssel verlieren, wie es bei der Sony PlayStation 3- Firmware der Fall war Signaturschlüssel aktualisieren. Im Gegensatz dazu wählt EdDSA die Nonce deterministisch als Hash eines Teils des privaten Schlüssels und der Nachricht. Sobald ein privater Schlüssel erzeugt ist, benötigt EdDSA also keinen Zufallszahlengenerator mehr, um Signaturen zu erstellen, und es besteht keine Gefahr, dass ein kaputter Zufallszahlengenerator, der zum Erstellen einer Signatur verwendet wird, den privaten Schlüssel preisgibt.

Inkonsistenzen bei Standardisierung und Implementierung

Beachten Sie, dass es zwei Standardisierungsbemühungen für EdDSA gibt, eine von der IETF, eine informationelle RFC  8032 und eine von NIST als Teil von FIPS 186-5 (2019). Die Unterschiede zwischen den Standards wurden analysiert und Testvektoren sind verfügbar.

Software

Bemerkenswerte Verwendungen von Ed25519 umfassen OpenSSH , GnuPG und verschiedene Alternativen sowie das Signify-Tool von OpenBSD . Die Verwendung von Ed25519 im SSH-Protokoll wird standardisiert. Im Jahr 2019 enthielt eine Entwurfsversion des FIPS 186-5-Standards das deterministische Ed25519 als genehmigtes Signaturschema.

• SUPERCOP-Referenzimplementierung ( C-Sprache mit Inline- Assembler )
• Eine langsame, aber prägnante alternative Implementierung, die keinen Seitenkanalangriffsschutz ( Python ) enthält.
• NaCl / Libnatrium
• Cryptokryptowährung Protokoll
• wolfSSL
• I2Pd hat eine eigene Implementierung von EdDSA
• Minisign und Minisign Miscellanea für macOS
• Virgil PKI verwendet standardmäßig Ed25519-Schlüssel
• Apple Watch und iPhone verwenden Ed25519-Schlüssel für die IKEv2- Authentifizierung miteinander
• Botanik
• Dropbear SSH seit 2013.61test
• OpenSSL 1.1.1
• Libgcrypt
• Java-Entwicklungskit 15

Ed448

Ed448 ist das EdDSA-Signaturschema, das SHA-3 und Curve448 verwendet, die in RFC  8032 definiert sind . Es wurde auch im Entwurf des FIPS 186-5-Standards genehmigt.

Verweise

Externe Links

• Ed25519-Homepage