Khufu
| Khufu | |
|---|---|
| Luoja | Ralph Merkle |
| Luotu | 1990 |
| julkaistu | 1990 |
| Avaimen koko | 512-bittinen |
| Lohkon koko | 64-bittinen |
| Kierrosten lukumäärä | 8-32 (64 asti) |
| Tyyppi | Feistelin verkko |
Khufu on Ralph Merklen vuonna 1990 kehittämä symmetrinen lohko 64-bittinen salausalgoritmi , joka on nimetty egyptiläisen faaraon Cheopsin mukaan .
Historiallinen tausta
Algoritmin luomishetkellä (vuoden 1990 lopussa) suurin osa tuolloin olemassa olevista symmetrisistä salausalgoritmeista oli sovitettu laitteistototeutuksiin huolimatta siitä, että salausalgoritmin laitteistototeutus on ennen kaikkea , kalliimpi kuin ohjelmisto, toisin sanoen useimpien potentiaalisten käyttäjien ulottumattomissa.
Joten 1990-luvun lopulla ryhmä Xerox -yhtiön kryptografeja kehitti salauksen - Khufu, joka on nimetty egyptiläisen faaraon Cheopsin mukaan. Algoritmi esiteltiin edelleen vuonna 1990 CRYPTO - konferenssissa .
Seuraavana vuonna (1991) Xerox Corporation sai patentin Khufu- ja Khafre-algoritmeille, minkä seurauksena patentinhaltija kielsi niiden kaupallisen käytön [1] .
Algoritmin luomisen edellytykset
Khufu-algoritmi on Feistel-verkkoon perustuva lohkoalgoritmi , joka on rakennettu seuraavien postulaattien perusteella:
- Salausalgoritmin ohjelmistototeutuksessa on käytettävissä paljon enemmän resursseja (RAM-muistin määrä ja haihtumaton muisti), toisin kuin laitteistototeutukseen perustuvissa algoritmeissa . Tämän seurauksena suuria määriä muistia käytetään taulukoiden, pyöreiden avainten jne. tallentamiseen.
- Tämä salausalgoritmi käyttää vain toimintoja, jotka on optimoitu käytettäväksi ohjelmistoympäristöissä [2] .
Khufu-algoritmin teoreettinen perusta on DES-algoritmin kehittämisestä saatu kokemus . Siksi algoritmia suunniteltaessa otettiin huomioon seuraavat edellytykset [3] :
- 56-bittinen DES -avaimen koko on liian pieni ja sitä pitäisi suurentaa.
- 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: n S-laatikot , joissa on vain 64 4-bittistä elementtiä, ovat liian pieniä, joten S - laatikoita on lisättävä. Lisäksi kaikki kahdeksan S -laatikkoa ovat käytössä samanaikaisesti. Tämä on kätevä laitteistolle, mutta ohjelmistototeutuksen kannalta se tuntuu turhalta rajoitukselta, joten on tarkoituksenmukaisempaa toteuttaa suurempi S -box-koko. Lisäksi S -laatikoiden sarjakäyttö (ei rinnakkaiskäyttö) vaihdon yhteydessä tulee toteuttaa.
- Alku- ja loppupermutaatiot ovat kryptografisesti merkityksettömiä, joten ne on eliminoitava.
- Kaikki nopeat DES-toteutukset laskevat avaimet kullekin vaiheelle. Tässä tilanteessa ei ole mitään järkeä monimutkaista näitä laskelmia.
- S -laatikoiden suunnittelukriteerit tulee olla julkisesti saatavilla.
Algoritmi
Algoritmin parametrit
Algoritmi salaa tiedot lohkoissa, lohkon koko on 64 bittiä. Sitten salausprosessin aikana jokainen lohko jaetaan 2 alilohkoon, joista kukin on kooltaan 32 bittiä.
Vaikka avaimen osia (aliavaimia K 0 ..K 3 ) käytetään vain alilohkojen lisäämiseen algoritmin alkuun ja loppuun, avaimen päätarkoituksena on luoda S -laatikoita. Algoritmi tarjoaa tavan luoda S -laatikoita avaimella [3] .
Algoritmilla on seuraavat parametrit [4] [3] :
- Salauslohkon koko on 64 bittiä.
- Salausavaimen koon on oltava 64-512 bittiä. Tässä tapauksessa avaimen koon on oltava 64:n kerrannainen.
- S - lohkossa on 8 tulobittiä ja 32 lähtöbittiä. On vaihteleva. Jokainen oktetti käyttää omaa S -laatikkoaan [1] .
Algoritmi S-laatikoiden rakentamiseen
Algoritmi koostuu aliavaimien luomisesta ja vakiokorvaustaulukosta. Standardin korvaustaulukon perusteella jokaiselle muunnosoktetille rakennetaan S -laatikot.
Vakiokorvaustaulukon rakentaminen- Tämän toimenpiteen alussa alustetaan taulukko, jossa on 256 riviä x 5 saraketta. Ensimmäinen sarake sisältää kaikki mahdolliset tavuarvot (00 - FF, vastaavasti). Muut neljä saraketta on täytetty samanlaisilla arvoilla. Alla on fragmentti tällaisesta taulukosta, joka osoittaa 1., 2. ja 256. rivin, vastaavasti [5] .
| tavu | 4 tavua | |||
|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 00 |
| 01 | 01 | 01 | 01 | 01 |
| FF | FF | FF | FF | FF |
- Yhdessä sarakkeessa tapahtuu tavupermutaatioita (menettely on samanlainen kuin S -laatikon tavujen permutaatio, kun se luotiin), jossa pseudona käytetään RAND Corporationin vuonna 1995 julkaisemaa miljoonan satunnaisluvun joukkoa. - satunnainen sekvenssi.
| tavu | 4 tavua | |||
|---|---|---|---|---|
| 00 | FA | A1 | 22 | 41 |
| 01 | 71 | 88 | B3 | viisitoista |
| FF | 44 | yksitoista | C4 | E1 |
- Näiden iteraatioiden jälkeen muodostetaan standardikorvaustaulukko. Katkelma tästä taulukosta on esitetty yllä.
Khufu-algoritmin pääajatuksena on, että aliavaimet ja S -laatikot riippuvat kierroksesta, kun taas jokaisen kierroksen aikana Khufu-algoritmi käyttää vain yhtä korvausta vasemman alilohkon viimeisistä 8 bitistä 32 bitillä, toisin kuin DES-algoritmi. Harkitse algoritmia S -laatikoiden ja aliavaimien rakentamiseen. Se on rakennettu useissa vaiheissa [6] :
- Ensimmäisessä vaiheessa avain kirjoitetaan tähän varattuun 64 tavuun, kun taas käyttämättömät bitit asetetaan nollaan (muista, että mahdollinen avaimen koko vaihtelee välillä 8-64 tavua).
- Toisessa vaiheessa tämä lohko salataan Khufu-algoritmilla salauslohkoketjutustilassa. Nollasekvenssi otetaan kunkin lohkon aliavaimiksi ( K 0 .. K 3 ) ja standarditaulukko, joka on kuvattu edellä, otetaan korvaustaulukoiksi. Tulos on näennäissatunnainen 64-tavuinen sekvenssi, joka riippuu vain salausavaimesta. On mahdollista, että taulukoiden ja aliavaimien luomiseen tarvitaan lisää tavuja, joten tämä vaihe voidaan toistaa useita kertoja.
- Kolmannessa vaiheessa aliavainarvot ( K 0 .. K 3 ) valitaan annetusta bittijoukosta .
- Neljännessä vaiheessa jokaiselle muunnosoktetille rakennetaan
S -laatikot:
- Jokainen laskettu S -laatikko alustetaan alkuperäisellä standardikorvaustaulukolla, joka on kuvattu yllä.
- Alkuperäisessä vakiokorvaustaulukossa syklissä sarakkeiden läpi (vastaavasti 0:sta tavuun 3. tavuun) suoritetaan sykli rivien yli (0:sta 255:een tavuun), jossa jokainen nykyinen tavu (tavun leikkauskohdassa oleva tavu) nykyinen rivi ja nykyinen sarake) vaihdetaan yhdellä saman sarakkeen seuraavista tavuista, määritettynä satunnaisesti (riippuu nykyisestä pseudosatunnaissekvenssitavusta); tuloksena on alkuperäinen taulukko, jossa jokaisen sarakkeen tavut on järjestetty "kaoottisesti" uudelleen [4] .
Salausmenettely
Salaus tapahtuu yhdellä 64-bittisellä tietolohkolla. Menettelyn alussa tälle lohkolle suoritetaan seuraavat toimet:
- 64-bittinen datalohko on jaettu kahteen 32-bittiseen lohkoon (tämän jälkeen kutsumme niitä L:ksi ja R:ksi).
- Kukin alilohko XOR - koodataan bittikohtaisesti alilohkoilla K0 ja K1 , vastaavasti (vasemmalle alilohkolle - K 0 , oikealle - K1 ) .
Sitten suoritetaan salaus. Vaiheiden toistojen määrä on yhtä suuri kuin algoritmin kierrosten lukumäärä.
- Ensimmäisessä vaiheessa vasemman alilohkon alhainen tavu (viimeiset 8 bittiä) viedään S -lohkon läpi, josta saadaan 4-tavuinen (32-bittinen) arvo. Lisäksi jokaisessa operaatiooktetissa käytetään S - lohkoa, joka on tarkoitettu tälle oktetille.
- Toisessa vaiheessa edellisessä vaiheessa saatu arvo lisätään bitti bitiltä (XOR) oikeanpuoleiseen tekstin alilohkoon.
- Kolmas askel pyörii vasemmalle vasemman alilohkon eri bittien määrällä, mikä riippuu oktetin pyöreästä numerosta:
- 8 - jos numero on 3 tai 4
- 24 - jos numero on 7 tai 8
- 16 - kaikissa muissa tapauksissa
- Neljännessä vaiheessa vasen ja oikea alilohko vaihdetaan.
Sen jälkeen kaikki vaiheet toistetaan uudelleen, mukaan lukien S - lohkon vaihtaminen 8 kierroksen välein.
Toimenpiteen lopussa, kun kaikki annetut kierrokset on käyty läpi, summaus suoritetaan samalla tavalla kuin summaus aliavaimilla K 0 ja K 1 , mutta muilla aliavaimilla K 2 ja K 3 [7 ] .
Käyttö ja kestävyys
S -laatikoiden ja aliavaimien riippuvuus tekee niistä salaisiksi kryptanalyytikon kannalta, mikä lisää merkittävästi algoritmin turvallisuutta differentiaalista kryptausanalyysiä vastaan. Tämä tarkoittaa tämän algoritmin pääspesifikaatiota: Khufu-algoritmia tulisi käyttää silloin, kun tarvitaan suurien tietomäärien nopea salaus harvinaisella avaimen vaihdolla [8] .
Algoritmin vertailu DES:n kanssa
Jotta jokainen lähtöbitti olisi riippuvainen DES-algoritmin jokaisesta syötteestä, on suoritettava 5 kierrosta. Khufu-algoritmissa samanlainen riippuvuus vaatii 9 kierrosta. Tässä tapauksessa suojakerroin on yhtä suuri kuin seuraava lauseke: , jossa parametrit ovat kierrosten lukumäärä , on kierrosten lukumäärä, joka tarvitaan täydelliseen salaukseen . Siten DES-algoritmille ja Khufu-algoritmille vastaava parametri on . Tässä tapauksessa tämän vertailun suhteen Khufu-algoritmi on huonompi kuin DES-algoritmi. Khufu-algoritmin S -laatikot ovat kuitenkin salaisia, toisin kuin DES-algoritmi [9] .
Hyökkäykset salaukseen
Gilbertin ja Showon paras [10] hyökkäys Khufu-salausta vastaan. Hyökkäys tehtiin 16 kierroksen Khufua vastaan. Piilotetun tiedon paljastamiseksi kokonaan tarvittiin 2 31 valittua selkeää tekstiä. Mutta tätä tulosta ei voitu laajentaa useampaan kierrokseen. Jos käytetään suurempaa avainta, algoritmi on yksinkertaisesti tehoton [10] .
Salaus kestää raa'an voiman hyökkäyksen. 512-bittinen avain tarjoaa murtumisvaikeuden 2512, mikä tekee salauksesta kestävän tätä menetelmää vastaan [3] .
Katso myös
- poikkeamaa
Muistiinpanot
- ↑ 1 2 Panasenko, 2009 .
- ↑ Panasenko, 2009 , s. 288-289.
- ↑ 1 2 3 4 Schneier Bruce. luku 13. s.7. // Sovellettu kryptografia.
- ↑ 1 2 Panasenko, 2009 , s. 289-290.
- ↑ Panasenko, 2009 , s. 291-292.
- ↑ Panasenko, 2009 , s. 290-292.
- ↑ Panasenko, 2009, 289-290 .
- ↑ Panasenko, 2009 , s. 293-294.
- ↑ Merkle, 1991 .
- ↑ 1 2 Biham, Biryukov, Shamir, 1999 , s. 131-137.
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
- Zhdanov O.N., Zolotorev V.V. Salaustietojen suojausmenetelmät ja keinot: Oppikirja .. - Krasnojarsk: BHV-Petersburg, 2007. - 217 s.
- Biham E. , Biryukov A. , Shamir A. Miss in the Middle Attacks on IDEA ja Khufu // Fast Software Encryption :, FSE'99 Rooma, Italia, 24.–26. maaliskuuta 1999 Proceedings / L. R. Knudsen - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 1999. - P. 124-138. - ( Lecture Notes in Computer Science ; Vol. 1636) - ISBN 978-3-540-66226-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-48519-8_10
- Merkle R. Fast Software Encryption Functions // Advances in Cryptology - CRYPTO '90 :10th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA , 11.-15. elokuuta 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berliini , Heidelberg York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 1991. - P. 476-501. - ( 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_34
| Symmetriset salausjärjestelmät | |
|---|---|
| Suoratoista salauksia | |
| Feistelin verkko | |
| SP verkko | |
| Muut | |