ECDSA

ECDSA (*Elliptic Curve Digital Signature Algorithm*, en espanyol: Algoritme de Firma Digital de Curva Elíptica) és un algoritme de firma digital basat en criptografia de curva elíptica. Constituïx una variant de l'algoritme DSA que ampra operacions sobre punts de curves elíptiques en lloc de les exponenciaciones modular utilisades per DSA, basades en el problema del logaritmo discret en grups multiplicativos.

La seguritat de ECDSA es fonamenta en la dificultat computacional del problema del logaritmo discret sobre curves elíptiques (*Elliptic Curve Discrete Logarithm Problem*, ECDLP). La principal ventaja d'este esquema és que requerix números de tamanys significativament menors per a brindar el mateix nivell de seguritat que DSA o RSA, lo que es traduïx en una major eficiència en térmens d'almagasenament, ample de banda i temps de còmput.

Existixen dos tipos principals de curves elíptiques segons el camp finito sobre el qual es definixquen: curves sobre camps primers GF(p) i curves sobre camps binarios GF(2^m). En la pràctica, els estàndarts moderns favorixen l'us de curves sobre camps primers per la seua millor interoperabilidad i a consideracions de seguritat i implementació.

Història

La criptografia de curva elíptica va ser proposta de manera independent per Neal Koblitz i Victor S. Miller en 1985 com una alternativa als sistemes criptográficos basats en exponenciación modular. A partir d'estes idees, es varen desenrollar esquemes de firma digital basats en curves elíptiques durant la década de 1990.

ECDSA va ser estandardisat formalment pel National Institute of Standards and Technology (NIST) en l'estàndart FIPS 186 i per Certicom en les especificacions SEC. Des de llavors, ha segut adoptat àmpliament en estàndarts internacionals, protocols de seguritat i aplicacions comercials.

Procés de firma i verificació

Generació de claus

1. Seleccione una curva elíptica I definida sobre un camp finito.
2. Seleccione un punt base P pertanyent a I d'orde primer n.
3. Seleccione aleatoriamente un número entero d en l'interval [1, n − 1].
4. Calcule Q = dP per mig de multiplicació escalar.
5. El valor d constituïx la clau privada.
6. El punt Q constituïx la clau pública.

Procés de firma

1. Seleccione un número entero aleatori k en l'interval [1, n − 1].
2. Calcule kP = (x₁, i₁).
3. Calcule r = x₁ mod n; si r = 0, retorne al primer pas.
4. Calcule l'invers modular k⁻¹ mod n.
5. Calcule s = k⁻¹(H(m) + dr) mod n; si s = 0, retorne al primer pas.
6. La firma del mensage m està composta pel parell ordenat (r, s).

Procés de verificació

1. Verifique que r i s pertanyguen a l'interval [1, n − 1].
2. Calcule w = s⁻¹ mod n.
3. Calcule o₁ = H(m)w mod n.
4. Calcule o₂ = rw mod n.
5. Calcule el punt (x₀, i₀) = o₁P + o₂Q.
6. Calcule v = x₀ mod n.
7. La firma és vàlida si i solament si v = r.