Suponha que o leitor (a quem vou chamar Bob) quer enviar um objecto valioso para uma amiga distante (a quem vou chamar Alice), usando para tal um mensageiro. Porém, o país está infestado de salteadores que roubarão qualquer coisa que não esteja fechada dentro de um cofre inviolável, usado pelo mensageiro para transportar bens com segurança. O problema é que Alice não tem a chave do cofre e Bob tem de arranjar forma de ela poder abrir o cofre no destino.

Suponha que o leitor (a quem vou chamar Bob) quer enviar um objecto valioso para uma amiga distante (a quem vou chamar Alice), usando para tal um mensageiro. Porém, o país está infestado de salteadores que roubarão qualquer coisa que não esteja fechada dentro de um cofre inviolável, usado pelo mensageiro para transportar bens com segurança. O problema é que Alice não tem a chave do cofre e Bob tem de arranjar forma de ela poder abrir o cofre no destino.

Como resolver o problema? A solução mais simples consiste em Bob enviar a chave do cofre, numa encomenda separada, para que Alice possa usá-la para o abrir. Esta é a solução tradicionalmente usada nos chamados sistemas de chave privada, e é nesta solução que se baseiam os sistemas de cifra militares mais usados no passado. Um método famoso é a cifra de César, onde cada letra do alfabeto é substituída por outra, deslocada um certo número de posições à esquerda ou à direita. Esta cifra, quase trivial, terá sido inventada por Júlio César, que usava uma deslocação de três letras à direita para proteger mensagens militares, substituindo A por D, B por E, e assim por diante.

A história mais conhecida da utilização militar de sistemas de chave privada é, provavelmente, o sistema de cifra usado pelos alemães na segunda guerra mundial. As máquinas de cifra alemãs, conhecidas como Enigma, eram configuradas usando chaves secretas, distribuídas antecipadamente para serem usadas dias, semanas ou meses no futuro. Quando eram interceptadas, porém, comprometiam a segurança das comunicações. Foi aliás a intercepção de algumas chaves que também ajudou os ingleses a quebrar os códigos das máquinas Enigma, conduzindo a uma vantagem decisiva que muito contribuiu para derrotar a Alemanha na segunda guerra mundial. É bem conhecido o esforço que conduziu ao sistema usado para decifrar as mensagens codificadas pelos alemães, que teve lugar em Bletchley Park, usando um computador chamado Bombe projectado por uma equipa liderada por Alan Turing. Porém, é menos conhecido o facto de outros terem também contribuído significativamente para desenvolver métodos de ataque às cifras das máquinas Enigma, nomeadamente os matemáticos polacos Jerzy Rózycki, Henryk Zygalski e Marian Rejewski.

A abordagem baseada em chaves privadas usada pelos alemães, que já não foi particularmente eficaz na segunda guerra mundial, não pode ser usada por Bob no mundo moderno da Internet. O problema é que os atacantes poderão conseguir ter acesso a qualquer chave que seja enviada por meios electrónicos. No caso da Internet, o objecto valioso enviado é, tipicamente, informação, por exemplo um número de cartão de crédito. Quando se pretende enviar um número de um cartão de crédito, numa mensagem cifrada, para fazer uma aquisição, não é razoável enviar por outra via (por exemplo, por correio físico) a chave privada da mensagem.

Como resolver então o problema de Bob e Alice? Se o leitor pensar um pouco, poderá chegar a uma solução, não muito óbvia, que consiste em usar dois cadeados e duas chaves. Uma possibilidade consiste em Bob enviar o cofre, fechado com um cadeado, cuja chave fica só com ele. Alice recebe o cofre, fecha-o com um segundo cadeado do qual guarda a chave, e envia o cofre de volta. Bob retira o seu cadeado, e envia novamente o cofre para Alice que, finalmente, o abre com a sua chave. O método funciona se for possível colocar e retirar os cadeados por uma ordem qualquer e não necessariamente pela ordem inversa com que foram colocados. Fica assim resolvido o problema da privacidade da comunicação entre Bob e Alice.

Os sistemas de chave pública na Internet funcionam com variações deste esquema, e partem sempre do princípio de que tudo o que passa no canal de comunicação pode ser observado por um atacante. Nos métodos de chave pública, não é necessária a existência de um canal seguro para troca de chaves, uma vez que assumem que toda a informação que é trocada pode passar por canais inseguros. O primeiro método proposto foi o método de Diffie–Hellman, que permite a Bob e a Alice trocarem informação usando um canal inseguro e usá-la para chegar a uma chave que só eles conhecem.

Porém, o sistema mais utilizado actualmente de criptografia de chave pública, o sistema RSA, deve-se aos investigadores Ron Rivest, Adi Shamir e Leonard Adleman, que propuseram um método para trocar mensagens, de forma segura, numa Internet insegura. Todos nós usamos este sistema de cifra, cada vez que executamos uma transacção segura na Internet e enviamos dados privados. Em cada segundo, são codificadas e descodificadas milhares de mensagens usando este sistema.

O sistema RSA funciona com base num algoritmo que usa o facto de ser muito difícil decompor nos seus factores primos um número com muitos algarismos. Um número que é o resultado de um produto de primos, os factores, chama-se um número composto. Quando os números compostos são muito grandes e têm centenas de dígitos, é muito difícil e demorado determinar os seus factores. A parte mais importante da chave pública usada pelo sistema RSA é um número composto, que resulta do produto de dois números primos.

Alice que, no nosso caso, está interessada em receber mensagens confidenciais, selecciona dois números primos e divulga o seu produto na chave pública, mas mantém secreta a chave privada, que é obtida a partir destes dois primos. A chave privada pode então ser usada para decifrar as mensagens codificadas com a chave que foi tornada pública.

O método pode ser atacado tentando recuperar a chave privada a partir da chave pública. Isto pode ser feito decompondo o número composto da chave pública nos seus factores primos. Isto, porém, é muito difícil para números muito grandes. As chaves RSA, usadas hoje na Internet, têm centenas de dígitos e não são passíveis de ser quebradas, mesmo pelos computadores mais rápidos existentes. À medida que os computadores se tornam mais rápidos será possível usar chaves maiores, mantendo-as fora do alcance de ataques com computadores tradicionais. Os computadores quânticos têm, teoricamente, o potencial para conseguir factorizar rapidamente números compostos, mesmo os números muito grandes usados no sistema RSA. Por enquanto, porém, os computadores quânticos apenas conseguiram factorizar números muito pequenos, como demonstração de que operam correctamente. Foi, em particular, demonstrada a factorização do número 15, igual a 3 vezes 5, por um computador quântico, usando o algoritmo de Shor. Isto está muito longe de permitir qualquer ataque ao sistema RSA, e não é claro se algum dia será possível usar computadores quânticos para atacar os sistemas de chave pública usados actualmente. Porém, se isso vier a acontecer, teremos de passar a usar outros sistemas de chave pública ou então arranjar outra forma de manter a informação privada na Internet.

Alice e Bob, os nomes tradicionalmente usados para analisar sistemas de cifra, são personagens fictícias, inventadas por Rivest, Shamir e Adleman, no seu artigo de 1978, que propôs o sistema RSA, e são normalmente usados para referir os actores que usam sistemas criptográficos.