O Livro dos Códigos

Nesses últimos dias eu li um livro chamado O Livro dos Códigos, de Simon Singh. O livro conta a história da criptografia, desde a antiguidade até a criptografia quântica. Mostra como as cifras e a busca pelo sigilo avançaram ao longo do tempo. Na antiguidade, se usava muito a esteganografia, que consiste em esconder a mensagem ao invés de cifrá-la. Uma das primeiras cifras utilizadas que se tem registro é a cifra de César. Ela consiste em você fazer um deslocamento no alfabeto. Por exemplo, se o deslocamento for de 1, PATY seria cifrado como QBUZ. Essa cifra claramente é muita fraca e fácil de quebrar. Esse tipo de cifra é chamada monoalfabética, pelo fato óbvio de usar apenas um alfabeto. Durante muito tempo os criptógrafos (as pessoas que cifram) ganharam a batalha com os criptoanalistas (aqueles que tentam quebrar esses códigos). Foram desenvolvidas cifras monoalfabéticas mais complicadas, mas os árabes inventaram uma técnica para quebrar essas cifras chamada de análise de freqüência. Assim, os criptoanalistas passaram a frente nessa batalha. Os criptógrafos então inventaram uma cifra polialfabética que eles chamavam de “A cifra indecifrável”. Ela foi assim considerada por muito tempo, mas Babbage conseguiu decifrá-la. Durante a segunda guerra mundial, a criptografia exerceu um papel fundamental. Os alemães criaram a maquina de encriptação Enigma, que eles consideravam muito segura. Mas os poloneses e depois os ingleses conseguiram quebrar e decifrar as mensagens do Enigma, afetando muito o curso da guerra. Com o desenvolvimento dos computadores e posteriormente da internet, havia na área uma preocupação enorme com relação à segurança. Como fazer para manter a segurança num ambiente como a internet? Para muitas transações, segurança é fundamental, como transações bancarias e de governo. Foram inventados diversos algoritmos de criptografia muito eficientes, mas que tinham um problema fundamental: a distribuição de chaves. Se Alice deseja se comunicar com Bob, eles precisam combinar uma chave para ser usada no algoritmo de encriptação. Desde a antiguidade, o sigilo era garantido através da chave e não do fato de o oponente conhecer o método usado para cifrar. O inimigo podia conhecer o método, mas contanto que ele não conhecesse a chave, ele não conseguiria decifrar. Esses métodos de cifrar evoluíram bastante ao longo do tempo, mas o problema da distribuição das chaves continuou. Se Alice quer se comunicar com Bob, como eles fazem para combinar a chave usada? Alice poderia mandar a chave pela internet para Bob, mas se o canal não é seguro para se enviar mensagens, tampouco vai ser seguro para enviar a chave. Então Alice e Bob precisariam encontrar outra maneira de trocar a chave. Eles poderiam se encontrar pessoalmente, por exemplo. Porém, isso requer bastante esforço e não é viável para as aplicações comerciais. Imagine uma empresa onde cada par de funcionários precisa ter a sua chave para se comunicar e essa empresa tem 200 funcionários. Casa funcionário deveria saber a chave para se comunicar com os outros 199, tarefa um tanto inviável. E quanto mais cresce o número de funcionários ou pessoas querendo se comunicar, mais complicado fica para fazer essa troca de chaves. Era necessária uma solução urgente para o problema da distribuição de chaves, mas a maioria dos estudiosos da época achava que o problema da distribuição de chaves era insolúvel. Foi aí que surgiram as idéias de dois pesquisadores, Whitfield Diffie e Martin Hellman. Eles criaram o conceito de criptografia de chave pública, que resolvia esse problema da distribuição de chaves. A idéia deles é que cada pessoa tivesse a sua chave privada e sua chave pública. A chave pública é usada para cifrar as mensagens e é de conhecimento público, todo mundo pode ter acesso. Já a chave privada fica em poder do seu dono que a guarda em segredo, sendo usada para decifrar as mensagens cifradas com a respectiva chave pública. Assim, se Alice deseja mandar uma mensagem para Bob, ela cifra a mensagem com a chave pública de Bob e envia a mensagem cifrada para ele. Só quem vai poder decifrá-la é Bob, pois apenas ele sabe a sua chave privada que é necessária para fazer isso. Assim, eles não precisam mais trocar chaves porque o único conhecimento que Alice precisa para mandar uma mensagem para Bob é a sua chave pública, a qual todos têm acesso e não dá meios de se encontrar a chave privada. Diffie e Hellman tiveram essa maravilhosa idéia, mas não conseguiram conceber um sistema que funcionasse eficientemente dessa maneira na prática. A partir do lançamento das idéias deles, começou-se uma busca por uma implementação viável da criptografia de chave pública. Ela veio um tempo depois com três pesquisadores chamados Ron Rivest, Adi Shamir, Len Adleman. Eles inventaram o algoritmo RSA, que é considerada por muitos a melhor implementação da criptografia de chave pública. Esse algoritmo é usado largamente na internet, para manter a segurança de transações bancarias, e-commerce e muitas outras aplicações. No RSA, a chave privada é basicamente dois números primos de um tamanho enorme e a chave pública é a multiplicação desses dois primos. O dono da chave privada consegue facilmente gerar a chave pública, porque a multiplicação é uma tarefa fácil. Já a fatoração de um número nos seus dois fatores primos é um tanto complicado quando o tamanho da entrada cresce. Atualmente, usa-se um tamanho de chave da ordem em torno de 10 elevado a 308, o que levaria todos os computadores do mundo mais do que a idade do universo para conseguir achar a resposta. Por isso, o RSA é considerado um algoritmo seguro. Com o advento dos computadores quânticos, essa segurança poderia ser quebrada, e aí teria que se inventar [e até já foi inventado] outro tipo de método criptográfico para conseguir manter o sigilo. Ah sim, e eu recomendo o livro, muito interessante.

20.000 Léguas Matemáticas

Essa semana eu li o livro 20.000 léguas matemáticas, de A. K. Dewdmey. Ele fala sobre a busca do professor Dewdney pela resposta de duas grandes perguntas: “Por que a matemática é tão incrivelmente útil nas ciências naturais?” e “A matemática é descoberta ou criada?”. Para isso, ele se encontrou com quatro estudiosos para tentar responder a essas perguntas. O primeiro deles foi Petros Pygonopolis, um historiador da matemática e da ciência, na antiga cidade grega de Mileto. O segundo foi o astrônomo árabe Jusuf al-Flayli no Egito. O terceiro encontro foi com Maria Canzoni, uma física de Veneza. Por último, ele se encontrou com Sir John Brainard, um matemático de Oxford. Os quatro possuíam opiniões um tanto quanto diferentes, mas todos concordavam com o mesmo ponto: a matemática é sim descoberta. Mesmo depois de ler todo esse livro com diversas opiniões diferentes acerca do assunto, eu continuo com a minha opinião que eu dei nessa postagem: A matemática é descoberta. Ela já existe, nós apenas vamos descobrindo as relações e inventando abstrações para representá-la. Existe a hipótese pitagórica, que diz que: ”O cosmo e tudo que há nele são regidos por leis matemáticas.” Pitágoras ainda ia além e dizia que o universo poderia ser todo descrito por inteiros. Nesse ponto eu não concordo. Houve uma parte do livro que me chamou uma particular atenção. Um matemático inglês chamado David Gridbourne julgava ter produzido criaturas vivas em seu computador. Ele desenvolveu um autômato celular chamado 2DWORLD, que é basicamente um universo bidimensional com a forma de uma vasta esfera. Esse autômato é regido por regras simples que imitam as equações da física moderna. Ele começou aleatoriamente distribuindo 0 ou 1 a cada célula dessa unidade. Isso acabou, para surpresa do próprio Gridbourne, gerando um cosmo bidimensional com estruturas complexas. Ele disse o seguinte a respeito desse universo: “E está [vivo]. Algumas regras da física parecem garantir o surgimento de níveis organizacionais, um após o outro, aparentemente de maneira infindável. Nesse nível, o sistema chegou a estruturas que se propagam interminavelmente. E elas têm mudado, desde que surgiram pela primeira vez. Decididamente, estão ficando mais complexas, e têm uma espécie de código genético, embora ele se baseie em estruturas muito diferentes da do nosso. ” Ele ainda considera que é possível que essas estruturas possam desenvolver a ciência e acabar descobrindo as leis que ele instalou no seu espaço celular e acha até possível que elas descubram que só existem em um computador, mas não teriam a menor idéia em qual computador nem onde. Uma viagem isso né? Enfim, o livro é bom. Recomendo a leitura por quem se interesse pelas perguntas de Dewdney e pela história da matemática.