Criptoanálisis RSA

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de junio de 2016; las comprobaciones requieren 8 ediciones .

Este artículo describe las condiciones para usar el criptoalgoritmo de clave pública RSA , que simplifica los ataques criptoanalíticos [1] , y los métodos para eliminar dichas condiciones.

Introducción

A partir de 2009, un sistema de cifrado basado en RSA se considera seguro a partir de 1024 bits. $norte$

Un grupo de científicos de Suiza, Japón, Francia, los Países Bajos, Alemania y los Estados Unidos han computado con éxito datos cifrados con una clave criptográfica RSA de 768 bits. [2] Según los investigadores, después de su trabajo, solo las claves RSA con una longitud de 1024 bits o más pueden considerarse un sistema de encriptación confiable. Además, el cifrado con una clave de 1024 bits debería abandonarse en los próximos tres o cuatro años. [3]

Como se desprende de la descripción del trabajo, el cálculo de los valores clave se llevó a cabo mediante el método general de criba de campos numéricos .

El primer paso (elegir un par de polinomios de grado 6 y 1) llevó aproximadamente medio año de cálculos en 80 procesadores, lo que representó aproximadamente el 3 % del tiempo dedicado a la etapa principal del algoritmo (cribado), que se realizó en cientos de computadoras durante casi dos años. Si interpolamos este tiempo para el funcionamiento de un procesador AMD Opteron de 2,2 GHz con 2 GB de memoria, serían unos 1500 años. Procesar los datos después de tamizarlos para el siguiente paso intensivo en recursos (álgebra lineal) tomó varias semanas en una pequeña cantidad de procesadores. El paso final después de encontrar soluciones OSLU no triviales no tomó más de 12 horas.

La solución OSLU se llevó a cabo utilizando el método de Wiedemann en varios clústeres separados y duró poco menos de 4 meses. Al mismo tiempo, el tamaño de la matriz dispersa era 192 796 550x192 795 550 con 27 795 115 920 elementos distintos de cero (es decir, un promedio de 144 elementos distintos de cero por fila). Se necesitaron alrededor de 105 gigabytes para almacenar la matriz en el disco duro. Al mismo tiempo, se necesitaron alrededor de 5 terabytes de datos comprimidos para construir esta matriz.

Como resultado, el grupo pudo calcular una clave de 232 dígitos que abre el acceso a datos encriptados.

Los investigadores confían en que, utilizando su método de factorización, será posible descifrar una clave RSA de 1024 bits en la próxima década.[ ¿cuándo? ] .

Conociendo la expansión del módulo en el producto de dos números primos, el adversario puede encontrar fácilmente el exponente secreto y así romper RSA. Sin embargo, hasta la fecha, el algoritmo de factorización más rápido es el General Number Field Sieve, cuya velocidad para un entero de k bits es $norte$ ${\ estilo de visualización d}$

$\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k),$ para algunos , $c<2$

no permite descomponer un entero grande en un tiempo razonable. Consideraremos posibles ataques a RSA que nos permitan romper este sistema sin usar una expansión directa del módulo n en el producto de dos números primos.

Ataques elementales

Consideremos varios ataques relacionados con el mal uso del algoritmo RSA.

Generación de números primos

La siguiente restricción adicional se impone a los números primos aleatorios : $pags$ $q$

$pags$ y no deben estar demasiado cerca uno del otro, de lo contrario será posible encontrarlos usando el método de factorización de Fermat . Sin embargo, si ambos números primos se generaron de forma independiente, esta restricción se satisface automáticamente con una gran probabilidad. $q$ $pags$ $q$

Esquema con módulo común n

Datos iniciales: Para evitar generar diferentes módulos para cada usuario, el servidor seguro utiliza un único n para cifrar todos los mensajes. La parte usa este servidor para recibir el mensaje $n=p*q$ $A$ $METRO$

Tarea: el adversario quiere descifrar el mensaje de la parte . $A$

Parecería que un texto cifrado enviado a una parte no puede ser descifrado por la parte a menos que posea la clave secreta . Sin embargo, la parte puede usar sus exponentes para descomponer el módulo , y después de eso, sabiendo , calcular el exponente secreto . $C=M^{e_{a}}\mod n$ $A$ $B$ $d_{a}$ $B$ ${\ estilo de visualización e_ {b}, d_ {b}}$ $norte$ $e_{a}$ $d_{a}$

Protección: cada usuario debe utilizar su propio módulo . $norte$

Ataque a la firma RSA en el régimen notarial

Datos iniciales: - clave pública del notario. El adversario recibe una negativa al intentar firmar un mensaje por un notario $(n, e)$ $M\in \mathbb {Z} _{n}$

Tarea: el adversario quiere obtener la firma del notario en el mensaje . $M\in \mathbb {Z} _{n}$

El adversario elige una arbitraria , calcula y envía este mensaje al notario para su firma. $r\in \mathbb {Z} _{n}$ $M'=r^{e}M\mod n$

Si el notario firma este mensaje:

S'=(M')^{d}\mod n

luego el adversario, habiendo computado , obtiene la firma del mensaje . $S=S'/r\mod n$ $METRO$

En realidad, $S^{e}=(S')^{e}/r^{e}=(M')^{ed}/r^{e}\equiv M'/r^{e}=M (\mod)$

Protección: al firmar, agregue algún número aleatorio (por ejemplo, la hora) al mensaje.

Valores pequeños del exponente secreto

Datos iniciales: Para aumentar la velocidad de descifrado (o creación de una firma digital), se ha reducido el número de bits distintos de cero de la representación binaria del exponente secreto (ver la velocidad del algoritmo RSA ). $d$

Tarea: Calcular el exponente secreto . $d$

En 1990, Michael J. Wiener demostró que en el caso de un valor pequeño , es posible romper el sistema RSA, a saber: $d$

Teorema de Wiener:

Vamos , donde Entonces, si se sabe donde ,

n=pq

{\ estilo de visualización q<p<2q}

d<{\frac{1}{3}}n^{{{\frac{1}{4}}}}

(n, e)

ed=1\mod\varphi (n)

entonces hay una forma eficiente de calcular .

d

Protección: Por lo tanto, si tiene un tamaño de 1024 bits, debe tener al menos 256 bits de longitud. $norte$ $d$

Valores pequeños del exponente abierto

Para aumentar la velocidad de encriptación y verificación de firmas digitales , utilice valores pequeños del exponente abierto . El más pequeño de ellos . Sin embargo, para aumentar la fuerza criptográfica del algoritmo RSA, se recomienda utilizar $mi$ ${\ estilo de visualización e = 3}$

$e=2^{16}+1=65537$ .

Ataque de Khastad

Condiciones iniciales: Parte envía un mensaje encriptado a los usuarios . Cada usuario tiene su propia clave pública y . La parte encripta el mensaje utilizando la clave pública de cada usuario y lo envía al destinatario correspondiente. El adversario escucha el canal de transmisión y recopila los textos cifrados transmitidos. $B$ $METRO$ ${\displaystyle P_{1},P_{2},...P_{k))$ ${\ estilo de visualización (n_ {i}, e_ {i})}$ $M<n_{i},\forall i$ $B$ $k$

Tarea: el adversario quiere recuperar el mensaje . $METRO$

Vamos , entonces el oponente puede recuperarse si . $e_{i}=3,\forall i$ $METRO$ $k \geqslant 3$

Prueba

De hecho, si el oponente recibió , donde ${\ estilo de visualización C_{1},C_{2},C_{3))$

C_{1}=M^{3}\mod n_{1}

{\displaystyle C_{2}=M^{3}\mod n_{2))

C_{3}=M^{3}\mod n_{3}

Suponemos que son coprimos, de lo contrario, el máximo común divisor distinto de uno significaría encontrar un divisor de uno de . Aplicando el teorema del resto chino a , obtenemos , ${\ estilo de visualización n_{1},n_{2},n_{3))$ $norte$ ${\ estilo de visualización C_{1},C_{2},C_{3))$ $C'\in \mathbb {Z} _{n_{1}n_{2}n_{3))$

{\displaystyle C'=M^{3}\mod n_{1}n_{2}n_{3))

Desde entonces _ $M<n_{i},\forall i$ $M^{3}<n_{1}n_{2}n_{3},\forall i$

C'=M^{3}

Es decir, el adversario puede recuperar el mensaje calculando la raíz cúbica de . $METRO$ $C'$

En general, si todos los exponentes abiertos son iguales , el adversario puede recuperarse en . $mi$ $METRO$ $k\geqslant e$

Considere la defensa más simple contra este ataque. Deje que el mensaje para cada usuario sea una permutación fija del mensaje original . Por ejemplo $Mi}$ $METRO$

M_{i}=i2^{m}+M

— mensaje para el i-ésimo usuario.

Hastad (Johan Hastad) demostró que incluso en este caso, el adversario puede recuperar el mensaje con un número suficiente de usuarios. $METRO$

Protección: este ataque solo es posible con un valor pequeño del exponente abierto , en cuyo caso la fuerza criptográfica del sistema RSA se puede lograr usando una permutación arbitraria, y no fija, cuyo ejemplo se dio anteriormente. $mi$

Ataque Franklin-Reiter

Condiciones iniciales :

Hay dos mensajes , y ${\displaystyle M_{1},M_{2}\en \mathbb {Z} _{n))$

M_{1}=f(M_{2})\mod n,

donde es algún polinomio abierto.

f\in \mathbb {Z} _{n}[x]

La parte con la clave pública recibe estos mensajes de la parte , que simplemente cifra los mensajes y transmite los textos cifrados recibidos . $A$ $(n, e)$ $B$ ${\ estilo de visualización M_ {1}, M_ {2}}$ ${\ estilo de visualización C_ {1}, C_ {2}}$

Tarea: El enemigo, sabiendo , quiere restaurar . ${\ estilo de visualización (n, e, C_ {1}, C_ {2}, f)}$ ${\ estilo de visualización M_ {1}, M_ {2}}$

Matthew K. Franklin y Michael K. Reiter demostraron la siguiente afirmación:

Dejar 1) es la clave pública del sistema RSA, y 2) y ,

(n, e)

{\ estilo de visualización e = 3}

{\displaystyle M_{1}\neq M_{2}\in \mathbb {Z} _{n))

M_{1}=f(M_{2})\mod N

para algún polinomio lineal , Entonces, sabiendo , el oponente puede recuperar

f=ax+b\in \mathbb {Z} _{n}[x]

b\neq 0

{\ estilo de visualización (n, e, C_ {1}, C_ {2}, f)}

{\ estilo de visualización M_ {1}, M_ {2}}

Prueba

De hecho, para un arbitrario : $mi$

$C_{1}={M^{e}}_{1}\mod n~~~~\rightarrow ~~~~M_{2}$ , es la raíz del polinomio

g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{n}[x]

pero, también es raíz del polinomio $M_{2}$

g_{2}(x)=x^{e}-C_{2}\in \mathbb {Z} _{n}[x]

Así divide ambos polinomios. Y el adversario puede usar el algoritmo de Euclides para calcular el GCD . Si el resultado resulta ser un polinomio lineal, entonces se encontrará. ${\ estilo de visualización (x-M_ {2})}$ ${\ estilo de visualización (g_{1},g_{2})}$ $M_{2}$

Cuando , gcd es un polinomio lineal y, por lo tanto, el adversario puede calcular mensajes de manera eficiente . ${\ estilo de visualización e = 3}$ ${\ estilo de visualización (g_{1},g_{2})}$ ${\ estilo de visualización M_ {1}, M_ {2}}$

Protección: cuando el tiempo para crackear el sistema RSA es proporcional a , por lo que este ataque solo puede usarse con valores pequeños del exponente abierto. ${\ estilo de visualización e> 3}$ ${\ estilo de visualización e ^ {2}}$

Ataque a un exponente secreto parcialmente conocido

Condiciones iniciales :

El adversario conoce parte de la representación binaria del exponente secreto . $d$

Tarea: restaurar . $d$

Resulta que:

Sea la clave secreta del sistema RSA, donde es el tamaño de los bits.

{\ estilo de visualización (n, d)}

n=pq

{\ estilo de visualización \ eta}

Entonces, conociendo los bits menos significativos del número , el adversario puede recuperarse en un tiempo proporcional a

{\ estilo de visualización \ eta / 4}

d

{\ estilo de visualización d}

e\log _{2}e

La posibilidad de descifrar el sistema RSA en el caso de que el exponente abierto sea pequeño también es obvia a partir del siguiente razonamiento: $mi$

de la definición y :

mi

d

ed-k\varphi (n)=ed-k(np-q+1)=1

Ya que, es obvio .

{\ estilo de visualización d <\ varphi (n)}

0<k\leqslant e

Dado un valor dado , el adversario puede calcular fácilmente

k

{\hat {d}}={\mathcal {b}}(kn+1)/e{\mathcal {c}}

entonces en

{\ estilo de visualización q<p<2q}

|{\hat {d}}-d|\leqslant k(p+q)/e\leqslant 3k{\sqrt {n}}/e<3{\sqrt {n}}

Por lo tanto, es una buena aproximación para .

{\ estilo de visualización {\ sombrero {d))}

d

Como solo son posibles valores distintos , el adversario puede construir una serie que contenga términos para los cuales la representación binaria de uno de sus elementos sea la misma que la mitad superior de la representación binaria del exponente secreto .

mi

k

mi

d

Protección: aumento de exponente abierto . $mi$

Ataque con una computadora cuántica

Con la ayuda de una computadora cuántica , si se construye, será posible descifrar RSA, ya que el algoritmo cuántico de Shor permite la factorización de grandes números en un tiempo bastante corto. Al descomponer el módulo n en factores primos (esto se puede hacer en el tiempo usando O (log n ) Q-bits lógicos ), se puede calcular el exponente secreto d. ${\textstyle {O(\log ^{2}n\log ^{3}(\log n))))$

Ataques relacionados con la implementación del sistema RSA

Ataque en tiempo de ejecución

Condiciones iniciales:

Considere una tarjeta inteligente cuyo microprocesador firma mensajes utilizando una clave privada RSA incrustada.

Objetivo: El enemigo quiere obtener un exponente secreto . $d$

Paul Kocher propuso un ataque basado en mediciones de alta precisión del tiempo que tarda el codificador de tarjetas inteligentes en realizar ciertas operaciones. Consideremos este ataque en el ejemplo del sistema RSA usando el algoritmo de exponenciación rápida :

El adversario obtiene firmas de tarjetas inteligentes para una gran cantidad de mensajes aleatorios y mide el tiempo que tarda en generar sus firmas . ${\displaystyle M_{1},M_{2},\dots,M_{k}\en \mathbb {Z} _{n))$ $T_{yo}$

Durante el ataque, el valor del exponente secreto se restaura poco a poco, comenzando por el bit menos significativo: $d$

$d$ extraño, por lo tanto . ${\ estilo de visualización d_ {0} = 1}$
si entonces el microprocesador de la tarjeta inteligente necesita realizar tres multiplicaciones de módulo , a diferencia de las dos necesarias cuando (ver algoritmo de exponenciación rápida ). Denotemos el tiempo de cálculo del procesador para el mensaje . ${\ estilo de visualización d_ {1} = 1}$ $norte$ ${\ estilo de visualización d_ {1} = 0}$ $t_{yo}$ $Mi}$

Kocher demostró que cuando dos conjuntos y se correlacionan . Sin embargo, en caso de que sean independientes. Así, recurriendo al análisis de correlación , el adversario puede determinar .

{\ estilo de visualización d_ {1} = 1}

{\mathcal {f}}t_{i}{\mathcal {g}}

{\mathcal {f}}T_{i}{\mathcal {g}}

{\ estilo de visualización d_ {1} = 0}

d_{1}

puede definirse de manera similar . ${\ estilo de visualización d_ {2}, d_ {3}, \ puntos}$

Tenga en cuenta que en el caso de un exponente abierto pequeño , se puede aplicar un ataque a un exponente secreto parcialmente abierto . En este caso, es suficiente recuperar la mitad de los bits del exponente secreto . $mi$ $d$

Seguridad: se debe agregar un retraso apropiado para que cada paso del algoritmo de exponenciación rápida tome un período de tiempo fijo.

Ataque de falla de implementación de hardware RSA

Condiciones iniciales:

Considere una tarjeta inteligente cuyo microprocesador firma mensajes utilizando una clave privada RSA incrustada. El microprocesador de la tarjeta utiliza el teorema chino del resto para acelerar el proceso de firma. El adversario está tratando de provocar un mal funcionamiento en los cálculos del microprocesador.

Tarea: el adversario quiere calcular el módulo . $norte$

El uso del teorema chino del resto aumenta la velocidad de creación de una firma digital.

En efecto, al calcular

\sigma _{p}=M^{d_{p}}\mod p

, dónde

d_{p}=d\mod (p-1)~~~~(a)

{\ estilo de visualización \ sigma _ {q} = M ^ {d_ {q}} \ mod q}

, dónde

d_{q}=d\mod (q-1)~~~~(b)

puedes obtener una firma

\sigma =T_{1}\sigma _{p}+T_{2}\sigma _{q}({\bmod {n)))

, dónde

T_{1}={\mathcal {f}}1\mod p,0\mod q{\mathcal {g}}

T_{2}={\mathcal {f}}0\mod p,1\mod q{\mathcal {g}}

Obviamente, los cálculos son mucho más rápidos que el módulo de exponenciación .

{\ estilo de visualización (a), (b)}

norte

Deje que las acciones del enemigo causen una falla, lo que resultará en un defecto en un bit de la firma. Entonces al menos uno de o se calcula incorrectamente. Supongamos que el defecto está contenido en . ${\ estilo de visualización \ sigma _ {p}}$ ${\ estilo de visualización \ sigma _ {q}}$ ${\ Displaystyle {\ sombrero {\ sigma _ {q}}}}$

En este caso

{\sombrero {\sigma ^{e))}\neq M\mod n

{\sombrero {\sigma ^{e))}\neq M\mod q

pero

{\sombrero {\sigma ^{e))}=M\mod p

Así, el adversario puede encontrar la descomposición como resultado de la búsqueda GCD . $norte$ ${\ estilo de visualización (n, {\ sombrero {\ sigma _ {e))}-m)}$

Proteccion:

al firmar, agregue algún número aleatorio al mensaje (por ejemplo, la hora).
comprobar la firma antes de enviarlo.

Vulnerabilidad en procesadores AMD

En 2021, un equipo de investigadores que incluía a la Universidad Tecnológica de Graz , el Instituto Tecnológico de Georgia y Lamarr Security Research, un centro de investigación sin fines de lucro, utilizó la vulnerabilidad SMT [4] en los procesadores AMD con arquitecturas Zen , Zen 2 y Zen 3 para " crackear" la clave de cifrado RSA -4096 [5] [6] .

Notas

↑ Yang S. Y. Criptoanálisis de RSA. - M.-Izhevsk: Centro de investigación "Dinámica regular y caótica", Instituto de investigación informática de Izhevsk, 2011. - 312 p.
↑ Anuncio de factorización de RSA-768 Archivado el 13 de abril de 2014 en Wayback Machine .
↑ Factorización de RSA-768 Archivado el 13 de diciembre de 2012 en Wayback Machine .
↑ SQUIP: Explotación del PDF del canal lateral de contención de la cola del programador
↑ Antón Shilov. Nueva vulnerabilidad afecta a todas las CPU AMD Zen: es posible que sea necesario desactivar el subprocesamiento . Hardware de Tom (11 de agosto de 2022). Recuperado: 12 Agosto 2022.
↑ Vladímir Fetisov. Resultó que la tecnología SMT en los procesadores Ryzen y EPYC te permite robar datos confidenciales . 3DNoticias (11 de agosto de 2022). Recuperado: 12 Agosto 2022. (Ruso)