FEAL

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. května 2022; ověření vyžaduje 1 úpravu .

FEAL
Tvůrce	Akihiro Shimizu a Shoji Miyaguchi (NTT)
zveřejněno	FEAL-4 v roce 1987 ; FEAL-N/NX v roce 1990
Velikost klíče	64 bit (FEAL), 128 bit (FEAL-NX)
Velikost bloku	64 bit
Počet kol	zpočátku 4, pak 8 a poté variabilní číslo (doporučeno - 32)
Typ	Síť Feistel

FEAL (Fast data Encipherment ALgorithm) je bloková šifra vyvinutá Akihiro Shimizu a Shoji Miyaguchi, zaměstnanci NTT .

Používá 64bitový blok a 64bitový klíč. Jeho myšlenkou je také vytvořit algoritmus podobný DES , ale se silnější jevištní funkcí. Použitím méně kroků by tento algoritmus mohl běžet rychleji. Kromě toho, na rozdíl od DES, funkce stage pro FEAL nepoužívá S-boxy , takže implementace algoritmu nevyžaduje další paměť pro uložení náhradních tabulek [1] .

Historie

Bloková šifra FEAL, kterou v roce 1987 publikovali Akihiro Shimizu a Shoji Miyaguchi, byla navržena tak, aby zvýšila rychlost šifrování bez snížení síly šifry ve srovnání s DES . Zpočátku algoritmus používal bloky 64 bitů, klíč 64 bitů a 4 kola šifrování. Již v roce 1988 však vyšla práce Berta Den-Boera , dokazující dostatečnost vlastnictví 10 000 šifrových textů k provedení úspěšného útoku na základě zvoleného otevřeného textu [2] . Lineární kryptoanalýza byla jednou z prvních, která byla aplikována na šifru FEAL . Konkrétně v roce 1992 Mitsuru Matsui a Atsuhiro Yamagishi dokázali, že k úspěšnému útoku stačí znát 5 šifrových textů [3] .

Pro boj s objevenými zranitelnostmi zdvojnásobili tvůrci počet kol šifrování zveřejněním standardu FEAL-8. Již v roce 1990 však Henri Gilbert zjistil, že tato šifra je také zranitelná vůči útoku v podobě shodného textu [4] . Dále v roce 1992 Mitsuru Matsui a Atsuhiro Yamagishi popsali útok v otevřeném textu vyžadující známé šifrové texty [3] . $2^{15}$

Vzhledem k velkému počtu úspěšných útoků se vývojáři rozhodli šifru dále zkomplikovat. Konkrétně v roce 1990 byl představen FEAL-N, kde N je libovolný sudý počet šifrovacích kol, a představen byl FEAL-NX, kde X (z angličtiny prodlouženo) označuje použití šifrovacího klíče rozšířeného na 128 bitů. Tato novinka však pomohla jen částečně. V roce 1991 Eli Biham a Adi Shamir pomocí metod diferenciální kryptoanalýzy ukázali možnost prolomit šifru počtem kol rychleji než hrubou silou [5] . $N\leq 31$

Nicméně, vzhledem k intenzitě výzkumu šifrovacího algoritmu komunitou, byly prokázány limity zranitelnosti šifry vůči lineární a diferenciální kryptoanalýze. Stabilitu algoritmu s více než 26 koly lineární kryptoanalýzy ukázali ve své práci Shiho Morai, Kazumaro Aoki a Kazuo Ota [6] a v práci Kazumaro Aoki, Kunio Kobayashi a Shiho Morai nemožnost použití diferenciální kryptoanalýzy na algoritmus využívající více než 32 kol bylo prokázáno šifrováním [7] .

Popis

Algoritmus FEAL-NX používá 64bitový blok otevřeného textu jako vstup do procesu šifrování [1] [8] . Proces šifrování je rozdělen do 3 fází.

Předzpracování
Iterativní výpočet
následné zpracování

Dále je popsán proces generování kulatých klíčů, od kterého začíná šifrování, a také funkce, s jejichž pomocí se transformace provádějí. ${\displaystyle S_{0},\;S_{1},\;F,\;F_{k))$

Definujme (A,B) — operaci zřetězení dvou sekvencí bitů.

Define - nulový blok o délce 32 bitů. $\phi$

Funkce S

$S_{0}(a,b)$ = otočení doleva o 2 bity $((a+b)\mod {256})$

$S_{1}(a,b)$ = otočení doleva o 2 bity $((a+b+1)\mod {256})$

F funkce

Funkce F vezme 32 datových bitů a 16 klíčových bitů a smíchá je dohromady.

$F=F(\alpha ,\beta )=(F_{0},F_{1},F_{2},F_{3})$
$\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\ beta_{1})$
${\displaystyle F_{1}=\alpha _{1}\oplus \beta _{0))$
${\displaystyle F_{2}=\alpha _{2}\oplus \beta _{1))$
${\displaystyle F_{1}=F_{1}\oplus \alpha _{0))$
${\displaystyle F_{2}=F_{2}\oplus \alpha _{3))$
$F_{1}=S_{1}(F_{1},F_{2})$
$F_{2}=S_{0}(F_{2},F_{1})$
$F_{0}=S_{0}(\alpha _{0},F_{1})$
$F_{3}=S_{1}(\alpha _{3},F_{2})$

Funkce $F_{k}$

Funkce pracuje se dvěma 32bitovými slovy. $F_{k}$

$F_{k}=F_{k}(\alpha ,\beta )=(F_{k_{0)),F_{k_{1)),F_{k_{2)),F_{k_{3 }})$
$\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\ beta _{1},\beta _{2},\beta _{3})$
$F_{k_{1}}=\alpha _{1}\oplus \alpha _{0}$
$F_{k_{2}}=\alpha _{2}\oplus \alpha _{3}$
$F_{k_{1}}=S_{1}(F_{k_{1}},(F_{k_{2}}\oplus \beta _{0}))$
$F_{k_{2}}=S_{0}(F_{k_{2}},(F_{k_{1}}\oplus \beta _{1}))$
$F_{k_{0}}=S_{0}(\alpha _{0},(F_{k_{1}}\oplus \beta _{2}))$
$F_{k_{3}}=S_{1}(\alpha _{3},(F_{k_{2}}\oplus \beta _{3}))$

Generování kulatého klíče

V důsledku generování kulatých klíčů se ze 128bitového klíče přijatého na vstupu získá sada N + 8 kulatých klíčů , každý o délce 16 bitů . Tento výsledek je získán jako výsledek následujícího algoritmu. $K_{i}$

Rozdělení vstupní klávesy na levou a pravou klávesu: , mají 64 bitů. $K=(K_{L},K_{R})$
Zpracování klíčů $K_{R}=(K_{R1},K_{R2})$
Zavedení dočasné proměnné pro : $Q_{r}$ $1\leq r\leq {\frac {N}{2}}+4$
- $Q_{r}=K_{R1}\oplus K_{R2},\;r=3i-2,\;i\in \mathbb {N}$
- $Q_{r}=K_{R1},\;r=3i-1,\;i\in \mathbb {N}$
- $Q_{r}=K_{R2},\;r=3i,\;i\in \mathbb {N}$
Zpracování klíčů $K_{L}=(A_{0},B_{0})$
Zavedení dočasné proměnné $D_{0}=\phi$
Sekvenční výpočty $K_{i}$
1. $D_{r}=A_{r-1}$
2. $A_{r}=B_{r-1}$
3. $B_{r}=F_{k}(A_{r-1},(B_{rq}\oplus D_{r-1})\oplus Q_{r)))=(B_{r_{0} },B_{r_{1}},B_{r_{2}},B_{r_{3}})$
4. $K_{2(r-1)}=(B_{r_{0)),B_{r_{1)))$
5. $K_{2(r-1)+1}=(B_{r_{2)),B_{r_{3)))$

Předzpracování

V počáteční fázi je datový blok připraven pro postup iterativního šifrování. $P$

$P=(L_{0},R_{0})$
$(L_{0},R_{0})=(L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{ N+3})$
$(L_{0},R_{0})=(L_{0},R_{0})\oplus (\phi ,L_{0})$

Iterativní zpracování

V této fázi se s datovým blokem provede N kol míchání bitů podle následujícího algoritmu.

$R_{r}=L_{r-1}\oplus F(R_{r-1},K_{r-1})$
$L_{r}=R_{r-1}$

Následné zpracování

Úkolem této fáze je připravit téměř připravený šifrový text k vydání.

$P=(R_{N},L_{N})$
$P=P\oplus (\phi ,R_{N})$
$P=P\oplus (K_{N+4},K_{N+5},K_{N+6},K_{N+7})$

Stejný algoritmus lze použít pro dešifrování. Jediný rozdíl je v tom, že při dešifrování se obrátí pořadí, ve kterém jsou části klíče použity.

Aplikace

Ačkoli byl algoritmus FEAL původně koncipován jako rychlejší náhrada za DES, včetně použití šifrování v čipových kartách, množství zranitelností, které se v něm rychle našly, ukončilo vyhlídky na použití tohoto algoritmu. Například v práci Eli Biham a Adi Shamir , publikované v roce 1991, byla prokázána dostatečnost 8 vybraných otevřených textů pro prolomení šifry FEAL-4, 2000 pro prolomení šifry FEAL-8 a pro FEAL-16 [5] . . Všechna tato čísla jsou výrazně nižší než počet vybraných otevřených textů potřebných k útoku na DES a skutečnost, že FEAL-32 je dostatečně spolehlivá, je spíše k ničemu, protože DES dosahuje srovnatelné spolehlivosti s výrazně menším počtem nábojů, čímž FEAL připravuje o výhodu, která byla původně zamýšleli tvůrci.. $2^{28}$

V tuto chvíli je na oficiálních stránkách autorů šifry - společnosti NTT , v popisu šifry FEAL umístěno upozornění, že NTT doporučuje nepoužívat šifru FEAL, ale používat šifru Camelia , vyvinutou rovněž tímto společnosti z důvodu spolehlivosti a rychlosti šifrování [9] .

Příspěvek k rozvoji kryptografie

Vzhledem k tomu, že šifra FEAL byla vyvinuta poměrně brzy, posloužila jako vynikající předmět školení pro kryptology po celém světě [10] .

Kromě toho byla na jeho příkladu objevena lineární kryptoanalýza. Mitsuru Matsui , vynálezce lineární kryptoanalýzy, ve své první práci na toto téma zvažoval právě FEAL a DES.

Poznámky

↑ 1 2 Panasenko, 2009 .
↑ Búr, 1988 .
↑ 1 2 Matsui, Yamagishi, 1992 .
↑ Gilbert, Chasse, 1990 .
↑ 1 2 Biham, Shamir, 1991 .
↑ Kazuo Ohta, Shiho Moriai, Kazumaro Aoki. Zlepšení vyhledávacího algoritmu pro nejlepší lineární výraz // Sborník příspěvků z 15. výroční mezinárodní kryptologické konference o pokroku v kryptologii. — Londýn, Spojené království, Spojené království: Springer-Verlag, 1995-01-01. — S. 157–170 . — ISBN 3540602216 .
↑ Aoki, Kobayashi, Moriai, 1997 .
↑ Specifikace šifrovacího algoritmu FEAL-N(NX) . Získáno 3. prosince 2016. Archivováno z originálu dne 23. ledna 2021. (neurčitý)
↑ NTT Encryption Archive List (downlink) . info.isl.ntt.co.jp. Získáno 27. listopadu 2016. Archivováno z originálu 7. října 2016. (neurčitý)
↑ Schneier B. Samostudijní kurz dešifrování blokových šifer . — Per. z angličtiny Bybin S.S. Archivováno 2. dubna 2022 na Wayback Machine

Literatura

Shimizu A. , Miyaguchi S. Fast Data Encipherment Algorithm FEAL // Advances in Cryptology - EUROCRYPT '87 : Workshop on the Theory and Application of Cryptographic Techniques Amsterdam, Nizozemsko, 13.–15. dubna 1987 sborník / D. Chaum Price , W. L. - Springer Science + Business Media , 1988. - S. 267-278. — 316 s. — ISBN 978-3-540-19102-5 — doi:10.1007/3-540-39118-5_24
Boer B. d. Cryptanalysis of FEAL // Advances in Cryptology - EUROCRYPT '88 :Workshop on the Theory and Application of Cryptographic Techniques, Davos, Švýcarsko, 25.-27. května 1988. Sborník / C. G. Günther - Springer Science+Business Media , 1988 . 293-299. — 383 s. — ISBN 978-3-540-45961-3 — doi:10.1007/3-540-45961-8_27
Miyaguchi S. The FEAL-8 Cryptosystem and a Call for Attack // Pokroky v kryptologii - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G Brassard - Berlin , Heidelberg , New York, NY , Londýn [atd.] : Springer New York , 1990. - S. 624-627. - ( Lecture Notes in Computer Science ; Vol. 435) - ISBN 978-0-387-97317-3 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/0-387-34805-0_59
Miyaguchi S. The FEAL Cipher Family // Pokroky v kryptologii - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, 11.-15.srpna 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 1991. - S. 628-638. - ( Lecture Notes in Computer Science ; Vol. 537) - ISBN 978-3-540-54508-8 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-38424-3_46
Murphy S. Kryptanalýza FEAL-4 s 20 vybranými otevřenými texty (anglicky) // Journal of Cryptology / I. Damgård - Springer Science + Business Media , International Association for Cryptologic Research , 1990. - Vol. 2, Iss. 3. - S. 145-154. — ISSN 0933-2790 ; 1432-1378 – doi:10.1007/BF00190801
Gilbert H. , Chassé G. Statistical Attack of the FEAL-8 Cryptosystem // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlín , Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 1991. - S. 22-33. - ( Lecture Notes in Computer Science ; Vol. 537) - ISBN 978-3-540-54508-8 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-38424-3_2
Biham E. , Shamir A. Diferenciální kryptoanalýza Feal a N-Hash // Pokroky v kryptologii - EUROCRYPT '91 : Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, duben 8–11, 1991. Proceedings / D. W. Davies - Berlin : Springer Berlin Heidelberg , 1991. - S. 1-16. - ISBN 978-3-540-54620-7 - doi:10.1007/3-540-46416-6_1
Tardy-Corfdir A. , Gilbert H. Známý prostý textový útok FEAL-4 a FEAL-6 // Pokroky v kryptologii — CRYPTO'91 :11. výroční mezinárodní kryptologická konference, Santa Barbara, Kalifornie, USA, 1991, Proceedings / J. Feigenbaum - Berlin , Heidelberg , New York, NY , Londýn [atd.] : Springer Science + Business Media , 1992. - 484 s. - ( Lecture Notes in Computer Science ; Vol. 576) - ISBN 978-3-540-55188-1 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-46766-1
Matsui M. , Yamagishi A. A New Method for Known Plaintext Attack of FEAL Cipher // Advances in Cryptology — EUROCRYPT '92 : Workshop onthe Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24-28, 1992 Proceedings Rueppel - Springer, Berlín, Heidelberg , 1993. - S. 81-91. — 491 s. - ISBN 978-3-540-56413-3 - doi:10.1007/3-540-47555-9
Aoki K. , Kobayashi K. , Moriai S. Nejlepší vyhledávání diferenciálních charakteristik FEAL // Rychlé softwarové šifrování :, FSE'97, Haifa, Izrael, 20. až 22. ledna 1997, Proceedings / E. Biham - Berlín , Heidelberg , New York, NY , Londýn [atd.] : Springer Science + Business Media , 1997. - S. 41-53. — 299 p. - ( Lecture Notes in Computer Science ; Vol. 1267) - ISBN 978-3-540-63247-4 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/BFB0052333
Panasenko S. P. Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - S. 206-212. — 576 s. — ISBN 978-5-9775-0319-8

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsobem ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher