Sistemas de criptografia (1)

GPG por mbernet (CC BY-NC-SA 2.0).

A criptografia é uma das aplicações mais relevantes ao nosso dia-a-dia das ideias em matemática e ciência da computação. Você depende dela ao comprar coisas pela internet, enviar dados importantes e realizar diversas transações bancárias. Nesta série de posts veremos os principais conceitos por trás dos sistemas de criptografia, desde fundamentos matemáticos até implementações.

Uma breve história da criptografia

A palavra criptografia é de origem grega e tem o sentido de "mensagem secreta". Métodos de criptografia sempre tiveram bastante importância para proteger segredos de Estado, a fim de impedir que nações inimigas lessem mensagens cruciais e obtivessem vantagem estratégica. Como é muito difícil evitar a interceptação dessas mensagens, buscou-se uma maneira de fazer com que apenas certas pessoas pudessem compreendê-las.

Um sistema notável é a cifra de César, elaborada durante a Antiguidade Clássica pelo imperador Júlio César. Cada letra é substituída pela letra 3 posições à frente; se não for possível ir mais adiante, então volte ao início ('z' é transformado em 'c', por exemplo). Seguindo essa regra, "alexandre magno" vira "dobdqguh pdjqr".

Avanços significativos começaram a ser feitos na época da Segunda Guerra Mundial, quando trabalhou-se em métodos eficientes para ocultar e revelar mensagens — não por coincidência, floresceu também o interesse pela computação como ferramenta militar —. Um dos especialistas mais notórios foi Alan Turing, creditado como o fundador da ciência da computação. A partir daí, muitos estudos aprofundados se seguiram, culminando nos métodos utilizados até hoje.

Por Mark Pellegrini (trabalho próprio) [CC-BY-SA-2.5], via Wikimedia Commons.

Teoria dos números

A teoria dos números, o estudo dos números inteiros, costumava ser vista como a disciplina mais "pura" da matemática, cuja única motivação era o fascínio dos matemáticos por ela. Contudo, os criptossistemas modernos utilizam vários resultados da teoria dos números — em especial dos números primos — como fundamentos teóricos.

A primeira noção importante é a divisibilidade. Dizemos que um inteiro a é divisível por outro inteiro b quando a = bq, para algum inteiro q, o que significa que a é um múltiplo de b. É mais comum usar a notação "b divide a", ou b|a: 3|6, 6|12, 5|10, 60|120, e por aí vai. Mas e quando essa divisão não é exata? Nesse caso, escrevemos a como:

a = bq + r

Onde q é o quociente da divisão e r o resto. O operador "mod" estabelece a relação entre dois inteiros e o resto da divisão de um pelo outro: a mod b = r. Esses restos são de especial interesse por surgirem em situações periódicas, como na cifra de César. Atribua valores numéricos às letras: A = 1, B = 2, ..., Z = 26. Quando aumentamos o valor de Z em 3 unidades, obtemos 29:

29 = 26 * 1 + 3

De fato, o resto 3 corresponde ao valor da letra C. Um modo simples de visualizar a situação é imaginando um ciclo com 26 pontos: atravessar 29 pontos significa dar 1 volta completa (quociente) e depois atravessar mais 3 unidades (resto). Isso também vale para A, que tem seu valor aumentado a 4:

4 = 26 * 0 + 4

Novamente, o resto 4 corresponde ao valor da letra D. Na prática, é comum usar a notação de congruência:

29 ≡ 3 (mod 26)  --> 29 é congruente a 3 módulo 26, ou seja, deixa o mesmo resto que 3 na divisão por 26.

No próximo post vamos falar um pouco mais sobre aplicações diretas da teoria dos números em criptossistemas e o papel dos números primos, mas por hora deixo algumas mini-aulas aprofundadas aos interessados no assunto:

Introdução à teoria dos números
Aritmética modular e aplicações - 1
Aritmética modular e aplicações - 2

Noções básicas de criptologia e criptografia

O estudo geral dos criptossistemas na verdade é conhecido como criptologia, ao contrário do que muitos costumam confundir. Fazem parte desse estudo a criptografia, preocupada em cifrar ou encriptar mensagens, e a criptoanálise, preocupada em decifrar ou decriptar mensagens. Tudo consiste em construir e analisar protocolos de comunicação.

Esses protocolos giram em torno de uma ou mais chaves, que determinam o tipo de transformação a ser sofrida pelo texto e geralmente são escolhidas aleatoriamente. De acordo com o tipo de chave, podemos identificar dois algoritmos principais:

Criptografia de chave simétrica

Os algoritmos de chave simétrica baseiam-se em uma única chave para os transmissores e receptores. Alguns deles continuam populares até hoje em certas aplicações, mas viu-se que seriam inviáveis para transações comerciais ou bancárias em escala global. Isso porque é necessário um gerenciamento de chaves bastante complexo para cada par que se comunica, além de um canal seguro para estabelecer a chave em comum.

Esta era a única forma de criptografia conhecida até 1976, com a chegada da...

Criptografia de chave pública ou assimétrica

A solução aos problemas veio na forma dos algoritmos baseados em chave pública, ou assimétrica. A "assimetria" deve-se ao fato que há uma chave para encriptar e outra para decriptar mensagens, sendo uma pública e outra privada. Cada usuário disponibiliza sua chave de encriptação a todos os outros, mas mantém uma chave secreta para decriptar mensagens.

Um exemplo prático: se A quer mandar uma mensagem a B, ele deve encriptar sua mensagem usando a chave pública de B; por sua vez, B utiliza a chave secreta para decriptar a mensagem.

A implementação mais famosa da criptografia de chave pública, usada em criptossistemas do mundo inteiro, é o algoritmo RSA. Um fato interessante é que ele se baseia na fatoração de números inteiros muito grandes, tarefa para a qual não há um procedimento rápido.

O que vem por aí

Agora que abordamos o básico, no próximo post vamos tratar com detalhes do sistema RSA e algumas considerações matemáticas envolvendo números primos. Em particular, a tal hipótese de Riemann, um problema em aberto lendário que garante um prêmio de um milhão de dólares ao solucionador. Até lá, confira informações sobre a hipótese de Riemann e o Prêmio do Milênio.

Fontes

A Hipótese de Riemann e a Internet (I)
Cryptography - Wikipedia
Problemas do Milênio - Numerofilia
Teoria dos números: Uma introdução