Sieć Feistela — definicja i zastosowania w szyfrach blokowych

Sieć Feistela — definicja i zastosowania w szyfrach blokowych: budowa, zalety, implementacja (np. DES) i wpływ na bezpieczeństwo kryptograficzne.

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.

Budowa i zasada działania

Sieć Feistla dzieli blok danych o stałym rozmiarze na dwie równe części — lewą (L) i prawą (R). Szyfrowanie odbywa się iteracyjnie przez zastosowanie wielu rund tej samej struktury. W każdej rundzie stosuje się funkcję rundową F, która przyjmuje część danych i podklucz rundy K_i i zwraca wartość, która jest następnie łączona z drugą połową bloku za pomocą operacji XOR.

Formalnie, dla rundy numer i (zakładając indeksowanie od 1), transformacja wygląda następująco:

• L_i = R_{i-1}
• R_i = L_{i-1} XOR F(R_{i-1}, K_i)

Po ostatniej rundzie (w zależności od implementacji) obie połowy mogą zostać zamienione miejscami lub pozostawione w tej samej kolejności. Odszyfrowanie uzyskuje się przez zastosowanie tych samych operacji w odwrotnej kolejności kluczy (czyli użycie K_n, K_{n-1}, ..., K_1), co czyni implementację deszyfracji bardzo podobną do szyfrowania.

Właściwości i zalety

• Odwrotność bez inwersji funkcji rundowej: Funkcja F nie musi być odwracalna. Dzięki konstrukcji Feistela cała permutacja bloku jest odwracalna nawet jeśli F nie ma odwrotności.
• Mały narzut implementacyjny: Szyfrowanie i odszyfrowywanie używają tej samej struktury kodu — wystarczy odwrócić kolejność harmonogramu kluczy.
• Łatwość implementacji sprzętowej: Struktura iteracyjna i prostota operacji (XOR, podstawienia, permutacje) sprzyjają efektywnej realizacji w układach cyfrowych.
• Elastyczność projektowa: Można stosować różne funkcje rundowe F — od prostych S-boxów i permutacji po bardziej złożone mieszania, co daje dużą swobodę w kształtowaniu bezpieczeństwa i wydajności.

Wady i ograniczenia

• Zależność od liczby i jakości rund: Bezpieczeństwo sieci Feistela silnie zależy od liczby rund oraz właściwości funkcji rundowej i harmonogramu kluczy. Zbyt mała liczba rund lub słaba F ułatwiają ataki kryptanalizy (np. różnicowej, liniowej).
• Ograniczona równoległość: Rundy są zazwyczaj ułożone sekwencyjnie — wynik kolejnej rundy zależy od poprzedniej — co utrudnia pełne równoleglenie przetwarzania pojedynczego bloku (choć wewnątrz rund można równolegle realizować pewne operacje).

Bezpieczeństwo i wyniki teoretyczne

Badania teoretyczne wykazały, że przy odpowiednio losowych niezależnych funkcjach rundowych sieci Feistela osiągają silne własności pseudolosowych. Klasyczny wynik Luby’ego i Rackoffa pokazuje, że przy pewnej liczbie rund i przy założeniu idealnych funkcji rundowych konstrukcja może działać jak pseudolosowa permutacja — co daje podstawę formalnej analizy bezpieczeństwa projektów opartych na sieciach Feistela.

W praktyce jednak funkcja rundowa i schemat kluczy są deterministyczne (zależne od projektanta szyfru), dlatego odporność na ataki (różnicowe, liniowe, związane z kolizjami itp.) musi być sprawdzona konkretnie dla danego szyfru.

Przykłady i zastosowania

Wiele znanych szyfrów blokowych wykorzystuje lub wykorzystywało schemat Feistela. Przykłady to:

• DES (Data Encryption Standard) — klasyczny i szeroko stosowany przykład sieci Feistela.
• Blowfish, CAST-128, FEAL — inne popularne szyfry oparte na Feistelu.
• GOST 28147-89 i TEA — również korzystają z wariantów konstrukcji Feistela.

Sieć Feistela pozostaje fundamentem wielu projektów szyfrów blokowych zarówno historycznie, jak i we współczesnych konstrukcjach, ze względu na prostotę, elastyczność i dobre właściwości praktyczne.

Wskazówki implementacyjne

• Dobór liczby rund: zwiększa się bezpieczeństwo kosztem wydajności — projektanci zwykle wybierają liczbę rund zapewniającą odporność na znane ataki.
• Projekt funkcji rundowej F: powinna zapewniać silną nieliniowość i dobre rozpraszanie bitów (dyfuzję), często realizowaną przy pomocy S-boxów i permutacji.
• Harmonogram kluczy: powinien unikać prostych struktur prowadzących do korelacji między rundami.
• Testowanie i analiza: przed wdrożeniem warto przeprowadzić analizę kryptograficzną (symulacje ataków różnicowych, liniowych) oraz testy implementacyjne (np. odporność na ataki bocznokanałowe).

Podsumowując, sieć Feistela to uniwersalna, sprawdzona konstrukcja do budowy szyfrów blokowych, łącząca prostotę implementacji z możliwością uzyskania wysokiego poziomu bezpieczeństwa przy właściwym doborze funkcji rundowej, liczby rund i harmonogramu kluczy.

Budowa

Niech F {\i1}jest 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} {\i1}będzie 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}, R 1 {\i1}, R 1 {\i1})

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

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

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

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

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

R i = L i + 1 {\i1} {\i1}{\i1}Styl 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})} .

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

Jedną z zalet tego modelu jest to, że zaokrąglona funkcja F {\i0} {\i1}jest 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 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 {\i1}i R 1 {\i1}nie 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.

Pytania i odpowiedzi

P: Co to jest szyfr Feistela?

P: Jakie są zalety stosowania struktury Feistela?

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

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

P: Jakim rodzajem szyfru jest sieć Feistela?

P: Kto opracował ten typ kryptografii?

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

Szukaj według litery