AlegsaOnline.com

Feistela (Feistel) šifrs: definīcija un darbības princips

Feistela (Feistel) šifrs — skaidra definīcija un darbības princips: kā darbojas Feistela tīkls, priekšrocības, struktūra un pielietojums modernajos bloku šifros.

Autors: Leandro Alegsa

04-01-2026

Feistela šifrs kriptogrāfijā ir simetriska struktūra, ko izmanto bloku šifru konstruēšanā un kas nosaukta vācu IBM kriptogrāfa Horsta Feistela vārdā; to parasti dēvē arī par Feistela tīklu. Šo shēmu izmanto liels skaits bloka šifru, tostarp datu šifrēšanas standarts (Data Encryption Standard)

Feistela struktūras priekšrocība ir tā, ka šifrēšanas un atšifrēšanas operācijas ir ļoti līdzīgas, dažos gadījumos pat identiskas, un ir nepieciešama tikai atslēgas grafika maiņa. Tāpēc šāda šifrāta ieviešanai nepieciešamā koda vai shēmas lielums ir gandrīz uz pusi mazāks.

Feistela konstrukcija ir iteratīva pēc būtības, kas atvieglo kriptosistēmas ieviešanu aparatūrā.

Feistela tīkli un tamlīdzīgas konstrukcijas ir produktu šifri, un tāpēc apvieno vairākas atkārtotu darbību kārtas, piemēram:

Bitu pārmijas (bieži sauktas par permutāciju kastēm vai P-kastēm).
Vienkāršas nelineāras funkcijas (bieži sauktas par aizvietošanas lodziņiem vai S-veida lodziņiem).
Lineāra sajaukšana (modulārās algebras izpratnē), izmantojot XOR, lai radītu funkciju ar lielu daudzumu to, ko Klods Šenons aprakstīja kā "apjukumu un difūziju".

Bitu sajaukšana rada difūzijas efektu, savukārt aizstāšana tiek izmantota, lai radītu apjukumu.

Sastāvdaļas un darbības princips

Tipiskā Feistela tīkla darbībā dati, ko vajadzīgs šifrēt, tiek sadalīti divās vienādās daļās: L (pa kreisi) un R (pa labi). Katrā kārtā tiek lietota nelineāra vai pusnelineāra "kārtas funkcija" F, kas parasti saņem kā ievadi vienu no pusēm (biežāk labā puse) un kārtas atslēgu K_i.

Vienkāršotā matemātiskā forma vienas kārtas transformācijai (no stāvokļa L_i, R_i uz L_i+1, R_i+1) ir:

L_i+1 = R_i
R_i+1 = L_i XOR F(R_i, K_i)

Pēc pietiekama kārtu skaita (piem., režīmā DES — 16 kārtas) kreisā un labā daļa tiek apvienota, veidojot šifrtekstblokā. Svarīgs Feistela tīkla īpašums ir tas, ka pati kārtas funkcija F nav jābūt invertējamai — invertējamība tiek nodrošināta ar Feistela struktūras maiņu un atslēgu grafika apgriešanu atšifrēšanas laikā.

Šifrēšana un atšifrēšana

Atšifrēšana izmanto tādas pašas darbības kā šifrēšana, tikai kārtu atslēgas tiek pielietotas apgrieztā secībā. Praktiski tas nozīmē, ka, ja šifrēšanā kārtu atslēgas ir K1,…,Kn, tad atšifrēšanā izmanto Kn,…,K1. Tā kā katra kārta izmanto XOR un apmaiņu starp pusēm, kopējā atgriezeniskā funkcija ir ātra un vienkārša.

Drošība un ierobežojumi

Feistela tīkla drošība lielā mērā ir atkarīga no:

kārtas funkcijas F nelinearitātes un tās rezistences pret diferenciālo un lineāro analīzi,
kārtu skaita — vairāku kārtu kombinācija palielina difūziju un apjukumu,
atslēgas grafikas (key schedule) kvalitātes — ja atslēgas no kārtas uz kārtu ir pārāk līdzīgas, var rasties ievainojamības.

Teorētiski pastāv rezultāti (piem., Luby–Rackoff) par to, cik kārtas nepieciešamas, lai Feistela tīkls uzvedas kā droša pseido‑permutaācija, ja kārtu funkcijas ir "pietiekami nejaušas". Tomēr reālām konstrukcijām jāņem vērā praktiskie uzbrukumi (diferenciālā un lineārā kriptanalīze u. c.), tāpēc praktiskie šifri parasti izmanto daudz kārtu un rūpīgi projektētas S‑kastes un atslēgu grafiku.

Varianti un pielietojumi

Ir vairāki Feistela tīkla varianti:

Balanced Feistel — abas daļas ir vienāda garuma (visizplatītākais variants);
Unbalanced Feistel — daļas atšķiras izmērā, lieto, piemēram, formāta saglabāšanas šifrēšanā (FPE);
Generalized Feistel Network (GFN) — blokā tiek dalīts vairāk nekā divās daļās, katra kārta manipulē ar vairākām daļām, izmantojot dažādas kombinācijas un funkcijas.

Piemēri reālām implementācijām: DES ir klasisks Feistela šifra piemērs. Citi pazīstami Feistela tipa šifri ir Blowfish, Twofish, CAST un dažas kamēlijas (Camellia) konstrukcijas. Feistela principu izmanto arī mūsdienu formāta saglabāšanas šifrēšanas algoritmos (piem., NIST standarti FF1/FF3 pamatojas uz Feistel‑līdzīgām konstrukcijām).

Praktiski padomi

Projektējot vai izvēloties Feistela‑bāzētu šifru, pievērs uzmanību S‑kastēm un to rezistencei pret diferenciālo un lineāro analīzi.
Izmanto drošu atslēgu grafiku, lai novērstu atslēgu atkārtotu parādīšanos vai korrelācijas starp kārtām.
Testē konstrukciju pret pazīstamiem kriptanalītiskiem uzbrukumiem un izvēlies pietiekami daudz kārtu atbilstoši drošības prasībām.

Feistela tīkls ir vienkāršs, elastīgs un efektīvs konstrukcijas veids, kas ļauj ar relatīvi mazām resursu izmaksām izveidot spēcīgus bloku šifrus, ja tiek ievērotas kriptogrāfijas dizaina pamatprasības.

Teorētiskais darbs

Daudzos mūsdienu simetriskajos blokšifros tiek izmantoti Feistela tīkli, un Feistela šifru struktūru un īpašības kriptogrāfi ir plaši pētījuši. Proti, Maikls Lūbijs (Michael Luby) un Čārlzs Račkovs (Charles Rackoff) analizēja Feistela bloka šifra konstrukciju un pierādīja, ka, ja apļa funkcija ir kriptogrāfiski droša pseidorandomā funkcija, kurā kā sēklu izmanto K_i, tad pietiek ar 3 apļiem, lai bloka šifrs būtu pseidorandomā permutācija, bet 4 apļi ir pietiekami, lai tas būtu "spēcīga" pseidorandomā permutācija (kas nozīmē, ka tā paliek pseidorandomā pat pretiniekam, kurš iegūst oracle piekļuvi tās inversai permutācijai). Šī ļoti svarīgā Lubija un Račkofa rezultāta dēļ Feistela šifrus dažkārt sauc par Lubija-Račkofa blokšifriem. Turpmākajos teorētiskajos pētījumos šī konstrukcija tika vispārināta un noteiktas precīzākas drošības robežas.

Būvniecība

Lai F {\displaystyle {\rm {F}}}} ${\rm F}$ ir raunda funkcija un lai K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} $K_1,K_2,\ldots,K_{n}$ ir $1,2,\ldots,n$ attiecīgi 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} raundu apakšatslēgas.

Tad pamatdarbība ir šāda:

Sadaliet atklātā teksta bloku divās vienādās daļās ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Katrai kārtai i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ aprēķina (aprēķina)

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

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

Tad šifrteksts ir ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Parasti abas daļas R n {\displaystyle R_{n}} R_n un L n {\displaystyle L_{n}} L_n pēc pēdējās kārtas netiek apmainītas).

Šifrteksta ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) atšifrēšanu veic, aprēķinot i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1}. $i=n,n-1,\ldots,1$

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

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

Tad ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} atkal (L_1,R_1) ir vienkāršais teksts.

Viena no šī modeļa priekšrocībām ir tā, ka apaļajai funkcijai F {\displaystyle {\rm {F}}} ${\rm F}$ nav jābūt apgriežamai un tā var būt ļoti sarežģīta.

Diagrammā ir attēlots šifrēšanas process. Dešifrēšana prasa tikai apmainīt K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ kārtību, izmantojot to pašu procesu; tā ir vienīgā atšķirība starp šifrēšanu un dešifrēšanu:

Nesabalansētie Feistela šifri izmanto modificētu struktūru, kurā L 1 {\displaystyle L_{1}} L_1 un R 1 {\displaystyle R_{1}} R_1 nav vienāda garuma. MacGuffin šifrs ir šāda šifra eksperimentāls piemērs.

Feistela konstrukcija tiek izmantota arī citos kriptogrāfijas algoritmos, kas nav blokķīfi. Piemēram, Optimālā asimetriskā šifrēšanas bloķēšanas shēma (OAEP) izmanto vienkāršu Feistela tīklu, lai randomizētu šifrtekstus dažās asimetrisko atslēgu šifrēšanas shēmās.

Feistela tīkla operācija blokķiprāfam, kur P ir atklāts teksts un C ir šifrēts teksts.

Feistela šifru saraksts

Feistels vai modificēts Feistels: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Vispārināts Feistels: CAST-256, MacGuffin, RC2, RC6, Skipjack

Jautājumi un atbildes

J: Kas ir Feistela šifrs?

A: Feistela šifrs ir simetriska struktūra, ko izmanto bloku šifru konstruēšanā un kas nosaukta vācu IBM kriptogrāfa Horsta Feistela vārdā. To parasti dēvē arī par Feistela tīklu.

J: Kādas ir dažas Feistela struktūras izmantošanas priekšrocības?

A: Galvenā Feistela struktūras izmantošanas priekšrocība ir tā, ka šifrēšanas un atšifrēšanas operācijas ir ļoti līdzīgas, dažos gadījumos pat identiskas, un ir nepieciešama tikai atslēgas grafika maiņa. Tas gandrīz uz pusi samazina šāda šifrāta ieviešanai nepieciešamā koda vai shēmas apjomu. Turklāt tā iteratīvais raksturs atvieglo kriptosistēmas ieviešanu aparatūrā.

J: Kā Klods Šenons apraksta "apjukumu un difūziju"?

A: Klods Šenons aprakstīja "apjukumu un difūziju" kā abu elementu lielu daudzumu, lai uzbrucējam būtu grūti atšifrēt šifrētu ziņojumu.

Kādi paņēmieni tiek izmantoti, lai radītu apjukumu un difūziju?

A: Apjukumu un difūziju rada, izmantojot bitu sajaukšanu (bieži sauktas par permutāciju kastēm jeb P-kastēm) un vienkāršas nelineāras funkcijas (bieži sauktas par aizvietošanas kastēm jeb S-kastēm), kā arī lineāru sajaukšanu (modulārās algebras izpratnē), izmantojot XOR. Bitu sajaukšana rada difūzijas efektu, bet aizstāšana tiek izmantota sajaukšanai.

J: Kāda veida šifrs ir Feistela tīkls?

A: Feistela tīkls ir produktu šifru veids, kas apvieno vairākas atkārtotu darbību kārtas, lai droši šifrētu datus.

J: Kas izstrādāja šo kriptogrāfijas veidu?

A: Feistela struktūru izstrādāja vācu IBM kriptogrāfs Horsts Feistels.

Vai datu šifrēšanas standarts ir balstīts uz šo kriptogrāfijas veidu?

A: Jā, datu šifrēšanas standartā izmanto šo kriptogrāfijas veidu, kas izmanto tos pašus iepriekš izklāstītos principus, lai šifrētā ziņojumā radītu apjukumu un izkliedi.