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.