FEAL

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. maj 2022; verifikation kræver 1 redigering .

FEAL
Skaber	Akihiro Shimizu og Shoji Miyaguchi (NTT)
offentliggjort	FEAL-4 i 1987 ; FEAL-N/NX i 1990
Nøglestørrelse	64 bit (FEAL), 128 bit (FEAL-NX)
Blokstørrelse	64 bit
Antal runder	først 4, derefter 8 og derefter et variabelt tal (anbefalet - 32)
Type	Feistel netværk

FEAL (Fast data Encipherment ALgorithm) er en blokchiffer udviklet af Akihiro Shimizu og Shoji Miyaguchi, ansatte i NTT .

Den bruger en 64-bit blok og en 64-bit nøgle. Hans idé er også at skabe en algoritme , der ligner DES , men med en stærkere scenefunktion. Ved at bruge færre trin kunne denne algoritme køre hurtigere. Derudover, i modsætning til DES, bruger scenefunktionen for FEAL ikke S-bokse , så implementeringen af algoritmen kræver ikke yderligere hukommelse til at gemme erstatningstabeller [1] .

Historie

Udgivet i 1987 af Akihiro Shimizu og Shoji Miyaguchi, blev FEAL-blokchifferet designet til at øge krypteringshastigheden uden at forringe chifferens styrke sammenlignet med DES . Til at begynde med brugte algoritmen blokke på 64 bit, en nøgle på 64 bit og 4 omgange kryptering. Allerede i 1988 blev Bert Den-Boers værk udgivet , hvilket beviste tilstrækkeligheden af at eje 10.000 chiffertekster til at udføre et vellykket angreb baseret på en valgt klartekst [2] . Lineær kryptoanalyse var en af de første, der blev anvendt på FEAL-chifferet . Især i 1992 beviste Mitsuru Matsui og Atsuhiro Yamagishi , at det er nok at kende 5 chiffertekster for at udføre et vellykket angreb [3] .

For at bekæmpe de opdagede sårbarheder fordoblede skaberne antallet af krypteringsrunder ved at udgive FEAL-8-standarden. Imidlertid opdagede Henri Gilbert allerede i 1990, at denne chiffer også var sårbar over for et matchet-klartekst-angreb [4] . Yderligere i 1992 beskrev Mitsuru Matsui og Atsuhiro Yamagishi et klartekstangreb, der kræver kendte chiffertekster [3] . $2^{15}$

På grund af det store antal vellykkede angreb besluttede udviklerne at komplicere chifferen yderligere. I 1990 blev nemlig FEAL-N introduceret, hvor N er et vilkårligt lige antal krypteringsrunder, og FEAL-NX blev introduceret, hvor X (fra engelsk udvidet) betegner brugen af en krypteringsnøgle udvidet til 128 bit. Denne innovation hjalp dog kun delvist. I 1991 viste Eli Biham og Adi Shamir , ved hjælp af metoder til differentiel kryptoanalyse , muligheden for at bryde en chiffer med antallet af runder hurtigere end brute force [5] . $N\leq 31$

Men på grund af intensiteten af forskning i krypteringsalgoritmen fra fællesskabet, er grænserne for chifferens sårbarhed over for lineær og differentiel kryptoanalyse blevet bevist. Stabiliteten af en algoritme med mere end 26 runder til lineær kryptoanalyse blev vist i deres arbejde af Shiho Morai, Kazumaro Aoki og Kazuo Ota [6] , og i arbejdet af Kazumaro Aoki, Kunio Kobayashi og Shiho Morai, umuligheden af at anvende differentiel kryptoanalyse til en algoritme ved hjælp af mere end 32 runder blev bevist kryptering [7] .

Beskrivelse

FEAL-NX-algoritmen bruger en 64-bit almindelig tekstblok som input til krypteringsprocessen [1] [8] . Krypteringsprocessen er opdelt i 3 trin.

Forbehandling
Iterativ beregning
efterbehandling

Derudover beskrives processen med at generere rundnøgler, hvorfra kryptering begynder, samt de funktioner , ved hjælp af hvilke transformationer udføres. ${\displaystyle S_{0},\;S_{1},\;F,\;F_{k))$

Lad os definere (A,B) — driften af sammenkædning af to sekvenser af bit.

Definer - en nulblok med en længde på 32 bit. $\phi$

S funktion

$S_{0}(a,b)$ = drej 2 bit til venstre $((a+b)\mod {256})$

$S_{1}(a,b)$ = drej 2 bit til venstre $((a+b+1)\mod {256})$

F-funktion

F-funktionen tager 32 databit og 16 nøglebit og blander dem sammen.

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

Funktion $F_{k}$

Funktionen fungerer med to 32 bit ord. $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}))$

Generering af rundnøgle

Som et resultat af genereringen af rundnøgler opnås et sæt af N + 8 rundnøgler , hver 16 bit lange, fra den 128 bit lange nøgle, der modtages ved indgangen . Dette resultat opnås som et resultat af følgende algoritme. $K_{i}$

Opdeling af inputtasten i venstre og højre tast: , de er 64 bit lange. $K=(K_{L},K_{R})$
Nøglebehandling $K_{R}=(K_{R1},K_{R2})$
Introduktion af en midlertidig variabel for : $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}$
Nøglebehandling $K_{L}=(A_{0},B_{0})$
Indførelse af en midlertidig variabel $D_{0}=\phi$
Sekventiel beregning $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)))$

Forbehandling

På den indledende fase forberedes datablokken til en iterativ krypteringsprocedure. $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})$

Iterativ behandling

På dette trin udføres N runder af bitblanding med datablokken i overensstemmelse med følgende algoritme.

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

Efterbehandling

Opgaven for denne fase er at udarbejde en næsten klar chiffertekst til udsendelse.

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

Den samme algoritme kan bruges til dekryptering. Den eneste forskel er, at under dekryptering er rækkefølgen, hvori nøglens dele bruges, omvendt.

Ansøgning

Selvom FEAL-algoritmen oprindeligt blev tænkt som en hurtigere erstatning for DES, herunder til brugen af kryptering i smart cards, satte antallet af sårbarheder, der hurtigt blev fundet i den, en stopper for mulighederne for at bruge denne algoritme. For eksempel, i arbejdet af Eli Biham og Adi Shamir , udgivet i 1991, blev tilstrækkeligheden af 8 udvalgte klartekster til at bryde FEAL-4-cifferet, 2000 til at bryde FEAL-8-cifferet og for FEAL-16 [5] bevist. . Alle disse tal er væsentligt mindre end antallet af valgte klartekster, der er nødvendige for at angribe DES, og det faktum, at FEAL-32 er ret pålideligt, er ret ubrugeligt, da DES opnår sammenlignelig pålidelighed med betydeligt færre runder, og dermed fratager FEAL den fordel, der var oprindeligt tænkt af skaberne. . $2^{28}$

I øjeblikket, på den officielle hjemmeside for forfatterne af chifferen - NTT -virksomheden , i beskrivelsen af FEAL-cifferet, er der lagt en advarsel om, at NTT anbefaler ikke at bruge FEAL-cifferet, men at bruge Camelia -cifferet , også udviklet af denne virksomhed af hensyn til pålideligheden og krypteringshastigheden [9] .

Bidrag til udvikling af kryptografi

På grund af det faktum, at FEAL-chifferet blev udviklet ret tidligt, har det tjent som et fremragende træningsobjekt for kryptologer over hele verden [10] .

Derudover blev lineær kryptoanalyse opdaget ved hjælp af hans eksempel. Mitsuru Matsui , opfinderen af lineær kryptoanalyse, betragtede i sit første arbejde om dette emne blot FEAL og DES.

Noter

↑ 1 2 Panasenko, 2009 .
↑ Boer, 1988 .
↑ 1 2 Matsui, Yamagishi, 1992 .
↑ Gilbert, Chasse, 1990 .
↑ 1 2 Biham, Shamir, 1991 .
↑ Kazuo Ohta, Shiho Moriai, Kazumaro Aoki. Forbedring af søgealgoritmen for det bedste lineære udtryk // Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology. — London, Storbritannien, Storbritannien: Springer-Verlag, 1995-01-01. — S. 157–170 . — ISBN 3540602216 .
↑ Aoki, Kobayashi, Moriai, 1997 .
↑ FEAL-N(NX) krypteringsalgoritmespecifikation . Hentet 3. december 2016. Arkiveret fra originalen 23. januar 2021. (ubestemt)
↑ Liste over NTT-krypteringsarkiv (downlink) . info.isl.ntt.co.jp. Hentet 27. november 2016. Arkiveret fra originalen 7. oktober 2016. (ubestemt)
↑ Schneier B. Selvstudiekursus om kryptoanalyse af blokcifre . — Trans. fra engelske Bybin S.S. Arkiveret 2. april 2022 på Wayback Machine

Litteratur

Shimizu A. , Miyaguchi S. Fast Data Encipherment Algorithm FEAL // Advances in Cryptology - EUROCRYPT '87 : Workshop om teorien og anvendelsen af kryptografiske teknikker Amsterdam, Holland, 13.-15. april 1987 Proceedings / D. Chaum , W. L. Price - 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 om teori og anvendelse af kryptografiske teknikker, Davos, Schweiz, 25.-27. maj 1988. Proceedings / C. G. Günther - Springer Science+Business Media , 1988.—P. 293-299. — 383 s. — ISBN 978-3-540-45961-3 — doi:10.1007/3-540-45961-8_27
Miyaguchi S. FEAL-8 Cryptosystem and a Call for Attack // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 20.-24. august 1989, Proceedings / G Brassard - Berlin , Heidelberg , New York, NY , London [etc.] : Springer New York , 1990. - P. 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 // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 11-15 august, 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1991. - P. 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. Kryptanalysen af FEAL-4 med 20 udvalgte klartekster (engelsk) // 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. A Statistical Attack of the FEAL-8 Cryptosystem // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 11.-15. august 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , London [etc.] : 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. Differential Cryptanalysis of Feal and N-Hash // Advances in Cryptology - EUROCRYPT '91 : Workshop om teorien og anvendelsen af kryptografiske teknikker Brighton, Storbritannien, 8.-11. april 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. Et kendt klartekstangreb af FEAL-4 og FEAL-6 // Fremskridt inden for kryptologi — CRYPTO'91 :11. årlige internationale kryptologikonference, Santa Barbara, Californien, USA, 1991, Proceedings / J. Feigenbaum - Berlin , Heidelberg , New York, NY , London [etc.] : 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. En ny metode til kendt klartekstangreb af FEAL Cipher // Fremskridt inden for kryptologi — EUROCRYPT '92 :Workshop om teori og anvendelse af kryptografiske teknikker, Balatonfüred, Ungarn, 24.-28. maj, 1992 Proceedings / R. Rueppel - Springer, Berlin, 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. Bedste differentialkarakteristiske søgning af FEAL // Fast Software Encryption :, FSE'97, Haifa, Israel, 20.-22. januar 1997, Proceedings / E. Biham - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 1997. - S. 41-53. — 299 sider. - ( 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. Krypteringsalgoritmer. Særlig opslagsbog - St. Petersborg. : BHV-SPb , 2009. - S. 206-212. — 576 s. — ISBN 978-5-9775-0319-8

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher