Vés al contingut

Xifratge XOR

De la Viquipèdia, l'enciclopèdia lliure

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

A 0 = A,
A A = 0,
A B = B A,
(A B) C = A (B C),
(B A) A = B 0 = B,

on denota l'operació de disjunció exclusiva (XOR).[2] Aquesta operació de vegades s'anomena suma de mòdul 2 (o resta, que és idèntica).[3] 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

[modifica]

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
11110011 11110011 11110011 11110011
= 10100100 10011010 10011000 10011010

I a la inversa, per desxifrar-ho:

10100100 10011010 10011000 10011010
11110011 11110011 11110011 11110011
= 01010111 01101001 01101011 01101001

Ús i seguretat

[modifica]

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.[3] 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 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

[modifica]

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.[4]

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.[4]

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) [a]

Exemple d'implementació

[modifica]

Exemple en el llenguatge de programació Python. [b]

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')

Notes

[modifica]
  1. Hi ha 3 maneres d'obtenir un bit xifrat a zero amb una operació AND:
    Missatge=0, clau=0;
    Missatge=0, clau=1;
    Missatge=1, clau=0.
    Per tant, si sabem que el text xifrat és un zero, hi ha una probabilitat de 2/3 que el missatge també fos un zero per a una clau realment aleatòria. Amb XOR, hi ha exactament dues maneres, i per tant la probabilitat és 1/2 (és a dir, equiprobable, i per tant, no podem aprendre res d'aquesta informació)
  2. Això s'inspira en Richter 2012

Referències

[modifica]
  1. Tutte 1998, p. 3
  2. Lewin, 2012, p. 14-19.
  3. 3,0 3,1 Churchhouse 2002
  4. 4,0 4,1 Paar i Pelzl, 2009, p. 32–34.

Bibliografia

[modifica]