Cómo funciona RSA:
1. Generación de claves:
*Elija dos números primos distintos, *p *y *q *. Cuanto más grandes son, más seguro es el cifrado.
* Calcule * n =p * q *. * N* es el módulo.
* Calcule φ (n) =(p-1) (q-1). Esta es la función total de Euler, que representa el número de enteros menos que *n *que son relativamente primos para *n *.
* Elija un entero * E * (exponente público) de modo que 1 <* e * <φ (n) y GCD (e, φ (n)) =1 (el mayor divisor común es 1; * e * y φ (n) son coprimi). Una elección común es 65537 (2
* Calcule * d * (exponente privado) de modo que * d * * e ≡ 1 (mod φ (n)). Esto significa * d * * * e * deja un resto de 1 cuando se divide por φ (n). Esto generalmente se realiza utilizando el algoritmo euclidiano extendido.
2. Clave pública: La clave pública es el par (*n*,*e*). Esto se comparte públicamente.
3. Clave privada: La clave privada es el par (*n*,*d*). Esto debe mantenerse en secreto.
4. Cifrado: Para cifrar un mensaje *m *(representado como un número menor que *n *):
* CIPHERTEXT * C * =* M
5. Decryto: Para descifrar el texto cifrado *C *:
* Texto de formación * m * =* c
Por qué funciona: El teorema de Euler establece que si *a *y *n *son Coprime, entonces *a
φ (n)
≡ 1 (mod n)*. La elección de * d * y la aritmética modular aseguran que el descifrado recupere correctamente el mensaje original. Breaking RSA se basa en Factoring *N *en *P *y *Q *, que es computacionalmente infalible para primos suficientemente grandes.
Resolver RSA Numéricos:
La dificultad de resolver problemas numéricos RSA depende de qué información se proporcione. Aquí hay ejemplos de problemas típicos y cómo resolverlos:
Ejemplo 1:Cifrado
* Problema: Dado * p * =11, * q * =13, * e * =7, y mensaje * m * =5, cifre el mensaje.
* Solución:
1. Calcule * n * =* p * * * q * =11 * 13 =143
2. Calcule φ (n) =(11-1) (13-1) =120
3. Verifique que GCD (7, 120) =1 (son Coprime)
4. Encrypt:*c *=*m
* 5
* 78125 ÷ 143 ≈ 546 con un resto de 67
* Por lo tanto, * C * =67
Ejemplo 2:descifrado
* Problema: Dado * p * =11, * q * =3, * e * =7 y textext * c * =10, descifrar el texto cifrado.
* Solución:
1. Calcule * n * =* p * * * q * =11 * 3 =33
2. Calcule φ (n) =(11-1) (3-1) =20
3. Encuentre * d * tal que * d * * * e * ≡ 1 (mod φ (n)) Esto significa 7 * * d * ≡ 1 (mod 20). Puede resolver esto utilizando el algoritmo Euclidiano extendido o por prueba y error. * D * =3 funciona porque (7 * 3) =21 ≡ 1 (mod 20).
4. Decrypt:*m *=*c
* 10
3
=1000
* 1000 ÷ 33 ≈ 30 con un resto de 10
* Por lo tanto, * m * =10
Ejemplo 3:Encontrar D (exponente privado)
Encontrar 'd' a menudo requiere el algoritmo euclidiano extendido, que está más allá del alcance de una explicación simple aquí. Sin embargo, para números más pequeños, la prueba y el error pueden funcionar. Estás buscando un número 'D' que satisfaga la congruencia * d * * e ≡ 1 (mod φ (n)).
Consideraciones importantes:
* Números grandes: El RSA del mundo real utiliza números primos extremadamente grandes (cientos o miles de bits). Los cálculos manuales son imposibles; Se requiere un software especializado.
* Aritmética modular: Comprender la aritmética modular es crucial para trabajar con RSA. Muchas calculadoras y lenguajes de programación tienen funciones incorporadas para la exponencia modular.
* Seguridad: La seguridad de RSA depende completamente de la dificultad de factorizar grandes números. A medida que aumenta la potencia informática, el tamaño de los primos utilizados también debe aumentar para mantener la seguridad.
Estos ejemplos ilustran los principios básicos. Para problemas más avanzados, es probable que necesite usar herramientas computacionales y una comprensión más profunda de la teoría de números.