Khafre

Khafre  je druhý (spolu s Khufu ) algoritmus navržený Ralphem Merklem ( Khufu ( Khufu ) a Khafre ( Khafre )  jsou jména egyptských faraonů . Tento algoritmus je podobný Khufuově algoritmu , ale nepotřebuje žádný předvýpočet. S-boxy jsou nezávislé na klíči , Khafre používá pevné S-boxy. Algoritmus Khafre neomezuje maximální počet kol algoritmu a maximální velikost klíče, na rozdíl od Khufu. Velikost klíče však musí být násobkem 64 bitů a počet kol musí být násobkem 8. Merkle navrhuje, aby se s Khafrem používaly 64 nebo 128bitové klíče a že Khafre bude mít více kol než Khufu . Každý krok Khafrea je také obtížnější než krok Khufu , díky čemuž je Khafre pomalejší. Khafre však nepotřebuje žádný předvýpočet, což umožňuje rychlejší šifrování malých částí dat.

Historie

Bezprostředně před vytvořením algoritmu (konec roku 1990) byla většina tehdy existujících symetrických šifrovacích algoritmů přizpůsobena hardwarovým implementacím, přestože hardwarová implementace šifrovacího algoritmu je dražší než softwarová implementace, která znamená, že je hůře dostupný pro drtivou většinu.většinu potenciálních uživatelů.

Na konci devadesátých let Merkle jako součást týmu kryptografů z Xeroxu vyvinul šifru - Khafre, pojmenovanou po egyptském faraonovi Khafre, synovi Khufa. O rok později získal Xerox patent na algoritmus Khafre, jehož komerční použití bylo držitelem patentu zakázáno.

Postuláty algoritmu

Algoritmus Khafre je blokový algoritmus založený na síti Feistel a splňuje následující postuláty:

• Softwarové implementace algoritmů mají téměř neomezené (ve srovnání s hardwarovými kodéry) množství operační a energeticky nezávislé paměti. To umožňuje šifrovacímu algoritmu používat velké množství paměti k ukládání substitučních tabulek, kulatých klíčů atd.
• V tomto šifrovacím algoritmu se používají pouze optimalizované elementární operace pro použití v softwarových implementacích.

Principy tvorby algoritmu

Na základě zkušeností získaných při návrhu algoritmu DES byly formulovány následující principy:

1. Velikost 56bitového klíče DES bylo možné zvětšit, protože náklady na paměť se staly zanedbatelné.
2. 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ší.
3. DES S-boxy s pouze 64 4bitovými prvky jsou příliš malé. Jak paměť zlevnila, bylo možné zvětšit i S-boxy. Navíc se všech osm S-boxů používá současně. Ačkoli je to vhodné pro hardware, není to nutné pro softwarovou implementaci. Musí být implementováno sériové (spíše než paralelní) použití S-boxů.
4. Eliminujte úvodní a koncové permutace, protože jsou kryptograficky nesmyslné
5. 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.
6. Kritéria návrhu S-boxu by měla být veřejná, na rozdíl od DES

Algoritmus

Parametry algoritmu

Algoritmus šifruje data v blocích o velikosti 64 bitů. Dále je během procesu šifrování každý blok rozdělen na 2 dílčí bloky o velikosti každého 32 bitů.

Algoritmus má následující parametry:

1. Velikost šifrovacího bloku je 64 bitů.
2. Velikost šifrovacího klíče musí být násobkem 64 bitů
3. S-box má 8 vstupních bitů a 32 výstupních bitů. Je trvalý a nezávisí na šifrovacím klíči. Každé kolo používá jiný S-blok.

Vytvoření standardní substituční tabulky

• Nejprve se vytvoří tabulka o 256 řádcích po 5 sloupcích. 1. sloupec obsahuje všechny možné hodnoty bajtů (od 00 do FF). Zbývající sloupce jsou vyplněny stejnými hodnotami. Níže je fragment takové tabulky.

• Bajty jsou v každém sloupci prohozeny pomocí sady jednoho milionu náhodných čísel od RAND Corporation, publikované v roce 1995, jako pseudonáhodná sekvence.

Generování podklíče

1. V první fázi se inicializuje 64bajtový klíč a nepoužité bity se nastaví na nulu.
2. Ve druhé fázi je tento blok zašifrován algoritmem Khafre v režimu řetězení šifrových bloků. Nulová sekvence se bere jako podklíče pro každý oktet. Ukáže se pseudonáhodná 64bajtová sekvence, která závisí pouze na šifrovacím klíči. Je pravděpodobné, že k inicializaci podklíčů může být zapotřebí více bajtů, takže tento krok lze opakovat vícekrát.
3. Ve třetí fázi se z přijaté sady bitů vyberou podklíče ( Ko .. Kn +3 ) .

Postup šifrování

Zdrojový text je rozdělen do bloků po 64 bitech. Na samém začátku postupu tento blok podstoupí následující operace:

• 64bitový datový blok je rozdělen na dva 32bitové podbloky, L (levý) a R (pravý).
• Dílčí bloky jsou bitově XORed s podklíči Ko a K1 (pro L- Ko , pro R - Ki ) .

Poté se spustí šifrování. Počet opakování kroků se rovná počtu kol.

1. V prvním kroku prochází posledních 8 bitů levého dílčího bloku S-boxem, který produkuje 32 bitů jako výstup. Každý operační oktet také používá jiný S-box pro aktuální oktet.
2. V dalším kroku je hodnota získaná v předchozím kroku XORed s R.
3. Ve třetím kroku se L cyklicky posouvá doleva o jiný počet bitů, v závislosti na počtu zaokrouhlení v oktetu:
   • 8 - na 3 a 4 kola
   • 24 - na 7 a 8 kol
   • 16 - pro další kola
4. Ve čtvrtém kroku jsou podbloky prohozeny (levý podblok je nyní R, pravý je L).
5. Kroky 1 až 4 se opakují 8krát, přičemž S-Block se mění pro každé opakování.
6. V posledním kroku jsou podbloky opět bitově XORed s podklíči K n+2 a K n+3 (pro L - K n+3 , pro R - K n+2 je n číslo oktetu)

Poté se všechny kroky znovu R-krát opakují.