The intuition behind elliptic curve digital signatures (ECDSA)

Last updated on Sep 25, 2024

Este artículo explica cómo funciona el ECDSA (Elliptic Curve Digital Signature Algorithm), así como por qué funciona.

En este tutorial, “redescubriremos” gradualmente el algoritmo desde sus principios fundamentales.

Requisitos previos

Asumimos conocimientos previos sobre

Repaso de las firmas digitales

Un algoritmo de firma digital es un protocolo que permite a un usuario otorgar un sello de aprobación criptográfico a una cadena de texto.

Dicho usuario tiene una clave pública (un par $(x,y)$ correspondiente a un punto en la curva elíptica). El punto fue generado a partir de una clave privada, la cual es un valor escalar secreto.

Dada una clave pública, un mensaje y una firma, otro usuario puede verificar que la firma fue producida por alguien que posee la clave privada correspondiente a esa clave pública, y que solo esa persona podría haber generado la firma.

Por ejemplo, las criptomonedas usan firmas digitales para verificar que un usuario realmente quería realizar una transacción. Una usuaria, Alice, puede enviar un mensaje a la blockchain diciendo “Envía 10 de mis tokens a Bob”. La red blockchain debe estar segura de que Alice realmente dio su sello de aprobación a ese mensaje y que Bob no está robando las monedas de Alice.

La firma producida debe ser específica para el mensaje y no ser aceptada para otros mensajes. De lo contrario, un atacante podría usar una firma para hacer que la víctima apruebe una transacción maliciosa. Si la firma para el mensaje “transferir 10 monedas a Bob” también pudiera usarse como un sello de aprobación para el mensaje “transferir 10 monedas a Eve”, entonces Eve podría usar la firma de la transferencia a Bob para robarle monedas a Alice.

Llamamos a la persona que genera la firma el probador o firmante y a la persona que comprueba si la tupla (Clave Pública, mensaje, firma) es válida el verificador.

En esencia, una firma digital de curva elíptica es una prueba de conocimiento de una clave privada. Específicamente, es una prueba de conocimiento del logaritmo discreto de un punto en la curva elíptica.

Para los lectores que ya han visto el algoritmo ECDSA:

\begin{align*} r &= kG\\ s &= k^{-1}(h + rp)\\ r &\stackrel{?}= s^{-1}(hG + rP) \end{align*}

pero no saben de dónde provienen las fórmulas, aprenderán el razonamiento detrás de cómo se derivaron.

Terminología y notación

Nos referimos a los puntos de la curva elíptica con letras mayúsculas, como $Q$ . El generador será denominado $G$ . El valor de $G$ es conocido por todas las partes involucradas. La multiplicación entre un escalar y un punto se escribe como $aG$ , lo que significa que $G$ se suma a sí mismo $a$ veces.

Dados dos puntos $P$ y $Q$ , decimos que alguien conoce la relación de logaritmo discreto entre $P$ y $Q$ si conoce $x$ tal que $xP = Q$ , o alternativamente, $y$ tal que $P = yQ$ .

Decimos que alguien conoce el logaritmo discreto de un punto $Q$ si conoce un escalar $q$ tal que $Q = qG$ .

Nos referimos al logaritmo discreto de un punto con la versión en minúscula de la misma letra, a menos que se indique lo contrario.

Toda la aritmética se realiza en un campo finito, pero omitimos la notación $\pmod p$ por brevedad.

Intentos fallidos de firmas digitales

Enfoque ingenuo: revelar la clave privada

Queremos demostrar que conocemos la clave privada $p$ para la clave pública $P$ , donde $P = pG$ .

El enfoque ingenuo es revelar la clave privada $p$ al verificador para que este pueda comprobar que, en efecto, $P = pG$ .

Por supuesto, esto anula el propósito de mantener $p$ en privado.

Demostrar el conocimiento de la relación de logaritmo discreto entre $P$ y $Q$

Demostrar que conocemos $p$ es equivalente a demostrar que conocemos la relación de logaritmo discreto entre el generador $G$ y la clave pública $P$ . Es decir, $G$ se suma a sí mismo $p$ veces para obtener $P$ . Revelar la relación de logaritmo discreto entre $G$ y $P$ revela la clave privada.

Por lo tanto, en lugar de demostrar que conocemos la relación de logaritmo discreto entre el generador $G$ y la clave pública $P$ , podemos demostrar que conocemos la relación de logaritmo discreto entre $P$ y $Q$ , donde $Q$ es elegido por el probador y cuyo logaritmo discreto $q$ es desconocido para el verificador. Si el logaritmo discreto de $Q$ es desconocido para el verificador, entonces este no puede derivar la clave privada, dada la relación de logaritmo discreto entre $P$ y $Q$ .

Sea $s$ el número de veces que $P$ necesita sumarse a sí mismo para producir $Q$ ; en otras palabras, $sP = Q$ . Si el probador conoce el logaritmo discreto de $P$ y $Q$ , como $p$ y $q$ respectivamente, puede calcular fácilmente $s$ como $s = q/p$ .

$s = q/p$ se derivó de la siguiente manera:

\begin{align*} Q &= sP\\ Q &= qG\\ P &= pG\\ qG &= spG \\ q &= sp \\ \frac{q}{p} &= s\\ \end{align*}

Luego, el verificador puede comprobar que, en efecto, $Q = sP$ , y esto demuestra que el probador conoce la relación de logaritmo discreto entre $P$ y $Q$ .

Sin embargo, este enfoque falla porque un probador malicioso puede tomar el $P$ de otra persona (del cual no conoce la clave privada), elegir un valor aleatorio $s$ , calcular $Q = sP$ y luego enviar $(P, Q, s)$ al verificador.

Por lo tanto, el hecho de que el probador demuestre que conoce la relación de logaritmo discreto entre $P$ y $Q$ no es suficiente para demostrar que conoce el logaritmo discreto de $P$ en sí. Solo demuestra que multiplicó algún $P$ por $s$ para producir $Q$ .

Prevenir la elección aleatoria de $Q$

El enfoque anterior fracasó porque el probador puede presentar $Q$ sin conocer realmente el logaritmo discreto de $Q$ en sí.

¿Qué pasaría si, para establecer que el probador conoce el logaritmo discreto de $Q$ , el probador revela $q$ (el logaritmo discreto de $Q$ ) al verificador?

En este caso, el probador debe revelar tanto $q$ como $s$ al verificador. Luego, $s$ demuestra que el probador sabe cuántas veces debe sumarse $P$ a sí mismo para obtener $Q$ , y $q$ demuestra que el probador conoce el logaritmo discreto de $Q$ . Presentar $q$ demuestra que $Q$ no fue seleccionado eligiendo un valor $s$ y sumando $P$ a sí mismo $s$ veces.

En ese caso, el verificador comprueba que

\begin{align*} qG &\stackrel{?}{=} Q &&\text{ // el probador conoce el logaritmo discreto de Q}\\ sP &\stackrel{?}{=} Q &&\text{ // el probador sabe cuántas veces debe sumarse P a sí mismo para obtener Q} \end{align*}

Con estas comprobaciones, el probador no puede crear o producir una relación válida sin conocer el logaritmo discreto de $Q$ y el logaritmo discreto de $P$ .

Sin embargo, el verificador puede calcular la clave privada basándose en esta información.

\begin{align*} Q &= sP\\ s^{-1}Q&=P\\ s^{-1}(qG)&=P\\ s^{-1}q &= P/G\\ s^{-1}q &= p\\ \end{align*}

Así que tenemos un dilema: si revelamos el logaritmo discreto de $Q$ , el verificador puede calcular la clave privada. Si el probador puede elegir $Q$ a voluntad, entonces puede crear firmas para claves públicas de las que no conoce el logaritmo discreto.

No podemos permitir que el verificador pueda calcular la clave privada, por lo que revelar $q$ está fuera de discusión.

Por lo tanto, nuestra solución debe incluir que el probador elija $Q$ , pero debemos evitar que el probador pueda elegir $Q$ de manera completamente arbitraria (como eligiendo un $s$ arbitrario y produciendo $Q = sP$ ).

En adelante, el probador debe demostrar que conoce el logaritmo discreto de $Q$ y el logaritmo discreto de $P$ , pero sin revelar ninguno de los logaritmos discretos $p$ o $q$ .

Resulta que demostrar que conocemos el logaritmo discreto de dos puntos sin revelarlos es más fácil que demostrar que conocemos el logaritmo discreto de un punto sin revelar ese único logaritmo discreto.

Si el probador conoce los logaritmos discretos de $P$ y $Q$ , entonces ¿qué más debe saber?

La idea clave es esta:

Si el probador conoce los logaritmos discretos de $P$ y $Q$ , entonces no solo debe conocer $s$ tal que $sP = Q$ , sino que también debe conocer $s'$ tal que $s'(hG + P) = Q$ , donde $h$ es un valor arbitrario elegido por el verificador y es un valor que el probador no puede predecir.

En otras palabras, vamos a empezar a incluir “desplazamientos” aditivos y multiplicativos en la relación entre $P$ y $Q$ , y si el probador conoce los logaritmos discretos de $P$ y $Q$ , entonces debe poder calcular $s'$ tal que $s'(hG +P) = Q$ , siempre y cuando el probador sepa de cuánto es el desplazamiento $h$ .

Un desplazamiento aditivo previene las falsificaciones

Para evitar que el probador elija $Q$ de modo que sea una simple multiplicación escalar de $P$ , el verificador puede inyectar un desplazamiento aditivo $h$ .

Después de que el probador envía $P$ y $Q$ al verificador, el verificador responde con $h$ (un valor escalar público). El probador debe entonces producir $s$ tal que $Q = s(hG + P)$ (ya no necesitamos la notación $s'$ ).

Ahora el probador no controla la relación de logaritmo discreto entre $P$ y $Q$ ; en su lugar, debe demostrar que conoce la relación de logaritmo discreto entre $(hG + P)$ y $Q$ .

Dado que el verificador ya está en posesión de $P$ y $Q$ , el probador no puede simplemente elegir un $s$ aleatorio y generar $Q$ tal que $Q = s(hG + P)$ . El probador debe demostrar que conoce la relación de logaritmo discreto entre el nuevo punto $(hG + P)$ y el $Q$ original.

Si el probador conoce los logaritmos discretos de $P$ y $Q$ , entonces $s$ es fácil de calcular como:

s = \frac{q}{h + p}

Específicamente, el probador resolvió

\begin{align*} s(hG + P)&=Q\\ s(h + p) &= q\\ s&=\frac{q}{h+p} \end{align*}

Resumamos el algoritmo interactivo que acabamos de crear:

Asumimos que ambas partes están de acuerdo en $G$ (y en el grupo de la curva elíptica al que pertenece).
El probador publica su clave pública $P$ y desea demostrar que conoce la clave privada $p$ .
El verificador responde con un escalar $h$ .
El probador elige un $q$ aleatorio y calcula $Q = qG$ .
El probador calcula $s = q(h + p)^{-1}$ y envía $(s, Q)$ al verificador
El verificador comprueba si $Q \stackrel{?}= s(hG + P)$

La última comprobación funciona porque, internamente, la $s$ cancela los logaritmos discretos de $h$ y $p$ :

\begin{align*} Q &= s(hG + P)\\ qG &= \frac{q}{h + p}(hG+P)\\ qG &= \frac{q}{h + p}(hG+pG)\\ qG &= \frac{q}{h + p}(h+p)G\\ qG &= \frac{q}{\cancel{h + p}}(\cancel{h+p})G\\ qG &= qG \end{align*}

Defensa contra firmas falsificadas

Veamos cómo un probador malicioso podría intentar calcular $s$ sin conocer los logaritmos discretos de $P$ y $Q$ , y por qué el intento falla.

El probador inventa un valor $\tilde{q}$ , genera $Q = \tilde{q}P$ y envía $Q$ al verificador. Sea $\tilde{q}$ un valor inventado por el probador malicioso, y no el logaritmo discreto de $Q$ .

El verificador responde con el escalar $h$ .

El probador malicioso debe ahora resolver la ecuación

s(P + hG) = Q

Dado que el probador sabe que $Q = \tilde{q}P$ (pero no conoce $p$ ), puede intentar dos sustituciones:

$Q = \tilde{q}P$
$P = \tilde{q}^{-1}Q$ .

Sin embargo, de cualquier forma en que el probador sustituya $Q$ o $P$ , se encuentra con el problema de que no puede resolver $s$ porque desconoce el logaritmo discreto de $P$ .

Sustituir $Q$

Aquí el probador sustituye la $Q$ :

s(P + hG) = \boxed{Q}

s(P + hG) = \boxed{\tilde{q}P}

s = \frac{\tilde{q}P}{P + hG}

No podemos dividir puntos de la curva elíptica, así que para calcular la fracción anterior, necesitamos conocer $p$ :

s = \frac{\tilde{q}p}{p + h}

Pero el probador no conoce $p$ , por lo que no puede calcular $s$ .

Sustituir $P$

Ahora el probador malicioso intenta sustituir $P$ en lugar de $Q$ , pero se encuentra con el problema de que no conoce el logaritmo discreto de $Q$ :

s(\tilde{q}^{-1}Q + hG) = Q

s = \frac{Q}{(\tilde{q}^{-1}Q + hG)}

Ahora el probador malicioso necesita conocer el logaritmo discreto de $Q$ para calcular la fórmula anterior. Sin embargo, el probador no conoce el logaritmo discreto de $Q$ ; solo sabe que es $\tilde{q}P$ , pero no conoce $p$ . Por lo tanto, el probador malicioso no puede producir $s$ .

Por qué el desplazamiento debe ser aditivo

¿Cómo supimos que debíamos sumar $hG$ a $P$ en lugar de multiplicar $hP$ y pedirle al probador que propusiera un $s$ tal que $Q = hsP$ ?

El problema es que, con un desplazamiento multiplicativo, el probador puede cancelar los factores de los logaritmos discretos de $Q$ y $P$ .

A modo de resumen: un probador malicioso no conoce $q$ , el logaritmo discreto de $Q$ , ni $p$ , el logaritmo discreto de $P$ . Sin embargo, sí sabe que $Q$ es $\tilde{q}$ veces mayor que $P$ , donde $\tilde{q}$ es un número que inventó y no el verdadero logaritmo discreto de $Q$ .

Si el verificador presenta $h$ y le pide al probador que proponga un $s$ tal que $Q = shP$ , entonces el probador simplemente calcula $s = \tilde{q}/h$ .

Esto superará la prueba del verificador:

\begin{align*} Q &= shP \\ Q &= \frac{\tilde{q}}{h}h P\\ Q &= \frac{\tilde{q}}{\cancel{h}}\cancel{h} P\\ Q &= qP \\ \end{align*}

Por lo tanto, el protocolo debe incluir un desplazamiento aditivo para que no haya una relación multiplicativa simple $sh$ entre el primer punto ( $P + hG$ ) y el segundo punto $Q$ .

Haciendo que nuestro protocolo sea no interactivo

Desafortunadamente, nuestra solución requiere que el verificador envíe $h$ después de recibir $P$ y $Q$ , lo que exige que el probador y el verificador interactúen entre sí.

Si queremos hacer que nuestro protocolo no sea interactivo, entonces $h$ no puede provenir del verificador y el probador debe producirlo.

Si el probador conoce $h$ de antemano (lo cual es necesario si la prueba no es interactiva), entonces volvemos a nuestro problema original.

En este escenario, un probador malicioso puede elegir $h$ al azar, luego elegir $s$ al azar, y calcular

Q = s(hG + P)

y luego enviar $(P, Q, s, h)$ al verificador. El verificador no sabe si $Q$ fue generado por un $s$ aleatorio.

Para evitar que el probador elija $h$ y la interacción con un verificador, podemos simular que el verificador elige $h$ simplemente aplicando una función hash a $Q$ :

h = \mathsf{hash}(Q)

Dado que el verificador elegirá $h$ de forma aleatoria de todos modos, el probador puede calcular $h$ de manera pseudoaleatoria usando una función hash. Esta técnica se llama Fiat-Shamir Transform.

Una prueba funcional de conocimiento de una clave privada

El algoritmo es el siguiente:

El probador elige un escalar aleatorio $q$ y calcula $Q = qG$ .
El probador calcula $h = \mathsf{hash}(Q)$ .
El probador calcula $s = \frac{q}{h + p}$ .
El probador envía $(P, Q, s, h)$ al verificador.
El verificador calcula $h = \mathsf{hash}(Q)$ .
El verificador comprueba que $Q = s(hG + P)$ .

La razón por la que esto es seguro es porque un probador malicioso no puede ejecutar el paso 3 sin conocer el logaritmo discreto de $Q$ y el logaritmo discreto de $P$ .

La falsificación es imposible

Supongamos que un probador malicioso elige $\tilde{q}$ y genera $Q = \tilde{q}G$ . Aquí, el probador conoce el logaritmo discreto de $Q$ , pero no el logaritmo discreto de $P$ . Después de aplicar el hash a $Q$ para obtener $h$ , el probador malicioso necesita calcular $s$ tal que $Q = s(hG + P)$ . Sin embargo, no puede hacerlo porque desconoce el logaritmo discreto de $(hG + P)$ , ya que el logaritmo discreto de $P$ es desconocido para él.

Así, hemos demostrado un algoritmo seguro para probar el conocimiento de una clave privada sin revelar la clave privada.

El algoritmo pre-ECDSA

El algoritmo que presentamos anteriormente simplemente prueba el conocimiento de una clave privada, no permite al firmante firmar un mensaje.

En ECDSA, una firma es una prueba de que conocemos el logaritmo discreto del punto generado al desplazar aditivamente nuestra clave pública por $hG$ , donde $h$ es el hash del mensaje, y el logaritmo discreto de otro punto $Q$ .

Sin embargo, el enfoque actual introduce una vulnerabilidad de seguridad, ya que el probador puede primero calcular $h = \mathsf{hash}(\text{message})$ y luego elegir un $s'$ aleatorio y calcular $Q = s'(hG + P)$ . Ahora $Q$ vuelve a estar completamente bajo el control del probador, por lo que no podemos confiar en que el probador realmente conozca el logaritmo discreto $q$ .

Para asegurar esto, necesitamos introducir nuevamente un poco de pseudoaleatoriedad adicional que esté fuera del control del probador.

Añadiendo la aleatoriedad $r$

Sea $r$ un valor aleatorio derivado de aplicar un hash a $Q$ . Si multiplicamos $r$ por $P$ de la siguiente manera, obtenemos un algoritmo de firma digital seguro. Al principio, esto parece crear una dependencia circular, pero en realidad es fundamental para hacer que el algoritmo sea seguro. El algoritmo para que el probador demuestre que conoce el logaritmo discreto de $(rP + hG)$ y $Q$ es:

Q = s(hG + rP)

El probador elige un $p$ aleatorio y publica su clave pública $P$ como $P = pG$ .
El probador elige un escalar aleatorio $q$ y calcula $Q = qG$ .
El probador elige una cadena de mensaje $\text{message}$ y calcula $h = \mathsf{hash}(\text{message})$ .
El probador calcula $r = \mathsf{hash}(Q)$ .
El probador calcula $s = q\cdot(h + rp)^{-1}$ .
El probador envía $(\text{message}, Q, s)$ al verificador
El verificador calcula $r' = \mathsf{hash}(Q)$
El verificador calcula $h = \mathsf{hash}(\text{message})$
El verificador comprueba que $Q \stackrel{?}= s(hG + r'P)$

Aunque el probador puede elegir un $h$ arbitrario, no puede controlar el logaritmo discreto del punto $(hG + rP)$ porque $r$ se genera aplicando un hash a $Q$ . Por lo tanto, para calcular $s$ , la relación de logaritmo discreto entre $Q$ y $(hG + rP)$ , el probador debe conocer realmente el logaritmo discreto $p$ de $P$ .

Optimizando el algoritmo pre-ECDSA

Optimización 1: Aplicar hash a $Q$ es innecesario porque la multiplicación en curvas elípticas ya se comporta como una función hash

Recordemos lo que $r = \mathsf{hash}(Q)$ intentaba lograr. La fórmula de verificación final es:

Q \stackrel{?}= s(hG + rP)

La idea es que queremos que $r$ dependa de $Q$ para que $Q$ no esté completamente determinado por el valor $s$ , sobre el cual el probador tiene control total. Para calcular $s$ , el probador debe conocer el logaritmo discreto de $P$ .

Queremos una alternativa más económica al uso del hash que haga que $r$ dependa de $Q$ .

Tenga en cuenta que si $r$ depende de $Q$ , entonces también depende del logaritmo discreto de $Q$ , $q$ , ya que $q$ determina completamente a $Q$ .

Ahora considere que, si se nos da un valor escalar $a$ , el punto de la curva elíptica $A$ creado por $A = aG$ parece aleatorio. No existe una relación aparente entre $A$ y $a$ . Esta falta de una relación aparente es lo que hace que calcular el logaritmo discreto sea difícil.

Las funciones hash también tienen una salida que parece aleatoria: no hay una relación aparente entre la entrada y la salida de un hash.

Por lo tanto, podemos tratar $Q = qG$ de la misma manera que trataríamos $\mathsf{hash}(q)$ . Es decir, el propio $Q$ se comporta como el resultado de un hash. Sin embargo, no podemos establecer que $r = Q$ ya que no son del mismo tipo. En su lugar, simplemente podemos tomar el valor $x$ de $Q$ y hacer que sea $r$ (recuerde, $Q$ es un punto $(x, y)$ ).

Ahora $r$ es esencialmente el hash de $q$ , y dado que $Q$ depende directamente de $q$ , $r$ se comporta como un hash de $Q$ .

Por lo tanto, en lugar de calcular $r = \mathsf{hash}(Q)$ , establecemos $r = Q.x$ (es decir, el valor $x$ del punto $Q$ ).

Optimización 2: No necesitamos enviar el punto $Q$ completo, solo el valor $x$ de $Q$

Los puntos de una curva elíptica constan de dos escalares: el valor $x$ y el valor $y$ del punto. Cada valor $x$ tiene solo dos valores $y$ posibles, las soluciones a $\sqrt{x^3 + b} \mod p$ .

Por lo tanto, no hay necesidad de enviar $Q$ , solo $r$ porque $r$ es el valor $x$ de $Q$ .

El algoritmo ECDSA completo: paso a paso

Ahora mostramos el algoritmo ECDSA estándar junto con la notación de uso más común. Notamos dónde difiere nuestra notación.

El probador elige un $p$ aleatorio y publica su clave pública $P$ como $P = pG$ .
El probador elige un mensaje que desea firmar y le aplica un hash para obtener $h = \mathsf{hash}(\text{message})$ .
El probador elige un escalar aleatorio $k$ (lo que hemos estado llamando $q$ , pero la literatura lo llama $k$ ) y calcula $R = kG$ . De nuevo, lo que nosotros llamamos $Q$ la literatura lo llama $R$ . Solo se conserva el valor $x$ de $R$ como $r = R.x$ .
El probador calcula $s$ para $R = s^{-1}(hG + rP)$ como

s = \frac{h + rp}{k}

Note que $s$ está ‘invertido’ en comparación con nuestra implementación anterior. En el algoritmo ECDSA real, el probador calcula $s^{-1}$ y el verificador invierte $s$ más tarde, como veremos.

El firmante envía $(P, h, r, s)$ al verificador.
El verificador calcula $R' = s^{-1}(hG + rP)$ y comprueba que el valor $x$ de $R'$ sea igual a $r$ .

La fórmula funciona internamente de la siguiente manera:

\begin{align*} &=s^{-1}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rpG)\\ &=\frac{k}{h + rp}(h + rp)G\\ &=\frac{k}{\cancel{h + rp}}(\cancel{h + rp})G\\ &=kG \end{align*}

Esto produce el mismo punto $R$ y, por lo tanto, la $r$ coincidirá con el valor $x$ del punto calculado mediante $s^{-1}(hG + rP)$ .

Derivando la clave pública dada una firma

Las blockchains Ethereum y Bitcoin no verifican firmas dadas la clave pública, el mensaje y la firma. En cambio, dado el mensaje y la firma, resuelven la clave pública y comprueban que la clave pública coincida con la esperada.

Para ver cómo funciona esto, podemos aplicar un poco de álgebra en la fórmula de verificación para derivar la clave pública dada la firma y el hash del mensaje.

\begin{align*} R &= s^{-1}(hG + rP)\\ R &= s^{-1}hG + s^{-1}rP\\ R - s^{-1}hG &= s^{-1}rP\\ sr^{-1}R-r^{-1}hG&=P\\ \end{align*}

Sin embargo, solo con $(\text{message}, r, s)$ no es suficiente porque $r$ corresponde a dos posibles puntos debido a los dos valores $y$ de $r = R.x$ . Para eliminar la ambigüedad, el firmante también debe enviar una variable booleana que indique qué valor de $y$ se está utilizando. Enviar la $y$ completa ocuparía más espacio.

El algoritmo ECDSA para ‘recuperar’ la clave pública dada una firma es el siguiente:

El probador publica su clave pública $P$ como $P = pG$ .
El probador elige un mensaje que desea firmar $\text{message}$ y le aplica un hash para obtener $h = \mathsf{hash}(\text{message})$ .
El probador elige un escalar aleatorio $k$ y calcula $R = kG$ .
El probador calcula $h = \mathsf{hash}(\text{message})$
El probador resuelve $s$ en $R = s^{-1}(hG + rP)$ como $s = \frac{h + rp}{k}$ .
El firmante envía $(\text{message}, r, s, v)$ al verificador, donde $v$ es un booleano que indica qué valor $y$ de $r$ se está utilizando.
El verificador deriva $R$ a partir de $v$ y $r$ .
El verificador deriva la clave pública $P$ como

P = sr^{-1}R - r^{-1}hG

y acepta la firma si el $P$ calculado coincide con la clave pública $P$ que publicó el probador.

Vulnerabilidades en ECDSA por un mal uso

Maleabilidad en ECDSA

Dada una firma $(\text{message}, r, s, v)$ , un atacante puede calcular una segunda firma $(\text{message}, r, s', v')$ tal que $v \neq v'$ y $s \neq s'$ que se recupere a la misma clave pública $P$ .

El atacante simplemente calcula el inverso aditivo de $s$ como $s' = s^{-1}$ y cambia el valor de $v$ para que $R$ se convierta en su inverso aditivo. Esencialmente, hemos reemplazado $s$ con $-s$ y $R$ con $-R$ . Dado que estos dos valores se multiplican, los factores -1 se cancelan y la clave pública recuperada es la misma:

\begin{align*}P &= (-s)r^{-1}(-R) - r^{-1}hG\\ &= sr^{-1}R - r^{-1}hG \end{align*}

Para prevenir este ataque, el verificador no debe aceptar una firma diferente para un mismo mensaje que ya ha visto antes. La solución más generalizada y robusta es usar un nonce, que es un número siempre creciente que el probador debe incluir en su mensaje. Un nonce (que significa ‘número usado una vez’) sirve como un identificador único para cada firma. Al exigir que el probador incorpore un nonce nuevo y mayor con cada firma, el verificador puede detectar y rechazar fácilmente los intentos de reutilizar o modificar firmas anteriores.

Si el verificador no le aplica un hash al mensaje, se pueden crear pruebas falsas.

Consideremos que un atacante puede crear un valor $R$ del cual no conocemos el logaritmo discreto, pero sí conocemos sus componentes. Por ejemplo, el atacante elige valores aleatorios $a$ y $b$ y calcula $R = aG + bP$ , y $r = R.x$ .

Luego, el atacante calcula $s = r/b$ y $h = ar / b$ .

Podemos ver cómo funciona este ataque sustituyendo los valores falsos de $s$ y $h$ en la fórmula de verificación:

\begin{align*} R &\stackrel{?}= s^{-1}(hG + rP) \\ R &\stackrel{?}= (\frac{r}{b})^{-1}((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (\frac{b}{r})((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (aG + bP) \end{align*}

La defensa contra este ataque es simple: $h$ debe ser el resultado de que el verificador aplique un hash al mensaje. Cuando se aplica un hash a un mensaje, es extremadamente improbable que el hash sea exactamente $ar/b$ .

Resumen

El algoritmo ECDSA es una prueba de conocimiento de la relación de logaritmo discreto entre un punto arbitrario $R$ y un punto que representa la suma del hash del mensaje multiplicado por el generador y la clave pública multiplicada por un valor pseudoaleatorio que el firmante no controla.

Específicamente, es una prueba de conocimiento de la relación de logaritmo discreto entre $R$ y $(hG + rP)$ .

Aunque el firmante puede elegir $R$ arbitrariamente, no puede controlar el logaritmo discreto del punto $(hG + rP)$ porque $r$ depende pseudoaleatoriamente de $R$ . La única manera de que el firmante pueda calcular $s$ en $R = s(hG + rP)$ es si realmente conoce el logaritmo discreto de $P$ , es decir, la clave privada.

Créditos y agradecimientos

Se consultaron los siguientes recursos durante la creación de este artículo:

La intuición detrás de las firmas digitales de curva elíptica (ECDSA)