Hromadné lemma - Piling-up lemma

v dešifrování, hromadění lemmatu je princip používaný v lineární dešifrování konstruovat lineární aproximace k akci blokové šifry. To bylo představeno Mitsuru Matsui (1993) jako analytický nástroj pro lineární dešifrování.

Teorie

Hromadící se lemma umožňuje dešifrujícímu analytikovi určit pravděpodobnost že rovnost:

{ displaystyle X_ {1} oplus X_ {2} oplus cdots oplus X_ {n} = 0}

drží, kde X jsou binární proměnné (tj. bity: 0 nebo 1).

Nechat P(A) označuje „pravděpodobnost, že A je pravdivá“. Pokud se to rovná jeden „Je jisté, že A, a pokud se rovná nule, A se nemůže stát. Nejprve vezmeme v úvahu hromadění lemmatu pro dvě binární proměnné, kde ${ displaystyle P (X_ {1} = 0) = p_ {1}}$ a ${ displaystyle P (X_ {2} = 0) = p_ {2}}$ .

Nyní uvažujeme:

{ displaystyle P (X_ {1} oplus X_ {2} = 0)}

Vzhledem k vlastnostem xor operace, to je ekvivalentní k

{ displaystyle P (X_ {1} = X_ {2})}

X₁ = X₂ = 0 a X₁ = X₂ = 1 jsou vzájemně se vylučující události, takže můžeme říci

{ 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)}

Nyní musíme učinit ústřední předpoklad hromadění lemmatu: binární proměnné, se kterými máme co do činění, jsou nezávislý; to znamená, že stav jednoho nemá žádný vliv na stav kteréhokoli z ostatních. Můžeme tedy rozšířit pravděpodobnostní funkci následujícím způsobem:

${ 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}$

Nyní vyjádříme pravděpodobnosti p₁ a p₂ jako ½ + ε₁ a ½ + ε₂, kde ε jsou pravděpodobnostní předsudky - množství, které se pravděpodobnost odchyluje od ½.

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

Tedy zkreslení pravděpodobnosti ε_1,2 pro výše uvedený součet XOR je 2ε₁ε₂.

Tento vzorec lze rozšířit na více X je následující:

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

Všimněte si, že pokud je některá z ε nula; to znamená, že jedna z binárních proměnných je nestranná, celá pravděpodobnostní funkce bude nestranná - rovná se ½.

Související mírně odlišná definice zkreslení je ${ displaystyle epsilon _ {i} = P (X_ {i} = 1) -P (X_ {i} = 0),}$ ve skutečnosti mínus dvojnásobek předchozí hodnoty. Výhodou je, že nyní s

${ displaystyle varepsilon _ {celkem} = P (X_ {1} oplus X_ {2} oplus cdots oplus X_ {n} = 1) -P (X_ {1} oplus X_ {2} oplus cdots oplus X_ {n} = 0)}$

my máme

{ displaystyle varepsilon _ {total} = (- 1) ^ {n + 1} prod _ {i = 1} ^ {n} varepsilon _ {i},}

přidání náhodných proměnných činí vynásobení jejich předsudků (2. definice).

Praxe

V praxi se Xs jsou aproximace k S-boxy (substituční složky) blokových šifer. Typicky, X hodnoty jsou vstupy do S-boxu a Y hodnoty jsou odpovídající výstupy. Pouhým pohledem na S-boxy může dešifrovaný pracovník zjistit, jaké jsou předpovědi pravděpodobnosti. Trik spočívá v hledání kombinací vstupních a výstupních hodnot, které mají pravděpodobnost nula nebo jedna. Čím blíže je aproximace k nule nebo jedné, tím užitečnější je aproximace v lineární kryptoanalýze.

V praxi však binární proměnné nejsou nezávislé, jak se předpokládá v odvození hromadícího se lemmatu. Tuto úvahu je třeba mít na paměti při aplikaci lemmatu; není to vzorec automatické dešifrování.

Reference

Matsui, Mitsuru (1994). "Metoda lineární kryptoanalýzy pro DES šifru". Pokroky v kryptologii - EUROCRYPT ’93. Springer. 386–397. doi:10.1007/3-540-48285-7_33.