Criptografia RSA

A criptografia RSA é um método pelo qual duas partes podem compartilhar informações com segurança sem precisar trocar nenhum "código secreto" que permitiria que um invasor comprometesse a segurança. O processo gira em torno da escolha de dois números primos, p e q, que são usados para calcular chaves públicas e privadas. A chave pública é usada para criptografar uma mensagem, mas é inútil para descriptografá-la.

Sua tarefa é criar duas funções:

Criptografia

RSAEncrypt(txt, n, k) ➞ ctxt

txt é o texto simples a ser criptografado. Os dois números n e k são a chave pública. ctxt é o texto criptografado.

Como o algoritmo funciona apenas com números, txt é, na verdade, um número formado pela concatenação dos valores ASCII das letras maiúsculas da mensagem. Por exemplo, "cab" seria representado como 676566 (ord("C")==67). Durante a descriptografia, o processo seria invertido para recuperar as letras.

Descriptografia

RSADecrypt(ctxt, p, q) ➞ txt

ctxt é o texto criptografado (na verdade, um número). p e q são os primos mencionados anteriormente.

O recurso que escolhi, "The RSA Algorithm Explained Using Simple Pencil and Paper Method", deve fornecer informações suficientes para criar essas duas funções. Você descobrirá que, ao determinar o valor de k, há várias opções disponíveis. Para os fins deste desafio, você deve escolher o menor valor possível de k, como foi feito no recurso.

Exemplos

RSAEncrypt("bad",891877236769,5) ➞ 493825093669
RSADecrypt(493825093669,900007,990967) ➞ "BAD"

RSAEncrypt("bad boy",5664239440446477941, 7) ➞ 605656648845318147
RSADecrypt(605656648845318147,3255706151,1739788291) ➞ "BAD BOY"

Observações

  • Você pode achar difícil determinar o valor da chave privada, j, quando p e q são grandes. Matematicamente falando, j é o inverso modular de k(mod z).
  • Consulte os Recursos adicionados.