Detalhes

Categoria: Assuntos Gerais

Atualização: Quinta, 19 Abril 2012 20:06

Autor: vovó Vicki

Acessos: 15705

Os algoritmos de chave pública representam um grande avanço na criptografia atual. A idéia do primeiro algoritmo do gênero parece ter sido do britânico James Ellis, da Communications Electronic Security Group - CESG, em 1960. Ele revela que se inspirou num texto anônimo escrito no Bell Labs durante a Segunda Guerra Mundial. A Agência Nacional de Segurança dos EUA (National Security Agency - NSA) alega ter inventado a criptografia de chave pública também na década de 1960. Como tanto a CESG, como a NSA, são organizações secretas, estas informações só foram tornadas públicas muitos anos mais tarde.

Na verdade, a criptografia de chave pública ficou conhecida com a atuação de civis. O trabalho pioneiro foi de Ralph Merkle e Martin Hellman, mas o que realmente chamou atenção e causou discussões generalizadas foi o algoritmo criado por Whitfield Diffie e Martin Hellman.

Um pouco de história

Malcom
Williamson

Simon Singh apresenta evidências de que James Ellis, da CESG, foi o primeiro a pensar num sistema de chave pública na década de 1960. Teve apenas a idéia, porém não conseguiu implementar um algoritmo. Em 1973 Ellis descreveu o seu conceito para um colega recém admitido, o matemático Clifford Cocks, que conseguiu chegar numa solução que, basicamente, é a mesma do RSA. Em 1974, outro colega de Ellis, Malcom Williamson, criou uma segunda alternativa, esta muito parecida com a solução de Diffie e Hellman.

Merkle, Hellman e Diffie em 1977
(da esquerda para a direita)

Em 1976, Ralph Merkle, hoje um especialista em nanotecnologia de renome internacional, e Martin Hellman, criaram o primeiro algoritmo de chave pública baseado no problema knapsack, um problema NP-completo. Devido à inércia da Communications of the ACM, a primeira contribuição de Merkle só foi publicada em 1978. Inicialmente o algoritmo só podia ser usado para encriptações, se bem que, mais tarde, Shamir adaptou o sistema para assinaturas digitais. Atualmente este algoritmo é considerado inseguro e não é mais utilizado.

Também em 1976, Diffie e Hellman apresentaram seu conceito na National Computer Conference. Alguns meses mais tarde, na mesma época em que se discutia a adoção do DES como padrão, apresentaram o trabalho New Directions in Cryptography na IEEE Transactions on Information Theory. Na ocasião, Diffie e Hellman criticaram o DES, chamando a atenção da NSA para o tamanho da chave e a fragilidade do sistema. A confusão causada foi apreciável, com alguns alegando que as críticas tinham como único objetivo desmerecer o trabalho alheio para valorizar o próprio trabalho. Em poucos anos o equívoco foi desfeito quando o DES foi quebrado por uma equipe independente de pesquisadores e a NSA ficou de calças curtas

Em 1978, Rivest, Shamir e Adleman lançaram o primeiro algoritmo de chave pública completo, que atende tanto a encriptação quanto as assinaturas digitais.

Leonard
Adleman

Adi Shamir

Ron Rivest

Depois destes primeiros algoritmos, muitos outros foram propostos, mas a maioria é considerada insegura. Dos que são considerados seguros, muitos são impraticáveis porque têm chaves excessivamente longas ou porque o texto cifrado fica muito maior do que o texto claro. Dentre os algoritmos seguros e práticos, alguns só se prestam para a distribuição de chaves. Outros só atendem encriptações (e, por extensão, distribuição de chaves). Outros, ainda, só servem para assinaturas digitais. Atualmente existem apenas dois algoritmos de chave pública considerados completos (encriptação + assinaturas digitais), o RSA e o ElGamal. Todos algoritmos de chave pública são lentos, bem mais lentos do que os algoritmos de bloco, sendo que alguns deles são tão lentos que não permitem a cifragem de grandes volumes de dados.

O problema da distribuição de chaves

Se quisermos enviar material sigiloso através de um canal inseguro, basta cifrá-lo com um algoritmo criptográfico seguro. Mesmo que seja interceptado, dificilmente poderá ser decifrado. Acontece que, neste caso, o destinatário também recebe o material cifrado e depende de uma chave para obter o texto claro. Se houvesse um canal seguro para enviar a chave, não haveria a necessidade de cifrar a mensagem - bastava enviá-la através deste canal. Cifrar a chave para enviá-la é um contrasenso e também não resolve o probelma. O fato é que a falta de canais seguros cria um problema muito sério, o problema da distribuição de chaves.

A troca antecipada de chaves

Uma das formas de contornar o problema seria a troca antecipada de chaves entre as partes. Apesar de possível, esta solução não é das melhores porque exige a presença física dos envolvidos. Se remetente e destinatário morarem perto um do outro, não há motivo para trocarem mensagens cifradas através de canais inseguros; se morarem distantes um do outro, a troca das chaves depende de grandes deslocamentos e de tempo.

Agora imagine uma empresa onde 3 funcionários precisam da chave - serão precisos dois encontros. Se forem 10 funcionários, o número de encontros sobe para 45. A fórmula 1/2(n² - n) dá o número de encontros necessários e mostra que, para 1000 funcionários, 1/2(1000² - 1000) revela o número astronômico de 499.500 trocas de chave! Neste caso, o melhor é instituir uma central de chaves (ou um key master) e deixar que cada um retire a sua. A idéia pode parecer boa, mas ainda continua sendo um enorme problema de logística.

Terceiros de confiança

Se a troca antecipada não é a solução ideal, pode-se optar por terceiros de confiança (Trusted Third Party ou TTP). TTP é uma variação da solução da central de chaves. Em termos de organização, talvez seja um pouco melhor, mas surgem dois novos problemas. Como o TTP possui todas as chaves, também será capaz de ler todas as mensagens cifradas. Pior do que isto, caso o TTP se demita ou seja demitido, a empresa precisa renovar todas as chaves que usa.

Mas o TTP pode ser uma empresa contratada. Neste caso, os funcionários que prestam serviços para esta empresa, teoricamente, não poderiam ter acesso às chaves. E quem é que pode garantir uma coisa deste tipo? Na verdade, os riscos acabam se multiplicando, o que também torna esta opção pouco viável.

Os algoritmos de chave pública

Sistema simétrico

O grande diferencial dos algoritmos de chave pública é a solução que oferecem para o problema da distribuição de chaves. Os chamados algoritmos simétricos usam a mesma chave para cifrar e para decifrar, portanto, as chaves precisam ser distribuídas. Já os sistemas assimétricos (que recebem este nome porque as chaves são diferentes) facilitam enormemente a distribuição das chaves porque existem duas chaves. Uma é a chave pública, que pode ser publicada e distribuída livremente e servirá para cifrar as mensagens. Esta chave não permite decifrar textos que foram cifrados com ela e também não fornece elementos para calcular a chave privada.

Sistema assimétrico

Fazendo par com a chave pública, há uma outra que serve apenas para decifrar textos cifrados com a sua correspondente. Esta é a chave privada, que fica apenas sob os cuidados do seu dono e precisa ser mantida em segredo. Por este motivo esta chave também é chamada de chave secreta.

A grande aquisição dos algoritmos de chave pública é justamente esta: a chave cifrante (pública) não precisa de maiores cuidados e a chave decifrante (privada) fica sob os cuidados do proprietário. Desta forma, o problema da distribuição de chaves se torna irrelevante. Além disso, a mudança de um par de chaves também não é complicado. Basta criar um novo par, distribuir livremente a chave pública e resguardar a chave privada. É o pulo do gato

Como calcular um par de chaves complementares que fazem esta mágica? Veja como isto pode ser feito nas descrições dos principais algoritmos de chave pública. Você as encontra na seção Criptografia / Chave Pública.

Fontes

• Simon Singh, "O Livro dos Códigos"
• Bruce Schneier, "Applied Cryptography"
• Steve Burnett e Stephen Paine, "RSA Security's Official Guide to Cryptography"