Hardwarová syntéza kryptoalgoritmu IDEA

Hardwarová syntéza kryptoalgoritmu IDEA . IDEA je symetrický blokový šifrovací algoritmus . Pro rok 2019 je IDEA spolehlivým šifrovacím algoritmem kvůli nedostatku úspěšných lineárních kryptoanalytických útoků . Jeho použití v kritických aplikacích, jako je armáda nebo použití v balíku šifrovacího softwaru PGP , vyžaduje efektivní, vysoce bezpečnou a správnou hardwarovou implementaci.

Spolehlivost IDEA

B. Schneier [1] a A. Tanenbaum [2] považují IDEA za jeden z nejbezpečnějších dostupných kryptografických algoritmů. Ve skutečnosti neexistují žádné úspěšné lineární kryptoanalytické útoky na IDEA a nejsou známy žádné jiné algebraické slabiny IDEA než ty, které objevil J Daemen [3] . Yoan Dimen provedl útok pomocí třídy 251 slabých klíčů během šifrování, což usnadnilo nalezení a obnovení klíče. Protože však existuje velký počet možných klíčů, tento výsledek neovlivňuje praktické zabezpečení šifry pro poskytnuté šifrování.

Hardwarové implementace minulých let

Hardwarová implementace tohoto kryptografického algoritmu byla oblastí aktivního vývoje.

Níže jsou uvedeny nejběžnější implementace:

Prezentována implementace jádra FPGA pro IDEA [4] . K implementaci IDEA použili systém s jedním jádrem, což bylo provedeno pomocí Xilinx FPGA .

Byla zkoumána vysoce výkonná implementace IDEA pomocí paralelních i sériových architektur [6] . Pro hodnocení a analýzu výkonu použili Xilinx Virtex XCV300-6 a XCV1000-6 FPGA.

Odkaz [7] uvádí srovnání implementace IDEA mezi počítači pro všeobecné použití SRC-6E a HC-36.

Implementace IDEA

Následující implementace je dílem Ali E. Abdallaha a Issama W. Damaje [8] .

Vyjasnění: stream je metoda postupného předávání hodnot. Znamená to sekvenci zpráv v kanálu, přičemž každá zpráva představuje jinou hodnotu. Za předpokladu, že je stream ukončen, bude po odeslání poslední hodnoty hlášen konec přenosu (EOT).

Zvažte algoritmus IDEA jako tři hlavní bloky. Globální pohled na tyto bloky by ukazoval šifrování (nebo dešifrování) jako blok se 2 vstupy, soukromým klíčem a otevřeným textem (nebo šifrovaným textem) a výstupem šifrovaného textu (nebo otevřeného textu). Dva zbývající bloky jsou generování podsekcí šifrování a dešifrování. V případě generování šifrovacích podsekcí bude blok přijímat příchozí soukromé klíče a vydávající požadované podsekce. Generátor dešifrovacích podklíčů vloží vygenerované šifrovací podklíče a vydá dešifrovací klíče. Pojďme definovat některé typy, které budou použity v následující specifikaci (Následující kód je napsán v HDL ):

type Private = [ Bool ] type SubKey = Typ Int Prostý text = [ Int ] typ Ciphertext = [ Int ] modVal = 65536

Základní stavební bloky v rámci IDEA

• Bitové XOR

• Přidání 16bitových celých čísel modulo 65536 ( )

• Násobit 16bitová celá čísla modulo 65537 ( ), kde celý blok vstupních nul je považován za .

Generování klíčů

Ze 128bitového šifrovacího klíče je generováno 52 16bitových podklíčů. Algoritmus generování je následující:

• Prvních osm podklíčů se vybírá přímo z klíče rozdělením klíče (128bitový seznam) na osm segmentů stejné délky (16bitové).

• Je použit kruhový posun 25bitových pozic. na klíč z předchozího kroku a poté je extrahováno osm podklíčů.

• Tento postup se opakuje, dokud není vygenerováno všech 52 podklíčů, tj. 8krát a 4 vyhrazené klíče v konečné fázi.

V následující specifikaci je generováním podklíčů  funkce generationEncSubKeys, tato funkce bere jako vstup šifrovací klíč a vydává seznam 52 16bitových podklíčů. Generuje odpovídající podklíče pro každou směnu pomocí funkce createSubKeys. Vygenerované klíče se pak spojí do jednoho seznamu. 52 podklíčů je pak extrahováno ze seznamu a převedeno na celá čísla ekvivalentní 16prvkovému boolovu seznamu, který představuje každý podklíč. Převod se provádí pomocí funkce btoi:

createEncSubKeys  :: Private -> [ SubKey ] generovatEncSubKeys klíč = map ( btoi ) ( take 52 ( foldr1 ( ++ ) ( map generationSubKeys ( take 8 ( keyRotation key ))))))

Všechny posunuté klávesy jsou určeny funkcí keyRotation, která je opakovaně generuje. Tato funkce používá opakující se polymorfní funkci , která přebírá funkci f a seznam xs a opakovaně aplikuje funkci f na xs. V tomto případě opakovaně vrací klíč ve 25bitových krocích. Proto budou hodnoty 0, 25, 50, 75, 100, 125:

keyRotation  :: Private -> Bool keyRotation key = vzít 8 ( opakovaná ( shift 25 ) klávesa ) repeat  :: ( a -> a ) -> a -> [ a ] ​​​​repeated fx = x: opakované f ( f x ) shift  : : Int -> [ a ] ​​​​-> [ a ] ​​Shift n klíč = ( n klíč klesnout ) ++ ( vzít n klíč )

Chcete-li vygenerovat 16bitové podklíče z posunutých klíčů, použijte funkci createEncSubKeys na funkci generationSubKeys v seznamu posunutých klíčů. Funkce createSubKeys používá segs, která vybírá n podseznamů ze seznamu xs:

createSubKeys  :: Private -> [ SubKey ] generationSubKeys klíč = segs 16 klíčových segmentů  :: Int -> [ a ] ​​​​-> a segs n [] = [] segs n xs = ( vzít n xs ) : segs n ( pokles n xs )

Nakonec jsou požadované podklíče zabaleny do seznamů 6 prvků v jednom pomocí balíčku funkcí:

pack  :: [ a ] ​​​​- > pack = segs 6

Dešifrování

Po vygenerování šifrování zvažte vygenerování dešifrování, kde každá podsekce dešifrování je funkcí jedné z podsekcí šifrování. Vztah mezi šifrovacím a dešifrovacím klíčem je definován ve funkci generationDecSubKeys. Tato funkce se provádí mapováním funkce do připraveného seznamu indexů. Funkce provádění používá addInv a mulInv, které odpovídají aditivní a multiplikativní inverzní. Tato funkce také používá funkce vyššího řádu, které přebírají seznam funkcí a seznam hodnot a aplikují (pomocí funkce použít) každou funkci v prvním seznamu na odpovídající hodnotu ve druhém seznamu (pomocí funkce vyššího řádu zipWith) :

createDecSubKeys  :: [ SubKey ] -> [ SubKey ] generationDecSubKeys eKeys = take 52 ( foldr1 ( ++ ) ( map perform indexs )) , kde indexy = mapWith fs ( map reverse ( pack ( reverse [ l | l <- [ 0. 51 ]]))) f1 ( xs ) = posun 2 xs f2 ( xs ) = zipWith ( + ) ( kopie ( xs !! 2 ) 6 ) [ 0 , 2 , 1 , 3 , - 2 , - 1 ] f3 = idfs = [ f1 , f2 , f2 , f2 , f2 , f2 , f2 , f2 , f3 ] provést ( as ) = mapWith [ mulInv , addInv , addInv , mulInv , id , id ]( zipWith ( !! ) ys ( kopie eKe ) as ) copy :: a -> Int -> [ a ] ​​​​copy x n = [ x | já <- [ 1. . n ]] mapWith :: [( a -> b )] -> [ a ] ​​​​-> [ b ] mapWith fs = zipWith ( použít ) fs použít :: ( a -> b ) -> a -> b použít f = f      

Definujeme aditivní inverzní aritmetickou operaci (modulo ) a multiplikativní inverzní aritmetickou operaci (modulo ), kterými jsou funkce addInv a mulInv. Funkce addInv jednoduše zadá číslo, které se má odečíst od hodnoty modulo:

addInv  :: Int -> Int addInv a = modVal - a

Pro výpočet multiplikativní inverzní aritmetické operace se používá rozšířený euklidovský algoritmus [9] . Funkční specifikace vypadá takto:

mulInv  :: Int -> IntmulInv 0 = 0 mulInv b = if ( y < 0 ) then (( modVal + 1 ) + y ) else ( y ) kde y = ( extendEucA ( modVal + 1 ) b ) !! 2 extendEucA :: Int -> Int -> [ Int ] extendEucA a b | b == 0 = [ a , 1 , 0 ] | jinak = iterateSteps [ a , b , 0 , 1 , 1 , 0 ] iterateSteps ls = if (( ls [ 1 ]) > 0 ) then ( iterateSteps s2 ) else ([( ls [ 0 ]), ( ls [ 3 ] ), ( ls [ 5 ])]) , kde s1 = ( krok1 ls ) s2 = ( krok 2 [( ls [ 1 ]), ( s1 [ 1 ]), ( ls [ 2 ]), ( s1 [ 2 ]), ( ls [ 4 ]), ( s1 [ 3 ])]) krok1 :: [ Int ] -> [ Int ] krok1 ls1 = [ q , ( ls1 [ 0 ]) - ( q * ( ls1 [ 1 ])), ( ls1 [ 3 ]) - ( q * ( ls1 [ 2 ])), ( ls1 [ 5 ]) - ( q * ( ls1 [ 4 ]))] kde q = div ( ls1 [ 0 ]) ( ls1 [ 1 ]) krok2 :: [ Int ] -> [ Int ] krok2 ls1 = [( ls1 [ 0 ]), ( ls1 [ 1 ]), ( ls1 [ 3 ]), ( ls1 [ 2 ]), ( ls1 [ 5 ] ), ( ls1 [ 4 ])]

Analýza a hodnocení výkonu

Výsledky pro různé šifrovací (dešifrovací) konstrukce odrážejí změnu výkonu. První test je nejrychlejší s maximální propustností 21,33 Gb/s (průměrná propustnost 21,5 Mb/s) zaznamenaným při testování náhodných vstupních vektorů s klíčem = {1, 2, 3, 4, 5, 6, 7 , osm} . Druhý test, který odpovídá sekvenčnímu provádění kol, má očekávanou nejpomalejší propustnost (maximální propustnost 5,82 Gbps a průměrná propustnost 19,53 Mbps). Stojí za zmínku, že různé implementace modulárních aritmetických operací významně ovlivňují výkon IDEA.

Srovnání s jinými implementacemi

Implementace pomocí Xilinx FPGA (Davor Runje a Mario Kovač) je výkonově mnohem horší, je to způsobeno také použitím samostatného napájení v PCI slotech (vstupní/výstupní vedení a hlavní logika rozšiřujících karet jsou odděleny zabránit poškození ovladače).

KH Tsoi, PHW Leong představil výkonnější implementaci založenou na Xilinx Virtex XCV300-6 FPGA. Propustnost ale opět nebyla na nejvyšší úrovni a za implementací Ali E. Abdallaha a Issama W. Damaje řádově zaostávala, zatímco bitová sériová implementace nabízí 600 Mbps na 150 MHz. Vypočítaný výkon bitově paralelní a bitové sériové implementace na zařízení XCV1000-6 je 5,25 Gb/s, respektive 2,40 Gb/s [10] .

Allen Michalski, Kris Gaj a Tarek El-Ghazawi dosáhli výsledků 2,5 MB/s – propustnost zpracování Crypto++. Rychlost hardwarového zpracování platformy SRC je 18,5krát vyšší pro jednotlivá datová pole a přibližně 24krát vyšší pro nepřetržitý proud polí.

Poznámky

  1. ↑ Anthony J. Farrell. Prado, Martial. Praktická španělská gramatika: Průvodce pro samouky. New York: John Wiley & Sons, 1983; Prado, Martial. Praktičtější španělská gramatika: Průvodce pro samouky. New York: John Wiley & Sons, 1984 Prado, Marcial. Praktická španělská gramatika: Průvodce pro samouky. New York: John Wiley & Sons, 1983. Pp. viii, 360; Prado, Martial. Praktičtější španělská gramatika: Průvodce pro samouky. New York: John Wiley & Sons, 1984. Pp. vi, 378.  Canadian Modern Language Review. — 1985-01. - T. 41 , č.p. 3 . — S. 587–588 . - ISSN 1710-1131 0008-4506, 1710-1131 . - doi : 10.3138/cmlr.41.3.587 .
  2. ↑ A. Tanenbaum. počítačové sítě. Prentice Hall, Upper Saddle River, NJ, třetí vydání, 1997
  3. ↑ J. Daemen, R. Govaerts a J. Vandewalle. Slabé klíče pro IDEA. Springer-Verlag, strany 224-231, 1994
  4. ↑ D. Runje a M. Kováč. Univerzální implementace jádra FPGA se silným šifrováním. In Proceedings of Design, Aautomatizace a Test in Europe, strany 923-924, 1998
  5. ↑ Kompromisy v paralelních a sériových implementacích mezinárodního algoritmu pro šifrování dat IDEA .
  6. ↑ OYH Cheung, KH Tsoi, PHW Leong a MP Leong. Kompromisy v paralelních a sériových implementacích mezinárodního šifrovacího algoritmu IDEA. Lecture Notes in Computer Science, 2162:333, 2001
  7. ↑ Allen Michalski, Kris Gaj a Tarek El-Ghazawi. Srovnání implementace šifrovacího kryptosystému IDEA na dvou univerzálních rekonfigurovatelných počítačích. In Field-Programmable Logic and Applications: 13th International Conference, FPL, Lecture Notes in Computer Science, strany 204-219, Lisabon - Portugalsko, 2003. Springer
  8. ↑ Rekonfigurovatelná hardwarová syntéza kryptografického algoritmu IDEA Ali E. ABDALLAH a Issam W. DAMAJ Research Institute for Computing, Spojené království
  9. ↑ Jean-Luc Beuchat. Modulární násobení pro FPGA implementaci blokové šifry IDEA. V Ed Deprettere, Shuvra Bhattacharyya, Joseph Cavallaro, Alain Darte a Lothar Thiele, editoři, Proceedings of the 14th IEEE International Conference on Application-Specific Systems, Architectures and Processors, strany 412-422. IEEE Computer Society, 2003
  10. ↑ Kompromisy v paralelních a sériových implementacích mezinárodního algoritmu pro šifrování dat IDEA .