Algoritmo de cifrado y descifrado RSA y descifrado por fuerza bruta de 12 bits
1. Seleccione aleatoriamente dos números primos y reemplácelos con p y q (cuanto mayor sea el valor del número primo, más confiable será el número)
Supongamos que tomamos 47 y 59
p = 47
q = 59
2. Calcula el producto de estos dos números primos y reemplázalo por n
n = 47 x 59 = 2773
La longitud de n es la longitud de la clave. La notación binaria de 2773 es 101011010101 y **** tiene 12 bits, por lo que la clave es de 12 bits. En aplicaciones prácticas, las claves RSA suelen ser de 1024 bits y, en casos importantes, de 2048 bits.
3. Calcular la función de Euler φ(n)
Fórmula de la función de Euler: φ(n) = (p-1)(q-1)
Sustituir : φ(2773) = (47 - 1) x (59 - 1) = 46 x 58 = 2668
4. Seleccione aleatoriamente un número entero e, la condición es 1lt e lt; , y e y φ(n)
son primos relativos, entonces elegimos un entero aleatorio e entre 1 y 2668
e = 17
5. Calcula el elemento inverso d del módulo de e de φ(n)
La fórmula del elemento inverso del módulo: ax ≡ 1 (mod b)
Esta es la derivación del teorema de Euler, que es decir, si a y b son primos relativos, entonces a multiplicado por un número entero es igual a 1. Este número entero es el recíproco del módulo de ay b.
La fórmula se puede escribir como: ax - b = 1 entonces x = (1 b) / a
Sustituir: d = (1 φ(n))/ e = ( 1 2668) / 17 = 157
Este es un número entero, pero en muchos casos, el resultado no es necesariamente un número entero, por lo que para facilitar el cálculo, agregamos un número entero k a la fórmula: x = (1 kb) / a, multiplicar k por b no significa que multipliquemos por b, sino que el resultado no es un número entero. Sumar k por b no afecta el resultado de un resto de 1.
Luego sustituimos: d = (1 kφ(n))/ e = (1 k x 2668) / 23
De esta forma obtenemos una ecuación lineal
Hay muchos puntos de coordenadas (k, d) que pueden resolver (1, 157), (18, 2825), (35, 5493) ....
Seleccionamos un punto al azar: ( 1, 157 )
Es decir: d = 157
6. Encapsule n y e en una clave pública y encapsule n y d en una clave privada
Es decir: La clave pública es: n = 2773, e = 17
La clave privada es: n = 2773, d = 157
¡Eso es! ¡Se generan las claves públicas y privadas RSA de 12 bits!
Supongamos que ciframos un carácter "A"
y lo representamos como un número, generalmente codificado en Unicode o ASCII
Para ASCII decimal 65, usamos m en lugar de texto plano, use c en lugar de texto cifrado
m = 65
Fórmula de cifrado RSA: m e ≡ c (mod n)
La fórmula de generación de clave privada es : n = 2773, d = 157
¡Eso es!
La fórmula de cifrado RSA se deriva de la fórmula de la función de Euler y la fórmula modular inversa
Sustituyendo: c = 65 17 2773 = 601
Esto es lo que ¡Obtén texto secreto!
Fórmula de descifrado RSA: c d ≡ m (mod n)
Fórmula de descifrado RSA derivada de la fórmula de la función de Euler y la fórmula del elemento antimodal
Sustitución ：m = 601 157 2773 = 65
¡De esta manera obtienes el texto plano!
Porque de los seis números p, q, n, φ(n), e y d, la clave pública utiliza dos de ellos (n y e), y los cuatro restantes no se hacen públicos. El más crítico es d, porque n y d constituyen la clave privada. Una vez que se filtra d, significa que se filtra la clave privada.
Se puede ver que para deducir d, p y q deben factorizarse.
En la clave pública, hay n = 2773
Entonces la forma de fuerza bruta la clave es factorizar 2773 y multiplicar los dos números primos.
El método más simple es enumerar repetidamente los productos de números primos:
lt; pregt
var distNum = 2773; var numList = [];
var p = 1;
var q = 1;
for(var i = 1; i lt; 100; i ) {
var isGetResult = false; // Si se encuentra el resultado
var isUseful = true // Si el número es primo
var isHave = false; // Si existe en la lista de números primos
for( var j = 0; j lt; numList.length; j ) {
if(numList[j] = = i) {
isHave = true
break
}
}
for(var k = 2; k lt ; i.k ) {
if(i k == 0) {
esÚtil = false
descanso
}
}
}
if(!isHave amp; isUseful) {
numList.push (i); / Agregar a la lista de números primos
// emparejar el producto
for(var n = 0; n lt; numList.length; n ) {
if(i ! = listanum[n] amp; amp; i * listanum[n] == distNum) {
p = i
q = listanum[n]; /p>
isGetResult = true;
descanso
}
}
} p>
}
console.log(JSON.stringify(numList));
if(isGetResult) {
console.log('p = ' p );
p>
console.log('q = ' q);
break;
}
}
lt; /pregt;
Resultados de ejecución:
La confiabilidad del cifrado RSA se basa en la dificultad computacional de la factorización, pero con el desarrollo de la computación cuántica. y la computación en la nube, ahora se utiliza el RSA de 1024 bits. Incluso el RSA de 2048 bits tiene sus desafíos. Se dice que 40 qubits equivalen a una supercomputadora.
Tus opiniones son lo que puedo mejorar. Los comentarios y sugerencias son bienvenidos. Si te resulta útil, dale me gusta, gracias~~
El tema del front-end de Feimai reúne. Buenos artículos de front-end. ¡Invita tu atención!