Pregunta:
Este documento (página 27) dice que:
La única diferencia significativa entre ECDSA y DSA está en la generación de $r$ .
- ECDSA $r = (kG)_x \bmod n$ y,
- DSA: $r=g^k \bmod p$
¿Por qué es necesario tener una función que tome un número aleatorio $k$? ¿Por qué no podemos usar los $k$ aleatorios directamente como nuestro valor de $r$ en las firmas?
Respuesta:
Primero, una advertencia importante: DSA y ECDSA no han demostrado ser seguros de ninguna manera. Este es el lote de la mayoría de los algoritmos criptográficos, por lo que, en el mejor de los casos, solo podemos tener una intuición sobre por qué garantizan la seguridad.
DSA (y luego ECDSA) es un derivado suelto de la firma de Schnorr (de hecho, no era exactamente el algoritmo de Schnorr con el propósito declarado de no estar dentro del alcance de la patente de Schnorr, lo que no impidió que ocurrieran algunos litigios). Puede entenderse así como una prueba de conocimiento . En este caso, el valor $k$ es un valor que NO DEBE revelarse al final; el firmante se compromete a ese valor calculando y revelando $g^k$ ($kG$ para ECDSA).
De hecho, si considera el algoritmo de verificación de firma, el verificador reconstruye el valor $g^k$, que solo conoce la clave pública: $$ \begin{eqnarray*} w &=& s^{-1} \mod q \\ u_1 &=& wH(m) \mod q \\ u_2 &=& rw \mod q \\ v &=& (g^{u_1} y^{u_2} \mod p) \mod q \\ \end{eqnarray*} $$
El valor $g^{u_1}y^{u_2} \pmod p$ es de hecho $g^k$ en su totalidad.
Sin embargo, si se revela $k$, entonces dado que la firma es $(r,s)$ donde $$r = (H(m)+xr)/k \pmod q$$ entonces $x$ (la clave secreta) se puede recalcular fácilmente: $$x = r – k^{-1}H(m) \pmod q$$
En resumen, necesitamos usar $g^k$ (o $kG$) y no directamente $k$ porque ahí es donde reside la magia del algoritmo de firma: en un compromiso con un valor aleatorio $k$, que es oculto detrás del logaritmo discreto, y aún ligado por relaciones algebraicas al (revelado) $g^k$, lo que permite su validación.