EdDSA

EdDSA
General
Dissenyadors	Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang, et al.
Data primera publicació	setembre 2011
Detall
Estructura	corba el·líptica

En criptografia de clau pública, l'algoritme de signatura digital de corba d'Edwards (EdDSA) és un esquema de signatura digital que utilitza una variant de la signatura de Schnorr basada en corbes d'Edwards retorçades. Està dissenyat per ser més ràpid que els esquemes de signatura digital existents sense sacrificar la seguretat. Va ser desenvolupat per un equip que incloïa Daniel J. Bernstein, Nie

Resum

La següent és una descripció simplificada d'EdDSA, ignorant els detalls de la codificació d'enters i punts de corba com a cadenes de bits; els detalls complets es troben als articles i a la RFC.

Un esquema de signatura EdDSA és una opció:

• de camp finit $\mathbb {F} _{q}$ sobre la potència prima imparella $q$ ;
• de corba el·líptica $E$ més de $\mathbb {F} _{q}$ el grup del qual $E(\mathbb {F} _{q})$ de $\mathbb {F} _{q}$ els punts racionals tenen ordre $\#E(\mathbb {F} _{q})=2^{c}\ell$, on $\ell$ és un primer gran i $2^{c}$ s'anomena cofactor;
• del punt base $B\in E(\mathbb {F} _{q})$ amb ordre $\ell$ ; i
• de la funció hash criptogràfica $H$ amb $2b$ sortides de -bit, on $2^{b-1}>q$ de manera que els elements de $\mathbb {F} _{q}$ i punts de corba en $E(\mathbb {F} _{q})$ es pot representar mitjançant cadenes de $b$ bits.

Aquests paràmetres són comuns a tots els usuaris de l'esquema de signatura EdDSA. La seguretat de l'esquema de signatura EdDSA depèn críticament de l'elecció dels paràmetres, excepte per l'elecció arbitrària del punt base; per exemple, s'espera que l'algoritme rho de Pollard per a logaritmes trigui aproximadament ${\sqrt {\ell \pi /4}}$ addicions de corbes abans de poder calcular un logaritme discret, de manera que $\ell$ ha de ser prou gran perquè això sigui inviable, i normalment es considera que supera 2²⁰⁰ L'elecció de $\ell$ està limitat per l'elecció de $q$, ja que pel teorema de Hasse, $\#E(\mathbb {F} _{q})=2^{c}\ell$ no pot diferir de $q+1$ per més de $2{\sqrt {q}}$ . La funció hash $H$ normalment es modela com un oracle aleatori en anàlisis formals de la seguretat d'EdDSA.

Dins d'un esquema de signatura EdDSA,

Clau pública

Una clau pública EdDSA és un punt de corba $A\in E(\mathbb {F} _{q})$, codificat en $b$ bits.

Verificació de signatura

Una signatura EdDSA en un missatge $M$ per clau pública $A$ és la parella $(R,S)$, codificat en $2b$ bits, d'un punt de corba $R\in E(\mathbb {F} _{q})$ i un nombre enter $0<S<\ell$ satisfent la següent equació de verificació, on $\parallel$ denota concatenació:

$$2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A.$$

Clau privada

Una clau privada EdDSA és una $b$ cadena de bits $k$ que s'han de triar uniformement a l'atzar. La clau pública corresponent és $A=sB$, on $s=H_{0,\dots ,b-1}(k)$ és el menys significatiu $b$ trossos de $H(k)$ interpretat com un enter en ordre de bytes.

Signatura

La signatura d'un missatge $M$ es calcula determinísticament com a $(R,S),$ on $R=rB$ per $r=H(H_{b,\dots ,2b-1}(k)\parallel M)$, i $$S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.$$ Això satisfà l'equació de verificació

$${\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}$$

Ed25519

Ed25519 és l'esquema de signatura EdDSA que utilitza SHA-512 (SHA-2) i una corba el·líptica relacionada amb la corba25519 on

• $q=2^{255}-19,$
• $E/\mathbb {F} _{q}$ és la corba d'Edwards torçada

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

• $\ell =2^{252}+27742317777372353535851937790883648493$ i $c=3$
• $B$ és el punt únic en $E(\mathbb {F} _{q})$ de qui $y$ coordenada és $4/5$ i de qui $x$ la coordenada és positiva. "positiu" es defineix en termes de codificació de bits:
  • Les coordenades "positives" són coordenades parells (el bit menys significatiu s'esborra)
  • Les coordenades "negatives" són coordenades imparelles (es defineix el bit menys significatiu)
• $H$ és SHA-512, amb $b=256$ .

La corba d'Edwards retorçada $E/\mathbb {F} _{q}$ es coneix com a edwards25519, i és biracionalment equivalent a la corba de Montgomery coneguda com a Curve25519 . L'equivalència és $$x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.$$