Detalhes

Categoria: Chave Pública

Atualização: Domingo, 14 Junho 2009 12:10

Autor: vovó Vicki

Acessos: 56060

O RSA é um algoritmo de chave pública idealizado por Ron Rivest, Adi Shamir e Leonard Adleman. O nome do algoritmo deriva das iniciais dos sobrenomes dos autores. Desde 1977, Diffie, Hellman e Merkle são considerados os inventores do conceito do algoritmo assimétrico e, desde 1978, Rivest, Shamir e Adleman são admirados por terem criado a implementação mais perfeita da criptografia de chave pública.

Os bastidores

Ron Rivest

Como era o trio de pesquisadores do Laboratório de Ciência da Computação do MIT em 1976? Ron Rivest é um jovem cientista da computação, dono de uma curiosidade científica insaciável e de uma imensa capacidade de absorver e aplicar novas idéias. Assim que leu o trabalho publicado por Diffie, Hellman e Merkle, ficou obcecado pelo assunto e passou a procurar sem descanso uma função matemática que pudesse transformar a idéia dos três criptólogos num sistema real e viável. Além disso, Rivest acabou "contaminando" um colega, Adi Shamir, também cientista da computação. Shamir, conhecido pelo seu intelecto brilhante, mordeu a isca. Os dois conjecturavam insistentemente à procura de uma cifra assimétrica produzindo teorias mirabolantes que, uma após a outra, eram contestadas pelo terceiro colega, Leonard Adleman. Depois de quase um ano de brainstorming, Adleman, um matemático calmo e detalhista, estava ganhando de mil a zero, pois, até então, todas as sugestões de Rivest e Shamir tinham falhas imperdoáveis.

Adi Shamir

A esperança estava quase se esgotando quando Rivest, no meio de uma noite de insônia, lembrou-se de uma particularidade da matemática. Era muito simples e provavelmente havia tomado conhecimento do assunto quando ainda estava na escola primária: a fatoração. Multiplicar dois números primos é uma questão de segundos mas, se temos apenas o resultado e quisermos encontrar os números primos (fatores) deste resultado, o processo é bem mais demorado. À medida que multiplicamos números primos cada vez maiores, o tempo gasto para fatorar o resultado aumenta exponencialmente. Talvez esta função fosse a resposta tão procurada!

A noite foi definitivamente de insônia. Rivest escreveu até o romper do dia e, logo de manhã, foi procurar seu "advogado do diabo". Adleman, acostumado com as explosões intelectuais do amigo, começou a ler o texto preparando-se para encontrar defeitos. Leu, releu e, para o espanto dos dois, não havia nada para ser contestado. Nascia o primeiro algoritmo de chave pública, a primeira cifra assimétrica perfeitamente acabada.

Leonard Adleman

Mais uma curiosidade: Rivest havia batizado o algoritmo de ARS, colocando as iniciais do sobrenome do trio pesquisador em ordem alfabética. Adleman protestou porque achava que tinha contribuído pouco e porque não via futuro algum na publicação do trabalho. Pediu inclusive que seu nome fosse retirado. Rivest, ciente da importância do papel desempenhado por cada um, pediu que Adleman pensasse melhor no assunto e desse a sua resposta no dia seguinte. Não querendo magoar os amigos, Adleman concordou que seu nome fosse citado em último lugar, motivo pelo qual a cifra foi rebatizada e passou a ser chamada de RSA.

Noções de Aritmética

Os conhecimentos necessários para entender o RSA são básicos. Antes de mais nada, é preciso lembrar que um número primo é um número diferente de 1 que só é divisível exatamente por 1 ou por ele mesmo. Assim, 3 é um número primo porque só tem uma divisão exata quando dividido por 1 ou por 3. Já o número 4 não é primo porque pode ser dividido exatamente por 1, 2 e 4. Se o número 4 não é um número primo, então pode ser fatorado, ou seja, pode-se encontrar os números primos que, multiplicados, resultam em 4 (no caso, 2 x 2).

Existem alguns números conhecidos como primos entre si. Dois números inteiros são ditos primos entre si quando não existir um divisor maior do que 1 que divida ambos. Isto significa que o máximo divisor comum dos primos entre si é igual a 1.

Outro conceito necessário á a aritmética modular. Na aritmética modular não dispomos de uma quantidade infinita de números, mas de um grupo finito deles. O melhor exemplo é o mostrador do relógio que, por sinal, trabalha no módulo 12. Quando o mostrador passa do 12, não tem como mostrar 13 horas porque o conjunto dos números disponíveis vai de 1 a 12. Desta forma, 12 horas + 1 hora = 1 e 9 horas + 8 horas = 5. Costuma-se escrever estas operações da seguinte forma: 12 + 1 = 1 (mod 12) e 9 + 8 = 5 (mod 12).

O modo de se encontrar um resultado modular é dividindo o resultado não modular pelo módulo e considerar o resto. Por exemplo, 9 + 8 = 17 e 17 ÷ 12 = 1 com resto 5. Da mesma forma, 11 x 9 (mod 13) é 11 x 9 = 99 e 99 ÷ 13 = 7 com resto 8, ou seja, 11 x 9 = 8 (mod 13). Podemos complicar um pouco as coisas e considerar uma potenciação. Digamos que a base seja 3 e que este número seja elevado a um número qualquer que chamaremos de x. Para analisar o comportamento da função 3^x (mod 7) acompanhe os resultados obtidos na tabela 1. Na operação normal, os valores encontrados são crescentes. Já na operação modular, os resultados são erráticos e difíceis de predizer.

Pois bem, por mais incrível que possa parecer, para entender a mecânica do algoritmo RSA não é preciso mais do que isto!

A mecânica do algoritmo RSA

Rivest, Shamir e Adleman criaram um função especial que praticamente pode ser considerada unidirecional (ou de mão única). As funções unidirecionais autênticas não têm volta, ou seja, o resultado não pode ser revertido para os valores iniciais. A função do RSA é tão complicada ou tão demorada de ser revertida que, para efeitos práticos, pode ser considerada como uma função de mão única. O algoritmo pode ser dividido em 6 fases, a saber:

1. Escolha de dois números primos gigantes

O destinatário ou dono da chave privada deve escolher dois números primos. Quanto maiores forem estes números, maior será a segurança obtida. Estes números são identificados por p e q e devem ser mantidos em segredo. Para facilitar o acompanhamento do processo, usaremos um exemplo com números primos pequenos: p = 19 e q = 23.

2. Cálculo da chave pública

Escolhidos os números primos secretos, o destinatário multiplica-os para obter um novo número N, ou seja:

     N = p x q
     N = 19 x 23
     N = 437

A seguir, escolhe um número e que não tenha fatores comuns com (p-1) x (q-1). Isto é o mesmo que dizer que e e (p-1) x ( q-1) precisam ser primos entre si:

     (p-1) x (q-1) = 18 x 22
     (p-1) x (q-1) = 396

Fatorando o resultado 396, obtemos o seguinte (lembra das aulas de aritmética do primeiro grau?):

     396 | 2
     198 | 2
      99 | 3
      33 | 3
      11 | 11
       1 |

     ou seja, 396 = 2 x 2 x 3 x 3 x 11

Para que e e 396 sejam primos entre si, o valor de e não pode ser divisível nem por 2, nem por 3 e nem por 11. Digamos que o número escolhido tenha sido 13.

Estes dois números, N = 437 e e = 13 são a chave pública.