EdDSA
I kryptografiske systemer med offentlig nøgle er Edwards-curve Digital Signature Algorithm (EdDSA) et digitalt signaturskema , der bruger en variant af Edwards elliptiske-kurve Schnor-skemaet [1] .
Den er designet til at være hurtigere end den eksisterende digitale signaturordning uden at kompromittere dens sikkerhed. Den blev designet af Daniel J. Bernstein , Nils Duif, Tanya Lange, Peter Schwabe og Bo-Yin Yang i 2011.
Design
Det følgende er en forenklet beskrivelse af EdDSA, der ikke inkluderer detaljerne om kodning af heltal og kurvepunkter som bitstrenge. En komplet beskrivelse og detaljer om denne digitale signaturimplementering kan findes i dokumentationen og de relevante RFC'er [2] [3] [1] .
EdDSA bruger følgende parametre:
- Valg af et begrænset rækkefølge q:
- Valg af en elliptisk kurve E over et felt, hvis gruppe af rationelle punkterhave orden[ specificer ] , hvor l er et stort primtal og 2^c kaldes en cofaktor
- Valg af basispunkt med rækkefølge l
- Og valget af en kollisionssikker hashfunktion H med 2b-bit udgange, hvor 2^(b-1)>q, så elementerne i det endelige felt og kurvens punkter i kunne repræsenteres som en længdestreng b bits.
Disse indstillinger er det minimum, der kræves for alle brugere af EdDSA-signaturskemaet. Sikkerheden af en EdDSA-signatur er meget afhængig af valget af parametre, med undtagelse af et vilkårligt valg af basispunkt. For eksempel Polards ro-algoritme for logaritmenskal tage nogenlunde kurver, før det kan[ clarify ] beregn logaritmen, [4] så l skal være stor nok til at dette ikke er muligt og normalt bør være større end 2^200. [5] Valget af l er begrænset af valget af q, da det ifølge Hasse-sætningen ikke bør afvige fra q + 1 med mere end
Under EdDSA signaturordningen
offentlig nøgle Den offentlige nøgle i EdDSA-skemaet er et kurvepunkt kodet i b bits. Underskrift EdDSA-signaturen i meddelelsen M af den offentlige nøgle A er parret (R,S) kodet i 2b bit, et kurvepunkt og et heltal , der opfylder verifikationsligningen 2 c S B = 2 c R + 2 c H ( R , EN , M ) EN . {\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R,A,M)A.} privat nøgle Den private nøgle i EdDSA-skemaet er en b-bit streng k, som skal vælges ensartet tilfældigt. Den tilsvarende offentlige nøgle i dette tilfælde er , hvor , er den mindst signifikante b-bit af H(k), fortolket som et lille-endian heltal. Meddelelsessignaturen M er parret (R,S), hvor R=rB for og S ≡ r + H ( R , EN , M ) s ( mod ℓ ) . {\displaystyle S\equiv r+H(R,A,M)s{\pmod {\ell )).} . Dette opfylder verifikationsligningen 2 c S B = 2 c ( r + H ( R , EN , M ) s ) B = 2 c r B + 2 c H ( R , EN , M ) s B = 2 c R + 2 c H ( R , EN , M ) EN . {\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R,A,M)s)B\\&=2^{c}rB+2^{c }H(R,A,M)sB\\&=2^{c}R+2^{c}H(R,A,M)A.\end{aligned}}}
privat nøgle
Den private nøgle i EdDSA-skemaet er en b-bit streng k, som skal vælges ensartet tilfældigt. Den tilsvarende offentlige nøgle i dette tilfælde er , hvor , er den mindst signifikante b-bit af H(k), fortolket som et lille-endian heltal. Meddelelsessignaturen M er parret (R,S), hvor R=rB for og
. Dette opfylder verifikationsligningen
2
c
S
B
=
2
c
(
r
+
H
(
R
,
EN
,
M
)
s
)
B
=
2
c
r
B
+
2
c
H
(
R
,
EN
,
M
)
s
B
=
2
c
R
+
2
c
H
(
R
,
EN
,
M
)
EN
.
{\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R,A,M)s)B\\&=2^{c}rB+2^{c }H(R,A,M)sB\\&=2^{c}R+2^{c}H(R,A,M)A.\end{aligned}}}
Ed25519
Ed25519 - EdDSA signaturskema ved hjælp af SHA-512 og Curve25519 [2] hvor:
- - Edwards elliptiske kurve
− x 2 + y 2 = en − 121665 121666 x 2 y 2 , {\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}
- og
- - et unikt punkt, hvis koordinat er , og koordinaten er positiv (taler i form af bitkodning),
- - SHA-512 , s .
Kurven er birationelt ækvivalent med Montgomery-kurven kendt som Curve25519. Ækvivalens [6] [2]
x = u v − 486664 , y = u − en u + en . {\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}
Effektivitet
Bernsteins team har optimeret Ed25519 til x86-64 Nehalem /Westmere familien af processorer. Verifikation kan udføres i batches af 64 digitale signaturer for endnu større gennemløb. Ed25519 er designet til at give angrebsmodstand sammenlignelig med kvaliteten af 128-bit symmetriske cifre . Offentlige nøgler er 256 bit lange, og signaturen er dobbelt så stor.
Sikker kodning
Som en sikkerhedsfunktion bruger Ed25519 ikke filialoperationer og array-indekseringstrin, der afhænger af hemmeligheder for at forhindre sidekanalangreb .
Som andre diskrete logaritmiske signaturskemaer bruger EdDSA en hemmelig værdi kaldet en nonce , der er unik for hver signatur. I DSA- og ECDSA- signaturordningerne genereres denne nonce traditionelt tilfældigt for hver signatur, og hvis tilfældige talgeneratoren er ødelagt eller forudsigelig under signaturgenerering, kan signaturen lække den private nøgle, hvilket er, hvad der skete med Sony PlayStation 3 -firmwaren opdater signaturnøgle [ 7] [8] . Sammenlignet med dem vælger EdDSA nonces deterministisk, såsom hashen af den private nøgle og beskeden. Når først en privat nøgle er blevet genereret, behøver EdDSA ikke længere en tilfældig talgenerator for at kunne lave signaturer, og der er ingen fare for, at en ødelagt tilfældig talgenerator, der bruges til at oprette en digital signatur, vil afsløre den private nøgle.
Software
Bemærkelsesværdige anvendelser af Ed25519 inkluderer OpenSSH , [9] GnuPG [10] og forskellige alternativer, såvel som OpenBSDs værdiværktøj . [elleve]
- Referenceimplementering af SUPERCOP [12] ( C-sprog ved hjælp af assembler-indsatser )
- Langsom, men kortfattet alternativ implementering, der ikke inkluderer side-kanal angrebsbeskyttelse ( Python )
- NaCl / libsodium [13]
- CryptoNote Cryptocurrency Protocol
- wolfSSL [14]
- I2Pd har sin egen implementering af EdDSA [15]
- Minisign og Minisign Miscellanea til macOS [16]
- Virgil PKI bruger Ed25519 nøgler som standard
- Botan
- Dropbear SSH fra test 2013.61
- OpenSSL 1.1.1 (TLS 1.3 og SHA3 understøttelse ud over X25519/Ed25519)
- Hashmap-server og klient (Go-sprog og Javascript )
- libgcrypt
Noter
- ↑ 1 2 Josefsson, S.; Liusvaara, I. (januar 2017). Edwards-Curve Digital Signature Algorithm (EdDSA) . Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070-1721. RFC 8032. Hentet 2017-07-31.
- ↑ 1 2 3 Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2012). "Højhastigheds højsikkerhedssignaturer" (PDF). Journal of Cryptographic Engineering . 2 (2):77-89. doi:10.1007/s13389-012-0027-1.
- ↑ Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe og Bo-Yin Yang (2015-07-04). EdDSA for flere kurver (PDF) (Teknisk rapport). Hentet 2016-11-14.
- ↑ Daniel J. Bernstein, Tanja Lange og Peter Schwabe (2011-01-01). Om den korrekte brug af negationskortet i Pollard rho-metoden (Teknisk rapport). IACR Cryptology ePrint-arkiv. 2011/003. Hentet 2016-11-14.
- ↑ Daniel J. Bernstein og Tanja Lange. "ECDLP Sikkerhed: Rho". SafeCurves: valg af sikre kurver til elliptisk kurvekryptering. Hentet 2016-11-16.
- ↑ Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru, red. Hurtigere tilføjelse og fordobling på elliptiske kurver . Fremskridt inden for kryptologi – ASIACRYPT. Forelæsningsnotater i datalogi. 4833 . Berlin: Springer. pp. 29-50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
- ↑ Johnston, Casey (2010-12-30). PS3 hacket gennem dårlig kryptografiimplementering. Ars Technica . Hentet 2016-11-15.
- ↑ fail0verflow (2010-12-29). Konsolhacking 2010: PS3 Epic Fail (PDF). 27C3: 27. Kaoskommunikationskonference. Hentet 2016-11-15.
- ↑ "Ændringer siden OpenSSH 6.4". 2014-01-03. Hentet 2016-10-07.
- ↑ Hvad er nyt i GnuPG 2.1". 2016-07-14. Hentet 2016-10-07.
- ↑ "Ting der bruger Ed25519". 2016-10-06. Hentet 2016-10-07.
- ↑ "eBACS: ECRYPT Benchmarking af kryptografiske systemer: SUPERCOP". 2016-09-10. Hentet 2016-10-07.
- ↑ Frank Denis (2016-06-29). "libsodium/ChangeLog". Hentet 2016-10-07.
- ↑ "wolfSSL Embedded SSL Library (tidligere CyaSSL)". Hentet 2016-10-07.
- ↑ "Heuristic Algorithms and Distributed Computing" (PDF) (på russisk). 2015.s. 55-56. ISSN 2311-8563. Hentet 2016-10-07.
- ↑ minisign-diverse på GitHub