Lógica binária XOR

Se você já viu a aula sobre a cifra de chave única, você sabe ela é a cifra de troca suprema. Ela envolve a aplicação de uma lista aleatória de trocas igual ao comprimento da mensagem. É importante entender exatamenta como e por que a cifra de chave única é inquebrável, ou, perfeitamenta secreta.

Para entender o porquê, precisamos primeiro introduzir as operações AND, OR e XOR (E, OU e OU Exclusivo, em português) de bit a bit. Especificamente por que XOR deve ser usado ao executar a cifra de chave única em computadores. Bit a bit significa simplesmente que estamos lidando com os bits individuais, ou números binários. Em qualquer esquema de criptografia moderno/informatizado, representamos nossos símbolos usando dígitos binários. Se você esqueceu o motivo, você pode conferir este vídeo sobre a memória do computador

Vamos começar com um exemplo visual, criptografando a cor do avatar folha verde da Khan Academy.

Como transformar uma cor em um número? Na sua tela você está olhando para cores HTML que são definidas usando o modelo de cor RGB. Esse é um modelo aditivo baseado na mistura de quantidades especificas de luz vermelha, verde e azul (Red, Green e Blue em inglês).

Podemos definir exatamente a quantidade de vermelho, verde e azul utilizando um número de 0 a 255. Preto é totalmente desligado (0,0,0), enquanto branco é totalmente ligado (255,255,255). Entre esses dois códigos de cores há 16 milhões de cores possíveis (256 * 256 * 256). Em seguida, vamos procurar o verde do avatar da Khan Academy em qualquer ferramenta de edição de imagem:

Observe que a cor é apresentada como VERMELHO=156, VERDE=181, AZUL=58.

Escrevendo esses números em binário, temos:
VERMELHO=10011100, VERDE=10110101, AZUL=00111010.

Podemos colocá-los juntos como: 100111001011010100111010

Agora vamos dizer que você gerou uma sequência de troca jogando uma moeda e convertendo o resultado em binário como:

Vamos pensar em como podemos aplicar essa sequência de troca na nossa cor para criptografá-la usando a cifra de chave única.

Para fazer a cifra de chave única funcionar, precisamos escolher a operação correta para que a sequência resultante possa ser qualquer cor. Vamos verificar três operações diferentes: AND, OR e XOR.

O operador AND também é conhecido como conjunção lógica e funciona como a multiplicação. 
Ele exibe um 1 somente se todas as entradas forem 1. Aqui está a tabela verdade:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

Isso resulta em um roxo muito escuro. Observe que quando executamos a operação AND em qualquer número binário, a sequência resultante não pode ser maior. In our color example this eliminates many possible shades as it pushes the color towards black.

O operador OR também é conhecido como disjunção lógica. Ele exibe um 1 sempre que uma ou mais de suas entradas forem 1. Aqui está a tabela verdade:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

Isso resulta em um roxo claro. Observe que quando executamos a operação OR em qualquer sequência binária, a sequência resultante não pode ser menor. Isso elimina muitas possibilidades, pois aproxima a cor do branco.

O operador XOR exibe um 1 sempre que as entradas não forem compatíveis, o que ocorre quando uma das duas entradas for exclusivamente verdade. É o mesmo que adição mod 2. Aqui está a tabela verdade:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

Isso resulta num roxo um pouco mais escuro em comparação à operação OR. Observe que quando executamos a operação XOR em uma sequência binária, o resultado pode ser qualquer sequência possível. Dada uma cor criptografada, tudo que nós sabemos é que a cor original“tem a mesma probabilidade de ser uma cor qualquer”. Não temos nenhuma informação que poderia melhorar um palpite às cegas (1/16 milhões).

Por fim, vamos fazer uma demonstração visual para que possamos ver a cifra de chave única em ação. Então, podemos ganhar mais pontos de energia!