Chufu
| Chufu | |
|---|---|
| Tvůrce | Ralph Merkle |
| Vytvořeno | 1990 |
| zveřejněno | 1990 |
| Velikost klíče | 512 bit |
| Velikost bloku | 64 bit |
| Počet kol | 8–32 (až 64) |
| Typ | Síť Feistel |
Khufu je symetrický blokový 64bitový kryptografický algoritmus vyvinutý Ralphem Merklem v roce 1990, pojmenovaný po egyptském faraonovi Cheopsovi .
Historické pozadí
V době vzniku algoritmu (konec roku 1990) byla naprostá většina tehdy existujících symetrických šifrovacích algoritmů přizpůsobena pro hardwarové implementace, přestože hardwarová implementace šifrovacího algoritmu je především , dražší než software, tedy hůře dostupný pro drtivou většinu potenciálních uživatelů.
Na konci 90. let tedy skupina kryptografů ze společnosti Xerox vyvinula šifru - Khufu, pojmenovanou po egyptském faraonovi Cheopsovi. Algoritmus byl dále představen v roce 1990 na konferenci CRYPTO .
Následující rok (1991) získala společnost Xerox Corporation patent na algoritmy Khufu a Khafre, v důsledku čehož bylo jejich komerční využití držitelem patentu zakázáno [1] .
Předpoklady pro vytvoření algoritmu
Khufuův algoritmus je blokový algoritmus založený na Feistelově síti , postavený na základě následujících postulátů:
- Softwarová implementace šifrovacího algoritmu má k dispozici mnohem více zdrojů (množství RAM a energeticky nezávislé paměti), na rozdíl od algoritmů založených na hardwarové implementaci . V důsledku toho se velké množství paměti používá k ukládání tabulek, kulatých klíčů atd.
- Tento šifrovací algoritmus používá pouze operace optimalizované pro použití v softwarových prostředích [2] .
Teoretickým základem Khufuova algoritmu jsou zkušenosti získané při vývoji algoritmu DES . Proto byly při návrhu algoritmu zohledněny následující předpoklady [3] :
- Velikost 56bitového klíče DES je příliš malá a měla by být zvětšena.
- Intenzivní používání permutací v DES je vhodné pouze pro hardwarové implementace, ale ztěžuje implementace softwaru. Nejrychlejší implementace DES provádějí permutace tabulkovým způsobem. Vyhledávání v tabulkách může poskytnout stejné "rozptylové" charakteristiky jako samotné permutace a může učinit implementaci flexibilnější.
- S-boxy DES, s pouze 64 4-bitovými prvky, jsou příliš malé, takže S - boxy je třeba zvětšit. Navíc je všech osm S -boxů použito současně. To je vhodné pro hardware, ale pro softwarovou implementaci se to zdá jako zbytečné omezení, takže je vhodnější implementovat větší velikost S -boxu. Kromě toho musí být implementováno sériové (spíše než paralelní) použití S - boxů při výměnách.
- Počáteční a konečná permutace jsou kryptograficky nesmyslné, takže je nutné je odstranit.
- Všechny rychlé implementace DES předem vypočítají klíče pro každý krok. Za této podmínky nemá smysl tyto výpočty komplikovat.
- Kritéria návrhu pro S -boxy by měla být veřejně dostupná.
Algoritmus
Parametry algoritmu
Algoritmus šifruje data v blocích, velikost bloku je 64 bitů. Poté se během procesu šifrování každý blok rozdělí na 2 dílčí bloky, každý o velikosti 32 bitů.
Ačkoli části klíče (podklíče K 0 .. K 3 ) se používají pouze k přidávání dílčích bloků na začátku a na konci algoritmu, hlavním účelem klíče je generovat S - boxy. Algoritmus poskytuje způsob, jak generovat S -boxy pomocí klíče [3] .
Algoritmus má následující parametry [4] [3] :
- Velikost šifrovacího bloku je 64 bitů.
- Velikost šifrovacího klíče musí být mezi 64 bity a 512 bity. V tomto případě musí být velikost klíče násobkem 64.
- S -blok má 8 vstupních bitů a 32 výstupních bitů. Je variabilní. Každý oktet používá svůj vlastní S - box [1] .
Algoritmus pro konstrukci S-boxů
Algoritmus se skládá z generování podklíčů a standardní substituční tabulky. Na základě standardní substituční tabulky jsou pro každý transformační oktet konstruovány S -boxy.
Vytvoření standardní substituční tabulky- Na začátku tohoto postupu je inicializována tabulka 256 řádků po 5 sloupcích. 1. sloupec obsahuje všechny možné hodnoty bajtů (od 00 do FF). Další čtyři sloupce jsou vyplněny podobnými hodnotami. Níže je fragment takové tabulky, který označuje 1., 2. a 256. řádek [5] .
| byte | 4 byty | |||
|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 00 |
| 01 | 01 | 01 | 01 | 01 |
| FF | FF | FF | FF | FF |
- V rámci jednoho sloupce dochází k bajtovým permutacím (postup je podobný permutaci bajtů v S -boxu při jeho vzniku), kde se jako pseudo - náhodná sekvence.
| byte | 4 byty | |||
|---|---|---|---|---|
| 00 | FA | A1 | 22 | 41 |
| 01 | 71 | 88 | B3 | patnáct |
| FF | 44 | jedenáct | C4 | E1 |
- Po těchto iteracích se vytvoří standardní substituční tabulka. Část této tabulky je uvedena výše.
Hlavní myšlenkou algoritmu Khufu je, že podklíče a S - boxy závisí na klíči kola, zatímco během každého kola používá algoritmus Khufu pouze jedno nahrazení posledních 8 bitů levého podbloku 32 bity, na rozdíl od Algoritmus DES. Zvažte algoritmus pro konstrukci S -boxů a podklíčů. Staví se v několika fázích [6] :
- V první fázi je klíč zapsán do 64 bajtů, které jsou k tomu přiděleny, zatímco nepoužité bity jsou nastaveny na nulu (připomeňme, že možná velikost klíče se pohybuje od 8 do 64 bajtů).
- Ve druhé fázi je tento blok zašifrován Khufuovým algoritmem v režimu řetězení šifrových bloků. Nulová sekvence je brána jako podklíče ( Ko .. K3 ) pro každý blok a standardní tabulka, která byla popsána výše, je brána jako substituční tabulky. Výstupem je pseudonáhodná 64bajtová sekvence, která závisí pouze na šifrovacím klíči. Je možné, že ke generování tabulek a podklíčů bude potřeba více bajtů, takže tento krok lze několikrát opakovat.
- Ve třetí fázi se z dané sady bitů vyberou hodnoty podklíče ( K 0 .. K 3 ) .
- Ve čtvrté fázi jsou vytvořeny S - boxy pro každý transformační oktet:
- Každý vypočítaný S -box je inicializován s původní standardní substituční tabulkou, která je popsána výše.
- V původní standardní tabulce substitucí se v cyklu po sloupcích (od 0 do 3 bajtu) provede cyklus přes řádky (od 0 do 255 bajtu), ve kterém každý aktuální bajt (byt na průsečíku aktuální řádek a aktuální sloupec) je zaměněn s jedním z následujících bajtů stejného sloupce, určeným náhodně (závisí na aktuálním bajtu pseudonáhodné sekvence); výsledkem je původní tabulka s „chaoticky“ přeskupenými byty každého sloupce [4] .
Postup šifrování
Šifrování probíhá přes jeden datový blok o 64 bitech. Na začátku procedury jsou na tomto bloku provedeny následující akce:
- 64bitový datový blok je rozdělen na dva bloky po 32 bitech (dále je budeme nazývat L a R).
- Každý z dílčích bloků je bitově XORed s dílčími bloky Ko a K1 ( pro levý dílčí blok - Ko , pro pravý - K1 ) .
Poté se provede šifrování. Počet opakování kroků se rovná počtu kol algoritmu.
- V prvním kroku se nízký bajt (posledních 8 bitů) levého podbloku předá přes S -blok, ze kterého se získá 4bajtová (32bitová) hodnota. Navíc v každém oktetu operací je použit S - blok určený pro tento oktet.
- Ve druhém kroku se hodnota získaná v předchozím kroku přičte bit po bitu (XOR) s pravým podblokem textu.
- Třetí krok se otočí doleva o jiný počet bitů levého podbloku, který závisí na kulatém čísle v oktetu:
- 8 - pokud je číslo 3 nebo 4
- 24 - pokud je číslo 7 nebo 8
- 16 - ve všech ostatních případech
- Ve čtvrtém kroku se prohodí levý a pravý podblok.
Poté se všechny kroky opakují znovu, včetně výměny S - bloku každých 8 kol.
Na konci procedury, po absolvování všech poskytnutých kol, se sčítání provede podobně jako sčítání s podklíči K 0 a K 1 , ale s dalšími podklíči K 2 a K 3 v tomto pořadí [7] .
Využití a udržitelnost
Závislost S -boxů a podklíčů je činí tajnými pro kryptoanalytika, což výrazně zvyšuje bezpečnost algoritmu proti diferenciální kryptoanalýze. Z toho vyplývá hlavní specifikace tohoto algoritmu: Khufuův algoritmus by měl být použit tam, kde je nutné vysokorychlostní šifrování velkého množství dat s vzácnou změnou klíče [8] .
Porovnání algoritmu s DES
Aby každý výstupní bit závisel na každém vstupu v algoritmu DES, musí být provedeno 5 kol. V Khufuově algoritmu vyžaduje podobná závislost 9 kol. V tomto případě je bezpečnostní faktor roven následujícímu výrazu: , kde parametry jsou počet kol , je počet kol potřebných pro úplné šifrování . Pro algoritmus DES a pro Khufuův algoritmus je tedy odpovídající parametr . V tomto případě je s ohledem na toto srovnání Khufuův algoritmus horší než algoritmus DES. S -boxy Khufuova algoritmu jsou však tajné, na rozdíl od algoritmu DES [9] .
Útoky na šifru
Nejlepší [10] útok na Khufuovu šifru provedli Gilbert a Showo. Útok byl proveden na 16-kolové Chufu. K úplnému odhalení skrytých informací bylo zapotřebí 2 31 vybraných otevřených textů. Tento výsledek ale nešlo rozšířit na více kol. Pokud je použit větší klíč, bude algoritmus jednoduše neefektivní [10] .
Šifra je odolná proti útoku hrubou silou. 512bitový klíč poskytuje obtížnost prolomení 2512, díky čemuž je šifra vůči této metodě odolná [3] .
Viz také
- odchylkami
Poznámky
- ↑ 1 2 Panasenko, 2009 .
- ↑ Panasenko, 2009 , s. 288-289.
- ↑ 1 2 3 4 Schneier Bruce. kapitola 13. str.7. // Aplikovaná kryptografie.
- ↑ 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 , pp. 131-137.
Literatura
- Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
- Panasenko S.P. Kapitola 3 // Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - S. 288-295. — 576 s. — ISBN 978-5-9775-0319-8
- Ždanov O.N., Zolotorev V.V. Metody a prostředky ochrany kryptografických informací: Učebnice .. - Krasnojarsk: 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 Řím, Itálie, 24.–26. března 1999 sborník / L. R. Knudsen - Berlín , Heidelberg , New York, NY , Londýn [atd.] : 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, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 1991. - S. 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
| Symetrické kryptosystémy | |
|---|---|
| Streamové šifry | |
| Síť Feistel | |
| Síť SP | |
| jiný | |