El ataque de Wiener

Ataque criptográfico al sistema RSA

El ataque de Wiener , llamado así en honor al criptólogo Michael J. Wiener, es un tipo de ataque criptográfico contra RSA . El ataque utiliza el método de fracción continua para exponer la clave privada d cuando d es pequeña.

Antecedentes sobre RSA

Los personajes de ficción Alice y Bob son personas que quieren comunicarse de forma segura. Más específicamente, Alice quiere enviarle un mensaje a Bob que solo Bob pueda 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 los mensajes dirigidos a 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 multiplicativo grupo ( Z ‍ / ‍ N Z ) ^× , 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 sólo 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 pequeño teorema de Fermat ) .

Usando 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 utilizar 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 es válido para valores pequeños de d . Wiener ha demostrado que el atacante puede encontrar d eficientemente cuando d <1/3 N ^1/4 . ^[2]

El artículo de Wiener también presenta 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 algo grande de k . Cuando e ′ es lo 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 .

Usando 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í no lo es, entonces un descifrado rápido de C se puede hacer 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 ^{[3] .}

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 GRAMO = mcd( p − 1, q − 1) .

Dado que ed ≡ 1 (mod λ ( N ) , existe un número 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 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/pqes un poco más pequeño quek/dgy el primero se compone íntegramente de información pública . Sin embargo, aún se requiere un método para verificar ^{[ se necesita aclaración ] y adivinar.}

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

teorema de wiener

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 eficientemente . ^{[2] [ verificación fallida ]}

Ejemplo

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 tratamos de encontrar la expansión en fracciones continuas demi/norte. Tenga en cuenta que este algoritmo encuentra fracciones en sus términos más bajos. Lo sabemos

${\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 la expansión continua de las fracciones demi/norte, todos convergentesk/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, la convergencia1/5rendimientos

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

luego 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}$.

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

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

Prueba del teorema de Wiener

La prueba se basa en aproximaciones que utilizan fracciones continuas. ^{[2] [4]}

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 prueba se puede reemplazar con G = 1 y φ ( N ) reemplazada por λ ( N ).

Luego multiplicando por1/GRAMO,

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

Por eso,k/Dioses una aproximación demi/φ ( norte ). Aunque el atacante no conoce φ ( N ), puede utilizar 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}}}$

Usando 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 , entonces kλ ( N ) < ed . Dado que e < λ ( N ) , entonces kλ ( N ) < ed < λ ( N ) d , entonces 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}}}}}$

Desde d <1/3 N ^1/4 , 2 d < 3 d , luego 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/2 b ², entoncesa/bes convergente de x , por lo tantok/Diosaparece entre los convergentes demi/norte. Por lo tanto, el algoritmo eventualmente encontrarák/Dios. ^{[ Se necesita más explicación ]}

Referencias

1. L. Render, Elaine (2007). El ataque de Wiener a los exponentes secretos breves. ^{[ enlace muerto ]}
2. Boneh, Dan (1999). Veinte años de ataques al Criptosistema RSA. Avisos de la Sociedad Estadounidense de Matemáticas (AMS) 46 (2).
3. Cui, Xiao-lei (2005). Ataques al criptosistema RSA.
4. Salah, Imad Khaled; Darwish, Abdullah; Oqeili, Saleh (2006). "Ataques matemáticos al criptosistema RSA" (PDF) . Revista de Ciencias de la Computación . 2 (8): 665–671. doi :10.3844/jcssp.2006.665.671.

Otras lecturas

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

• Dujella, Andrej (2004). Fracciones continuas y RSA con exponente secreto pequeño.
• Wiener, Michael J. (1990). "Criptoanálisis de exponentes secretos RSA cortos" . Transacciones sobre teoría de la información . 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 (2e ed.). Una empresa de prensa CRC. págs. 200-204. ISBN 1-58488-206-9.