Algoritmos de Chave Pública
RSA
Introdução
• O problema da distribuição de chaves sempre foi
o elo mais fraco da maioria dos sistemas de
criptografia.
• Em 1976, dois pesquisadores da Universidade de
Stanford, Diffie e Hellman propuseram um
sistema de criptografia totalmente novo:
– As chaves de criptografia e decriptografia são
diferentes. Uma pública e a outra privada.
– A chave de decriptografia (privada) não consegue ser
derivada da chave de criptografia (pública).
Proposta
• Cada usuário precisa ter duas chaves: Uma
pública e a outra privada.
• O algoritmo de criptografia E e o algoritmo de
decriptografia D tem de atender a três
requisitos:
– D (E (P)) = P.
– É extremamente difícil deduzir D a partir de E.
– O texto criptografado não pode ser decifrado por
um ataque de texto claro escolhido.
Requisitos
• O primeiro requisito diz que se aplicarmos o
algoritmo D a um texto claro P criptografado por
E obteremos novamente a mensagem em texto
claro.
• O segundo requisito é autoexplicativo.
• O terceiro requisito significa que os intrusos
podem experimentar o algoritmo exaustivamente
que não conseguirão quebrá-lo.
– Logo, não há razão para a chave não tornar-se pública.
Funcionamento do método
• O remetente criptografa uma mensagem
utilizando a chave pública do destinatário.
– A chave pública pode estar:
• Em um arquivo público, por exemplo no web site do
destinatário.
• Em uma Infraestrutura de Chaves Públicas.
• Alice calcula EB (P) e envia para Bob.
• Bob calcula DB (EB (P)) = P
Os pesquisadores
• Três pesquisadores do
MIT.
– Rivest (cientista da
computação),
– Shamir (cientista da
computação) ,
– Adleman (matemático) .
• Examinaram o artigo de
Diffie e Hellman.
• Propuseram entre si, inúmeras soluções durante
o ano.
A solução
• Em abril de 1977.
• Rivest.
– É possível construir uma cifra assimétrica?
– Encontrar uma função de mão única que possa ser
revertida apenas se o receptor possuir alguma
informação especial?
A matemática do RSA (1)
• Alice escolhe dois números primos gigantes, p e
q.
• Os primos devem ser enormes, geralmente de
1024 bits, mas para simplicidade vamos dizer que
Alice escolhe p = 17 e q = 11. Ela mantém esses
números em segredo.
• A seguir, Alice multiplica os números um pelo
outro para conseguir outro número, n.
– p x q = n.
– Logo, n = 187.
A matemática do RSA (2)
• A seguir, calcula também z = (p-1) x (q-1).
– Logo, z = 160.
• Depois, Alice escolhe outro número, e, de modo que
este e z sejam primos relativos. Ou seja, não possuam
fatores comuns.
• Suponha que Alice escolhe e = 7.
– Repetindo, e, (p-1) x (q-1), ou se preferir, e e z, precisam
ser primos relativos, não tendo fatores comuns.
– Observe que temos várias opções: 7, 11, 13, 17, 19
• n e e tornam-se a chave pública de Alice (187 e 7).
Primos relativos
• Os números 8 e 15 são primos relativos
porque os divisores positivos de 8, são:
– 1, 2, 4 e 8.
• E os de 15, são:
– 1, 3, 5 e 15.
• De modo que o 1 é o único inteiro nas duas
listas.
Cálculo da chave privada
• Finalmente, Alice calcula um número d de
forma que d x e = 1 mod z.
• Conforme exemplo abaixo:
Chave Pública
• Alice divulga e e n como sendo a sua chave
pública.
• O e pode ser parte da chave pública de todos,
desde que cada pessoa tenha um n diferente,
o que depende da escolha de p e q.
Restrição ao tamanho do bloco
• Cada bloco de texto claro, P, precisa estar no
intervalo entre 0 ≤ P < n.
• O que pode ser feito agrupando-se o texto
claro em blocos de k bits onde k é o maior
inteiro para o qual a desigualdade 2k < n é
verdadeira.
Criptografando
• Para criptografar são necessários e e n e para
decriptografar, d e n.
• Em outras palavras, para criptografar faça:
C = Pe (mod n)
• Para descriptografar, faça:
P = Cd (mod n).
Convertendo a entrada
• A mensagem a ser cifrada, P, precisa ser
convertida em um número.
– Por exemplo, binários em ASC convertidos para
decimal.
• O número P então é cifrado para produzir C,
de acordo com a fórmula: C = Pe (mod n).
Exemplo
• Supondo que Bob deseje enviar para Alice a letra
“X”.
• Em ASC o X é representado por 1011000 o que
equivale a 88 em decimal. Assim, P = 88.
• Para cifrar a mensagem, Bob pega a chave pública
de Alice, n = 187 e e = 7, o que resulta na
seguinte fórmula: C = 887 (mod 187).
C = 40867559636992 (mod 187)
C = 40867559636992 / 187 = 218543099663 (resto 11).
• Bob agora envia o texto cifrado, C = 11, para
Alice.
Considerações
• Exponenciais em aritmética modular são
funções de mão única.
• É muito difícil, a partir de C = 11, recuperar a
mensagem original, P.
– Logo, Eva não pode decifrar a mensagem.
• Alice pode decifrá-la porque ela tem uma
informação especial.
– Ela conhece os valores de p e q.
Decifrando
• Para decifrar a mensagem, Alice simplesmente
usa a fórmula:
P = Cd (mod 187)
P = 1123 (mod 187)
P = 88
• O que corresponde a letra “X” em ASC.
Exemplo
Sumário da operação
• Suponha que o navegador web possua um texto a ser
transmitido.
• Inicialmente o navegador envia uma solicitação.
– Ola servidor, mande-me a sua chave pública.
• O servidor responde.
– Aqui está: n=187 e e=7.
• Após receber a chave pública do servidor, o navegador
(cliente) criptografa com ela o texto a ser enviado e o
envia.
• Ao receber o texto criptografado, o servidor o
descriptografa com a sua própria chave privada.
Descobrindo o código
• As chaves pública e privada são relacionadas, mas a sua
relação é difícil de ser derivada por terceiros.
• A chave pública possui dois valores, n e k onde k é
calculado a partir de z e z é calculado a partir de p e q.
• A chave privada d é calculada a partir de k e z que são
calculados a partir de p e q.
– Observe a relação matemática entre as chaves.
• Então, para um interceptador encontrar a chave
privada d, a única maneira é determinando quais foram
os números primos usados para determiná-la (p e q).
– Decomposição de números com mais de uma centena de
dígitos.