Xifratge XOR

En criptografia, el xifratge XOR simple és un tipus de xifratge additiu, un algorisme de xifratge que funciona segons els principis:

A $\oplus$ 0 = A,

A $\oplus$ A = 0,

A $\oplus$ B = B $\oplus$ A,

(A $\oplus$ B) $\oplus$ C = A $\oplus$ (B $\oplus$ C),

(B $\oplus$ A) $\oplus$ A = B $\oplus$ 0 = B,

on $\oplus$ denota l'operació de disjunció exclusiva (XOR). Aquesta operació de vegades s'anomena suma de mòdul 2 (o resta, que és idèntica). Amb aquesta lògica, es pot xifrar una cadena de text aplicant l'operador XOR per bits a cada caràcter amb una clau determinada. Per desxifrar la sortida, només tornar a aplicar la funció XOR amb la clau eliminarà el xifrat.

Exemple

Per exemple, la cadena "Wiki" (01010111 01101001 01101011 01101001 en ASCII de 8 bits) es pot xifrar amb la clau de repetició 11110011 de la següent manera:

	01010111 01101001 01101011 01101001
$\oplus$	11110011 11110011 11110011 11110011
=	10100100 10011010 10011000 10011010

I a la inversa, per desxifrar-ho:

	10100100 10011010 10011000 10011010
$\oplus$	11110011 11110011 11110011 11110011
=	01010111 01101001 01101011 01101001

Ús i seguretat

L'operador XOR és extremadament comú com a component en xifratges més complexos. Per si mateix, utilitzant una clau de repetició constant, un xifrat XOR simple es pot trencar de manera trivial mitjançant l'anàlisi de freqüència. Si el contingut d'algun missatge es pot endevinar o conèixer d'una altra manera, es pot revelar la clau. El seu principal mèrit és que és senzill d'implementar i que l'operació XOR és computacionalment barata. Per tant, de vegades s'utilitza un xifrat XOR repetitiu simple (és a dir, utilitzant la mateixa clau per a l'operació xor sobre totes les dades) per ocultar informació en els casos en què no es requereix cap seguretat particular. El xifratge XOR s'utilitza sovint en programari maliciós informàtic per dificultar l'enginyeria inversa.

Si la clau és aleatòria i és almenys tan llarga com el missatge, el xifrat XOR és molt més segur que quan hi ha repetició de clau dins d'un missatge. Quan el flux de claus és generat per un generador de números pseudoaleatoris, el resultat és un xifratge de flux. Amb una clau que és realment aleatòria, el resultat és un coixinet d'una sola vegada, que en teoria és irrompible .

L'operador XOR en qualsevol d'aquests xifrats és vulnerable a un atac de text pla conegut, ja que el text pla $\oplus$ text xifrat = clau . També és trivial capgirar bits arbitraris en el text pla desxifrat manipulant el text xifrat. Això s'anomena mal·leabilitat .

Utilitat en criptografia

La raó principal per la qual XOR és tan útil en criptografia és perquè està "perfectament equilibrat"; per a una entrada de text pla donada 0 o 1, el resultat del text xifrat és igualment probable que sigui 0 o 1 per a un bit de clau realment aleatori.

La taula següent mostra els quatre parells possibles de text pla i bits clau. És clar que si no se sap res sobre la clau o el text pla, no es pot determinar res només a partir del text xifrat.

Taula de traça de xifratge XOR

Text simple	clau	Text xifrat
0	0	0
0	1	1
1	0	1
1	1	0

Altres operacions lògiques com i AND o OR no tenen aquest mapeig (per exemple, AND produiria tres 0 i un 1, de manera que saber que un bit de text xifrat donat és un 0 implica que hi ha 2/3 de possibilitats que el text pla original). el bit era un 0, a diferència de la 1/2 oportunitat ideal en el cas de XOR)

Exemple d'implementació

Exemple en el llenguatge de programació Python.

from os import urandom

def genkey(length: int) -> bytes:
 """Generate key."""
 return urandom(length)

def xor_strings(s, t) -> bytes:
 """xor two strings together."""
 if isinstance(s, str):
 # Text strings contain single characters
 return b"".join(chr(ord(a) ^ ord(b)) for a, b in zip(s, t))
 else:
 # Bytes objects contain integer values in the range 0-255
 return bytes([a ^ b for a, b in zip(s, t)])

message = 'This is a secret message'
print('Message:', message)

key = genkey(len(message))
print('Key:', key)

cipherText = xor_strings(message.encode('utf8'), key)
print('cipherText:', cipherText)
print('decrypted:', xor_strings(cipherText, key).decode('utf8'))

# Verify
if xor_strings(cipherText, key).decode('utf8') == message:
 print('Unit test passed')
else:
 print('Unit test failed')

Bibliografia

• Budiman, MA; Tarigan, JT; Winata, AS «Arduino UNO and Android Based Digital Lock Using Combination of Vigenere Cipher and XOR Cipher». Journal of Physics: Conference Series. IOP Publishing, 1566, 1, 2020, pàg. 012074. Bibcode: 2020JPhCS1566a2074B. DOI: 10.1088/1742-6596/1566/1/012074. ISSN: 1742-6588.
• Churchhouse, Robert. Codes and Ciphers: Julius Caesar, the Enigma and the Internet. Cambridge University Press, 2002. ISBN 978-0-521-00890-7. 
• Garg, Satish Kumar «Cryptography Using Xor Cipher». Research Journal of Science and Technology. A and V Publications, 9, 1, 2017, pàg. 25. DOI: 10.5958/2349-2988.2017.00004.3. ISSN: 0975-4393.
• Gödel, Kurt «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I» (en alemany). Monatshefte für Mathematik und Physik, 38-38, 1, desembre 1931, pàg. 173–198. DOI: 10.1007/BF01700692. ISSN: 0026-9255.
• Lewin, Michael «All About XOR». Overload, 2, (109, juny 2012, pàg. 14–19 [Consulta: 29 agost 2021].
• Paar, Christof; Pelzl, Jan. Understanding cryptography : a textbook for students and practitioners. Springer, 2009. ISBN 978-3-642-04101-3. OCLC 567365751. 
• Richter, Wolfgang. Unbreakable Cryptography in 5 Minutes. Association for Computing Machinery, 2012. 
• Tutte, W. T. «Fish and I», 19-06-1998. [Consulta: 11 gener 2020]. Transcripció d'una classe del Prof. Tutte a la Universitat de Waterloo