IDEA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. října 2016; kontroly vyžadují 29 úprav .

IDEA, International Data Encryption Algorithm

Tvůrce	Ascom
Vytvořeno	1991
zveřejněno	1991
Velikost klíče	128 bit
Velikost bloku	64 bit
Počet kol	8.5
Typ	Úprava sítě Feistel [1]

IDEA ( anglicky International Data Encryption Algorithm , International Data Encryption Algorithm ) je symetrický blokový šifrovací algoritmus patentovaný švýcarskou společností Ascom . Známý pro použití v softwarovém balíčku pro šifrování PGP . V listopadu 2000 byla IDEA představena jako kandidát pro projekt NESSIE programu Evropské komise IST ( Information Societies Technology ) .

Historie

První verzi algoritmu vyvinuli v roce 1990 Lai Xuejia ( Xuejia Lai ) a James Massey ( James Massey ) ze švýcarského institutu ETH Zürich (na základě smlouvy s Hasler Foundation , která se později sloučila do Ascom-Tech AG) jako náhradu. pro DES ( Eng. Data Encryption Standard , standard pro šifrování dat) a nazval jej PES ( Eng. Proposed Encryption Standard , navrhovaný standard šifrování). Poté, po zveřejnění práce Bihama a Shamira o diferenciální kryptoanalýze PES, byl algoritmus vylepšen, aby se zvýšila kryptografická síla , a byl pojmenován IPES ( anglicky Improved Proposed Encryption Standard , vylepšený navrhovaný šifrovací standard). O rok později byl přejmenován na IDEA ( International Data Encryption Algorythm ) .

Popis

Protože IDEA používá 128bitový klíč a 64bitovou velikost bloku , je prostý text rozdělen do bloků po 64 bitech. Pokud takový oddíl není možný, je poslední blok vycpán různými způsoby s určitou posloupností bitů. Aby se zabránilo úniku informací o každém jednotlivém bloku, používají se různé režimy šifrování . Každý původní nezašifrovaný 64bitový blok je rozdělen do čtyř podbloků po 16 bitech, protože všechny algebraické operace používané v procesu šifrování se provádějí na 16bitových číslech. IDEA používá stejný algoritmus pro šifrování a dešifrování.

Zásadní inovací v algoritmu je použití operací z různých algebraických grup , konkrétně:

modulo přidání $2^{16}$
modulo násobení $2^{{16}}+1$
bitový exkluzivní OR ( XOR ).

Tyto tři operace jsou neslučitelné v tom smyslu, že:

žádné dva z nich nesplňují zákon rozdělování, tzn. $a*(b+c)\ \neq \ (a*b)+(a*c)$
žádné dva z nich nesplňují asociační zákon, tzn. $a+(b\oplus c)\ \neq \ (a+b)\oplus c$

Použití těchto tří operací znesnadňuje kryptoanalýzu IDEA než DES , který je založen výhradně na operaci XOR , a také eliminuje použití S-boxů a nahrazovacích tabulek. IDEA je modifikací sítě Feistel .

Generování klíčů

Ze 128bitového klíče se vygeneruje šest 16bitových podklíčů pro každé z osmi kol šifrování a čtyři 16bitové podklíče se vygenerují pro výstupní transformaci. Celkem bude vyžadováno 52 = 8 x 6 + 4 různé podklíče po 16 bitech. Proces generování padesáti dvou 16bitových klíčů je následující:

Nejprve je 128bitový klíč rozdělen do osmi 16bitových bloků. Toto bude prvních osm podklíčů po 16 bitech − $(K_{1}^{{(1)}}K_{2}^{{(1)}}K_{3}^{{(1)}}K_{4}^{{(1)}}K_ {5}^{{(1)}}K_{6}^{{(1)}}K_{1}^{{(2)}}K_{2}^{{(2)}})$
Tento 128bitový klíč se poté otočí doleva o 25 pozic, načež se nový 128bitový blok opět rozdělí na osm 16bitových bloků. Toto je dalších osm podklíčů po 16 bitech - $(K_{3}^{{(2)}}K_{4}^{{(2)}}K_{5}^{{(2)}}K_{6}^{{(2)}}K_ {1}^{{(3)}}K_{2}^{{(3)}}K_{3}^{{(3)}}K_{4}^{{(3)}})$
Postup otáčení a blokování pokračuje, dokud není vygenerováno všech 52 16bitových podklíčů.

Tabulka podklíčů pro každé kolo

Kulaté číslo	zapojit
jeden	$K_{1}^{{(1)}}K_{2}^{{(1)}}K_{3}^{{(1)}}K_{4}^{{(1)}}K_{ 5}^{{(1)}}K_{6}^{{(1)}}$
2	$K_{1}^{{(2)}}K_{2}^{{(2)}}K_{3}^{{(2)}}K_{4}^{{(2)}}K_{ 5}^{{(2)}}K_{6}^{{(2)}}$
3	$K_{1}^{{(3)}}K_{2}^{{(3)}}K_{3}^{{(3)}}K_{4}^{{(3)}}K_{ 5}^{{(3)}}K_{6}^{{(3)}}$
čtyři	$K_{1}^{{(4)}}K_{2}^{{(4)}}K_{3}^{{(4)}}K_{4}^{{(4)}}K_{ 5}^{{(4)}}K_{6}^{{(4)}}$
5	$K_{1}^{{(5)}}K_{2}^{{(5)}}K_{3}^{{(5)}}K_{4}^{{(5)}}K_{ 5}^{{(5)}}K_{6}^{{(5)}}$
6	$K_{1}^{{(6)}}K_{2}^{{(6)}}K_{3}^{{(6)}}K_{4}^{{(6)}}K_{ 5}^{{(6)}}K_{6}^{{(6)}}$
7	$K_{1}^{{(7)}}K_{2}^{{(7)}}K_{3}^{{(7)}}K_{4}^{{(7)}}K_{ 5}^{{(7)}}K_{6}^{{(7)}}$
osm	$K_{1}^{{(8)}}K_{2}^{{(8)}}K_{3}^{{(8)}}K_{4}^{{(8)}}K_{ 5}^{{(8)}}K_{6}^{{(8)}}$
výstupní transformace	$K_{1}^{{(9)}}K_{2}^{{(9)}}K_{3}^{{(9)}}K_{4}^{{(9)}}$

Šifrování

Struktura algoritmu IDEA je znázorněna na obrázku. Proces šifrování se skládá z osmi stejných kol šifrování a jedné výstupní transformace. Původní otevřený text je rozdělen do bloků po 64 bitech. Každý takový blok je rozdělen do čtyř podbloků po 16 bitech. Na obrázku jsou tyto podbloky označeny , , , . Každé kolo používá své vlastní podklíče podle tabulky podklíčů. Následující operace se provádějí s 16bitovými podklíči a podbloky s prostým textem: $D_{1}$ $D_{2}$ $D_{3}$ $D_{4}$

násobení modulo = 65537 a místo nuly $2^{{16}}+1$ $2^{16}$
modulo přidání $2^{16}$
bitový XOR

Na konci každého šifrovacího kola jsou čtyři 16bitové dílčí bloky, které se pak použijí jako vstupní dílčí bloky pro další šifrovací kolo. Výstupní transformace je zkrácené kolo, konkrétně čtyři 16bitové podbloky ve výstupu osmého kola a čtyři odpovídající podbloky jsou podrobeny operacím:

modulo násobení $2^{{16}}+1$
modulo přidání $2^{16}$

Po provedení výstupní transformace je zřetězení podbloků , a šifrový text. Poté se vezme další 64bitový blok prostého textu a šifrovací algoritmus se opakuje. Toto pokračuje, dokud nejsou zašifrovány všechny 64bitové bloky původního textu. $D_{1}'$ $D_{2}'$ $D_{3}'$ $D_{4}'$

Matematický popis

64bitový blok otevřeného textu je rozdělen do čtyř stejných 16bitových podbloků. $(D_{1}^{{(0)}},D_{2}^{{(0)}},D_{3}^{{(0)}},D_{4}^{{(0) }})$
Pro každé kolo se počítá: $(i=1...8)$

$A^{{(i)}}\ =\ D_{1}^{{(i-1)}}*K_{1}^{{(i)}}$
$B^{{(i)}}\ =\ D_{2}^{{(i-1)}}+K_{2}^{{(i)}}$
$C^{{(i)}}\ =\ D_{3}^{{(i-1)}}+K_{3}^{{(i)}}$
$D^{{(i)}}\ =\ D_{4}^{{(i-1)}}*K_{4}^{{(i)}}$
$E^{{(i)}}\ =\ A^{{(i)}}\oplus C^{{(i)}}$
$F^{{(i)}}\ =\ B^{{(i)}}\oplus D^{{(i)}}$

$D_{1}^{{(i)}}\ =\ A^{{(i)}}\oplus ((F^{{(i)}}+E^{{(i)}}*K_{ 5}^{{(i)}})*K_{6}^{{(i)}})$
$D_{2}^{{(i)}}\ =\ C^{{(i)}}\oplus ((F^{{(i)}}+E^{{(i)}}*K_{ 5}^{{(i)}})*K_{6}^{{(i)}})$
$D_{3}^{{(i)}}\ =\ B^{{(i)}}\oplus (E^{{(i)}}*K_{5}^{{(i)}}+ (F^{{(i)}}+E^{{(i)}}*K_{5}^{{(i)}})*K_{6}^{{(i)}})$
$D_{4}^{{(i)}}\ =\ D^{{(i)}}\oplus (E^{{(i)}}*K_{5}^{{(i)}}+ (F^{{(i)}}+E^{{(i)}}*K_{5}^{{(i)}})*K_{6}^{{(i)}})$
Výsledkem provedení osmi kol budou následující čtyři dílčí bloky $(D_{1}^{{(8)}},D_{2}^{{(8)}},D_{3}^{{(8)}},D_{4}^{{(8) }})$

Provede se výstupní transformace : $(i=9)$

$D_{1}^{{(9)}}\ =\ D_{1}^{{(8)}}*K_{1}^{{(9)}}$
$D_{2}^{{(9)}}\ =\ D_{3}^{{(8)}}+K_{2}^{{(9)}}$
$D_{3}^{{(9)}}\ =\ D_{2}^{{(8)}}+K_{3}^{{(9)}}$
$D_{4}^{{(9)}}\ =\ D_{4}^{{(8)}}*K_{4}^{{(9)}}$
Výsledkem provedení výstupní transformace je šifrový text $(D_{1}^{{(9)}},D_{2}^{{(9)}},D_{3}^{{(9)}},D_{4}^{{(9) }})$

Přepis

Metoda výpočtu použitá k dešifrování textu je v podstatě stejná jako metoda použitá k jeho šifrování. Jediný rozdíl je v tom, že k dešifrování se používají různé podklíče. Během procesu dešifrování musí být podklíče použity v opačném pořadí. První a čtvrtý podklíč i-tého kola dešifrování jsou získány z prvního a čtvrtého podklíče (10-i)-tého kola šifrování multiplikativní inverzí. Pro 1. a 9. kolo se druhý a třetí dešifrovací podklíč získá z druhého a třetího podklíče 9. a 1. šifrovacího kola aditivní inverzí. Pro kola 2 až 8 se druhý a třetí dešifrovací podklíč získá ze třetího a druhého podklíče šifrovacích kol 8 až 2 aditivní inverzí. Poslední dva podklíče i-tého kola dešifrování se rovnají posledním dvěma podklíčům (9-i)-tého kola šifrování. Multiplikativní inverze podklíče K je označena 1/K a . Protože je prvočíslo , má každé nenulové celé číslo K jedinečné multiplikativní inverzní modulo . Aditivní inverze podklíče K je označena -K a . $(1/K)*K=1\ mod\ (2^{{16}}+1)$ $2^{{16}}+1$ $2^{{16}}+1$ $-K+K=0\ mod\ (2^{{16}})$

Tabulka podklíčů pro každé kolo

Kulaté číslo	zapojit
jeden	$1/K_{1}^{{(9)}}\ -K_{2}^{{(9)}}\ -K_{3}^{{(9)}}\ 1/K_{4}^ {{(9)}}\ K_{5}^{{(8)}}\ K_{6}^{{(8)}}$
2	$1/K_{1}^{{(8)}}\ -K_{3}^{{(8)}}\ -K_{2}^{{(8)}}\ 1/K_{4}^ {{(8)}}\ K_{5}^{{(7)}}\ K_{6}^{{(7)}}$
3	$1/K_{1}^{{(7)}}\ -K_{3}^{{(7)}}\ -K_{2}^{{(7)}}\ 1/K_{4}^ {{(7)}}\ K_{5}^{{(6)}}\ K_{6}^{{(6)}}$
čtyři	$1/K_{1}^{{(6)}}\ -K_{3}^{{(6)}}\ -K_{2}^{{(6)}}\ 1/K_{4}^ {{(6)}}\ K_{5}^{{(5)}}\ K_{6}^{{(5)}}$
5	$1/K_{1}^{{(5)}}\ -K_{3}^{{(5)}}\ -K_{2}^{{(5)}}\ 1/K_{4}^ {{(5)}}\ K_{5}^{{(4)}}\ K_{6}^{{(4)}}$
6	$1/K_{1}^{{(4)}}\ -K_{3}^{{(4)}}\ -K_{2}^{{(4)}}\ 1/K_{4}^ {{(4)}}\ K_{5}^{{(3)}}\ K_{6}^{{(3)}}$
7	$1/K_{1}^{{(3)}}\ -K_{3}^{{(3)}}\ -K_{2}^{{(3)}}\ 1/K_{4}^ {{(3)}}\ K_{5}^{{(2)}}\ K_{6}^{{(2)}}$
osm	$1/K_{1}^{{(2)}}\ -K_{3}^{{(2)}}\ -K_{2}^{{(2)}}\ 1/K_{4}^ {{(2)}}\ K_{5}^{{(1)}}\ K_{6}^{{(1)}}$
výstupní transformace	$1/K_{1}^{{(1)}}\ -K_{2}^{{(1)}}\ -K_{3}^{{(1)}}\ 1/K_{4}^ {{(jeden)}}$

Příklad

Pro usnadnění jsou čísla uvedena v hexadecimálním tvaru.

Příklad šifrování

Používáme K = (0001,0002,0003,0004,0005,0006,0007,0008) jako 128bitový klíč a M = (0000,0001,0002,0003) jako 64bitový prostý text

Tabulka podklíčů a podbloků pro každé kolo

Kolo	Kulaté klíče						Hodnoty datových bloků
Kolo	$K_{1}^{{(i)}}$	$K_{2}^{{(i)}}$	$K_{3}^{{(i)}}$	$K_{4}^{{(i)}}$	$K_{5}^{{(i)}}$	$K_{6}^{{(i)}}$	$D_{1}^{{(i)}}$	$D_{2}^{{(i)}}$	$D_{3}^{{(i)}}$	$D_{4}^{{(i)}}$
—	—	—	—	—	—	—	0000	0001	0002	0003
jeden	0001	0002	0003	0004	0005	0006	00f0	00f5	010a	0105
2	0007	0008	0400	0600	0800	0a00	222f	21b5	f45e	e959
3	0c00	0e00	1000	0200	0010	0014	0f86	39be	8ee8	1173
čtyři	0018	001c	0020	0004	0008	000 c	57df	ac58	c65b	ba4d
5	2800	3000	3800	4000	0800	1000	8e81	ba9c	f77f	3a4a
6	1800	2000	0070	0080	0010	0020	6942	9409	e21b	1c64
7	0030	0040	0050	0060	0000	2000	99 d0	c7f6	5331	620e
osm	4000	6000	8000	a000	c000	e001	0a24	0098	ec6b	4925
9	0080	00c0	0100	0140	-	-	11fb	ed2b	0198	6de5

Příklad dešifrování

Jako 128bitový klíč používáme K = (0001,0002,0003,0004,0005,0006,0007,0008) a jako 64bitový šifrový text C = (11fb, ed2b, 0198, 6de5)

Tabulka podklíčů a podbloků pro každé kolo

Kolo	Kulaté klíče						Hodnoty datových bloků
Kolo	$K_{1}^{{'(i)}}$	$K_{2}^{{'(i)}}$	$K_{3}^{{'(i)}}$	$K_{4}^{{'(i)}}$	$K_{5}^{{'(i)}}$	$K_{6}^{{'(i)}}$	$D_{1}^{{(i)}}$	$D_{2}^{{(i)}}$	$D_{3}^{{(i)}}$	$D_{4}^{{(i)}}$
jeden	fe01	ff40	ff00	659a	c000	e001	d98d	d331	27f6	82b8
2	ffd	8000	a000	cccc	0000	2000	bc4d	e26b	9449	a576
3	a556	ffb0	ffc0	52ab	0010	0020	0aa4	f7ef	da9c	24e3
čtyři	554b	ff90	e000	fe01	0800	1000	cca 46	fe5b	dc58	116d
5	332d	c800	d000	ffd	0008	000 c	748f	8f08	39 da	45 ccm
6	4aab	ffe0	ffe4	c001	0010	0014	3266	045e	2fb5	b02e
7	aa96	f000	f200	ff81	0800	0a00	0690	050a	00fd	1dfa
osm	4925	fc00	fff8	552b	0005	0006	0000	0005	0003	000 c
9	0001	fffe	ffd	c001	-	-	0000	0001	0002	0003

Režimy šifrování

IDEA je blokový šifrovací algoritmus, který pracuje s 64bitovými bloky. Pokud velikost zašifrovaného textu neodpovídá této pevné velikosti, blok je doplněn na 64.

Algoritmus se používá v jednom z následujících režimů šifrování [ISO 1] :

Režim elektronického číselníku ( ECB ) .
Režim Cipher Block Chaining ( CBC ) .
Šifrovaný režim zpětné vazby ( CFB ) .
Režim výstupní zpětné vazby ( OFB )

Algoritmus lze také použít pro výpočet

Ověřovací kód zprávy (MAC ) [ ISO 2] [ISO 3]
hodnoty hash [ISO 4]
distribuce klíčů [ISO 5]

Implementace hardwaru

Hardwarová implementace má oproti softwaru následující výhody:

výrazné zvýšení rychlosti šifrování díky použití paralelismu při provádění operací
nižší spotřeba energie

První implementaci algoritmu IDEA na integrovaném obvodu ( Very Large Scale Integration ) vyvinuli a ověřili Lai, Massey a Murphy v roce 1992 pomocí 1,5 µm procesu a technologie CMOS [IS 1] . Rychlost šifrování tohoto zařízení byla 44 Mb/s.

V roce 1994 vyvinuli zařízení VINCI Kariger, Bonnenberg, Zimmerman et al . Rychlost šifrování této implementace IDEA byla 177 Mb/s při taktovací frekvenci 25 MHz , výrobní proces 1,2 mikronu. Jednalo se o první polovodičové zařízení, které již mohlo být použito pro šifrování v reálném čase ve vysokorychlostních síťových protokolech , jako je ATM ( Asynchronous Transfer Mode , metoda asynchronního přenosu dat) nebo FDDI ( Fibre Distributed Data Interface , distribuované datové rozhraní pro optické vlákno) . . Rychlosti 177 Mb/s bylo dosaženo použitím poměrně sofistikovaného schématu zpracování potrubí a čtyř konvenčních modulonásobičů . Zařízení také používá dva jednosměrné vysokorychlostní 16bitové datové porty. Tyto porty zajišťují konstantní zatížení šifrovacích bloků [IS 2] [IS 3] . $2^{{16}}+1$

Hned příští rok představili Voltaire a spol. zařízení s rychlostí šifrování 355 Mb/s. Této rychlosti bylo dosaženo díky implementaci jednoho kola šifrování na 0,8mikronovém procesu pomocí technologie CMOS . Architektura tohoto zařízení zahrnuje paralelní autotest založený na systému zpracování chyb modulo 3, který umožňuje určit chyby vyskytující se v jednom nebo více bitech v datové cestě IDEA, což umožňuje spolehlivě zabránit poškození šifrovaných resp. dešifrovaná data [IS 4] .

Nejvyšší rychlosti šifrování 424 Mb/s v roce 1998 na jediném integrovaném obvodu dosáhla skupina inženýrů vedená Salomaem z Federální univerzity v Rio de Janeiru COPPE na 0,7mikronovém procesu na frekvenci 53 MHz. Architektura této implementace využívá prostorový i časový paralelismus dostupný v algoritmu IDEA [IS 5] .

Ve stejném roce byla na čtyřech zařízeních XC4020XL implementována IDEA od Menser et al. Rychlost šifrování 4 x XC4020XL je 528 Mbps [IS 6] .

V roce 1999 byly společností Ascom představeny dvě komerční implementace IDEA. První se nazývá IDEACrypt Kernel a dosahuje rychlosti 720 Mbps pomocí 0,25 µm technologie [IS 7] . Druhý se nazývá IDEACrypt Coprocessor, založený na jádře IDEACrypt Kernel a dosahuje rychlosti šifrování 300 Mb/s [IS 8] .

V roce 2000 inženýři z Čínské univerzity v Hong Kongu, Liong a kol., vydali šifrovací zařízení založená na Xilinx FPGA : Virtex XCV300-6 a XCV1000-6 [IS 9] . Rychlost šifrování Virtex XCV300-6 dosahuje 500 Mb/s při 125 MHz a očekávaný výkon XCV1000-6 je 2,35 Gb/s, díky čemuž je toto zařízení vhodné pro šifrování ve vysokorychlostních sítích. Vysoké rychlosti šifrování bylo dosaženo pomocí bitově sekvenční architektury pro provádění operace násobení modulo . Výsledky experimentů s různými zařízeními jsou shrnuty v tabulce: $2^{{16}}+1$

Specifikace zařízení

Zařízení (XCV)	300-6	600-6	1000-6
škálovatelnost	1x	2x	4x
počet sekcí	2801	5602	11204
použití oddílů	91,18 %	81,05 %	91,18 %
hodinová frekvence (MHz)	125,0	136,6	147,1
šifrování za sekundu (x ) $10^{6}$	7,813	17,075	36,775
rychlost šifrování (Mb/s)	500,0	1092,8	2353,6
latence (µs)	7,384	6,757	6,275

O něco později titíž vývojáři navrhli zařízení založené na Xilinx Virtex XCV300-6 FPGA založené na bitparalelní architektuře. Při implementaci pomocí bitově paralelní architektury na 82 MHz je šifrovací rychlost XCV300-6 1166 Mb/s, zatímco s bitově sériovou architekturou bylo dosaženo 600 Mb/s při 150 MHz. XCV300-6 s oběma architekturami je škálovatelný. Při použití bit-paralelní architektury je odhadovaná rychlost šifrování XCV1000-6 5,25 Gb/s [IS 10] .

Také v roce 2000 Goldstein a kol., vyvinuli zařízení PipeRench FPGA využívající 0,25 µm výrobní proces s rychlostí šifrování 1013 Mbps [IS 11] .

Vývoj hardwarových implementací IDEA

Rok	Implementace	Rychlost šifrování (Mb/s)	Autoři
1998	software	23,53	Limpaa
2000	software [1]	44	Limpaa
1992	ASIC 1,5 µm CMOS	44	Bonnenberg a další.
1994	ASIC 1,2 µm CMOS	177	Curiger, Zimmermann a další.
1995	ASIC 0,8 µm CMOS	355	Wolter a další
1998	ASIC 0,7 µm CMOS	424	Salomao a další.
1998	4x XC4020XL	528	Mencer a další.
1999	ASIC 0,25 µm CMOS	720	Ascom
2000	Xilinx Virtex XCV300-6	1166	Leong a další.
2000	ASIC 0,25 µm CMOS	1013	Goldstein a další.

V roce 2002 vyšla práce o implementaci IDEA na FPGA stejné firmy Xilinx z rodiny Virtex-E. XCV1000E-6BG560 na 105,9 MHz dosahuje rychlosti šifrování 6,78 Gb/s. [2]

Implementace založené na FPGA jsou dobrou volbou, pokud jde o vysoce výkonnou kryptografii. Mezi aplikacemi jsou VPN ( anglicky Virtual Private Networks , virtuální privátní síť), komunikace přes satelit a také hardwarové akcelerátory pro šifrování velkých souborů nebo celých pevných disků .

Zabezpečení

Algoritmus IDEA se objevil jako výsledek drobných úprav algoritmu PES. Obrázek ukazuje struktury obou algoritmů a je zřejmé, že zde není tolik změn:

násobení podbloku s podklíčem druhého kola nahrazeným sčítáním $D_{2}$
přidání podbloku s podklíčem čtvrtého kola nahrazeným násobením $D_{4}$
změněný posun dílčích bloků na konci kola

Jeden z nejslavnějších kryptologů na světě, Bruce Schneier , ve své knize "Applied Cryptography" poznamenal: "...je úžasné, jak takové drobné změny mohou vést k tak velkým rozdílům."

Ve stejné knize z roku 1996 Bruce Schneier řekl o IDEA: "Myslím, že je to nejlepší a nejrobustnější blokový algoritmus, který byl dosud publikován."

Algoritmus IDEA používá 64bitové bloky. Délka bloku musí být dostatečná, aby skryla statistické charakteristiky původní zprávy. Ale s rostoucí velikostí bloku exponenciálně roste složitost implementace kryptografického algoritmu. Algoritmus IDEA používá 128bitový klíč. Délka klíče musí být dostatečně velká, aby se zabránilo opakování klíče. Chcete-li otevřít 128bitový klíč pomocí vyhledávání hrubou silou, za předpokladu, že je znám otevřený text a odpovídající šifrovaný text, jsou vyžadována šifrování (v řádu ). S touto délkou klíče je IDEA považováno za poměrně bezpečné. Vysokou kryptografickou sílu IDEA poskytují také následující vlastnosti: $2^{128}$ $10^{{38}}$

zmatek – šifrování závisí na klíči složitým a matoucím způsobem
rozptyl – každý kousek otevřeného textu ovlivňuje každý kousek šifrovaného textu

Lai Xuejia ( Xuejia Lai ) a James Massey ( James Massey ) provedli důkladnou analýzu IDEA s cílem objasnit její kryptografickou odolnost vůči diferenciální kryptoanalýze . Za tímto účelem představili koncept Markovovy šifry a ukázali, že odolnost vůči diferenciální kryptoanalýze lze modelovat a kvantifikovat [bezpečnost 1] . V IDEA nebyly žádné lineární nebo algebraické slabiny. Bihamův pokus o útok pomocí kryptoanalýzy s propojeným klíčem byl také neúspěšný [síla 2] .

Existují úspěšné útoky použitelné na IDEA s méně koly (plná IDEA má 8,5 kola). Útok je považován za úspěšný, pokud k prolomení šifry vyžaduje méně operací než úplný výčet klíčů. Metoda útoku Williho Meiera se ukázala jako účinnější než útok hrubou silou pouze pro IDEA se 2 ranami [tvrdost 3] . Metoda setkání uprostřed otevřela IDEA se 4,5 koly. To vyžaduje znalost všech bloků z kódového slovníku a složitost analýzy je operací [tvrdost 4] . Nejlepší útok pro rok 2007 se vztahuje na všechny klíče a dokáže rozlousknout IDEA na 6 kol [Fortitude 5] . $2^{64}$ $2^{112}$

Slabé klíče

Existují velké třídy slabých klíčů . Jsou slabé v tom smyslu, že existují procedury, které umožňují určit, zda klíč patří do dané třídy, a poté klíč samotný. V současné době jsou známy následující:

$2^{{23}}+2^{{35}}+2^{{51}}$ klíče slabé na diferenciální kryptoanalýzu . Členství ve třídě lze vypočítat v operacích pomocí shodného prostého textu. Autoři tohoto útoku navrhli modifikaci algoritmu IDEA. Tato úprava spočívá v nahrazení podklíčů odpovídajícími , kde r je číslo šifrovacího kola. Přesná hodnota a není kritická. Například, když (v hexadecimálním zápisu ) jsou tyto slabé klíče vyloučeny [síla 6] . $2^{{51}}$ $2^{12}$ $K_{i}^{{(r)}}$ $K_{i}^{{'(r)}}\ =a\oplus K_{i}^{{(r)}}$ $a\ =\ 0dae$

$2^{{63}}$ klíče slabé k lineární diferenciální kryptoanalýze [síla 7] . Členství v této třídě se určuje pomocí testu na přidružených klíčích.

$2^{{53}}+2^{{56}}+2^{{64}}$ Slabé klíče byly nalezeny pomocí metody bumerangového útoku navržené Davidem Wagnerem [ síla 8 ] . Zkouška příslušnosti do této třídy se provádí v operacích a bude vyžadovat paměťové buňky [tvrdost 9] . $2^{16}$ $2^{16}$

Existence takto velkých tříd slabých klíčů neovlivňuje praktickou kryptografickou sílu algoritmu IDEA, protože celkový počet všech možných klíčů je . $2^{128}$

Porovnání s některými blokovými algoritmy

Pro srovnání s IDEA jsou vybrány DES , Blowfish a GOST 28147-89 . Volba DES je dána tím, že jako jeho náhrada byla navržena IDEA. Blowfish je vybrán, protože je rychlý a byl vytvořen renomovaným kryptologem Brucem Schneierem. Pro srovnání je také vybrána GOST 28147-89 , bloková šifra vyvinutá v SSSR . Jak je vidět z tabulky, velikost klíče IDEA je větší než u DES, ale menší než u GOST 28147-89 a Blowfish. Rychlost šifrování IDEA na Intel486SX /33MHz je 2krát vyšší než u DES, vyšší než u GOST 28147-89, ale téměř 2krát nižší než u Blowfish.

Tabulka parametrů

Algoritmus	Velikost klíče, bit	Délka bloku, bit	Počet kol	Rychlost šifrování na Intel486SX / 33 MHz (KB/s)	Základní operace
DES	56	64	16	35	Substituce, permutace, bitový XOR
IDEA	128	64	osm	70	Modulo násobení, modulo sčítání , bitové XOR $2^{{16}}+1$ $2^{16}$
blowfish	32-448	64	16	135	Modulo sčítání , substituce, bitové XOR $2^{32}$
GOST 28147-89	256	64	32	53	Modulo sčítání , substituce, bitové XOR, kruhový posun $2^{32}$

Níže je tabulka srovnávající rychlosti softwarové implementace na procesorech Pentium , Pentium MMX , Pentium II , Pentium III . Označení 4-way IDEA znamená, že se paralelně provádějí 4 šifrovací nebo dešifrovací operace. K tomu se algoritmus používá v paralelních režimech šifrování. Helger Limpaa implementoval 4-cestnou IDEA v režimu šifrování elektronické číselnice ( CBC4 ) a režimu čítače (CTR4). Tak bylo dosaženo rychlosti šifrování/dešifrování 260-275 Mbps pomocí CBC4 na 500 MHz Pentium III a pomocí CTR4 na 450 MHz Pentium III . Ve výše uvedené tabulce jsou rychlosti škálovány na hypotetický stroj 3200 MHz.

Srovnávací tabulka rychlosti

Bloková šifra	Délka bloku, bit	Počet cyklů	Rychlost šifrování, MB/s	Autor	procesor
Náměstí	128	192	254,4	Limpaa	Pentium II
RC6	128	219	222,8	Limpaa	Pentium II , Pentium III
4cestný NÁPAD	4x64	440	222,0	Limpaa	Pentium III
Rijndael	128	226	216,0	Limpaa	Pentium II , Pentium III
Náměstí	128	244	200,0	Bosselaers	Pentium
4cestný NÁPAD	4x64	543	180,0	Limpaa	Pentium MMX
SC2000	128	270	180,8	Limpaa	Pentium II , Pentium III , gcc (bez asm )
4cestný NÁPAD	4x64	554	176,4	Limpaa	AMD Athlon
Dvě ryby	128	277	176,4	Aoki, Limpaa	Pentium II , Pentium III
Rijndael	128	300	162,8	Gladman	Pentium III
Kamélie	128	302	161,6	Aoki	Pentium II , Pentium III
MARS	128	306	160,0	Limpaa	Pentium II , Pentium III
blowfish	64	158	154,4	Bosselaers	Pentium
RC5-32/16	64	199	122,8	Bosselaers	Pentium
CAST5	64	220	110,8	Bosselaers	Pentium
DES	64	340	72,0	Bosselaers	Pentium
IDEA	64	358	68,0	Limpaa	Pentium MMX
BEZPEČNĚJŠÍ (S)K-128	64	418	58,4	Bosselaers	Pentium
ŽRALOK	64	585	41.6	Bosselaers	Pentium
IDEA	64	590	41.2	Bosselaers	Pentium
3DES	64	158	154,4	Bosselaers	Pentium

Výhody a nevýhody IDEA

Výhody

V softwarové implementaci na Intel486SX oproti DES je IDEA dvakrát rychlejší, což je výrazný nárůst rychlosti, IDEA má délku klíče 128 bitů, oproti 56 bitům u DES, což je dobré zlepšení proti hrubé síle. Pravděpodobnost použití slabých klíčů je velmi malá a činí . IDEA je rychlejší než algoritmus GOST 28147-89 (v softwarové implementaci na Intel486SX ). Použití IDEA v režimech paralelního šifrování na procesorech Pentium III a Pentium MMX vám umožní dosáhnout vysokých rychlostí. Ve srovnání s finalisty AES je 4-way IDEA jen o málo pomalejší než Pentium II RC6 a Rijndael , ale rychlejší než Twofish a MARS . Na Pentiu III je 4cestná IDEA ještě rychlejší než RC6 a Rijndael . Výhodou je také dobrá znalost a odolnost vůči známým prostředkům kryptoanalýzy. $1/2^{{64}}$

Nevýhody

IDEA je výrazně pomalejší, téměř dvakrát pomalejší než Blowfish (v softwarové implementaci na Intel486SX ). IDEA nepočítá se zvýšením délky klíče.

Srovnání s některými blokovými šiframi v implementaci PGP

Srovnávací tabulka hlavních parametrů blokových šifer v implementaci PGP [2]

Algoritmus	Klíč, bit	Blok, bit	Poznámky
Triple-DES	168	64	síť Feistel ; má prostor poloslabých a slabých kláves.
AES ( Rijndael )	256	128	Na základě operací s tabulkou datového pole; přijat jako stát standard v USA; má vysokou kryptografickou sílu.
CAST6	128	64	síť Feistel ; nemá slabé klíče; odolný vůči kryptoanalýze.
IDEA	128	64	Na základě směšovacích operací z různých algebraických grup; má slabý klíčový prostor; ne všechny práce o kryptoanalýze byly zveřejněny.
Dvě ryby	256	128	síť Feistel ; rychlé šifrování, pomalé nastavení klíče; je poměrně složitý, což ztěžuje analýzu; má velkou bezpečnostní rezervu.
blowfish	maximálně 448	64	síť Feistel ; rychlé šifrování, pomalé nastavení klíče; poměrně jednoduchý; má malý prostor pro slabé klávesy; má velkou bezpečnostní rezervu.

Použití IDEA

V minulosti byl algoritmus patentován v mnoha zemích a samotný název „IDEA“ byl registrovanou ochrannou známkou. Poslední patent spojený s algoritmem však vypršel v roce 2012 a nyní lze samotný algoritmus volně používat pro jakýkoli účel. V roce 2005 společnost MediaCrypt AG (držitel licence IDEA) oficiálně představila novou šifru IDEA NXT (původně nazvanou FOX), která měla nahradit IDEA. Typické aplikace pro IDEA:

šifrování audio a video dat pro kabelovou televizi , videokonference , dálkové studium , VoIP
ochrana obchodních a finančních informací odrážejících výkyvy trhu
komunikační linky přes modem , router nebo ATM linku, technologie GSM
čipové karty
veřejný balíček důvěrného e-mailu verze PGP v2.0 [3] a (volitelně) v OpenPGP

Registrace algoritmu IDEA v normách

ISO 9979/0002 : ISO Register of Cryptographic Algorithms - ISO registrace kryptografických algoritmů
UN / EDIFACT ( anglicky United Nations / Electronic Data Interchange For Administration, Commerce, and Transport - OSN / elektronická výměna dat pro administrativu, obchod a dopravu): EDIFACT Security Implementation Guidelines - bezpečnostní doporučení
Doporučení ITU-T H.233: Systém důvěrnosti pro audiovizuální služby - Doporučení H.233: Systém důvěrnosti pro audiovizuální služby
IETF ( Internet Engineering Task Force ) RFC 3058 : Použití šifrovacího algoritmu IDEA v CMS
TBSS: Telematic Base Security Services - základní zabezpečení služby vzdáleného zpracování dat
OpenSSL je open source kryptografický balíček pro práci s SSL / TLS
WAP ( Wireless Application Protocol ) WTLS ( Wireless Transport Layer Security )
NESSIE ( angl. New European Schemes for Signature, Integrity, and Encryption - nové evropské projekty v oblasti digitálního podpisu, integrity a šifrování)

Zdroje

Xuejia Lai a James Massey. Návrh nového standardu blokového šifrování, EUROCRYPT 1990. - Springer-Verlag, 1991. - S. 389-404. — ISBN 3-540-53587-X .
Xuejia Lai a James Massey. Markovovy šifry a diferenciální kryptoanalýza = Markovovy šifry a diferenciální kryptoanalýza, Advances in Cryptology, EUROCRYPT 1991. - Springer-Verlag, 1992. - S. 17-38. — ISBN 3540546200 .
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (anglicky) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0
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 .
Huseyin Demirci, Erkan Türe, Ali Aydin Selçuk. A New Meet in the Middle Attack on the IDEA Block Cipher : Proceedings of Conf. / 10. výroční workshop o vybraných oblastech kryptografie, 2003.
Helger Limpaa. IDEA: Šifra pro multimediální architektury? = IDEA: Šifra pro multimediální architektury? In Stafford Tavares a Henk Meijer, editoři, Selected Areas in Cryptography '98, svazek 1556 Lecture Notes in Computer Science - Springer-Verlag, 17.-18. srpna 1998. - S. 248-263.

Poznámky

↑ Menezes, Oorschot, Vanstone, 1996 , pp. 263.
↑ Srovnávací přehled PGP algoritmů . Získáno 10. listopadu 2008. Archivováno z originálu 13. května 2012. (Ruština)
↑ S. Garfinkel. Docela dobré soukromí = PGP: Docela dobré soukromí. - 1. prosince 1994. - 430 s. — ISBN 978-1565920989 .

Zabezpečení

↑ X. Lai. O návrhu a zabezpečení blokových šifer, řada ETH ve zpracování informací // Poznámky k přednáškám z informatiky = Poznámky k přednáškám z informatiky. - Berlín / Heidelberg: Springer-Verlag, 10. dubna 2006 - S. 213-222. — ISBN 978-3-540-62031-0 .
↑ E. Biham, osobní komunikace, 1993
↑ W. Meier, HTL. Brugg Windisch, Švýcarsko. O bezpečnosti blokové šifry IDEA // Workshop o teorii a aplikaci kryptografických technik o pokroku v kryptologii EUROCRYPT '93 Proceedings. - Secaucus, NJ, USA: Springer-Verlag New York, Inc, 1994. - S. 371-385. — ISBN 3-540-57600-2 .
↑ Biham E. , Biryukov A. , Shamir A. Miss in the Middle Attacks on IDEA and Khufu // Fast Software Encryption : 6th International Workshop , 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
↑ E. Biham, O. Dunkelman, N. Keller. A New Attack on 6-round IDEA // Lecture Notes in Computer Science = Lecture Notes In Computer Science. - Berlín / Heidelberg: Springer-Verlag, 18. srpna 2007 - S. 211-224. — ISBN 978-3-540-74617-1 .
↑ J. Daemen, R. Govaerts a J. Vandewalle. Weak Keys for IDEA // Poznámky k přednášce z teorie výpočetních systémů; Práce komise na 13. výroční mezinárodní konferenci o kryptologii EUROCRYPT 1993 = Lecture Notes In Computer Science; Sborník příspěvků z 13. výroční mezinárodní kryptologické konference o pokroku v kryptologii. - Londýn, Velká Británie: Springer-Verlag, 1993. - S. 224-231. — ISBN 3-540-57766-1 .
↑ P. Hawkes. Diferenciálně-lineární slabé klíčové třídy IDEA // Lecture Notes in Computer Science = Lecture Notes In Computer Science. - Berlín / Heidelberg: Springer-Verlag, 28. července 2006 - S. 112-126. — ISBN 978-3-540-64518-4 .
↑ D. Wagner. The Boomerang Attack // Přednáškové poznámky o teorii výpočetních systémů; Panelová práce na 6. mezinárodním semináři o rychlém softwarovém šifrování = Lecture Notes In Computer Science; Sborník příspěvků z 6. mezinárodního workshopu o rychlém softwarovém šifrování. - Londýn, Velká Británie: Springer-Verlag, 1999. - S. 156-170. — ISBN 3-540-66226-X .
↑ A. Biryukov, J. Nakahara Jr, B. Preneel, J. Vandewalle. New Weak-Key Classes of IDEA // Přednáškové poznámky o teorii výpočetních systémů; Práce komise na čtvrté mezinárodní konferenci o informační a komunikační bezpečnosti = Lecture Notes In Computer Science; Sborník příspěvků ze 4. mezinárodní konference o informační a komunikační bezpečnosti. - Londýn, Velká Británie: Springer-Verlag, 2002. - S. 315-326. — ISBN 3-540-00164-6 . Archivováno 28. září 2011 na Wayback Machine

Implementace hardwaru

↑ H. Bonnenberg, A. Curiger, N. Felber, H. Kaeslin a X. Lai. VLSI implementace nové blokové šifry // Sborník příspěvků z mezinárodní konference IEEE o počítačovém designu: VLSI v počítačích a procesorech. - Washington, DC, USA: IEEE Computer Society, 1991. - S. 510-513. — ISBN 0-8186-2270-9 .
↑ A. Curiger, H. Bonnenberg, R. Zimmerman, N. Felber, H. Kaeslin a W. Fichtner. VINCI: VLSI implementace nové blokové šifry tajného klíče IDEA // Proceedings of the IEEE Custom Integrated Circuits Conference. - San Diego, CA, USA: IEEE Computer Society, 9.-12. května 1993. - S. 15.5.1-15.5.4. - ISBN 0-7803-0826-3 .
↑ R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber a W. Fichtner. 177Mb/s VLSI implementace mezinárodního algoritmu šifrování dat // IEEE Journal of Solid-State Circuits. - Březen 1994. - T. 29 . - S. 303-307 .
↑ S. Wolter, H. Matz, A. Schubert a R. Laur. O implementaci VLSI mezinárodního algoritmu šifrování dat IDEA // Sborník z IEEE International Symposium on Circuits and Systems. - Seattle, Washington, USA: IEEE Computer Society, 30. dubna - 3. května 1995. - S. 397-400. - ISBN 0-7803-2570-2 .
↑ SLC Salomao, VC Alves a EMC Filho. HiPCrypto: Vysoce výkonný VLSI kryptografický čip // Sborník z jedenácté výroční konference IEEE ASIC . - Rochester, NY, USA: IEEE Computer Society, 13.-16. září 1998. - S. 7-11. - ISBN 0-7803-4980-6 .
↑ O. Mencer, M. Morf a M. J. Flynn. Hardwarový software tri-design šifrování pro mobilní komunikační jednotky // Sborník z IEEE International Conference on Acoustics, Speech and Signal Processing. - Seattle, Washington, USA: IEEE Computer Society, 12.-15. května 1998. - S. 3045-3048. - ISBN 0-7803-4428-6 .
↑ Ascom, IDEACrypt Kernel Data Sheet, 1999.
↑ Ascom, IDEACrypt Coprocessor Data Sheet, 1999.
↑ MP Leong, OYH Cheung, KH Tsoi a PHW Leong. Bitová sériová implementace mezinárodního algoritmu pro šifrování dat IDEA // Sborník ze sympozia IEEE z roku 2000 o programovatelných vlastních výpočetních strojích. - Seattle, Washington, USA: IEEE Computer Society, 2000. - S. 122-131. — ISBN 0-7695-0871-5 .
↑ OYH Cheung, KH Tsoi, PHW Leong a MP Leong. Kompromisy v paralelních a sériových implementacích mezinárodního algoritmu šifrování dat IDEA // Kryptografický hardware a vestavěné systémy 2001 = CHES 2001: kryptografický hardware a vestavěné systémy. - INIST-CNRS, Cote INIST : 16343, 35400009702003.0270: Springer, Berlín, ALLEMAGNE ETATS-UNIS (2001) (Monographie), 2001. - S. 333-347. — ISBN 3-540-42521-7 .
↑ SC Goldstein, H. Schmit, M. Budiu, M. Moe a RR Taylor. Piperench: Překonfigurovatelná architektura a kompilátor // Počítač. - Duben 2000. - T. 33 , č. 4 . - S. 70-77 .

Normy

↑ ISO 10116: Zpracování informací — Provozní režimy pro algoritmus n-bitové blokové šifry.
↑ ISO 9797: Techniky šifrování dat — Mechanismus integrity dat využívající funkci kryptografické kontroly využívající algoritmus blokové šifry.
↑ ISO 9798-2: Informační technologie – Bezpečnostní technika – Mechanismy autentizace entit – Část 2: Autentizace entit pomocí symetrických technik.
↑ ISO 10118-2: Informační technologie - Bezpečnostní technika - Hashovací funkce - Část 2: Hashovací funkce využívající n-bitový blokový šifrovací algoritmus.
↑ ISO 11770-2: Informační technologie - Bezpečnostní technika - Správa klíčů - Část 2: Mechanismy správy klíčů využívající symetrické techniky.

Odkazy

Hardwarová syntéza kryptoalgoritmu IDEA

Implementace

IDEA ve 448 bajtech 80x86 (anglicky) . - implementace IDEA v programovacím jazyce Assembler . Získáno 6. listopadu 2008. Archivováno z originálu 28. ledna 2012.

Rusové

Nejčastější dotazy týkající se symetrických šifer (odkaz není k dispozici) . - na základě materiálů konference fido7.ru.crypt. Získáno 6. listopadu 2008. Archivováno z originálu dne 22. srpna 2011. (Ruština)
Symetrické blokové šifry . — Analýza spolehlivosti blokových šifer při implementaci PGP. Staženo: 6. listopadu 2008. (Ruština)

Zahraniční

RSA FAQ o blokových šifrách . Získáno 6. listopadu 2008. Archivováno z originálu dne 19. října 2004.
SCAN vstup pro IDEA . Získáno 6. listopadu 2008. Archivováno z originálu 28. ledna 2012.
Applet IDEA (německy) . Získáno 6. listopadu 2008. Archivováno z originálu 1. února 2012.
Erläuterung und Schaubild zum Verfahren (německy) . Získáno 6. listopadu 2008. Archivováno z originálu 28. ledna 2012.

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher