Criptografía RSA

La criptografía RSA es un método mediante el cual dos partes pueden compartir información de forma segura sin tener que intercambiar ningún "código secreto" que permitiera a un atacante comprometer la seguridad. El proceso gira en torno a elegir dos números primos, p y q, que se utilizan para calcular claves públicas y privadas. La clave pública se utiliza para cifrar un mensaje, pero es inútil para descifrarlo.

Tu tarea es crear dos funciones:

Cifrado

RSA_encrypt(txt, n, k) ➞ ctxt

txt es el texto plano que se va a cifrar. Los dos números n y k son la clave pública. ctxt es el texto cifrado.

Como el algoritmo solo funciona con números, txt es en realidad un número formado al concatenar los valores ASCII de las letras mayúsculas del mensaje. Por ejemplo, "cab" se representaría como 676566 (ord("C")==67). Durante el descifrado, el proceso se invertiría para recuperar las letras.

Descifrado

RSA_decrypt(ctxt, p, q) ➞ txt

ctxt es el texto cifrado (en realidad, un número). p y q son los primos mencionados anteriormente.

El recurso que he elegido, "The RSA Algorithm Explained Using Simple Pencil and Paper Method", debería darte suficiente información para crear estas dos funciones. Verás que, al determinar el valor de k, hay varias opciones disponibles. Para los fines de este desafío, debes elegir el valor más pequeño posible de k, tal como se hizo en el recurso.

Ejemplos

RSA_encrypt("bad",891877236769,5) ➞ 493825093669
RSA_decrypt(493825093669,900007,990967) ➞ "BAD"

RSA_encrypt("bad boy",5664239440446477941, 7) ➞ 605656648845318147
RSA_decrypt(605656648845318147,3255706151,1739788291) ➞ "BAD BOY"

Notas

• Puede resultarte difícil determinar el valor de la clave privada, j, cuando p y q son grandes. Matemáticamente hablando, j es el inverso modular de k(mod z).
• Consulta los Recursos añadidos.