Criptografia

Historicamente, quatro grupos de pessoas utilizaram e contribuíram para a arte da criptografia: os militares, os diplomatas, as pessoas que gostam de guardar memórias e os amantes. Dentre eles, os militares tiveram o papel mais importante e definiram as bases para a tecnologia. Dentro das organizações militares, tradicionalmente as mensagens a serem cifradas são entregues a auxiliares mal pagos que se encarregam de criptografá-las e transmiti-las. O grande volume de mensagens impedia que esse trabalho fosse feito por poucos especialistas.

Até o advento dos computadores, uma das principais restrições da criptografia era a habilidade do auxiliar de criptografia fazer as transformações necessárias, em geral com poucos equipamentos e no campo de batalha. Uma outra restrição era a dificuldade de alternar os métodos criptográficos rapidamente, pois isso exigia a repetição do treinamento de um grande número de pessoas. No entanto, o perigo de um auxiliar de criptografia ser capturado pelo inimigo tornou indispensável a possibilidade de alterar o método criptográfico instantaneamente, se necessário.

A criptografia funciona do seguinte modo: as mensagens a serem criptografadas, conhecidas como texto simples, são transformadas por uma função que é parametrizada por uma chave. Em seguida, a saída do processo de criptografia, é conhecida como texto cifrado.

A arte de criar mensagens cifradas (criptografia) e solucioná-las (criptoanálise) é coletivamente chamada de criptologia (criptology).

Será sempre útil e prático ter uma notação para estabelecer uma relação entre o texto simples, o texto cifrado e as chaves. Utilizaremos C = E_K(P) para denotar que a criptografia do texto simples ‘P’ usando a chave ‘K’ gera o texto cifrado ‘C’. da mesma forma, P = D_K(C) representa a decriptografia de ‘C’ para obter-se o texto simples outra vez. Em seguida temos:

D_K(E_K(P)) = P

Essa notação sugere que ‘E’ e ‘D’ são simplesmente funções matemáticas, o que é verdade. A única parte complicada é que ambas são funções de dois parâmetros, e escrevemos um desses parâmetros (a chave) como um caractere subscrito, em vez de como um argumento, para distingui-lo da mensagem.

Uma regra fundamental da criptografia é que se deve assumir que o analista especializado conheça o método genérico de criptografia que é utilizado. Em outras palavras, o criptoanalista sabe como funciona o método de criptografia, ‘E’. O esforço necessário para inventar, testar e instalar um novo método a cada que o antigo é (supostamente) comprometido sempre dificultou a manutenção deste segredo.

É nesse ponto que a chave entra. A chave consiste em um string (relativamente) curto que seleciona uma das muitas possíveis formas de criptografia. Ao contrário do método genérico, que só pode ser modificado de anos em anos, a chave pode ser alterada sempre que necessário. Portanto, nosso modelo básico é um método genérico publicamente conhecido, parametrizado com uma chave secreta que pode ser alterada com facilidade.

Não é possível enfatizar o caráter não-sigiloso do algorítimo. Ao tornar o algorítimo público, o especialista em criptografar se livra de consultar inúmeros de criptólogos ansiosos por decodificar o sistema para que possam publicar artigos demonstrando sua esperteza e inteligência. Caso muitos especialistas tenham tentado decodificar o algorítimo durante cinco anos após a sua publicação e nenhum tenha tido sucesso, isso provavelmente significa que o algorítimo seja muito bom.

Na verdade o sigilo está na chave, e seu tamanho é uma questão muito importante do projeto. Considere que uma combinação esteja bloqueada. O princípio geral é o de que você informa os dígitos seqüencialmente. Todo mundo sabe disso, mas a chave é secreta. Uma chave com o tamanho de dois dígitos permite 100 combinações , e uma chave com seis dígitos significa um milhão de combinações. Quanto maior for a chave, mais alto será o fator de trabalho (work factor) com que o criptoanalista terá de lidar. O fator de trabalho para decodificar o sistema através de uma exaustiva pesquisa no espaço da chave é exponencial em relação ao tamanho da chave. O sigilo é decorrente da presença de um algorítimo eficaz (mas público) e de uma chave longa. Para impedir que o seu irmãozinho leia as suas mensagens de correio eletrônico, serão necessárias chaves de 64 bits. Para manter o governo de outros países à distância, são necessárias chaves de pelo menos 256 bits.

Do ponto de vista do criptoanalista, o problema de criptoanálise apresenta três variações principais. Quando tem um determinado volume de texto cifrado mas nenhum texto simples, o analista é confrontado com o problema de haver somente texto cifrado (ciphertext only). Os criptogramas da seção de palavras cruzadas do jornal são um exemplo desse tipo de problema. Quando há uma correspondência entre o texto cifrado e o texto simples, o problema passa a ser chamado de texto simples conhecido (known plain text). Por fim, quando o criptoanalista tem a possibilidade de codificar trechos do texto simples escolhidos por ele mesmo, temos o problema do texto simples escolhidos (chosen plaintext). Os criptogramas dos jornais poderiam ser trivialmente decodificados se o criptoanalista tivesse a permissão de fazer perguntas tais como: Qual é a criptografia para ABCDE?

Com freqüência, os novatos na área de criptografia pressupõem que se uma condição puder resistir a uma estratégia de texto cifrado, isso significa que ela é segura. Essa suposição é muito ingênua. Em muitos casos, o criptoanalista pode fazer uma estimativa com base em trechos do texto simples. Por exemplo, a primeira mensagem que muitos sistema de tempo compartilhado emite quando você o chama é: “POR FAVOR, ESTABELEÇA O LOGIN”. Equipado com alguns pares do texto simples / texto cifrado, o trabalho do criptoanalista se torna muito mais fácil. Para obter segurança, o autor da criptografia deve ser conservador e se certificar de que o sistema seja inviolável mesmo que seu oponente seja capaz de criptografar o texto simples escolhido.

Historicamente, os métodos de criptografia têm sido divididos em duas categorias : as cifras de substituição e as cifras de transposição. Em seguida, trataremos de cada uma destas técnicas como informações básicas para a criptografia moderna.

Cifras de Substituição

Em uma cifra de substituição (substitution ciphers), cada letra ou grupo de letras é substituído por outra letra ou grupo de letras, de modo a criar um “disfarce”. Uma das cifras mais antigas conhecidas é a cifra de César. Nesse modo, ’a’ passa a ser ‘D’, ‘b’ torna-se ‘E’, ‘c’ passa a ser ‘F’ e assim por diante. Por exemplo, ‘attack’ passaria a ser ‘DWWDFN’. Nestes exemplos, o texto simples é apresentado em letras minúsculas e o texto cifrado em maiúsculas.

Uma ligeira generalização da cifra de César permite que o alfabeto do texto cifrado seja deslocado ‘k’ letras, em vez de 3. Neste caso ‘k’ passa a ser uma chave para o método genérico dos alfabetos deslocados circularmente. A cifra de César pode ter enganado os cartagineses, mas não enganou ninguém desde então.

O próximo aprimoramento é fazer com que cada um dos símbolos do texto simples, digamos 26 letras, seja mapeado para alguma outra letra.

Texto simples: a b c d e f g h i j k l m n o p q r s t u v w x y z

Texto cifrado: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Este sistema geral é chamado de substituição monoalfabética, sendo a chave o string de 26 letras correspondente ao alfabeto completo. Para a chave anterior, o texto ‘attack’ seria transformado no texto cifrado ‘QZZQEA’.

A primeira vista, talvez este sistema pareça seguro ,pois apesar de conhecer o sistema genérico (substituição de letra por letra), o criptoanalista não sabe quais das 26! (aproximadamente 4x10²⁶) chaves possíveis estão em uso. Ao contrário do que acontece com a cifra de César, experimentar todas elas não é uma estratégia muito interessante. Mesmo a 1µs por solução, um computador levaria 10¹³ anos para experimentar todas as chaves.

Todavia, com um volume de texto cifrado surpreendentemente pequeno, a cifra pode ser descoberta com facilidade. A estratégia básica se beneficia das propriedades estatística dos idiomas.

Outra estratégia é adivinhar uma palavra ou frase provável, nos EUA por exemplo, uma palavra muito provável em uma mensagem de uma empresa de contabilidade é ‘financial’. Utilizando o nosso conhecimento de que ‘financial’ tem três caracteres repetidos (‘n’, ‘i’ e ‘a’), com outras letras entre suas ocorrências, estamos procurando letras repetidas no texto com esse espaço entre elas. Desse ponto em diante, fica fácil deduzir a chave utilizando a estatística de freqüência para o texto em inglês.

Cifras de Transposição

As cifras de substituição disfarçam a ordem dos símbolos no texto simples, apesar de preservarem sua ordem. Por outro as cifras de transposição (transposition ciphers) reordenam as letras, mas não as disfarçam. A figura abaixo mostra uma cifra de transposição muito comum, a transposição de colunas. A cifra se baseia em uma chave que é uma palavra ou frase contendo letras repetidas. Nesse exemplo, MEGABUCK é a chave. O objetivo da chave é numerar colunas de modo que a coluna 1 fique abaixo da letra da chave mais próxima do início do alfabeto, e assim por diante. O texto simples é escrito horizontalmente, em linhas. O texto cifrado é lido em colunas, a partir daquela cuja letra da chave seja mais baixa.

Texto simples: pleasetransferonemilliondollarsto myswissbankaccountsixtwotwo Texto cifrado: AFLLSKSOSELAWAIATOOSSCTCLNMOMMANT ESILYNTWRNNTSOWDPAEDOBUOERIRICXB

Para romper uma cifra de transposição, o criptoanalista deve primeiro estar ciente de que está lidando com uma cifra de transposição.

A próxima etapa é fazer uma perspectiva do número de colunas. Em muitos casos, uma palavra ou frase provável pode ser deduzida através do contexto da mensagem.

A última etapa é ordenar as colunas. Quando o número de colunas , ‘k’, é pequeno, cada um dos pares de colunas k(k-1) pode ser examinado para que seja constatado se suas freqüências de diagrama correspondem às do texto simples em inglês. O par que tiver a melhor correspondência será considerado como posicionado da forma correta. Em seguida, cada uma das colunas restantes é experimentada como sucessora deste par. A coluna cujas freqüências de diagramas e trigramas proporcione a melhor correspondência será experimentalmente considerada como correta.

Criptografia Moderna

DES

Em janeiro de 1977, o governo dos Estados Unidos adotou uma cifra de produto desenvolvida pela IBM como seu padrão oficial para informações não-confidenciais. A cifra, DES (Data Encryption Standard), foi largamente adotada pelo setor de informática para uso de produtos de segurança. Em sua forma original, ela já não é tão segura; no entanto se modificada ela ainda pode ser útil. Agora explicaremos como o DES funciona.

O DES é basicamente uma cifra de substituição monoalfabética que utiliza um caractere de 64 bits. Sempre que o mesmo bloco de texto cifrado de 64 bits é submetido ao processo, obtém-se o mesmo bloco de texto cifrado em 64 bits. Um criptoanalista pode explorar essa propriedade para ajudá-lo a decifrar o DES.

Para vermos como essa propriedade da cifra de substituição monoalfabética pode ser usada para subverter o DES, consideraremos a criptografia de uma longa mensagem de maneira mais óbvia: através de sua divisão em blocos consecutivos de 8 bytes (64 bits) e de sua decodificação um após o outro com a mesma chave. O último bloco volta a ter 64 bits, se necessário. Essa técnica é chamada de modo do livro de código eletrônico (electronic code book mode).

IDEA

O IDEA foi projetado por dois pesquisadores na Suíça. Ele utiliza uma chave de 128 bits, que o tornará imune à qualquer técnica ou máquina conhecida atualmente.

A estrutura básica do algoritmo se assemelha à do DES no que diz respeito ao fato dos blocos de entrada de texto simples de 64 bits serem deturpados em uma seqüência de interações parametrizadas para produzir blocos de saída de texto cifrado com 64 bits. Devido à extensiva deturpação dos bits (em cada iteração, cada bit de saída depende de cada bit de entrada), são necessárias oito interações.

Algorítimos de chave pública

Historicamente, o problema da distribuição de chaves sempre foi o ponto fraco da maioria dos sistemas de criptografia. Mesmo sendo sólido, se um intruso pudesse roubar a chave, o sistema acabaria se tornando inútil. Como todos os criptólogos sempre presumem que a chave de criptografia e a chave de decriptografia são iguais (ou facilmente derivadas uma da outra) e que a chave seja distribuída a todos os usuários do sistema, tinha-se a impressão de que havia um problema embutido inerente: as chaves tinham de ser protegidas contra roubo, mas também tinham de ser distribuídas; portanto, elas não podiam ser simplesmente trancadas no caixa-forte de um banco.

Em 1976, dois pesquisadores da Universidade de Stanford, Diffie e Hellman (1976), propuseram um sistema de criptografia radicalmente novo, no qual as chaves de criptografia e de decriptografia eram diferentes e a chave de decriptografia não podia ser derivada da chave de criptografia. Em sua proposta, o algorítimo de criptografia (chaveado), E, e o algorítimo de decriptografia (chaveado), D, tinham de atender a três requisitos, que podem ser declarados da seguinte forma:

1. D(E(P)) = P.

2. É excessivamente difícil deduzir D de E.

3. E não pode ser decifrado através do ataque de texto simples escolhido.

O primeiro requisito diz que se aplicarmos D a uma mensagem criptografada, E(P), obteremos a mensagem de texto simples original P, outra vez. O segundo é auto-explicativo. O terceiro é necessário porque, como veremos em um minuto, os intrusos podem experimentar o algoritmo até se cansarem. Sob essas condições, não há razão para a chave criptográfica não se tornar pública.

O método funciona da seguinte forma: Uma pessoa, desejando receber mensagens secretas, primeiro cria dois algoritmos, E_A e D_A, que atendem aos requisitos mostrados anteriormente. O algoritmo de criptografia e a chave, E_A, se tornam públicos, daí o nome criptografia com chave pública – public key criptography (para diferenciá-la da criptografia tradicional com chave secreta). Isso pode ser feito colocando-se a chave em um arquivo que todos os interessados possam ler. Essa pessoa publica o algoritmo de decriptografia (para obter a consultoria grátis), mas mantém a chave de decriptografia secreta. Assim, E_A é pública, mas D_A é privada.

Talvez seja interessante fazer uma observação sobre terminologia. A criptografia com chave pública exige que cada usuário tenha duas chaves: uma chave pública, que é usada pelo mundo inteiro para criptografar as mensagens a serem enviadas para esse usuário, e uma chave privada, que o usuário utiliza para decriptografar mensagens.