Sieć Feistela

W kryptografii szyfr Feistla jest symetryczną strukturą używaną do budowy szyfrów blokowych, nazwaną na cześć niemieckiego kryptografa IBM Horsta Feistla; jest on również powszechnie znany jako sieć Feistla. Duży zestaw szyfrów blokowych wykorzystuje ten schemat, w tym standard Data Encryption Standard

Struktura Feistel ma tę zaletę, że operacje szyfrowania i odszyfrowywania są bardzo podobne, a nawet identyczne w niektórych przypadkach, co wymaga jedynie odwrócenia harmonogramu kluczy. W związku z tym rozmiar kodu lub schematu wymaganego do wdrożenia takiego szyfru jest prawie o połowę mniejszy.

Konstrukcja Feistel ma charakter iteracyjny, co ułatwia implementację kryptosystemu w sprzęcie.

Sieci Feistel i podobne konstrukcje są szyframi produktowymi, a więc łączą wiele rund powtarzających się operacji, np:

Bit-shuffling (często nazywane pudełkami permutacyjnymi lub P-boxami)
Proste funkcje nieliniowe (często nazywane pudełkami zastępczymi lub S-boxami)
Liniowe mieszanie (w sensie algebry modułowej) przy użyciu XOR w celu uzyskania funkcji z dużą ilością tego, co Claude Shannon określił jako "dezorientację i dyfuzję".

Bit shuffling tworzy efekt dyfuzji, podczas gdy substytucja jest używana do dezorientacji.

Praca teoretyczna

Wiele nowoczesnych symetrycznych szyfrów blokowych wykorzystuje sieci Feistel, a struktura i właściwości szyfrów Feistel zostały szeroko zbadane przez kryptografów. W szczególności Michael Luby i Charles Rackoff przeanalizowali konstrukcję szyfrów blokowych Feistel i udowodnili, że jeśli funkcja okrągła jest kryptograficznie bezpieczną funkcją pseudolosową, z użyciem Ki jako ziarenka, to 3 rundy wystarczą, aby uczynić z szyfru blokowego pseudolosową permutację, podczas gdy 4 rundy wystarczą, aby uczynić z niego "silną" pseudolosową permutację (co oznacza, że pozostaje pseudolosowa nawet dla przeciwnika, który uzyskuje dostęp wyroczni do jego odwrotnej permutacji). Z powodu tego bardzo ważnego wyniku Luby i Rackoff, szyfr Feistela jest czasami nazywany szyfrem blokowym Luby-Rackoff. Dalsze badania teoretyczne uogólniły konstrukcję i określiły bardziej precyzyjne granice bezpieczeństwa.

Budowa

Niech F {\i1}jest ${\rm F}$ funkcją rundy i niech K 1 , K 2 , ... , K n {\i1},K_{\i0},K_{\i1},K_{\i1},{\i1},K_{\i0},{\i1},{\i1},K_{\i0},{\i1},Kldots, K_{\i0} {\i1},{\i1},K_{\i1} $K_1,K_2,\ldots,K_{n}$ {\i1}będzie $1,2,\ldots,n$ odpowiednio podklawiszami dla rund 1 , 2, ..., n {\i1,2,{\i0},n}.

Następnie podstawowa operacja jest następująca:

Podziel blok tekstowy na dwa równe kawałki, ( L 1 {\i1} L_1 , R 1 {\i1}, R 1 {\i1} R_1 )

Dla każdej rundy i = 1,2 , ... , n {\i1,2 , \i0}doty, n} $i =1,2,\dots,n$ , obliczyć (obliczyć)

L i + 1 = R i {\i1}==R_{i}\i1},} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) {\i1}=L_{i}\i1}oplus {\i1}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Wtedy szyfr jest ( R n + 1 , L n + 1 ) {\i1} $(R_{n+1}, L_{n+1})$ . (Zwykle dwie części R n R_n {\i1}i L n {\i1}{\i1}nie L_n są przełączane po ostatniej rundzie).

Rozszyfrowanie szyfru ( R n , L n ) {\i1}displaystylu (R_n, L_n) ( R_{n},L_{n})}jest realizowane poprzez obliczenie dla i = n , n - 1 , ... , 1 {\i1}displastylu i=n, n-1, \i1,\i0}ldots , 1} $i=n,n-1,\ldots,1$

R i = L i + 1 {\i1} {\i1}{\i1}Styl R_{i}=L_{i+1},} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\i1}=R_{i+1}\i1}\i1}oplus {\i1}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Wtedy ( L 1 , R 1 ) {\i1} (L_1,R_1) {\i1}jest to znowu ten prosty tekst.

Jedną z zalet tego modelu jest to, że zaokrąglona funkcja F {\i0} {\i1}jest ${\rm F}$ nie musi być odwracalna i może być bardzo złożona.

Schemat ilustruje proces szyfrowania. Deszyfrowanie wymaga jedynie odwrócenia kolejności podklasy K n , K n - 1 , ... , K 1 {\i1}, K_{\i1},K_{\i1},\i1}ldots , K_{\i1}}przy $K_{n},K_{n-1},\ldots,K_1$ użyciu tego samego procesu; jest to jedyna różnica pomiędzy szyfrowaniem a deszyfrowaniem:

Niewyważone szyfrów Feistela używa zmodyfikowanej struktury, gdzie L 1 L_1 {\i1}i R 1 {\i1}nie R_1 mają jednakowej długości. Eksperymentalnym przykładem takiego szyfru jest szyfr MacGuffina.

Konstrukcja Feistela jest również wykorzystywana w algorytmach kryptograficznych innych niż szyfry blokowe. Na przykład, schemat Optimal Asymmetric Encryption Padding (OAEP) wykorzystuje prostą sieć Feistel do randomizacji szyfrogramów w niektórych asymetrycznych schematach szyfrowania.

Praca w sieci Feistel na szyfrze blokowym, gdzie P jest tekstem prostym, a C szyfrem.

Lista szyfrów Feistela

Feistel lub zmodyfikowany Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Generalised Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Pytania i odpowiedzi

P: Co to jest szyfr Feistela?

O: Szyfr Feistela to symetryczna struktura wykorzystywana w budowie szyfrów blokowych, nazwana tak na cześć niemieckiego kryptografa IBM Horsta Feistela. Jest on również powszechnie znany jako sieć Feistela.

P: Jakie są zalety stosowania struktury Feistela?

O: Główną zaletą stosowania struktury Feistela jest to, że operacje szyfrowania i deszyfrowania są bardzo podobne, a w niektórych przypadkach nawet identyczne, wymagają jedynie odwrócenia schematu klucza. Dzięki temu wielkość kodu lub obwodu niezbędnego do realizacji takiego szyfru zmniejsza się prawie o połowę. Dodatkowo, jego iteracyjna natura ułatwia implementację kryptosystemu w sprzęcie.

P: Jak Claude Shannon opisał "zamieszanie i dyfuzję"?

O: Claude Shannon opisał "zamieszanie i dyfuzję" jako występowanie dużej ilości obu elementów, aby utrudnić atakującemu odszyfrowanie zaszyfrowanej wiadomości.

P: Jakie techniki są wykorzystywane do tworzenia zamieszania i dyfuzji?

O: Zamieszanie i dyfuzję tworzy się poprzez tasowanie bitów (często nazywane skrzynkami permutacji lub P-boxami) i proste funkcje nieliniowe (często nazywane skrzynkami substytucji lub S-boxami), a także mieszanie liniowe (w sensie algebry modułowej) za pomocą XOR. Tasowanie bitów tworzy efekt dyfuzji, natomiast podstawianie służy do wprowadzania w błąd.

P: Jakim rodzajem szyfru jest sieć Feistela?

O: Sieć Feistela to rodzaj szyfru produktowego, który łączy wiele rund powtarzających się operacji w celu bezpiecznego zaszyfrowania danych.

P: Kto opracował ten typ kryptografii?

O: Struktura Feistela została opracowana przez niemieckiego kryptografa IBM Horsta Feistela.

P: Czy Data Encryption Standard opiera się na tym typie kryptografii?

O: Tak, Data Encryption Standard korzysta z tego typu kryptografii, która wykorzystuje te same, opisane powyżej zasady tworzenia zamieszania i rozproszenia w zaszyfrowanej wiadomości.