Conceptos básicos de criptografía (3): cifrado asimétrico (principio del algoritmo RSA)

El cifrado y el descifrado utilizan dos claves diferentes. Este algoritmo se denomina cifrado asimétrico. El cifrado asimétrico también se denomina cifrado de clave pública y RSA es solo un tipo de cifrado de clave pública.

Hay firmas en la vida real y firmas en Internet. La firma tiene dos funciones, una es la verificación de identidad y la otra es la verificación de la integridad de los datos. Las firmas digitales utilizan un algoritmo de resumen para garantizar que los datos recibidos no hayan sido manipulados y luego los cifran con la clave privada del firmante, que solo se puede descifrar utilizando la clave pública correspondiente para garantizar la coherencia de la identidad.

Un certificado digital se genera juntando información personal y una firma digital y cifrándola con la clave privada de la CA. Por supuesto, un certificado que está firmado por sí mismo sin pasar por la organización de CA se denomina certificado autofirmado. Como institución básica en el sistema de criptografía de Internet, la institución CA tiene capacidades de prevención de seguridad muy avanzadas. La suposición o premisa básica de todos los sistemas de certificados es que la clave privada de la institución CA no será robada una vez que algo le suceda a la CA J. institución, toda la cadena de información se perderá de nuevo.

El proceso de generación del certificado de CA es el siguiente:

El proceso de participación del certificado en la transmisión de información para completar el cifrado y descifrado es el siguiente:

Prime recíproco relación: Primo recíproco es sólo el denominador común. Dos números enteros de 1, 1 y 1 son primos relativos, pero 13 y 13 no son primos relativos.

Función de Euler: representa cualquier entero positivo n dado, entre los enteros positivos menores o iguales a n, cuantos de ellos forman una relación coprimo con n, su expresión es:

Entre ellos, si P es un número primo, su expresión se puede abreviar como:

Caso 1: φ(1)=1

1 y cualquier número son primos relativos, entonces φ ( 1)=1;

Caso 2: n es un número primo, φ(n)=n-1

Debido a que n es un número primo, todos los números más pequeños que él mismo son relación coprimo, entonces φ(n)=n-1;

Caso 3: Si n es una determinada potencia de un número primo, es decir, n = p^k (p es un número primo, k es un número entero mayor o igual a 1 ), entonces φ(n)=(p-1)p^(k-1)

Debido a que p es un número primo, excepto los múltiplos de p, todos los números menores que n son números primos de n

Caso 4: Si n se puede descomponer en el producto de dos enteros primos relativos, n = p1 × p2, entonces φ(n) = φ(p1p2) = φ(p1)φ(p2)

Caso 5: Basado en el caso 4, si p1 y p2 son números primos y n=p1 × p2, entonces φ(n) = φ(p1p2) = φ(p1)φ(p2)=( p1-1)(p2-1)

El principio básico del algoritmo RSA es el quinto caso de la función de Euler, es decir: φ(n) =(p1-1)(p2-1)

Si dos números enteros positivos a y n son primos relativos, entonces el número entero b se puede encontrar de modo que ab-1 sea divisible por n, o el resto. de ab dividido por n es 1. En este momento, b se denomina "elemento módulo negativo" de a. El teorema de Euler se puede utilizar para demostrar que deben existir elementos modulares inversos.

Se puede observar que la potencia φ(n)-1 de a es el elemento inverso de un módulo n.

n=p

/p>

Debido a que n, p y q son todos números primos, φ(n) = (p-1)(q-1)=60×52= 3120

Nota ¡Que aquí está la suma φ (n) es mutuamente prima en lugar de n! Supongamos que el valor seleccionado es 17, es decir, e=17;

El elemento inverso modular significa que hay un número entero d que puede hacer que el resto de ed dividido por φ(n) sea 1. Expresado como: (ed-1)=φ(n) y --gt; 17d=3120y 1, un conjunto de soluciones se calcula como (2753, 15), es decir, d=2753, y=-15, es decir , (17 2753-1)/3120=15.

Tenga en cuenta que 3119 no se puede seleccionar aquí; de lo contrario, las claves pública y privada serán las mismas

Clave pública: (n, e)=(3233, 2753)

Clave privada: (n, e) = (3233, 2753) n, d) = (3233, 17)

La clave pública es pública, es decir, m=p*q =3233 es público, entonces, ¿cómo encontrar e? e se obtiene mediante la función inversa modular, 17d = 3120y 1, y e es públicamente igual a 17. En este momento, si quieres preguntar por d, necesitas saber 3120, que es φ (n), que es φ (3233). Para decirlo sin rodeos, 3233 es públicamente hablando, si puedes factorizar 3233, puedes saber d y puedes descifrar la clave privada.

En circunstancias normales, podemos factorizar 3233 en 61*53, pero para números muy grandes, los humanos solo pueden factorizarlos mediante enumeración, por lo que la esencia de la seguridad RSA es: antipolar La dificultad de factorizar números enteros grandes determina la confiabilidad del algoritmo RSA. En otras palabras, cuanto más difícil sea factorizar un número entero muy grande, más fiable será el algoritmo RSA.

El número entero más grande que los humanos han factorizado es:

El número entero más grande que los humanos han factorizado es de 232 dígitos decimales y 768 dígitos binarios. No existe una factorización más grande que este. informó, por lo que la clave RSA más larga que se ha descifrado hasta ahora es de 768 bits. Por lo tanto, la clave secreta de 1024 bits en el uso real es básicamente segura y la clave secreta de 2048 bits es absolutamente segura.

Hay un chiste en Internet:

Se ha obtenido la composición de las claves pública y privada:

Clave pública: (n, e) = (3233, 2753)

Clave privada: (n, d)=(3233, 17)

El proceso de cifrado es

El proceso de descifrado es el siguiente :

Donde m es el número a cifrar, c es el resultado de salida después del cifrado y m lt , se puede demostrar que se debe establecer el proceso de descifrado y aquí se omite el proceso de prueba; .

En resumen, el cifrado RSA consiste en utilizar la función inversa modular para cifrar y resolver números. En el uso real, debido a que se debe establecer m lt, existen dos métodos de cifrado:

<. p> Aunque el cifrado simétrico es rápido, tiene la desventaja fatal de que es necesario transmitir la clave secreta. Aunque el cifrado asimétrico puede completar el cifrado y descifrado sin transferir la clave secreta, su desventaja fatal es que no es lo suficientemente rápido y no se puede utilizar en escenarios de cifrado de alta frecuencia y alta capacidad.

Es por eso que existe una relación complementaria entre los dos. Se utiliza el cifrado asimétrico al transmitir la clave secreta del cifrado simétrico, y el cifrado simétrico se utiliza una vez completada la transmisión de la clave, para que puedan complementarse perfectamente.