[Criptografia] Como reverter um XOR?

[Alexandre Souza]

​Olá,

Eu defini 2 strings:

0 -> Um texto;

1 -> Uma chave;

Para cada string, eu gerei uma lista/array/vetor equivalente de números inteiros, utilizando o valor de cada elemento da string (podemos entender essa string como uma lista/array/vetor) na tabela ASCII. Exemplo:

String ​[0] = "GAROA CRIPTO"

Lista de inteiros = [71, 65, 82, 79, 65, 32, 67, 82, 73, 80, 84, 79]

(Key) String [1] = "CHAVESECRETA"

Lista de inteiros = [67, 72, 65, 86, 69, 83, 69, 67, 82, 69, 84, 65]

O próximo passo foi combinar (fazer um zip) com as duas listas e utilizar XOR para cada par. Algo como:

Lista com os pares = [(71, 67), (65, 72), (82, 65), (79, 86), (65, 69), (32, 83), (67, 69), (82, 67), (73, 82), (80, 69), (84, 84), (79, 65)]

​Resultado do XOR:

[4, 9, 19, 25, 4, 115, 6, 17, 27, 21, 0, 14]

OK, eu sei qual é a chave e tenho essa lista de inteiros...como podemos recuperar a mensagem ?

Algo que eu ainda não compreendi, é como reverter um XOR. Os recursos do Python que eu usei:

"^" - operador XOR, nós podemos importar do módulo operator a função xor;
list comprehension;
ord();
range;
zip;

[ ]'s

​

[DQ]

Como eu disse na minha apresentação "AVR 100 Noção", XOR é um luxo, um símbolo de ostentação! Qualquer programador usa AND e OR, mas só a elite usa XOR...

Brincadeira a parte, o xor não é complicado, mas tem algumas propriedades interessantes que levam a resultados inesperados. Se você olhar a "tabela verdade"

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

vai reparar algumas coisas interessantes:

a ^ b = b ^ a (comutativa)
a ^ 0 = a
a ^ 1 = ~a
a ^ a = 0 (velho truque jedi para zerar registradores em assembler)

o uso do XOR na criptografia se deve à segunda e à quarta propriedade da lista assima, em conjunto com a associativa:

(a ^ b) ^ b =  a ^ (b ^ b) = a ^ 0 = a

Deu para ver o que você precisa fazer?

Outro velho truque jedi:

a := a ^ b
b := a ^ b
a := a ^ b

onde := é atribuição; a sequência acima troca o conteúdo de duas variáveis sem usar uma variável temporária

DQ

[Alexandre Souza]

DQ,

"(a ^ b) ^ b =  a ^ (b ^ b) = a ^ 0 = a"

(a ^ b) -> resultado do meu XOR (texto + chave)

(a ^ b) ^b -> com o resultado, aplico XOR utilizando os inteiros relacionados a minha chave. Exemplo do que eu entendi:

"GAROA CRIPTO" -> texto

"CHAVESECRETA" -> chave

Eu pego apenas o primeiro item de cada:

G = 71, C = 67

(a ^ b) = ('G' ^ 'C') = (71 ^ 67) = 4

(a ^ b) ^ b = (71 ^ 67) ^ 67 = (4 ^ 67) = 71

E isso eu aplico ao texto todo. Substituindo a expressão toda, seria algo como (utilizando o exemplo acima):

(a ^ b) ^ b =  a ^ (b ^ b) = a ^ 0 = a

(71 ^ 67) ^ 67 = 71 ^ (67 ^ 67) = 71 ^ 0 = 71

[ ]'s

[Alexandre Souza]

Algo que eu esqueci:

Ainda pensando na lista de inteiro e etc e tal, eu tenho:

71 ^ 67 = 4

71 = 4 ^ 67

Desde que eu tenha 2 valores - resultado + texto, resultado + chave... eu consigo obter o outro, certo?

Valeu, DQ! =]

[ ]'s 

[DQ]

Exato!

Portanto, se você tiver o texto original e o criptografado, você consegue obter a chave.

DQ

[Samuel Lopes Grigolato]

Apenas adicionando um pouco, eu mudaria o texto da pergunta, pois reverter o XOR seria uma outra coisa.

Uma função que reverte f(x), é uma função r(x) tal que r(f(x)) = x. Isso implica que a função f(x) é injetora (na verdade precisa ser bijetora, ou então assumir que r(x) será indefinido para algum x). Se ela não for, teremos várias possibilidades de coeficientes e portanto não conseguiremos reverter no sentido que se está sendo buscado. Exemplo besta:

f(x) = |x| (valor absoluto de x)

Função que "reverte" f(x):

r(x) = { x, -x } (tanto x quanto seu oposto servem como resposta, portanto temos um conjunto e não uma única solução)

Como r(f(x)) != x, não podemos dizer que é uma reversão.

Podemos ver que o XOR (f(x, y) = x^y) não é uma função injetora, visto que mais de uma tupla de entrada gera a mesma saída, logo, ele não possui reversa. A diferença é que estamos nos permitindo usar um dos termos da tupla para reverter, o que muda totalmente a figura. Fixando um dos termos, nossa função passa a ser:

f(x) = x^0 (ou x^1)

Que é uma função bijetora, cuja reversa é (valeu DQ pelos insights) ela própria:

r(x) = x^0 (ou x^1) = f(x)

Podemos testar, para todo x do domínio {0,1}, que r(f(x)) ou f(f(x)) é igual a x. Não precisamos testar para um domínio maior, pois, é fácil demonstrar que a prova no domínio {0, 1} pode ser levada por indução para números com mais "casas", devido ao fato do XOR ser uma operação que opera isoladamente bit a bit (bitwise).

Atte.,

Samuel.

PS: esse truque jedi das variáveis é demais... kkkkkkk.. não conhecia..

--
.--. .- .-. .- .--. --- ... - .- .-. . ... -.-. .-. . ...- .- .--. .- .-. .- .... .- -.-. -.- . .-. ... .--. .- -.-. . ... .--. .- - --. --- --- --. .-.. . --. .-. --- ..- .--. ... -.. --- - -.-. --- --
Regras da Lista: http://garoa.net.br/wiki/Lista:LeiaAntesDeClicarNoSend
Para mais informações sobre o Garoa Hacker Clube acesse http://garoa.net.br
Maiores opções sobre o Google Groups, visite: http://groups.google.com/group/hackerspacesp
.--. .- .-. .- -- .- .. ... .. -. ..-. --- .-. -- .- . ... .- -.-. . ... ... . --- .-- .. -.- ..
Epoch 0 <=> Fundação: 1298244863 s ~ 2.408064*10^52 tP (tempos de Planck)