Feistela šifrs

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.

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.