Szyfr Feistela - Feistel cipher

W kryptografii , A szyfr Feistel (znany również jako Luby-Rackoff szyfru blokowego ) jest symetryczna struktura stosowane w konstrukcji szyfrów blokowych , nazwany na cześć niemieckiego -born fizyka i kryptolog Horst Feistel którzy nie pionierskich badań pracując dla IBM (USA) ; jest również powszechnie znany jako sieć Feistel . Duża część szyfrów blokowych wykorzystuje ten schemat, w tym amerykański standard szyfrowania danych , radziecki / rosyjski GOST oraz nowsze szyfry Blowfish i Twofish . W szyfrze Feistela szyfrowanie i deszyfrowanie są bardzo podobnymi operacjami i obie składają się z iteracyjnego uruchamiania funkcji zwanej „funkcją okrągłą” ustaloną liczbę razy.

Historia

Wiele nowoczesnych symetrycznych szyfrów blokowych jest opartych na sieciach Feistela. Sieci Feistel po raz pierwszy pojawiły się komercyjnie w szyfrze Lucifera IBM , zaprojektowanym przez Horsta Feistela i Dona Coppersmitha w 1973 roku. Sieci Feistel zyskały uznanie, kiedy rząd federalny USA przyjął DES (szyfr oparty na Lucyferze, ze zmianami wprowadzonymi przez NSA ) w 1976 roku. Podobnie jak inne komponenty DES, iteracyjny charakter konstrukcji Feistel ułatwia implementację kryptosystemu w sprzęcie (szczególnie na sprzęcie dostępnym w czasie projektowania DES).

Projekt

Sieć Feistel wykorzystuje funkcję okrągłą, funkcję , która pobiera dwa wejścia, blok danych i podklucz, i zwraca jedno wyjście tego samego rozmiaru co blok danych. W każdej rundzie funkcja rundy jest uruchamiana na połowie danych do zaszyfrowania, a jej dane wyjściowe są poddawane XORowaniu z drugą połową danych. Jest to powtarzane określoną liczbę razy, a ostatecznym wynikiem są zaszyfrowane dane. Ważną zaletą sieci Feistel w porównaniu z innymi projektami szyfrów, takimi jak sieci z substytucją i permutacją, jest to, że cała operacja jest odwracalna (to znaczy, że zaszyfrowane dane można odszyfrować), nawet jeśli funkcja rundy sama w sobie nie jest odwracalna. Okrągła funkcja może być dowolnie skomplikowana, ponieważ nie musi być zaprojektowana jako odwracalna. Ponadto operacje szyfrowania i deszyfrowania są bardzo podobne, a w niektórych przypadkach nawet identyczne, wymagając jedynie odwrócenia harmonogramu kluczy . Dlatego rozmiar kodu lub obwodów wymaganych do implementacji takiego szyfru jest prawie o połowę mniejszy.

Praca teoretyczna

Struktura i właściwości szyfrów Feistela zostały szczegółowo przeanalizowane przez kryptologów .

Michael Luby i Charles Rackoff przeanalizowali konstrukcję szyfru Feistela i udowodnili, że jeśli funkcja okrągła jest kryptograficznie bezpieczną funkcją pseudolosową , z K _i użytym jako ziarno, to wystarczą 3 rundy, aby szyfr blokowy był permutacją pseudolosową , podczas gdy 4 rundy są wystarczające, aby uczynić ją „silną” pseudolosową permutacją (co oznacza, że pozostaje pseudolosową nawet dla przeciwnika, który uzyska dostęp wyroczni do jej odwrotnej permutacji). Z powodu tego bardzo ważnego wyniku Luby'ego i Rackoffa, szyfry Feistela są czasami nazywane szyframi blokowymi Luby-Rackoffa.

Dalsze prace teoretyczne nieco uogólniły konstrukcję i dały bardziej precyzyjne granice bezpieczeństwa.

Szczegóły konstrukcyjne

Niech będzie funkcją rundy i odpowiednio podklawiszami dla rund . ${\ displaystyle {\ rm {F}}}$ ${\ Displaystyle K_ {0}, K_ {1}, \ ldots, K_ {n}}$ ${\ Displaystyle 0,1, \ ldots, n}$

Wtedy podstawowa operacja wygląda następująco:

Podziel blok tekstu jawnego na dwie równe części, ( , ) ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

Dla każdej rundzie , obliczyć ${\ displaystyle i = 0,1, \ kropki, n}$

{\ Displaystyle L_ {i + 1} = R_ {i} \,}

{\ Displaystyle R_ {i + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}

Gdzie oznacza XOR . Wtedy jest szyfrogram . ${\ displaystyle \ oplus}$ ${\ Displaystyle (R_ {n + 1}, L_ {n + 1})}$

Odszyfrowanie tekstu zaszyfrowanego odbywa się przez obliczenia dla ${\ Displaystyle (R_ {n + 1}, L_ {n + 1})}$ ${\ Displaystyle i = n, n-1, \ ldots, 0}$

{\ Displaystyle R_ {i} = L_ {i + 1} \,}

{\ Displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ {i + 1}, K_ {i}).}

Potem znowu tekst jawny. ${\ displaystyle (L_ {0}, R_ {0})}$

Diagram ilustruje zarówno szyfrowanie, jak i deszyfrowanie. Zwróć uwagę na odwrócenie kolejności podklucza do odszyfrowania; to jedyna różnica między szyfrowaniem a deszyfrowaniem.

Niezrównoważony szyfr Feistela

Niezrównoważone szyfry Feistela używają zmodyfikowanej struktury, gdzie i nie są równej długości. Skipjack szyfr jest przykładem takiego szyfru. Texas Instruments transponder podpis cyfrowy używa własnego niesymetrycznego sieć feistela do wykonywania uwierzytelniania challenge-response . ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

Thorp Shuffle jest skrajnym przypadku niezrównoważonej sieć feistela, w której jedna strona jest pojedynczy bit. Ma to lepsze bezpieczeństwo niż zrównoważony szyfr Feistela, ale wymaga więcej rund.

Inne zastosowania

Konstrukcja Feistela jest również wykorzystywana w algorytmach kryptograficznych innych niż szyfry blokowe. Na przykład, schemat optymalnego asymetrycznego szyfrowania szyfrowania (OAEP) wykorzystuje prostą sieć Feistel do losowego ustawiania szyfrogramów w pewnych asymetrycznych schematach szyfrowania klucza .

Uogólniony algorytm Feistela może być użyty do tworzenia silnych permutacji w małych domenach o rozmiarze nie potęgi dwóch (patrz szyfrowanie z zachowaniem formatu ).

Sieci Feistel jako element projektu

Niezależnie od tego, czy cały szyfr jest szyfrem Feistela, czy nie, sieci podobne do Feistela mogą być używane jako element projektu szyfru. Na przykład MISTY1 jest szyfrem Feistela wykorzystującym trzyrundową sieć Feistel w swojej funkcji rundy, Skipjack jest zmodyfikowanym szyfrem Feistela używającym sieci Feistel w permutacji G, a Threefish (część Skein ) jest szyfrem blokowym innym niż Feistel, który używa funkcji MIX podobnej do Feistela.

Lista szyfrów Feistela

Feistel lub zmodyfikowany Feistel:

Uogólniony Feistel:

Zobacz też

Kryptografia
Szyfr strumieniowy
Sieć substytucyjno-permutacyjna
Schemat podnoszenia dla dyskretnej transformaty falkowej ma prawie taką samą strukturę
Szyfrowanie z zachowaniem formatu
Schemat Lai-Massey

Languages

In other projects