Khafre
Khafre on toinen ( Khufun ohella ) Ralph Merklen ehdottama algoritmi ( Khufu ( Khufu ) ja Khafre ( Khafre ) ovat Egyptin faaraoiden nimiä ). Tämä algoritmi on samanlainen kuin Khufu , mutta se ei vaadi esilaskentaa. S-laatikot ovat avainriippumattomia , Khafre käyttää kiinteitä S-laatikoita. Khafre-algoritmi ei rajoita algoritmikierrosten enimmäismäärää ja suurinta avaimen kokoa, toisin kuin Khufu. Avaimen koon on kuitenkin oltava 64 bitin kerrannainen ja kierrosten määrän on oltava 8:n kerrannainen. Merklen ehdotus on, että Khafren kanssa tulisi käyttää 64 tai 128 bitin avaimia ja että Khafrella on enemmän kierroksia kuin Khufulla . Lisäksi jokainen Khafren askel on vaikeampi kuin Khufun askel , mikä tekee Khafresta hitaamman. Mutta Khafre ei tarvitse esilaskentaa, mikä mahdollistaa pienten tietojen salaamisen nopeammin.
Historia
Juuri ennen algoritmin luomista (vuoden 1990 lopussa) suurin osa tuolloin olemassa olevista symmetrisistä salausalgoritmeista sovitettiin laitteistototeutuksiin huolimatta siitä, että salausalgoritmin laitteistototeutus on kalliimpaa kuin ohjelmistototeutus, mikä tarkoittaa, että suurin osa potentiaalisista käyttäjistä on vähemmän saatavilla.
Joten 1990-luvun lopulla Merkle osana Xeroxin kryptografiryhmää kehitti salauksen - Khafre, joka on nimetty egyptiläisen faaraon Khafren, Khufan pojan mukaan. Vuotta myöhemmin Xerox sai patentin Khafre-algoritmille, patentin haltija kielsi sen kaupallisen käytön.
Algoritmin postulaatit
Khafre-algoritmi on Feistel-verkkoon perustuva lohkoalgoritmi, joka täyttää seuraavat oletukset:
- Algoritmien ohjelmistototeutuksissa on lähes rajoittamaton määrä (verrattuna laitteistokooderiin) toiminnallista ja haihtumatonta muistia. Tämä sallii salausalgoritmin käyttää suuria määriä muistia korvaustaulukoiden, pyöreiden avainten jne. tallentamiseen.
- Tässä salausalgoritmissa käytetään vain optimoituja perusoperaatioita käytettäviksi ohjelmistototeutuksissa.
Algoritmin luomisen periaatteet
DES-algoritmin suunnittelusta saadun kokemuksen perusteella muotoiltiin seuraavat periaatteet:
- 56-bittisen DES-avaimen kokoa oli mahdollista kasvattaa, kun muistin kustannukset tulivat merkityksettömiksi.
- Raskas permutaatioiden käyttö DES:ssä on kätevää vain laitteistototeutuksissa, mutta vaikeuttaa ohjelmistototeutuksia. DES:n nopeimmat toteutukset suorittavat permutaatioita taulukkomuodossa. Taulukkohaut voivat tarjota samat "sironta"-ominaisuudet kuin itse permutaatiot ja voivat tehdä toteutuksesta joustavamman.
- DES S-boxit , joissa on vain 64 4-bittistä elementtiä, ovat liian pieniä. Muistin halpeneessa tuli mahdolliseksi lisätä myös S-boxeja. Lisäksi kaikkia kahdeksaa S-laatikkoa käytetään samanaikaisesti. Vaikka tämä on kätevää laitteistolle, se ei ole välttämätöntä ohjelmiston toteutuksessa. S-laatikoiden sarjakäyttö (eikä rinnakkainen) on toteutettava.
- Poista alku- ja loppupermutaatiot, koska ne ovat kryptografisesti merkityksettömiä
- Kaikki nopeat DES-toteutukset laskevat avaimet kullekin vaiheelle. Tässä tilanteessa ei ole mitään järkeä monimutkaista näitä laskelmia.
- S-boxin suunnittelukriteerien tulee olla julkisia, toisin kuin DES
Algoritmi
Algoritmin parametrit
Algoritmi salaa tiedot 64-bittisiksi lohkoiksi. Lisäksi salausprosessin aikana jokainen lohko jaetaan 2 alilohkoon, joiden kunkin koko on 32 bittiä.
Algoritmilla on seuraavat parametrit:
- Salauslohkon koko on 64 bittiä.
- Salausavaimen koon on oltava 64 bitin kerrannainen
- S-boxissa on 8 tulobittiä ja 32 lähtöbittiä. Se on pysyvä eikä riipu salausavaimesta. Jokaisella kierroksella käytetään erilaista S-lohkoa.
Vakiokorvaustaulukon rakentaminen
- Ensin luodaan taulukko, jossa on 256 riviä x 5 saraketta. Ensimmäinen sarake sisältää kaikki mahdolliset tavuarvot (00 - FF, vastaavasti). Loput sarakkeet täytetään samoilla arvoilla. Alla on fragmentti tällaisesta taulukosta.
Fragmentti vakiotaulukosta
tavu
|
4 tavua
|
00
|
00
|
00
|
00
|
00
|
01
|
01
|
01
|
01
|
01
|
02
|
02
|
02
|
02
|
02
|
…
|
…
|
…
|
…
|
…
|
FF
|
FF
|
FF
|
FF
|
FF
|
- Tavuja vaihdetaan kussakin sarakkeessa käyttämällä näennäissatunnaisena sekvenssinä miljoonan satunnaisluvun sarjaa RAND Corporationilta, joka julkaistiin vuonna 1995.
Fragmentti standarditaulukosta permutaatioiden jälkeen
tavu
|
4 tavua
|
00
|
FC
|
21
|
23
|
FF
|
01
|
E2
|
27
|
71
|
FA
|
02
|
D.F.
|
B5
|
BB
|
29
|
…
|
…
|
…
|
…
|
…
|
FF
|
kolmekymmentä
|
24
|
1C
|
Facebook
|
Aliavaimen luominen
- Ensimmäisessä vaiheessa 64-tavuinen avain alustetaan ja käyttämättömät bitit asetetaan nollaan.
- Toisessa vaiheessa tämä lohko salataan Khafre-algoritmilla salauslohkoketjutustilassa. Nollasekvenssi otetaan kunkin oktetin aliavaimina. Osoittautuu näennäissatunnainen 64-tavuinen sekvenssi, joka riippuu vain salausavaimesta. On todennäköistä, että aliavaimien alustamiseen tarvitaan lisää tavuja, joten tämä vaihe voidaan toistaa useita kertoja.
- Kolmannessa vaiheessa aliavaimia (K0 ...Kn + 3 ) valitaan vastaanotetusta bittijoukosta.
Salausmenettely
Lähdeteksti on jaettu 64 bitin lohkoihin. Menettelyn alussa tälle lohkolle suoritetaan seuraavat toiminnot:
- 64-bittinen datalohko on jaettu kahteen 32-bittiseen alilohkoon, L (vasen) ja R (oikea).
- Alilohkot XOR -koodataan bittikohtaisesti aliavaimilla K 0 ja K 1 vastaavasti (L - K 0 , R - K 1 ).
Tämän jälkeen salaus alkaa. Toistojen määrä on yhtä suuri kuin kierrosten lukumäärä.
- Ensimmäisessä vaiheessa vasemman alilohkon viimeiset 8 bittiä viedään S-laatikon läpi, joka tuottaa 32 bittiä ulostulona. Lisäksi jokainen operaatiooktetti käyttää eri S-laatikkoa nykyiselle oktettille.
- Seuraavassa vaiheessa edellisessä vaiheessa saatu arvo XOR-korjataan R:llä.
- Kolmannessa vaiheessa L siirretään syklisesti vasemmalle eri bittien määrällä riippuen oktetin pyöreästä numerosta:
- 8 - 3 ja 4 kierrokselle
- 24 - 7 ja 8 kierrokselle
- 16 - muille kierroksille
- Neljännessä vaiheessa alilohkot vaihdetaan (vasen alilohko on nyt R, oikea on L).
- Vaiheet 1-4 toistetaan 8 kertaa S-lohkon vaihtuessa joka toistokerralla.
- Viimeisessä vaiheessa alilohkot XOR-koodataan jälleen bittikohtaisesti aliavaimilla K n+2 ja K n+3 (L - K n+3 , R - K n+2 , n on oktettiluku)
Sen jälkeen kaikki vaiheet toistetaan uudelleen R kertaa.
Algoritmin toteutus
[1]
L : int ;
R : int ;
standardSBoxes : ARRAY [ 1 .. tarpeeksi / 8 ] OF ARRAY [ 0 .. 255 ] OF int ;
näppäin : ARRAY [ 0 .. avaimen koko -1 ] OF ARRAY [ O .. 1 ] of int ;
keyIndex : [ 0 .. avaimen koko - 1 ];
kiertoaikataulu : ARRAY [ l .. 8 ] = [ 16 , 16 , 8 , 8 , 16 , 16 , 24 , 24 ];
L = L XOR- näppäin [ O ][ O ];
R = R XOR- näppäin [ O ][ 1 ];
keyIndex = 1 MOD - avainkoko ;
oktetti = 1 ;
FOR kierros = 1 TO tarpeeksi DO
ALKAA
L = L XOR standardiSBoxes [ oktetti ] [ R AND # FF ];
R = RotateRight [ R , rotateSchedule [ round mod 8 + 1 ] 1 ;
VAIHTO [ L , R ];
JOS kierros MOD 8 = 0 NIIN
ALKAA
L = L XOR rotateRight [ näppäin [ keyIndex ][ O ], oktetti ];
R = R XOR rotateRight [ avain [ keyIndex ][ 1 ], oktetti ];
keyIndex = keyIndex + 1 ;
JOS keyIndex = avaimen koko NIIN keyIndex = 0 ;
oktetti = oktetti + 1 ;
LOPPU ;
LOPPU ;
Muistiinpanot
- ↑ Ralph C. Merkle. Nopeat ohjelmiston salaustoiminnot // Salaustekniikan edistysaskel. - S. 482-483 .
Kirjallisuus
- Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
- Panasenko S.P. Luku 3 // Salausalgoritmit. Erityinen hakuteos - Pietari. : BHV-SPb , 2009. - S. 288-295. — 576 s. — ISBN 978-5-9775-0319-8
- Ralph C. Merkle. Nopeat ohjelmiston salaustoiminnot // Advances in Cryptology - CRYPTO '90: julkaisut (tietotekniikan luentomuistiinpanot) : Proceedings of Conf. / Advances in Cryptology - CRYPTO '90, Santa Barbara, Kalifornia, USA, 11.-15. elokuuta 1991. - Springer Berlin Heidelberg, 1991. - P. 476-501 . — ISBN 3-540-54508-5 . (linkki ei saatavilla)