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.

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.

Būvniecība

Lai F {\displaystyle {\rm {F}}}} ir raunda funkcija un lai K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}ir 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}} , R 1 {\displaystyle R_{1}} ).

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

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

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

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

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

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

Viena no šī modeļa priekšrocībām ir tā, ka apaļajai funkcijai F {\displaystyle {\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ā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}} un R 1 {\displaystyle 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.

Jautājumi un atbildes

J: Kas ir Feistela šifrs?

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

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

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

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

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

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

Meklēt pēc burta