O que temos até agora?

• método: o algoritmo matemático que faz a cifra e a decifragem. Não deve ser segredo.
• chave: único segredo. Uma informação que alimenta o algoritmo para cifrar ou decifrar. Quanto mais possibilidades, mais inviável é o força bruta.

Assim como uma porta de uma casa com sua fechadura que só pode ser aberta por quem tiver a chave. Considerando que a fechadura é a prova de criptoanálise, ou seja, a prova de "chaveiros", a única forma de abrir a porta sem a chave correta é se um chaveiro viesse com uma sacola com todas as possíveis chaves para aquela fechadura e ficasse tentando até uma servir. Se forem bilhões de chaves possíveis, torna inviável (isto seria um força bruta).

Mas veja que neste exemplo a mesma chave que fecha também abre. Existe apenas uma chave e ela serve para trancar a porta e também para destrancá-la! Neste caso tem-se o que se chama de algoritmo simétrico, onde existe apenas uma única chave e ela serve para cifrar e decifrar.

Um problema crônico existe com os algoritmos simétricos e ele atormentou os cientistas durante muito tempo: como pode ocorrer de forma segura a troca das chaves?

Se eu quero trocar uma mensagem com a pessoa B como conto ao B que usarei k=10 para cifrar a mensagem? Se tiver a oportunidade de me encontrar pessoalmente com ele, ok, converso de forma reservada e lhe conto a chave. Mas e se ele estiver distante, sem a possibilidade de um encontro pessoal? Telefono para ele? E se alguém estiver com uma escuta telefônica? Envio um email? Veja, não tem como realizar esta comunicação de forma segura.

Este problema atormentou muita gente. Na segunda guerra o livro dos códigos da Enigma, com chaves diárias de um mês inteiro, era entregue em mãos aos operadores de rádio. Este tinha ordens para, sob ataque, imediatamente destruir a máquina e o livro. Se os aliados tivessem acesso a este livro seriam capazes de quebrar as comunicações de um mês inteiro (o filme "U-571 - A Batalha do Atlântico" explora este fato, onde os aliados disfarçam um submarino como sendo alemão a fim de tentar capturar a Enigma).

Simon conta detalhes deste fato histórico e revela que uma das primeiras formas que os aliados acharam para ler as mensagens foi subornar um oficial alemão (depois eles quebraram com colas e depois com máquinas implementadas por Alan Turing chamadas de "bombas")!

Seria possível a troca de chaves de forma segura usando um meio de comunicação inseguro? Isto se consagrou como matematicamente impossível, exceto para os "loucos" Marin Hellman e Whitfield Diffie. Loucos pois aparentemente estavam pesquisando algo impossível, para o qual já se havia desistido: um algoritmo de troca de chaves seguro em um meio inseguro.

Este artigo ficaria muito longo se começasse a contar a história do famoso algoritmo Diffie-Hellman e o quanto ele revolucionou a ciência da criptografia. Cabe apenas ressaltar o raciocínio que embasou estes "loucos". Eles pensaram facilmente em um protocolo de troca de informações sigilosas via correio. É interessante para ilustrar.

Imagine que quero enviar documentos sigilosos pelo correio para "P" e que eu não confio no carteiro. Colocar os documentos em uma caixa com cadeado não serve, pois como enviaria a chave do cadeado para o "P"? Pelo correio? Por teletransporte? Se não confio no meio, não adianta variar os métodos usando este meio de transporte no qual não confio. Estamos falando de criptografia onde se leva as teorias ao extremo.

Mas DH pensaram em um método (eu sou o "E" enviando documentos para "P"):

1. "E" compra um cadeado em uma ferragem;
2. "E" coloca os documentos em uma caixa e coloca o seu cadeado. Pressupõe-se que tanto a caixa como o cadeado são invioláveis e que a única forma de abrir a caixa é com a chave;
3. "E" envia a caixa pelo Correio. Veja que ninguém poderá abir, pois "E" não enviou a chave. O carteiro curioso nada pode fazer;
4. "P" recebe a caixa. Bom, "P" também não a pode abrir pois ele não tem a chave (surpreso?). Mas "P" ao invés de abrir, compra o seu cadeado e coloca ele também na caixa. A caixa agora tem DOIS cadeados: o de "E" e o de "P";
5. "P" devolve a caixa pelo correios ao "E";
6. Legal, agora nem mesmo "E" consegue abrir sua caixa. Mas ele apenas usa a sua chave para tirar o seu cadeado, mantendo o cadeado de "P";
7. "E" devolve a caixa para "P" que agora pode abrí-la.

Observe que neste protocolo jamais houve uma troca de chaves. DH pensavam que deveria existir um princípio matemático que reproduzisse este efeito e depois de muita pesquisa o encontraram na aritmética modular usando números primos (mais tarde se soube que eles não foram pioneiros, pois pesquisas secretas neste sentido haviam sido realizadas muitos anos antes).

Prometi que não ia falar do algoritmo de Diffie-Hellman e não vou. Apenas devo dizer que ele, em sua forma original, é vulnerável e sua importância histórica é mais por ter abertos portas. O famoso e ainda extremamente usado algorítimo RSA é baseado na mesma aritmética modular do DH.

Um algoritmo assimétrico, portanto, é quando se usa uma chave para cifrar, porém, magicamente, esta chave não serve para abrir o que se cifrou. Não tem espaço aqui para explicar isto em termos matemáticos (se alguém quiser, me peça), mas o fato é que tais algoritmos existem.

Muitos chamam estes algoritmos de chave pública e privada, mas o nome técnico deles é algoritmos assimétricos. Esta confusão no nome é porque uma das chaves, normalmente a que serve para cifrar, é tornada pública e a outra é mantida sob sigilo conhecida como chave privada (eu tenho que tomar muito cuidado quando falo disto. Sempre "chave privada". Não foram poucas as vezes que me peguei falando "Se você der a sua privada para o fulano").

Para entender os assimétricos eu uso uma excelente analogia! Voltemos aos correios e ao uso das caixas. Tem uma maneira ainda mais eficiente de receber ou enviar documentos sigilosos.

Digamos que eu quero enviar um documento para "P". Bastaria isto:

1. "P" compra um cadeado e me envia ele ABERTO pelo correio. Não envia a chave;
2. "E" recebe o cadeado aberto de "P" e o usa para fechar a caixa. Uma vez fechada, "E" já não tem mais condições de abrí-la;
3. "E" envia a caixa com o cadeado fechado de "P";
4. "P" a abre pois tem a chave.

Nesta analogia a chave pública seria o cadeado aberto: ele só serve para cifrar.

Estendendo a analogia, "P" poderia pedir a um fabricante de cadeados que confeccionasse milhares de cadeados com a mesma chave. O cadeado de "P" estaria em todas as agências de correios, por exemplo. Esta é a ideia.

Claro que para que isto funcione o cadeado deve ser forte e a chave deve possuir muitas combinações, senão um ataque de força bruta seria viável. Deve também ser imune a criptoanálise, ou seja, nenhum chaveiro do mundo seria capaz de construir uma nova chave apenas analisando o cadeado.

Voltando aos termos "informáticos" a ideia do cadeado foi implementada pelo algoritmo RSA baseado na fatoração de números primos. Constitui em duas chaves, uma chamada de Ke (K para "e"ncriptar) e Kd (k para "d"ecriptar). Uma complementa a outra. O que cifra-se usando Ke apenas com a Kd é possível recuperar (não vou descrever o funcionamento do RSA).

Um atacante conhece Ke pois a tornei pública. Contudo, mesmo tendo ela, ele está computacionalmente inviabilizado de calcular Kd. RSA garante isto através do uso de números primos gigantes, hoje com tamanhos de 512 bits.