El ataque de Wiener

El ataque de Wiener , que recibe su nombre del criptólogo Michael J. Wiener, es un tipo de ataque criptográfico contra RSA . El ataque utiliza la representación de fracción continua para exponer la clave privada d cuando d es pequeño.

Los personajes ficticios Alice y Bob son personas que desean comunicarse de forma segura. Más específicamente, Alice quiere enviar un mensaje a Bob que solo él pueda leer. Primero, Bob elige dos números primos secretos p y q . Luego calcula el módulo RSA N = pq . Este módulo RSA se hace público junto con el exponente de cifrado e . N y e forman el par de claves públicas ( e , N ) . Al hacer pública esta información, cualquiera puede cifrar mensajes para Bob. El exponente de descifrado d satisface ed ≡ 1 (mod λ ( N )) , donde λ ( N ) denota la función de Carmichael , aunque a veces se usa φ ( N ), la función totiente de Euler (nota: este es el orden del grupo multiplicativo ( Z / NZ ) × ^, que no es necesariamente un grupo cíclico). El exponente de cifrado e y λ ( N ) también deben ser primos relativos para que exista un inverso modular . La factorización de N y la clave privada d se mantienen en secreto, de modo que solo Bob puede descifrar el mensaje. Denotamos el par de claves privadas como ( d , N ) . El cifrado del mensaje M viene dado por C ≡ M ^e (mod N ) y el descifrado del texto cifrado C viene dado por C ^d ≡ ( M ^e ) ^d ≡ M ^ed ≡ M (mod N ) (usando el teorema de Euler ).

Utilizando el algoritmo euclidiano , se puede recuperar eficientemente la clave secreta d si se conoce la factorización de N. Al tener la clave secreta d , se puede factorizar eficientemente el módulo ^de N. [ ^{1 ]}

En el criptosistema RSA , Bob podría tender a usar un valor pequeño de d , en lugar de un número aleatorio grande, para mejorar el rendimiento del descifrado RSA . Sin embargo, el ataque de Wiener muestra que elegir un valor pequeño para d dará como resultado un sistema inseguro en el que un atacante puede recuperar toda la información secreta, es decir, romper el sistema RSA . Esta ruptura se basa en el teorema de Wiener, que se cumple para valores pequeños de d ^{. Wiener} ha demostrado que el atacante puede encontrar d de manera eficiente cuando d < 1/3 N 1/4 ^. [ ² ]

El artículo de Wiener también presentó algunas contramedidas contra su ataque que permiten un descifrado rápido. A continuación se describen dos técnicas.

Elegir una clave pública grande : Reemplazar e por e ′, donde e ′ = e + k ⋅ λ ( N ) para algún k grande . Cuando e ′ es suficientemente grande, es decir, e ′ > N ^3/2 , entonces el ataque de Wiener no se puede aplicar independientemente de cuán pequeño sea d .

Utilizando el teorema chino del resto : Supongamos que se elige d tal que tanto d _p ≡ d (mod ( p − 1)) como d _q ≡ d (mod ( q − 1)) sean pequeños, pero d mismo no lo sea, entonces se puede realizar un descifrado rápido de C de la siguiente manera:

1. Primero calcula M _p ≡ C ^{d _p} (mod p ) y M _q ≡ C ^{d _q} (mod q ) .
2. Utilice el teorema chino del resto para calcular el valor único de 0 ≤ M < N que satisface M ≡ M _p (mod p ) y M ≡ M _q (mod q ) . El resultado de M satisface M ≡ C ^d (mod N ) como se requiere. El punto es que el ataque de Wiener no se aplica aquí porque el valor de d mod λ ( N ) puede ser grande.

Tenga en cuenta que

${\displaystyle \lambda (N)=\operatorname {lcm} (p-1,q-1)={\frac {(p-1)(q-1)}{G}}={\frac {\varphi (N)}{G}}}$

donde G = mcd( p − 1, q − 1) .

Dado que ed ≡ 1 (mod λ ( N )) , existe un entero K tal que

${\displaystyle ed=K\times \lambda (N)+1}$

${\displaystyle ed={\frac {K}{G}}(p-1)(q-1)+1}$

Definiendo k = ⁠ K / mcd( K , G ) ⁠ y g = ⁠ G / mcd( K , G ) ⁠ , y sustituyendo en lo anterior se obtiene:

${\displaystyle ed={\frac {k}{g}}(p-1)(q-1)+1}$.

Dividido por dpq :

${\displaystyle {\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )}$, dónde${\displaystyle \delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}}$.

Así pues, e / pq es ligeramente menor que k / dg , y el primero se compone enteramente de información pública . Sin embargo , aún se requiere un método de verificación y estimación.

Mediante el uso de manipulaciones algebraicas simples e identidades , se puede comprobar la exactitud de una suposición . ^{[ 1 ]}

Sea N = pq con q < p < 2 q . Sea d < ⁠ 1 / 3 ⁠ N ^1/4 .

Dado ⟨ N , e ⟩ con ed ≡ 1 (mod λ ( N )) , el atacante puede recuperar d de manera eficiente . ^{[ 2 ] [ 3 ]}

Supongamos que las claves públicas son ⟨ N , e ⟩ = ⟨ 90581, 17993 ⟩ . El ataque debe determinar d . Usando el teorema de Wiener y fracciones continuas para aproximar d , primero intentamos encontrar la expansión en fracciones continuas de ⁠ e / N ⁠ . Nótese que este algoritmo encuentra fracciones en su mínima expresión. Sabemos que

${\displaystyle {\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]}$

Según el desarrollo en fracciones continuas de ⁠ e / N ⁠ , todas las convergentes ⁠ k / d ⁠ son:

${\displaystyle {\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}}$

Podemos verificar que la primera convergente no produce una factorización de N. Sin embargo , la convergente 1/5 produce

${\displaystyle \varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964}$

Ahora, si resolvemos la ecuación

${\displaystyle x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0}$

${\displaystyle x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0}$

${\displaystyle x^{2}-618x+90581=0}$

Entonces encontramos las raíces que son x = 379; 239. Por lo tanto, hemos encontrado la factorización.

${\displaystyle N=90581=379\times 239=p\times q}$.

Nótese que, para el módulo N = 90581 , el teorema de Wiener funcionará si

${\displaystyle d<{\frac {N^{1/4}}{3}}\approx 5.7828}$.

La demostración se basa en aproximaciones que utilizan fracciones continuas. ^{[ 2 ]}

Dado que ed = 1 (mod λ ( N )) , existe un k tal que ed − kλ ( N ) = 1. Por lo tanto,

${\displaystyle \left|{\frac {e}{\lambda (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\lambda (N)}}}$.

Sea G = mcd( p − 1, q − 1) ; tenga en cuenta que si se usa φ ( N ) en lugar de λ ( N ), entonces la demostración se puede reemplazar con G = 1 y φ ( N ) reemplazado con λ ( N ).

Luego multiplicando por 1 / G ,

${\displaystyle \left|{\frac {e}{\varphi (N)}}-{\frac {k}{Gd}}\right\vert ={\frac {1}{d\varphi (N)}}}$

Por lo tanto, k / Gd es una aproximación de e / φ ( N ) . Aunque el atacante no conoce φ ( N ), puede usar N para aproximarla. En efecto, dado que φ ( N ) = N − p − q + 1 y p + q − 1 < 3 √ N , tenemos:

${\displaystyle \left\vert p+q-1\right\vert <3{\sqrt {N}}}$

${\displaystyle \left\vert N-\varphi (N)\right\vert <3{\sqrt {N}}}$

Sustituyendo φ ( N ) por N obtenemos:

${\displaystyle {\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert &=\left\vert {\frac {edG-kN}{NGd}}\right\vert \\&=\left\vert {\frac {edG-k\varphi (N)-kN+k\varphi (N)}{NGd}}\right\vert \\&=\left\vert {\frac {1-k(N-\varphi (N))}{NGd}}\right\vert \\&<\left\vert {\frac {-k(N-\varphi (N))}{NGd}}\right\vert (\porque 0<|N-\varphi (N)|)\\&<\left\vert {\frac {3k{\sqrt {N}}}{NGd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}Gd}}\leq {\frac {3k}{d{\sqrt {N}}}}\end{aligned}}}$

Ahora bien, kλ ( N ) = ed − 1 < ed , por lo que kλ ( N ) < ed . Dado que e < λ ( N ) , entonces kλ ( N ) < ed < λ ( N ) d , obtenemos:

${\displaystyle k\lambda (N)<\lambda (N)d}$

${\displaystyle k<d}$

Dado que k < d y d < 1/3 N 1/4 . Por lo tanto , obtenemos ^:

(1)${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {1}{dN^{\frac {1}{4}}}}}$

Dado ^que d < 1/3 N 1/4 , 2d < 3d , entonces 2d < 3d < N ^1/4 , obtenemos :​​

${\displaystyle 2d<N^{1/4}}$, entonces (2)${\displaystyle {\frac {1}{2d}}>{\frac {1}{N^{1/4}}}}$

De (1) y (2), podemos concluir que

${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2}}}}$

Si | x − ⁠ a / b ⁠ | < ⁠ 1 / 2 b ² ⁠ , entonces ⁠ a / b ⁠ es una convergente de x , por lo tanto ⁠ k / Gd ⁠ aparece entre las convergentes de ⁠ e / N ⁠ . Por consiguiente, el algoritmo encontrará finalmente ⁠ k / Gd ⁠ .

• Coppersmith, Don (1996). RSA de exponente bajo con mensajes relacionados. Springer-Verlag Berlín Heidelberg.

• Dujella, Andrej (2004). "Fracciones continuas y RSA con exponente secreto pequeño". arXiv : cs/0402052 .
• Implementación en Python del ataque de Wiener.
• R. Stinson, Douglas (2002). Teoría y práctica de la criptografía (2.ª  ed.). A CRC Press Company. pp. 200–204 . ISBN  1-58488-206-9.