Khufu
| Khufu | |
|---|---|
| Skapare | Ralph Merkle |
| Skapad | 1990 |
| publiceras | 1990 |
| Nyckelstorlek | 512 bitar |
| Block storlek | 64 bitar |
| Antal omgångar | 8-32 (upp till 64) |
| Sorts | Feistel nätverk |
Khufu är en symmetrisk 64-bitars kryptografisk algoritm utvecklad av Ralph Merkle 1990, uppkallad efter den egyptiska faraon Cheops .
Historisk bakgrund
Vid tidpunkten för skapandet av algoritmen (slutet av 1990) var den stora majoriteten av de symmetriska krypteringsalgoritmerna som fanns vid den tiden anpassade för hårdvaruimplementationer, trots att hårdvaruimplementeringen av krypteringsalgoritmen först och främst är , dyrare än mjukvara, det vill säga mindre tillgänglig för de allra flesta potentiella användare.
Så i slutet av 1990-talet utvecklade en grupp kryptografer från företaget Xerox ett chiffer - Khufu, uppkallat efter den egyptiske faraon Cheops. Algoritmen presenterades ytterligare 1990 på CRYPTO- konferensen .
Följande år (1991) fick Xerox Corporation ett patent för Khufu- och Khafre-algoritmerna, vilket resulterade i att deras kommersiella användning förbjöds av patentinnehavaren [1] .
Förutsättningar för att skapa en algoritm
Khufu-algoritmen är en blockalgoritm baserad på Feistel-nätverket , byggd på basis av följande postulat:
- Programvaruimplementeringen av krypteringsalgoritmen har mycket mer tillgängliga resurser (mängden RAM och icke-flyktigt minne), i motsats till algoritmer baserade på hårdvaruimplementering . Som ett resultat används stora mängder minne för att lagra tabeller, runda nycklar, etc.
- Denna krypteringsalgoritm använder endast operationer som är optimerade för användning i mjukvarumiljöer [2] .
Den teoretiska grunden för Khufu-algoritmen är erfarenheterna från utvecklingen av DES-algoritmen . Därför, vid utformningen av algoritmen, beaktades följande förutsättningar [3] :
- 56-bitars DES -nyckelstorleken är för liten och bör utökas.
- Den kraftiga användningen av permutationer i DES är bara praktiskt för hårdvaruimplementationer, men gör programvaruimplementeringar svåra. De snabbaste implementeringarna av DES utför permutationer i tabellform. Tabelluppslagningar kan ge samma "spridnings"-egenskaper som själva permutationer och kan göra implementeringen mer flexibel.
- S-boxarna i DES, med endast 64 4-bitars element, är för små, så S - boxarna måste utökas. Dessutom används alla åtta S -boxarna samtidigt. Detta är bekvämt för hårdvara, men för mjukvaruimplementering verkar det vara en onödig begränsning, så det är mer lämpligt att implementera en större S -boxstorlek. Dessutom måste seriell (snarare än parallell) användning av S -boxar vid byten implementeras.
- De initiala och slutliga permutationerna är kryptografiskt meningslösa, så de måste elimineras.
- Alla snabba DES-implementeringar förberäknar nycklar för varje steg. Under detta villkor är det ingen idé att komplicera dessa beräkningar.
- Designkriterier för S -boxar bör vara allmänt tillgängliga.
Algoritm
Algoritmparametrar
Algoritmen krypterar data i block, blockstorleken är 64 bitar. Sedan, under krypteringsprocessen, delas varje block upp i 2 underblock, vart och ett 32 bitar stort.
Även om delar av nyckeln (undernycklar K 0 ..K 3 ) endast används för att lägga till underblock i början och slutet av algoritmen, är huvudsyftet med nyckeln att generera S -boxar. Algoritmen tillhandahåller ett sätt att generera S -boxar med nyckel [3] .
Algoritmen har följande parametrar [4] [3] :
- Krypteringsblockets storlek är 64 bitar.
- Krypteringsnyckelns storlek måste vara mellan 64 bitar och 512 bitar. I det här fallet måste nyckelstorleken vara en multipel av 64.
- S -blocket har 8 ingångsbitar och 32 utgångsbitar. Är variabel. Varje oktett använder sin egen S -box [1] .
Algoritm för att konstruera S-boxar
Algoritmen består av att generera undernycklar och en standardsubstitutionstabell. Baserat på standardsubstitutionstabellen konstrueras S -boxar för varje transformationsoktett.
Bygga en standard ersättningstabell- I början av denna procedur initieras en tabell med 256 rader med 5 kolumner. Den första kolumnen innehåller alla möjliga bytevärden (från 00 till FF). De andra fyra kolumnerna är fyllda med liknande värden. Nedan finns ett fragment av en sådan tabell, som anger 1:a, 2:a respektive 256:e raden [5] .
| byte | 4 bytes | |||
|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 00 |
| 01 | 01 | 01 | 01 | 01 |
| FF | FF | FF | FF | FF |
- Inom en kolumn inträffar bytepermutationer (proceduren liknar permutationen av bytes i S -boxen när den skapades), där en uppsättning av en miljon slumptal från RAND Corporation, publicerad 1995, används som en pseudo -slumpmässig sekvens.
| byte | 4 bytes | |||
|---|---|---|---|---|
| 00 | FA | A1 | 22 | 41 |
| 01 | 71 | 88 | B3 | femton |
| FF | 44 | elva | C4 | E1 |
- Efter dessa iterationer bildas en standardsubstitutionstabell. Ett fragment av denna tabell visas ovan.
Huvudidén med Khufu-algoritmen är att undernycklar och S -boxar beror på den runda nyckeln, medan Khufu-algoritmen under varje omgång endast använder en ersättning av de sista 8-bitarna i det vänstra underblocket med 32 bitar, till skillnad från DES algoritm. Tänk på algoritmen för att konstruera S -boxar och undernycklar. Den är byggd i flera etapper [6] :
- I det första steget skrivs nyckeln till de 64 byte som tilldelats för detta, medan de oanvända bitarna sätts till noll (kom ihåg att den möjliga nyckelstorleken sträcker sig från 8 till 64 byte).
- I det andra steget krypteras detta block av Khufu-algoritmen i chifferblockkedjeläget. Nollsekvensen tas som undernycklar (Ko .. K3 ) för varje block, och standardtabellen, som beskrevs ovan, tas som substitutionstabell. Utdata är en pseudo-slumpmässig 64-byte sekvens som endast beror på krypteringsnyckeln. Det är möjligt att fler byte kan behövas för att generera tabeller och undernycklar, så detta steg kan upprepas flera gånger.
- I det tredje steget väljs undernyckelvärden ( K 0 .. K 3 ) från den givna uppsättningen bitar .
- I det fjärde steget byggs S -boxar för varje transformationsoktett:
- Varje beräknad S -box initieras med den ursprungliga standardsubstitutionstabellen, som beskrivs ovan.
- I den ursprungliga standardtabellen för substitutioner, i en cykel genom kolumner (från 0:e till 3:e byte, respektive), utförs en cykel över rader (från 0:e till 255:e byte), där varje aktuell byte (byten i skärningspunkten mellan aktuell rad och aktuell kolumn) byts ut med en av nästa byte i samma kolumn, bestäms slumpmässigt (beror på den aktuella pseudo-slumpmässiga sekvensbyten); resultatet är den ursprungliga tabellen med "kaotiskt" omarrangerade bytes av varje kolumn [4] .
Krypteringsförfarande
Kryptering sker över ett enda datablock på 64 bitar. I början av proceduren utförs följande åtgärder på detta block:
- Ett 64-bitars datablock är uppdelat i två block om 32 bitar vardera (hädanefter kommer vi att kalla dem L respektive R).
- Vart och ett av delblocken XOR-behandlas bitvis med delblocken Ko respektive Ki ( för det vänstra delblocket - Ko , för det högra - K1 ) .
Därefter utförs kryptering. Antalet repetitioner av steg är lika med antalet omgångar av algoritmen.
- I det första steget förs den låga byten (sista 8 bitarna) i det vänstra delblocket genom S -blocket, från vilket ett 4-byte (32-bitars) värde erhålls. Dessutom, i varje oktett av operationer, används ett S -block, avsett för denna oktett.
- I det andra steget adderas värdet som erhållits i föregående steg bit för bit (XOR) med det högra underblocket av text.
- Det tredje steget roterar åt vänster med ett annat antal bitar i det vänstra delblocket, vilket beror på det runda talet i oktetten:
- 8 - om siffran är 3 eller 4
- 24 - om siffran är 7 eller 8
- 16 - i alla andra fall
- I det fjärde steget byts de vänstra och högra underblocken.
Därefter upprepas alla steg på nytt, inklusive byte av S - block var 8:e varv.
I slutet av proceduren, efter att ha passerat alla de angivna omgångarna, utförs tillägget på samma sätt som tillägget med undernycklarna K 0 och K 1 , men med andra undernycklar K 2 respektive K 3 [ 7] .
Användning och hållbarhet
Beroendet av S -boxar och undernycklar gör dem hemliga för kryptoanalytikern, vilket avsevärt ökar säkerheten för algoritmen mot differentiell kryptoanalys. Detta innebär huvudspecifikationen för denna algoritm: Khufu-algoritmen bör användas där höghastighetskryptering av stora mängder data med en sällsynt nyckeländring är nödvändig [8] .
Jämförelse av algoritmen med DES
För att varje utgångsbit ska vara beroende av varje ingång i DES-algoritmen måste 5 omgångar utföras. I Khufu-algoritmen kräver ett liknande beroende 9 omgångar. I det här fallet är säkerhetsfaktorn lika med följande uttryck: , där parametrarna är antalet rundor , är antalet rundor som krävs för full kryptering . Således, för DES-algoritmen och för Khufu-algoritmen, är motsvarande parameter . I detta fall, med avseende på denna jämförelse, är Khufu-algoritmen sämre än DES-algoritmen. S - boxarna i Khufu-algoritmen är dock hemliga, till skillnad från DES-algoritmen [9] .
Attacker mot chiffer
Den bästa [10] attacken mot Khufu-chifferet är av Gilbert och Showo. Attacken gjordes på en 16-round Khufu. För att helt avslöja den dolda informationen krävdes 2 31 utvalda klartexter. Men detta resultat kunde inte utökas till fler omgångar. Om en större nyckel används blir algoritmen helt enkelt ineffektiv [10] .
Chifferet är resistent mot brute force attack. 512-bitarsnyckeln ger en sprickningssvårighet på 2512, vilket gör chifferet resistent mot denna metod [3] .
Se även
- avvikelser
Anteckningar
- ↑ 1 2 Panasenko, 2009 .
- ↑ Panasenko, 2009 , sid. 288-289.
- ↑ 1 2 3 4 Schneier Bruce. kapitel 13. s.7. // Tillämpad kryptografi.
- ↑ 1 2 Panasenko, 2009 , sid. 289-290.
- ↑ Panasenko, 2009 , sid. 291-292.
- ↑ Panasenko, 2009 , sid. 290-292.
- ↑ Panasenko, 2009, 289-290 .
- ↑ Panasenko, 2009 , sid. 293-294.
- ↑ Merkle, 1991 .
- ↑ 1 2 Biham, Biryukov, Shamir, 1999 , s. 131-137.
Litteratur
- Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
- Panasenko S.P. Kapitel 3 // Krypteringsalgoritmer. Särskild uppslagsbok - St Petersburg. : BHV-SPb , 2009. - S. 288-295. — 576 sid. — ISBN 978-5-9775-0319-8
- Zhdanov O.N., Zolotorev V.V. Metoder och medel för kryptografiskt informationsskydd: Lärobok .. - Krasnoyarsk: BHV-Petersburg, 2007. - 217 sid.
- Biham E. , Biryukov A. , Shamir A. Miss in the Middle Attacks on IDEA and Khufu // Fast Software Encryption :, FSE'99 Rom, Italien, 24–26 mars 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, Kalifornien, USA, 11-15 augusti 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
| Symmetriska kryptosystem | |
|---|---|
| Streama chiffer | |
| Feistel nätverk | |
| SP nätverk | |
| Övrig | |