EdDSA

A nyilvános kulcsú kriptográfiai rendszerekben az Edwards-görbe digitális aláírási algoritmus (EdDSA) egy digitális aláírási séma, amely az Edwards elliptikus görbe Schnor -séma egy változatát használja [1] .

Úgy tervezték, hogy gyorsabb legyen, mint a meglévő digitális aláírási séma, anélkül, hogy veszélyeztetné a biztonságát. Daniel J. Bernstein , Nils Duif, Tanya Lange, Peter Schwabe és Bo-Yin Yang tervezte 2011-re.

Tervezés

A következő az EdDSA egyszerűsített leírása, amely nem tartalmazza az egész számok és görbepontok bitkarakterláncként való kódolásának részleteit. A digitális aláírás megvalósításának teljes leírása és részletei megtalálhatók a dokumentációban és a vonatkozó RFC-kben [2] [3] [1] .

Az EdDSA a következő paramétereket használja:

A q sorrend véges mezőjének kiválasztása : $\mathbb {F} _{q}$
Az E elliptikus görbe választása olyan mező felett, amelynek racionális pontjainak csoportja $\mathbb {F} _{q}$ $E(\mathbb {F} _{q})$ $\mathbb {F} _{q}$ rendet tartva[ adja meg ] , ahol l egy nagy prímszám, és 2^c-t kofaktornak nevezzük $\#E(\mathbb {F} _{q})=2^{c}\ell$
Bázispont választása l $B\in E(\mathbb {F} _{q})$
És egy ütközésbiztos H hash függvény választása 2b bites kimenetekkel, ahol 2^(b-1)>q, hogy a végső mező elemeit és a görbe pontjait egy hosszúságú karakterláncként lehessen ábrázolni. b bitek. $\mathbb {F} _{q}$ $E(\mathbb {F} _{q})$

Ezek a minimális beállítások az EdDSA aláírási séma összes felhasználója számára. Az EdDSA aláírás biztonsága nagymértékben függ a paraméterek megválasztásától, kivéve az alappont tetszőleges megválasztását. Például Polard ro-algoritmusa a logaritmushozdurván görbét kell vennie, mielőtt megtehetné ${\sqrt {\ell \pi /4))$ [ pontosítás ] számítsa ki a logaritmust, [4] tehát l-nek elég nagynak kell lennie ahhoz, hogy ez ne legyen lehetséges, és általában nagyobbnak kell lennie 2^200-nál. [5] Az l választását q választása korlátozza, mivel a Hasse-tétel szerint nem térhet el q + 1-től többel, mint $\#E(\mathbb {F} _{q})=2^{c}\ell$ $2{\sqrt {q))$

Az EdDSA aláírási séma szerint

nyilvános kulcs Az EdDSA sémában a nyilvános kulcs egy b bitben kódolt görbepont.

A\in E(\mathbb {F} _{q})

Aláírás Az A nyilvános kulcs által az M üzenetben lévő EdDSA aláírás a 2b bitben, egy görbepontban és egy egész számban kódolt (R,S) pár , amely kielégíti az ellenőrző egyenletet.

R\in E(\mathbb {F} _{q})

0<S<\ell

2 c S B = 2 c R + 2 c H ( R , A , M ) A . {\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R,A,M)A.}

2^{c}SB=2^{c}R+2^{c}H(R,A,M)A.

privát kulcs Az EdDSA sémában a privát kulcs egy b-bites k karakterlánc, amelyet egyenletesen véletlenszerűen kell kiválasztani. A megfelelő nyilvános kulcs ebben az esetben , ahol , a H(k) legkisebb jelentőségű b-bitje, egy kisvégű egész számként értelmezve. Az M üzenetaláírás az (R,S) pár, ahol R=rB és és

A=sB

s=H_{0,\dots ,b-1}(k)

r=H(H_{b,\pontok ,2b-1}(k),M)

S ≡ r + H ( R , A , M ) s ( mod ℓ ) . {\displaystyle S\equiv r+H(R,A,M)s{\pmod {\ell )).}

S\equiv r+H(R,A,M)s{\pmod {\ell )).

. Ez kielégíti az igazolási egyenletet

2 c S B = 2 c ( r + H ( R , A , M ) s ) B = 2 c r B + 2 c H ( R , A , M ) s B = 2 c R + 2 c H ( R , A , M ) A . {\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{igazítva}}} ${\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{igazítva}}$

Ed25519

Ed25519 – EdDSA aláírási séma SHA-512 és Curve25519 használatával [2] ahol:

$q=2^{255}-19,$
${\displaystyle E/\mathbb {F} _{q))$ - Edwards elliptikus görbe

− x 2 + y 2 = egy − 121665 121666 x 2 y 2 , {\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}

-x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},

$\ell =2^{252}+27742317777372353535851937790883648493$ és $c=3,$
$B$ - egy egyedi pont , amelynek koordinátája , és a koordinátája pozitív (bitkódolásról beszélve), $E(\mathbb {F} _{q})$ $y$ $4/5$ $x$
$H$ - SHA-512 , p . $b=256$

A görbe biracionálisan egyenértékű a Curve25519 néven ismert Montgomery-görbével. Egyenértékűség [6] [2] $E(\mathbb {F} _{q})$

x = u v − 486664 , y = u − egy u + egy . {\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}

x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.

Hatékonyság

Bernstein csapata az Ed25519-et az x86-64 Nehalem /Westmere processzorcsaládhoz optimalizálta. Az ellenőrzés 64 digitális aláírásból álló kötegekben hajtható végre a még nagyobb átvitel érdekében. Az Ed25519-et úgy tervezték, hogy a 128 bites szimmetrikus titkosítások minőségéhez hasonló támadási ellenállást biztosítson . A nyilvános kulcsok 256 bitesek, az aláírás pedig kétszer akkora.

Biztonságos kódolás

Biztonsági szolgáltatásként az Ed25519 nem használ olyan elágazási műveleteket és tömbindexelési lépéseket, amelyek titkoktól függenek az oldalcsatornás támadások megelőzésére .

Más diszkrét logaritmikus aláírási sémákhoz hasonlóan az EdDSA is egy nonce nevű titkos értéket használ , amely minden aláíráshoz egyedi. A DSA és ECDSA aláírási sémákban ezt a nonce-t hagyományosan véletlenszerűen generálják minden aláíráshoz, és ha a véletlenszám-generátor meghibásodik vagy megjósolható az aláírás generálása során, az aláírás kiszivároghat a privát kulcs, ami a Sony PlayStation 3 firmware-ével történt. aláíró kulcs frissítése [ 7] [8] . Hozzájuk képest az EdDSA determinisztikusan választja ki a nonce-okat, például a privát kulcs és az üzenet hash-ét. Így a privát kulcs generálása után az EdDSA-nak már nincs szüksége véletlenszám-generátorra az aláírások készítéséhez, és nem áll fenn annak a veszélye, hogy a digitális aláírás létrehozásához használt véletlenszám-generátor felfedje a titkos kulcsot.

Szoftver

Az Ed25519 figyelemre méltó felhasználási területei közé tartozik az OpenSSH , [9] GnuPG [10] és különféle alternatívák, valamint az OpenBSD értékeszköze . [tizenegy]

A SUPERCOP [12] referencia implementációja ( C nyelv assembler beillesztésekkel )
Lassú, de tömör alternatív megvalósítás, amely nem tartalmaz oldalcsatornás támadás elleni védelmet ( Python )
NaCl / libsodium [13]
CryptoNote Cryptocurrency Protocol
wolfSSL [14]
Az I2Pd saját EdDSA implementációval rendelkezik [15]
Minisign és Minisign Miscellanea macOS -hez [16]
A Virgil PKI alapértelmezés szerint az Ed25519 kulcsokat használja
Botan
Dropbear SSH 2013.61 tesztből
OpenSSL 1.1.1 (TLS 1.3 és SHA3 támogatás az X25519/Ed25519 mellett)
Hashmap szerver és kliens (Go Language és Javascript )
libgcrypt

Jegyzetek

↑ 1 2 Josefsson, S.; Liusvaara, I. (2017. január). Edwards-görbe digitális aláírási algoritmus (EdDSA) . Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070-1721. RFC 8032. Letöltve: 2017-07-31.
↑ 1 2 3 Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Péter; Bo-Yin Yang (2012). "Nagy sebességű, nagy biztonságú aláírások" (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 és Bo-Yin Yang (2015-07-04). EdDSA további görbékért (PDF) (műszaki jelentés). Letöltve 2016-11-14.
↑ Daniel J. Bernstein, Tanja Lange és Peter Schwabe (2011-01-01). A negációs térkép helyes használatáról a Pollard rho módszerben (Technikai jelentés). IACR Cryptology ePrint archívum. 2011/003. Letöltve 2016-11-14.
↑ Daniel J. Bernstein és Tanja Lange. "ECDLP biztonság: Rho". Biztonságos görbék: biztonságos görbék kiválasztása elliptikus görbületű titkosításhoz. Letöltve 2016-11-16.
↑ Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru, szerk. Gyorsabb összeadás és megkettőzés az elliptikus görbéken . A kriptológia fejlődése – ASIACRYPT. Előadásjegyzetek számítástechnikából. 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.). A PS3 feltört a rossz kriptográfiai megvalósítás miatt. Ars Technica . Letöltve: 2016-11-15.
↑ fail0verflow (2010-12-29). Konzolhacking 2010: PS3 Epic Fail (PDF). 27C3: 27. Chaos Communication Conference. Letöltve: 2016-11-15.
↑ "Változások az OpenSSH 6.4 óta". 2014-01-03. Letöltve: 2016-10-07.
↑ A GnuPG 2.1 újdonságai". 2016-07-14. Letöltve: 2016-10-07.
↑ "Az Ed25519-et használó dolgok". 2016-10-06. Letöltve: 2016-10-07.
↑ "eBACS: ECRYPT Benchmarking of Cryptographic Systems: SUPERCOP". 2016-09-10. Letöltve: 2016-10-07.
↑ Frank Denis (2016-06-29). "libsodium/ChangeLog". Letöltve: 2016-10-07.
↑ "wolfSSL Embedded SSL Library (korábban CyaSSL)". Letöltve: 2016-10-07.
↑ "Heurisztikus algoritmusok és elosztott számítástechnika" (PDF) (orosz nyelven). 2015.pp. 55-56. ISSN 2311-8563. Letöltve: 2016-10-07.
↑ minisign-misc a GitHubon

Linkek

Ed25519 honlap

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya