Firmas ElGamal y "aleatoriedad relacionada"

Question

Como parte de un concurso de seguridad CTF , había que romper la siguiente variación del esquema de firma ElGamal:

Dejemos que $q$ sea primo y $p = 2q + 1$ también de primera. En la práctica, estos dos primos estaban codificados. La página web código fuente del algoritmo de firma y verificación está disponible como Gist. El orden del subgrupo multiplicativo generado por $g = 2$ en $F_p$ tiene orden $q$ .

Una firma para el hash de un mensaje $m$ y una clave privada $x$ se produce de la siguiente manera:

1. Seleccione un número entero $k$ "al azar" en el rango $[0, q)$
2. Calcula $r = g^k \ \text{mod}\ p$
3. Emitir la firma $(s = k^{-1} (m + xr) \ \text{mod}\ q, r \ \text{mod}\ q)$

La diferencia entre esto y clásico ElGamal es que $m + xr$ se utiliza en lugar de $m - xr$ . Por lo tanto, la verificación también es algo más complicada.

Ahora nos dan las firmas $(s_1, r_1)$ y $(s_2, r_2)$ para los dos mensajes $m_1 =$ sha256("f $m_2 =$ sha256("bar"). $k_1$ se elige efectivamente al azar, sin embargo tenemos $k_2 = (a\cdot k_1 + b) \ \text{mod}\ 2^{1024}$ para $a = 713030730552717, b = 123456789$ .

La tarea consiste en recuperar la clave privada $x$ de esta información. Sé que la reutilización de la aleatoriedad es un obstáculo para ElGamal, sin embargo, no he sido capaz de utilizar un enfoque similar para romper la "aleatoriedad relacionada" utilizada aquí. Parece especialmente complicado que la relación lineal entre $k_1$ y $k_2$ es solo modulo $2^{1024}$ no modulo $q$ .

EDITAR: Bien, creo que he descubierto un paso hacia la solución: Tenemos (módulo q):

(1) $k \cdot s_1 = m_1 + x\cdot r_1$

(2) $((ak + b) \ \text{mod} \ 2^{1024}) s_2 = m_2 + x\cdot r_2$

Multiplica la primera ecuación por $l = r_2 / r_1 \ \text{mod} \ q$ :

(1') $lk \cdot s_1 = l\cdot m_1 + x\cdot r_2$

Con alta probabilidad, tenemos $(ak + b) \ \text{mod} \ 2^{1024} = ak \ \text{mod} \ 2^{1024} + b$ .

Restando (2) - (1') obtenemos entonces:

$((ak \ \text{mod}\ 2^{1024}) s_2 - lk \cdot s_1) = m_2 - m_1 \cdot l - b \cdot s_2$

Si el módulo de reducción $2^{1024}$ no estaba allí, sería trivial desde aquí recuperar $k$ porque es el único valor desconocido en la ecuación. Sin embargo, no sé cómo proceder con él.

Answer 1

Bien, esta es una posible solución, basada en este escrito de @nneonneo: Podemos reformular la ecuación final de la pregunta a

$$(ak + b - tN) s_2 - lk \cdot s_1 = m_2 - m_1 \cdot l$$

y por lo tanto

$$k = \frac{m_2 - m_1 \cdot l + (tN - b) \cdot s_2}{a \cdot s_2 - l \cdot s_1}$$

Donde $N = 2^{1024}$ y $0 \le t \le (ak + b) / N \le a + 1$ .

También sabemos que

$$r_2 \equiv 2^{ak + b - tN} \equiv r_1^a \cdot 2^b\cdot (2^N)^t\pmod{p}$$

y por lo tanto

$$(2^N)^t \equiv 2^{ak + b - tN} \equiv r_1^a \cdot 2^b\cdot r_2^{-1} \pmod{p}$$

Sólo se nos da $r_1$ y $r_2$ módulo reducido $p$ y luego $q$ pero podemos obtener fácilmente los valores modulo $p$ probando todas las opciones posibles (sólo hay cuatro). Ahora bien, como $t \le a + 1$ podemos resolver el problema del logaritmo discreto en $\mathcal{O}(\sqrt{a})$ utilizando el algoritmo de paso de gigante y enchufe $t$ en la primera ecuación para calcular $k$ . A partir de ahí es fácil reconstruir $x$ también.