El progreso del ataque del algoritmo RSA

Los ataques más populares contra RSA generalmente se basan en la factorización de grandes números. En 1999, RSA-155 (512 bits) se descompuso con éxito, lo que tomó cinco meses (aproximadamente 8000 años MIPS) y 224 horas de CPU para completarse en una computadora Cray C916 con memoria central de 3.2G.

En 2002, también se factorizó con éxito RSA-158.

El 12 de diciembre de 2009, también se descompuso con éxito el número RSA-768 (768 bits, 232 dígitos).

Noticias de la mañana del 15 de febrero de 2013, hora de Beijing. Según el informe del New York Times del martes, matemáticos y criptógrafos europeos y estadounidenses descubrieron accidentalmente que existen lagunas en el algoritmo de cifrado de clave pública RSA. que es ampliamente utilizado en todo el mundo.

Descubrieron que 27.000 claves públicas entre 7 millones de muestras experimentales no se generaron aleatoriamente según la teoría. Es decir, tal vez alguien pueda encontrar el número primo secreto que genera la clave pública.

El proyecto de investigación está liderado por el criptólogo independiente estadounidense James P. Hughes y el matemático holandés Arjen K. Lenstra. Su informe decía: "Descubrimos que la gran mayoría de las claves públicas se generan según la teoría, pero dos de cada mil claves públicas tienen riesgos de seguridad".

Para evitar que alguien explote la vulnerabilidad , la clave pública en cuestión fue eliminada de la base de datos de acceso público. Para garantizar la seguridad del sistema, el sitio web debe realizar cambios en el terminal.

Fórmulas y teoremas

Las sumas de números son mutuamente primos

Cualquier número entero mayor que 1 se puede factorizar en la siguiente forma única:

a=p1p2…pl(p1,p2,…,pl es un número primo)

2. Operación modular

①{[a(mod n)]×[ b(mod n)]}modn≡(a×b)(mod n)

②Si (a×b)=(a×c)(mod n), a y n son primos relativos, entonces

b=c(mod n)

3. Teorema de Fermat

Si p es un número primo y a y p son primos relativos, entonces

a ^(p-1)≡1 (mod p)

IV. Teorema de Euler

La función de Euler φ (n) representa un entero positivo no mayor que n y primo relativo a n número.

Cuando n es un número primo, φ(n)=n-1. Cuando n = pq, p y q son todos números primos, entonces φ (n) = φ (p) φ (q) = (p-1) (q-1).

Para a y n mutuamente primos, existe a^φ(n)≡1(mod n)

Cómo utilizar un programa informático para encontrar a partir de la clave pública e, y φ(n) ¿Obtener la clave privada d?

El problema se puede reducir a encontrar: e *x +φ (n) * y = 1 tipo de ecuación, que se puede resolver usando el algoritmo euclidiano extendido

(La siguiente es la implementación java de este problema) //El ejemplo es la solución de 47?*?x?+?30?*?y?==1? public?static?void?main(String[] ?args){int[]?p?=?new?int[2];int?a?=?47;int?b?=?30;RSA(a, b,p);System.out.print( "p[0]?es:?"?+?p[0]?+?";p[1]?es: "?+?p[1]); //p1 es la clave privada}public?static? int[]?RSA(int?a,int?b,int[]?p)//Asuma aquí a?>?b{if(a%b?== ?1){p[0]?=?1 ;p[1]?=?-(a?-?1)?/?b;return?p;}else{RSA(b,a?%?b, p);int?t?=?p[0 ];p[0]?=?p[1];p[1]?=?t?-?(a?/?b)?*?p[1 ];?retorno?p;}}}