El ataque de Wiener

Ataque criptográfico al sistema RSA

El ataque de Wiener , llamado así por el criptólogo Michael J. Wiener, es un tipo de ataque criptográfico contra RSA . El ataque utiliza la representación de fracciones continuas para exponer la clave privada d cuando d es pequeño.

Antecedentes sobre RSA

Los personajes ficticios Alice y Bob son personas que quieren comunicarse de forma segura. Más específicamente, Alice quiere enviar un mensaje a Bob que solo Bob puede leer. Primero Bob elige dos 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 a Bob. El exponente de descifrado d satisface ed ≡ 1 (mod λ ( N )) , donde λ ( N ) denota la función de Carmichael , aunque a veces se utiliza φ ( N ), la función totient de Euler (nota: este es el orden del grupo multiplicativo ( Z ‍ / ‍ N Z ) ^× , que no es necesariamente un grupo cíclico). El exponente de cifrado e y λ ( N ) también deben ser primos entre sí para que haya una inversa 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 está dado por C ≡ M ^e (mod N ) y el descifrado del texto cifrado C está dado por C ^d ≡ ( M ^e ) ^d ≡ M ^ed ≡ M (mod N ) (utilizando el pequeño teorema de Fermat ).

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]

Pequeña clave privada

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 de 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 . ^[2]

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.

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

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

1. Primero calcule M _p ≡ C ^{d _p} (mod p ) y M _q ≡ C ^{d _q} (mod q .
2. Utilice el teorema del resto chino 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 ) según sea necesario. El punto es que el ataque de Wiener no se aplica aquí porque el valor de d mod λ ( N ) puede ser grande. ^{[ cita requerida ]}

Cómo funciona el ataque

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) .

Como 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 = ⁠GRAMO/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}}}$

Entonces, ⁠mi/pq⁠ es un poco más pequeño que ⁠a/escaño⁠ , y el primero se compone enteramente de información pública. Sin embargo, todavía se requiere un método de verificación ^{[ aclaración necesaria ] y de conjeturas.}

Mediante el uso de manipulaciones algebraicas y de identidades simples , se puede comprobar la precisión de una suposición . ^[1]

Teorema de Wiener

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

Dado ⟨ N , e ⟩ con ed ≡ 1 (mod λ ( N )) , el atacante puede recuperar eficientemente d . ^{[2] [ verificación fallida ]}

Ejemplo

Supongamos que las claves públicas son ⟨ N , e ⟩ = ⟨90581, 17993⟩ . El ataque debería determinar d . Al usar el teorema de Wiener y fracciones continuas para aproximar d , primero tratamos de encontrar la expansión en fracciones continuas de ⁠mi/norte⁠ . Nótese que este algoritmo encuentra fracciones en sus términos más bajos. 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]}$

De acuerdo con la expansión de fracciones continuas de ⁠mi/norte⁠ , todos convergentes ⁠a/dson :

${\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 el primer convergente no produce una factorización de N . Sin embargo, el convergente ⁠1/5⁠ rendimientos

${\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}$.

Demostración del teorema de Wiener

La prueba se basa en aproximaciones utilizando fracciones continuas. ^[2]

Como 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) ; note que si se utiliza φ ( N ) en lugar de λ ( N ), entonces la prueba se puede reemplazar con G = 1 y φ ( N ) reemplazado con λ ( N ).

Luego multiplicando por1/GRAMO⁠ ,

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

Por lo tanto ,a/Dios⁠ es una aproximación de ⁠mi/φ ( N )⁠ . Aunque el atacante no conoce φ ( N ), puede usar N para aproximarlo. De hecho, 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}}}$

Utilizando N en lugar de φ ( 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 (\because 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, kλ ( N ) = ed − 1 < ed , por lo que kλ ( N ) < ed . Como e < λ ( N ) , por lo que 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 . De ahí 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 , 2 d < 3 d , entonces 2 d < 3 d < 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/2b2​^​⁠ , entonces ⁠a/b⁠ es un convergente de x , por lo tantoa/Dios⁠ aparece entre los convergentes de ⁠mi/norte⁠ . Por lo tanto, el algoritmo eventualmente encontrará ⁠a/Dios⁠ . ^{[ se necesita más explicación ]}

Referencias

1. L. Render, Elaine (2007). El ataque de Wiener a los exponentes secretos cortos. ^{[ enlace roto ‍ ]}
2. Boneh, Dan (1999). Veinte años de ataques al criptosistema RSA. Avisos de la American Mathematical Society (AMS) 46 (2).

Lectura adicional

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

• Dujella, Andrej (2004). "Fracciones continuas y RSA con exponente secreto pequeño". arXiv : cs/0402052 .
• Wiener, Michael J. (1990). "Criptoanálisis de exponentes secretos RSA cortos" . IEEE Transactions on Information Theory . 36 (3). IEEE : 553–558. doi :10.1109/18.54902 . Consultado el 9 de marzo de 2024 .
• Implementación en Python del ataque de Wiener.
• R. Stinson, Douglas (2002). Teoría y práctica de la criptografía (2.ª edición). Una empresa de CRC Press. Págs. 200–204. ISBN 1-58488-206-9.