Criptografia em poucas equações

Criptografando e descriptografando...

Suponha que você, por motivos particulares, queira receber secretamente o dia que foi agendada a sua consulta médica.

Primeiro você manda as chaves públicas para seu médico. São duas. Por exemplo, mande n = 15, e = 3.
Seu médico pega a data (t), por exemplo, dia 13, e calcula o número secreto (c) com:

c = (t^e) mod n
(sendo mod simplesmente o resto da divisão de t^e por n)
t^e = 13^3 = 2197
2197/n = 2197/15 = 146 e resto 7.
Logo, c = 7.

Então seu médico manda o número 7 para você!

Você recebe o número e vai descriptografar. Para isso você precisa da sua chave secreta que só você tem, neste caso d = 11. Você tem o número secreto (c) e quer achar o dia (t).

t = (c^d) mod n
c^d = 7^11 = 1977326743
1977326743/n = 1977326743/15 = 131821782 e resto 13
t = 13!!!

Fácil, não? Agora vamos ver como achar as chaves n, e e d.

Encontrando as chaves...

Primeiro, você precisa de um n (chamado de módulo público) tal que n>t. Para isso escolha dois números primos tal que n=p*q.

No nosso exemplo, foi usado p=3, q=5. Logo, n=3*5=15. Detalhe, como n=15, o médico só consegue criptografar números de 1 a 14! Para o dia do mês, melhor escolher os primos 5 e 7, n=5*7=35.

Agora calcule o e (chamado de expoente público). Antes, calcule m=(p-1)*(q-1), também chamado de phi. No nosso caso m=(3-1)*(5-1)=2*4=8. O e é um número qualquer, tal que m não é divisível por e (ou se preferir, o MDC - máximo divisor comum - entre eles é 1, ou ainda, e e m são co-primos), também 1 < e <m.

No nosso caso, e=3 não tem fatores em comum com m=8. Outros números que poderiam ser usados são 5 e 7. Não precisa ser primo.

Achou e e n. Falta achar d, que é a inversão modular. Para achar d, simplesmente encontre um valor qualquer tal que (d*e) mod m = 1 (ou se preferir, d= (1/e) mod m. Também 1 < d < m, e claro, você quer d diferente de e.
No nosso caso, d=11, isto é, existe um inteiro k tal que d = (1 +km)/e = (1 + 4*8)/3 = 33/3 = 11, ou se preferir, (d*e) mod m = 1, (11*3) mod 8 = 33 mod 8 = 4 e sobra resto 1.
Agora que tem todos os números, publique as chaves n (módulo público) e e (expoente público). Guarde a chave secreta d (expoente secreto).

Recomendações:

A seguir, recomendações que não invalidam matematicamente a equação, mas que se não forem seguidas permitem quebrar a criptografia mais facilmente.

1. p e q devem ser números de tamanho parecido em bits.
2. p e q devem ser grandes (digo, grandes mesmo).
3. p e q não devem ser próximos, ou seja, p-q deve ser grande.
4. Para ter uma chave de 1024 bits, p e q devem ter 512 bits.
5. e pode ser pequeno, mas não muito pequeno. Números pequenos ajudam na velocidade de encriptação. Mas pelo menos e>65537 é um começo popular para buscar o valor de e.
6. d deve ser mais ou menos do tamanho de n.
7. Se precisar de segurança por mais tempo, use chaves de 2048 bits.
8. Se a mensagem a ser criptografada for muito curta, aumente-a com texto aleatório.
9. Se for enviar a mesma mensagem para diversos receptores, faça pequenas alterações aleatórias em cada mensagem.

Tamanho: um número de bits por dígitos
bits | dígitos
 512 |  154
1024 |  308
2048 |  616

Outro exemplo:

Suponha que escolhemos os primos:
p = 5
q = 7
Agora:
n = p*q = 35
m = (p-1)*(q-1) = 24
Achar e, sem fatores em comum com m:
m = 2 * 2 * 2 * 3
e = 5
Achar d = (1+km)/e = (1 + k*24)/5, para k=1 temos:
d = (1 + 24)/5 = 25/5
d = 5
Mas não está bom, pois achamos d = e! Vamos achar outro d. Para k = 6 temos:
d = (1 + 6*24)/5 = (1 + 144)/5 = 145/5
d = 29
Agora sim!

Públicos: n=35, e=5
Secreto: d=29

Criptografando: 

Supondo que o dia seja t=11, temos:
c = t^e mod n = 11^5 mod 35 = 161051 mod 35 = 40601 e resto 16
Logo, c = 16

Descriptografando:

Recebemos a mensagem secreta c = 16, temos:
t = c^d mod n = 16^29 mod 35 = 83076749736557242056487941267521536 mod 35 = 2373621421044492630185369750500615 e resto 11
Logo voltamos a t = 11