Khufu
| Khufu | |
|---|---|
| Skaber | Ralph Merkle |
| Oprettet | 1990 |
| offentliggjort | 1990 |
| Nøglestørrelse | 512 bit |
| Blokstørrelse | 64 bit |
| Antal runder | 8-32 (op til 64) |
| Type | Feistel netværk |
Khufu er en symmetrisk blok 64-bit kryptografisk algoritme udviklet af Ralph Merkle i 1990, opkaldt efter den egyptiske farao Cheops .
Historisk baggrund
På tidspunktet for oprettelsen af algoritmen (slutningen af 1990) var langt størstedelen af de symmetriske krypteringsalgoritmer, der eksisterede på det tidspunkt, tilpasset til hardwareimplementeringer, på trods af at hardwareimplementeringen af krypteringsalgoritmen først og fremmest er , dyrere end software, det vil sige mindre tilgængelig for langt de fleste potentielle brugere.
Så i slutningen af 1990'erne udviklede en gruppe kryptografer fra Xerox -virksomheden en chiffer - Khufu, opkaldt efter den egyptiske farao Cheops. Algoritmen blev yderligere præsenteret i 1990 på CRYPTO- konferencen .
Året efter (1991) modtog Xerox Corporation et patent på Khufu- og Khafre-algoritmerne, som et resultat af hvilket deres kommercielle brug blev forbudt af patentindehaveren [1] .
Forudsætninger for at oprette en algoritme
Khufu-algoritmen er en blokalgoritme baseret på Feistel-netværket , bygget på basis af følgende postulater:
- Softwareimplementeringen af krypteringsalgoritmen har meget flere ressourcer til rådighed (mængden af RAM og ikke-flygtig hukommelse), i modsætning til algoritmer baseret på hardwareimplementering . Som følge heraf bruges store mængder hukommelse til at gemme borde, rundnøgler osv.
- Denne krypteringsalgoritme bruger kun operationer, der er optimeret til brug i softwaremiljøer [2] .
Det teoretiske grundlag for Khufu-algoritmen er erfaringerne fra udviklingen af DES-algoritmen . Derfor blev følgende forudsætninger taget i betragtning ved udformningen af algoritmen [3] :
- 56-bit DES nøglestørrelsen er for lille og bør øges.
- Den store brug af permutationer i DES er kun praktisk til hardwareimplementeringer, men gør softwareimplementeringer vanskelige. De hurtigste implementeringer af DES udfører permutationer på en tabelform. Tabelopslag kan give de samme "sprednings"-karakteristika som selve permutationer og kan gøre implementeringen mere fleksibel.
- S-boksene i DES, med kun 64 4-bit elementer, er for små, så S - boksene skal øges. Desuden bruges alle otte S -bokse samtidigt. Dette er praktisk til hardware, men for softwareimplementering virker det som en unødvendig begrænsning, så det er mere hensigtsmæssigt at implementere en større S -box størrelse. Derudover skal seriel (frem for parallel) brug af S -bokse under udskiftninger implementeres.
- De indledende og endelige permutationer er kryptografisk meningsløse, så de skal elimineres.
- Alle hurtige DES-implementeringer forudberegner nøgler for hvert trin. Under denne betingelse er der ingen mening i at komplicere disse beregninger.
- Designkriterier for S -bokse bør være offentligt tilgængelige.
Algoritme
Algoritmeparametre
Algoritmen krypterer data i blokke, blokstørrelsen er 64 bit. Derefter, under krypteringsprocessen, er hver blok opdelt i 2 underblokke, hver 32 bit store.
Selvom dele af nøglen (undernøgler K 0 ..K 3 ) kun bruges til at tilføje underblokke i begyndelsen og slutningen af algoritmen, er hovedformålet med nøglen at generere S -bokse. Algoritmen giver en måde at generere S -bokse med tasten [3] .
Algoritmen har følgende parametre [4] [3] :
- Krypteringsblokstørrelsen er 64 bit.
- Krypteringsnøglens størrelse skal være mellem 64 bit og 512 bit. I dette tilfælde skal nøglestørrelsen være et multiplum af 64.
- S -blokken har 8 input bits og 32 output bits. Er variabel. Hver oktet bruger sin egen S -boks [1] .
Algoritme til at konstruere S-bokse
Algoritmen består af generering af undernøgler og en standard substitutionstabel. Baseret på standard substitutionstabellen konstrueres S -bokse for hver transformationsoktet.
Opbygning af en standard erstatningstabel- I begyndelsen af denne procedure initialiseres en tabel med 256 rækker gange 5 kolonner. Den 1. kolonne indeholder alle mulige byteværdier (fra henholdsvis 00 til FF). De andre fire kolonner er fyldt med lignende værdier. Nedenfor er et fragment af en sådan tabel, som angiver henholdsvis 1., 2. og 256. linje [5] .
| byte | 4 bytes | |||
|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 00 |
| 01 | 01 | 01 | 01 | 01 |
| FF | FF | FF | FF | FF |
- Inden for en kolonne forekommer byte-permutationer (proceduren ligner permutationen af bytes i S -boksen, da den blev oprettet), hvor et sæt på en million tilfældige tal fra RAND Corporation, udgivet i 1995, bruges som en pseudo -tilfældig rækkefølge.
| byte | 4 bytes | |||
|---|---|---|---|---|
| 00 | FA | A1 | 22 | 41 |
| 01 | 71 | 88 | B3 | femten |
| FF | 44 | elleve | C4 | E1 |
- Efter disse iterationer dannes en standard substitutionstabel. Et fragment af denne tabel er vist ovenfor.
Hovedideen med Khufu-algoritmen er, at undernøgler og S -bokse afhænger af den runde nøgle, mens Khufu-algoritmen under hver runde kun bruger én udskiftning af de sidste 8-bit af den venstre underblok med 32 bit, i modsætning til DES algoritme. Overvej algoritmen til at konstruere S -bokse og undernøgler. Det er bygget i flere etaper [6] :
- I det første trin skrives nøglen til de 64 bytes, der er allokeret til dette, mens de ubrugte bits sættes til nul (husk på, at den mulige nøglestørrelse går fra 8 til 64 bytes).
- På det andet trin krypteres denne blok af Khufu-algoritmen i chifferblokkædetilstanden. Nulsekvensen tages som undernøgler ( K 0 .. K 3 ) for hver blok, og standardtabellen, som blev beskrevet ovenfor, tages som substitutionstabeller. Outputtet er en pseudo-tilfældig 64-byte-sekvens, der kun afhænger af krypteringsnøglen. Det er muligt, at flere bytes kan være nødvendige for at generere tabeller og undernøgler, så dette trin kan gentages flere gange.
- På det tredje trin vælges undernøgleværdier ( K 0 .. K 3 ) fra det givne sæt bits.
- På det fjerde trin bygges S -bokse for hver transformationsoktet:
- Hver beregnet S -boks initialiseres med den originale standardsubstitutionstabel, som er beskrevet ovenfor.
- I den oprindelige standardtabel over erstatninger, i en cyklus gennem kolonner (fra henholdsvis 0. til 3. byte), udføres en cyklus over rækker (fra 0. til 255. byte), hvor hver aktuelle byte (byten i skæringspunktet mellem nuværende række og aktuelle kolonne) byttes med en af de næste bytes i samme kolonne, bestemt tilfældigt (afhænger af den aktuelle pseudo-tilfældige sekvensbyte); resultatet er den originale tabel med "kaotisk" omarrangerede bytes af hver kolonne [4] .
Krypteringsprocedure
Kryptering foregår over en enkelt datablok på 64 bit. I begyndelsen af proceduren udføres følgende handlinger på denne blok:
- En 64-bit datablok er opdelt i to blokke på hver 32 bit (herefter kalder vi dem henholdsvis L og R).
- Hver af underblokkene XOR - behandles bitvist med henholdsvis underblokkene Ko og K1 (for den venstre underblok - Ko , for den højre - K1 ) .
Derefter udføres kryptering. Antallet af gentagelser af trin er lig med antallet af runder af algoritmen.
- I det første trin føres den lave byte (sidste 8 bit) af den venstre underblok gennem S -blokken, hvorfra en 4-byte (32-bit) værdi opnås. Desuden bruges der i hver oktet af operationer en S -blok, beregnet til denne oktet.
- I det andet trin tilføjes værdien opnået i det foregående trin bit for bit (XOR) med den højre underblok af tekst.
- Det tredje trin roterer til venstre med et andet antal bits i den venstre underblok, hvilket afhænger af det runde tal i oktetten:
- 8 - hvis tallet er 3 eller 4
- 24 - hvis tallet er 7 eller 8
- 16 - i alle andre tilfælde
- I det fjerde trin ombyttes venstre og højre underblok.
Derefter gentages alle trin igen, inklusive skift af S - blokken hver 8. runde.
Ved afslutningen af proceduren, efter at have passeret alle de angivne runder, udføres tilføjelsen på samme måde som tilføjelsen med undernøgler K 0 og K 1 , men med andre undernøgler henholdsvis K 2 og K 3 [7] .
Brug og bæredygtighed
Afhængigheden af S -bokse og undernøgler gør dem hemmelige for kryptoanalytikeren, hvilket markant øger algoritmens sikkerhed mod differentiel kryptoanalyse. Dette indebærer hovedspecifikationen af denne algoritme: Khufu-algoritmen bør bruges, hvor højhastighedskryptering af store mængder data med en sjælden nøgleændring er nødvendig [8] .
Sammenligning af algoritmen med DES
For at hver outputbit kan afhænge af hvert input i DES-algoritmen, skal der udføres 5 runder. I Khufu-algoritmen kræver en lignende afhængighed 9 runder. I dette tilfælde er sikkerhedsfaktoren lig med følgende udtryk: , hvor parametrene er antallet af runder , er antallet af runder, der kræves for fuld kryptering . For DES-algoritmen og for Khufu-algoritmen er den tilsvarende parameter . I dette tilfælde, med hensyn til denne sammenligning, er Khufu-algoritmen ringere end DES-algoritmen. Khufu-algoritmens S -bokse er dog hemmelige, i modsætning til DES-algoritmen [9] .
Angreb på chifferen
Det bedste [10] angreb på Khufu-chifferet er af Gilbert og Showo. Angrebet blev lavet på en 16-rund Khufu. For fuldstændigt at afsløre den skjulte information krævede det 2 31 udvalgte klartekster. Men dette resultat kunne ikke udvides til flere runder. Hvis en større nøgle bruges, vil algoritmen simpelthen være ineffektiv [10] .
Chifferen er modstandsdygtig over for brute force angreb. 512-bit nøglen giver en cracking sværhedsgrad på 2512, hvilket gør chifferen modstandsdygtig over for denne metode [3] .
Se også
- afvigelser
Noter
- ↑ 1 2 Panasenko, 2009 .
- ↑ Panasenko, 2009 , s. 288-289.
- ↑ 1 2 3 4 Schneier Bruce. kapitel 13. s.7. // Anvendt kryptografi.
- ↑ 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.
Litteratur
- Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
- Panasenko S.P. Kapitel 3 // Krypteringsalgoritmer. Særlig opslagsbog - St. Petersborg. : BHV-SPb , 2009. - S. 288-295. — 576 s. — ISBN 978-5-9775-0319-8
- Zhdanov O.N., Zolotorev V.V. Metoder og midler til kryptografisk informationsbeskyttelse: Lærebog .. - Krasnoyarsk: BHV-Petersburg, 2007. - 217 s.
- Biham E. , Biryukov A. , Shamir A. Miss in the Middle Attacks on IDEA and Khufu // Fast Software Encryption :, FSE'99 Rom, Italien, 24.-26. marts 1999 Proceedings / L. R. Knudsen - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1999. - S. 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, Californien, USA, 11.-15. august 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , London [etc.] : 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
| Symmetriske kryptosystemer | |
|---|---|
| Stream-cifre | |
| Feistel netværk | |
| SP netværk | |
| Andet | |