Criptografia chave simétrica de bloco e de fluxo

Historicamente nunca se precisou agrupar uma mensagem em tamanhos de bloco para poder cifrá-la. Os algoritmos de substituição monoalfabética usados no passado permitiam cifrar letra a letra e não precisavam que eu agrupasse-as em conjunto de X letras e tão pouco que eu inserisse caracteres de lixo para completar um bloco. Tradicionalmente, portanto, as cifras eram de fluxo.

Em um algoritmo de fluxo não é necessário ter um bloco para cifrar. Cifra-se o que se tem e, se desejar, no momento que se quiser. Se tenho um byte, cifro e já envio se for o meu desejo. Ao ter mais um byte, cifro e envio e se este era o último byte a ser cifrado, encerro o algoritmo sem qualquer necessidade de completar a informação com "lixo".

De fato, considerando que dentro do processador a menor unidade de informação é um bit, os algoritmos de fluxo permitem cifrar até mesmo bit a bit. Na prática não o fazem por questões de desempenho, já que dificilmente teria apenas um bit para transmitir, sendo que o byte é considerado a informação mínima na maioria dos casos.

O mais incrível é que a operação matemática que permite tal façanha é bem conhecida de muitos. Trata-se do XOR.

O XOR, também conhecido como "OU exclusivo" é uma operação bit a bit, assim como o AND e o OR. No ramo da microeletrônica (onde reside meu passado) o XOR é uma porta lógica. A chamada "Tabela verdade" apresentada na Figura 2 mostra os resultados das operações binárias AND, OR e XOR. Analisando os resultados da Figura 2 percebe-se que no caso do AND, ambos os bits, A e B, precisam estar em 1 para que a saída seja 1. No caso do OR, basta que um dos bits, A ou B, esteja em 1 para que a saída seja 1. AND e OR não nos interessam aqui, sendo nosso alvo o XOR.

Veja que no XOR, sempre de dois bits A e B forem iguais, o bit resultante será ZERO, sendo UM nos demais casos.

A propriedade que mais nos interessa do XOR é a sua comutatividade e possibilidade de reversão. Se eu faço A xor B = X, ao fazer X xor B eu terei o A e ao fazer X xor A eu terei o B. Ainda, se preciso fazer A xor B xor C, não importa a ordem em que eu faça, o resultado será o mesmo, isto é, pode fazer (A xor B) xor C ou A xor (B xor C) ou qualquer outra combinação.

Veja o exemplo de um XOR bit a bit de 011 com 101:


Aplicando-se o XOR bit a bit de A com B, ou seja, cada bit de A xor com o bit de B de acordo com a tabela verdade, chega-se ao valor de X=110. Observe que se eu fizer A xor X terei:


Veja que os bits resultantes correspondem na verdade aos bits de B. Neste sentido que o XOR é comutativo e reversível, sendo um algoritmo de criptografia por si só. O Word, quando eu o usava há uns 15 anos, permitia que se cifrasse o DOC usando apenas XOR.

Para usar o XOR como algoritmo basta que A seja a mensagem a ser cifrada e B a chave, sendo X o texto cifrado. O destinatário receberá apenas o X e se ele souber antecipadamente o valor de B, poderá realizar X xor B recuperando o A original.

O XOR não pode, porém, ser usado simplesmente como um algoritmo natural pois se o for, será muito vulnerável a criptoanálise. Ele tem uma limitação, pois a chave não pode ser reaproveitada para cifrar mensagens futuras (para não tornar este capítulo massante, explico este problema em um capítulo a parte, no final do artigo).

De qualquer forma o XOR poderia ser usado com segurança se jamais houver uma repetição de chave. Em outras palavras, a chave deve ser tão grande quanto a mensagem e não pode ser reaproveitada. Se a mensagem tiver 1Mbit a chave terá que ter, pelo menos, 1Mbit também.

Esta limitação é uma barreira ao uso seguro do XOR, pois como usaríamos uma chave tão grande quanto a mensagem e ainda descartável. Impraticável.

Porém o algoritmo RC4 conseguiu esta façanha.