Exemplo de aplicação do método RSA

Muito se fala do método RSA para criptografia, que utiliza chaves assimétricas.

Eu queria mostrar um exemplo numérico prático, simples, para entendimento do conceito.

Suponha que Alice queira mandar uma mensagem para Bob, utilizando o protocolo RSA.

A regra. Para encriptar uma mensagem “m” (que Alice tem), é necessária uma chave de encriptação “e”, e um grande número “N” (fornecidos por Bob).

O mensagem criptografada “c” é dada por

Por exemplo, com as chaves N = 143, e = 7, Alice quer encriptar a mensagem 14.

c = 14 ^7 mod 143 = 53.

A mensagem encriptada 53 é enviada a Bob.

Para números pequenos, é possível fazer essas contas no Excel. Para números grandes, não é possível, porque esbarra no limite de representação de números inteiros do Excel.

É mais jogo usar o Wolfram Alpha ( https://www.wolframalpha.com/)

Basta digitar 14⁷ mod 143 e teclar Enter.

Para decriptar a mensagem, é necessária uma chave privada d, que apenas Bob tem acesso.

Para N = 143 e e = 7, a chave d é 103.

A operação de decriptação é dada por:

53¹⁰³ mod 143 = 14

Ou seja, a partir da mensagem codificada “53”, chego à mensagem original “14”, a partir da chave “d” e “N” dadas.

O que pode ser facilmente conferido no Wolfram.

Note a conta:

27866250152903255949613700932664192497233760436337513808125157659660832022830419160542997833111266662693511527862300002983908469396426328154756199536698210695663230149227499041×143 + 14

Apesar de 52¹⁰³ ser um número enorme, não é necessário fazer toda essa conta para descobrir o resto. Como é uma função periódica e não preciso saber o coeficiente (só preciso do resto), há atalhos numéricos que fazem o cálculo ser eficiente.

Portanto, preciso de “N”, “d” e “e”.

N = 143 = 11*13

E toda a dificuldade do método baseia-se na assimetria da fatoração. É fácil fazer a multiplicação 11*13, porém, muito mais difícil é encontrar os fatores primos, dado apenas o número 143.

Dos fatores p = 11 e q = 13, calculo r = (p-1)*(q-1) = 10*12 = 120.

Para encontrar a chave “e”, escolho um valor maior igual a 3, e relativamente primo a 120.

Como gcd(7,120) = 1, “e” = 7 é uma chave possível.

Para encontrar “d”, para decodificar, tenho que ter um número que seja o inverso mod N de “e”.

Basta usar o Wolfram novamente, digitar 7^-1 mod 120. O resultado será d = 103.

=======================

Outro exemplo. N = 143, e = 17, d = 113.

Seja a mensagem m = 48.

A mensagem codificada será:

c = 48¹⁷ mod 143 = 16.

A mensagem decodificada será:

m = 16 ^113 mod 143 = 48, exatamente a mensagem original.

=======================

Último exemplo. N = 187 (igual a 11*17), e = 3 e d = 107.

Seja a mensagem m = 72.

A mensagem codificada será:

c = 72³ mod 187 = 183.

A mensagem decodificada será:

m = 183 ^ 107 mod 187 = 72, exatamente a mensagem original.

Originally published at http://informacaoquantica.wordpress.com on March 7, 2021.