Lemat dotyczący spiętrzenia

W kryptoanalizie lemat spiętrzania jest zasadą stosowaną w kryptoanalizie liniowej do konstruowania liniowych przybliżeń działania szyfrów blokowych . Zostało wprowadzone przez Mitsuru Matsui (1993) jako narzędzie analityczne do kryptoanalizy liniowej. Lemat stwierdza, że ​​obciążenie (odchylenie wartości oczekiwanej od 1/2) liniowej funkcji logicznej (klauzula XOR) niezależnych binarnych zmiennych losowych jest powiązane z iloczynem odchyleń wejściowych:

${\ Displaystyle \ epsilon (X_ {1} \ oplus X_ {2} \ oplus \ cdots \ oplus X_{n})=2^{n-1}\prod _{i=1}^{n}\epsilon (X_{i})}$

Lub

$\ oplus X_ {2} \ oplus \ cdots \ oplus X_ {n}) =\prod _{i=1}^{n}I(X_{i})}$

gdzie ${\ Displaystyle \ epsilon \ in [- {\ tfrac {1} {2}}, {\ tfrac {1} {2}}]}$ jest odchyleniem (w kierunku zera) i ${\ Displaystyle I \ w [-1,1]}$ brak równowagi :

${\ Displaystyle \ epsilon (X) = P (X = 0) - {\ Frac {1} {2}}}$

${\ Displaystyle I (X) = P (X = 0) -P (X = 1) = 2 \ epsilon (X)}$ .

I odwrotnie, jeśli lemat nie jest spełniony, wówczas zmienne wejściowe nie są niezależne.

Interpretacja

Lemat implikuje, że niezależne zmienne binarne wykonujące XOR zawsze zmniejszają odchylenie (lub przynajmniej go nie zwiększają); ponadto wynik jest nieobciążony wtedy i tylko wtedy, gdy istnieje co najmniej jedna nieobciążona zmienna wejściowa.

${\ Displaystyle P (X = Y) -P (X \ równoważnik Y)}$ ilość jest miarą korelacji i równą $\ Displaystyle$$oplus$$)}$ ; ${\ displaystyle I (X)}$ można $interpretować$ jako $z$ .

Sformułowanie wartości oczekiwanej

$przyjmują$ spiętrzaniu można wyrazić bardziej naturalnie, gdy w Jeśli wprowadzimy zmienne ${\ Displaystyle \ chi _ {i} = 1-2X_ {i} = (-1) ^ {X_ {i}}$ } 0 do 1 i 1 do -1), następnie po kontroli operacja XOR przekształca się w produkt:

${\ displaystyle \ chi _ {1} \ chi _ {2}\cdots \chi _{n}=1-2(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=(-1)^{X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}}}$

a ponieważ oczekiwane wartości to brak równowagi, lemat stwierdza teraz: ${\ displaystyle E (\ chi _ {i}) = I (X_ {i})}$

${\ Displaystyle E \ lewo (\ prod _ {i = 1} ^ {n} \ chi _ {i} \ prawo) = \prod _{i=1}^{n}E(\chi _{i})}$

co jest znaną właściwością wartości oczekiwanej dla zmiennych niezależnych .

W przypadku zmiennych zależnych powyższe sformułowanie zyskuje (dodatni lub ujemny) składnik kowariancji , zatem lemat nie jest spełniony. W rzeczywistości, ponieważ dwie Bernoulliego są niezależne wtedy i tylko wtedy, gdy są nieskorelowane (tj. mają zerową kowariancję; patrz nieskorelowanie ), mamy odwrotność lematu o stosowaniu: jeśli to nie zachodzi, zmienne nie są niezależne (nieskorelowane) .

Wyprowadzenie logiczne

Lemat o stosowaniu pozwala kryptoanalitykowi określić prawdopodobieństwo, że równość:

${\ Displaystyle X_ {1} \ oplus X_ {2} \ oplus \ cdots \ oplus X_ {n} = 0}$

zachodzi, gdzie X są zmiennymi binarnymi (tzn. bitami: 0 lub 1) .

Niech P (A) oznacza „prawdopodobieństwo, że A jest prawdą”. Jeśli jest równe jeden , A na pewno się wydarzy, a jeśli jest równe zero, A nie może się wydarzyć. Przede wszystkim rozważamy lemat dotyczący spiętrzania dla dwóch zmiennych binarnych, gdzie i ${\ Displaystyle P (X_ {2} = 0) = p_ {2}}$${1} = 0) =$ X_ .

Teraz rozważymy:

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$

Ze względu na właściwości operacji xor jest to równoważne

${\ Displaystyle P (X_ {1} = X_ {2})}$

X ₁ = X ₂ = 0 i X ₁ = X ₂ = 1 są zdarzeniami wzajemnie się wykluczającymi , więc możemy powiedzieć

${\ Displaystyle P (X_ {1} = X_ {2}) = P (X_ {1} = X_ {2} = 0) + P (X_ {1} = X_ {2} = 1) = P (X_ { 1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1)}$

Musimy teraz przyjąć główne założenie lematu o stosowaniu: zmienne binarne, z którymi mamy do czynienia, są niezależne ; oznacza to, że stan jednego nie ma wpływu na stan żadnego z pozostałych. W ten sposób możemy rozszerzyć funkcję prawdopodobieństwa w następujący sposób:

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$	${\ Displaystyle = P (X_ {1} = 0) P (X_ {2} = 0) +P(X_{1}=1)P(X_{2}=1)}$
	${\ Displaystyle = p_ {1} p_ {2} + (1-p_ {1}) (1-p_ {2})}$
	${\ Displaystyle = p_ {1} p_ {2} + (1-p_ {1} -p_ {2} + p_ {1} p_ { 2})}$
	${\ Displaystyle = 2p_ {1} p_ {2} -p_ {1} -p_ {2} +1}$

Teraz wyrażamy prawdopodobieństwa p ₁ i p ₂ jako ½ + ε ₁ i ½ + ε ₂ , gdzie ε to błąd prawdopodobieństwa — wielkość, o którą prawdopodobieństwo odbiega od ½.

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$	$($
	$1/2 + \ epsilon _ {1}$
	${\ Displaystyle = 1/2 + 2 \ epsilon _ {1} \ epsilon _ {2}}$

Zatem odchylenie prawdopodobieństwa ε _1,2 dla powyższej sumy XOR wynosi 2 ε ₁ ε ₂ .

Formułę tę można rozszerzyć na więcej X w następujący sposób:

${\ Displaystyle P (X_ {1} \ oplus X_ {2} \ oplus \ cdots \ oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\epsilon _{i}}$

Zauważ, że jeśli którekolwiek z ε wynosi zero; to znaczy, że jedna ze zmiennych binarnych jest nieobciążona, cała funkcja prawdopodobieństwa będzie nieobciążona — równa ½.

Powiązana, nieco inna definicja odchylenia to ${\ Displaystyle \ epsilon _ {i} = P (X_ {i} = 1) -P (X_ {i}=0),}$ w rzeczywistości minus dwukrotność poprzedniej wartości. Zaletą jest to, że teraz z

${\ Displaystyle \ varepsilon _ {całkowita} = P (X_ {1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

mamy

${\ Displaystyle \ varepsilon _ {całkowita} = (-1) ^ {n+1} \ prod _ {i = 1} ^{n}\varepsilon _{i},}$

dodanie zmiennych losowych jest równoznaczne z pomnożeniem ich odchyleń (druga definicja).

Ćwiczyć

W praktyce X są przybliżeniami S-boxów (składników podstawieniowych) szyfrów blokowych. Zazwyczaj X są wejściami do S-boxa, a wartości Y są odpowiadającymi wyjściami. Po prostu patrząc na S-boxy, kryptoanalityk może stwierdzić, jakie są odchylenia prawdopodobieństwa. Sztuka polega na znalezieniu kombinacji wartości wejściowych i wyjściowych, których prawdopodobieństwo wynosi zero lub jeden. Im przybliżenie jest bliższe zera lub jedności, tym bardziej przydatne jest przybliżenie w kryptoanalizie liniowej.

Jednak w praktyce zmienne binarne nie są niezależne, jak zakłada się przy wyprowadzaniu lematu o stosowaniu. Stosując lemat, należy o tym pamiętać; nie jest to formuła automatycznej kryptoanalizy.

Zobacz też

• Wariancja sumy niezależnych zmiennych rzeczywistych