XOR ha la seguente tabella di verità:
0, 0 : 0
0, 1 : 1
1, 0 : 1
1, 1 : 0
Quindi per bit in un'operazione XOR, c'è una probabilità del 50% che il risultato sia 1 e il 50% di possibilità che sia 0. Se XOR è un numero casuale (tutte le possibilità erano ugualmente probabili quando create, diciamo da un CSPRNG ) e un numero non casuale, tale risultato appare casuale?
Un valore casuale non perde nessuna delle sue casualità se è combinato senza perdita di informazioni con un valore non casuale. XOR contro un valore fisso (cioè non casuale) non causa tale perdita di informazioni, cioè il valore casuale originale può essere ricreato dal risultato semplicemente XORando di nuovo con lo stesso valore fisso. Contrariamente a ciò, AND o OR causerebbero perdite di informazioni, cioè non possono essere invertiti.
Ma la casualità non aumenta neanche. Pertanto, se si XOR un valore casuale a 8 bit su un valore non casuale a 32 bit, si otterrà 8 bit di casualità, non 32 bit.
Alcuni semplici esercizi matematici possono fornirti una risposta.
Diciamo che hai una sequenza di N bit. p(n) può essere la probabilità che il numero di bit n tra N abbia valore 1. Quindi ovviamente 1-p(n) è una probabilità che sia uno 0.
Ora facciamo un XOR della precedente sequenza di N bit con una sequenza della stessa lunghezza casuale. Per questa seconda sequenza, p'(n) = 0.5 in quanto vi è uguale probabilità di avere un 0 o un 1 .
Per calcolare il p''(n) probabilmente perché il risultato sia un bit al valore uno, dobbiamo cercare i casi in cui il risultato è 1.
Ci sono due casi:
p(n) ) e il bit della seconda sequenza è 0 (probabilità 1-p'(n) ) 1-p(n) ) e il bit della seconda sequenza è 1 (probabilità p'(n) ) Quindi la probabilità p''(n) che il bit risultante alla posizione n ha valore 1 è
p(n) × (1-p'(n)) + (1-p(n)) × p'(n)
Ma dal momento che p'(n) = 0.5 = 1-p'(n) (abbiamo detto che è casuale), la formula di cui sopra si semplifica facilmente:
p''(n) = p(n) × (1 - p'(n)) + (1 - p(n)) × p'(n) p''(n) = p(n) × 0.5 + (1 - p(n)) × 0.5 p''(n) = p(n) × 0.5 + 0.5 - 0.5 × p(n) p''(n) = 0.5 La stringa risultante è casuale, non appena uno dei due XORed è casuale.
Questa è la proprietà principale dell'operazione XOR, proveniente dalla sua tabella logica, che spiega il motivo per cui la crittografia perfetta si ottiene con XORing qualcosa con una stringa casuale in quanto il risultato è casuale e quindi può essere decodificato in modo uguale a qualsiasi valore nel completo spazio di valori. E ovviamente non è pratico da usare perché richiede una sequenza casuale della stessa lunghezza di quella che deve essere crittografata, mai da riutilizzare e da condividere tra il mittente e il destinatario.
Leggi altre domande sui tag random cryptography