Internationell datakrypteringsalgoritm - International Data Encryption Algorithm
 En krypteringsrunda av IDEA
| |
| Allmän | |
|---|---|
| Formgivare | Xuejia Lai och James Massey |
| Härrörande från | PES |
| Efterträdare |
MMB , MESH , Akelarre , IDEA NXT (FOX) |
| Chifferdetaljer | |
| Nyckelstorlekar | 128 bitar |
| Blockstorlekar | 64 bitar |
| Strukturera | Lai – Massey -plan |
| Avrundningar | 8.5 |
| Bästa offentliga kryptanalys | |
| Nyckeln kan återställas med en beräkningskomplexitet på 2 126,1 med hjälp av smala cyklar . Denna attack är beräkningsmässigt snabbare än en full brutal kraftattack, men inte, från och med 2013, beräkningsmässigt genomförbar. | |
Inom kryptografi är International Data Encryption Algorithm ( IDEA ), ursprungligen kallad Improved Proposed Encryption Standard ( IPES ), en symmetrisk nyckelblockschiffer som designades av James Massey från ETH Zürich och Xuejia Lai och beskrevs först 1991. Algoritmen var avsedd som ersättning för datakrypteringsstandarden (DES). IDEA är en mindre översyn av en tidigare Cipher Proposed Encryption Standard (PES).
Chiffern utformades enligt ett forskningskontrakt med Hasler Foundation, som blev en del av Ascom-Tech AG. Chifferet patenterades i ett antal länder men var fritt tillgängligt för icke-kommersiellt bruk. Namnet "IDEA" är också ett varumärke . De sista patenten gick ut 2012, och IDEA är nu patentfritt och därmed helt gratis för alla användningsområden.
IDEA användes i Pretty Good Privacy (PGP) v2.0 och införlivades efter att den ursprungliga krypteringen som användes i v1.0, BassOmatic , befanns vara osäker. IDEA är en valfri algoritm i OpenPGP -standarden.
Drift
IDEA fungerar på 64-bitars block med en 128-bitars nyckel och består av en serie med 8 identiska transformationer (en runda , se bilden) och en utmatningstransformation ( halvrundan ). Processerna för kryptering och dekryptering är liknande. IDEA hämtar mycket av sin säkerhet genom att sammanfoga operationer från olika grupper - modulärt addition och multiplikation, och bitvis eXclusive OR (XOR) - som är algebraiskt ”inkompatibla” i någon mening. Mer detaljerat är dessa operatörer, som alla hanterar 16-bitars kvantiteter:
- Bitvis XOR (exklusiv ELLER) (markerad med en blå cirkel plus ⊕ ).
- Tilläggsmodul 2 16 (markerad med en grön låda plus ⊞ ).
- Multiplikationsmodul 2 16 + 1, där hela-nollordet (0x0000) i ingångar tolkas som 2 16 , och 2 16 i utmatning tolkas som hel-nollordet (0x0000) (betecknat med en röd cirkelpunkt ⊙ ).
Efter de åtta omgångarna kommer en sista "halvrunda", utmatningstransformationen som visas nedan (bytet mellan de två mellersta värdena avbryter bytet i slutet av den sista omgången, så att det inte blir någon nätbyte):
Strukturera
Den övergripande strukturen för IDEA följer Lai – Massey -systemet . XOR används för både subtraktion och addition. IDEA använder en nyckelberoende halvrundfunktion. För att arbeta med 16-bitars ord (vilket betyder 4 ingångar istället för 2 för 64-bitars blockstorlek) använder IDEA Lai – Massey-schemat två gånger parallellt, där de två parallella rundfunktionerna är sammanvävda med varandra. För att säkerställa tillräcklig diffusion byts två av delblocken efter varje omgång.
Viktigt schema
Varje omgång använder 6 16-bitars undertangenter, medan halvrundan använder 4, totalt 52 för 8,5 omgångar. De första 8 undernycklarna extraheras direkt från nyckeln, med K1 från den första omgången som de nedre 16 bitarna; ytterligare grupper om 8 nycklar skapas genom att rotera huvudnyckeln 25 bitar mellan varje grupp på 8. Detta innebär att den roteras mindre än en gång per omgång i genomsnitt för totalt 6 varv.
Dekryptering
Dekryptering fungerar som kryptering, men ordningen på de runda nycklarna är inverterad och undernycklarna för de udda rundorna är omvända. Exempelvis ersätts värdena för delnycklarna K1 – K4 med inversen av K49 – K52 för respektive gruppoperation, K5 och K6 för varje grupp bör ersättas av K47 och K48 för dekryptering.
säkerhet
Konstruktörerna analyserade IDEA för att mäta dess styrka mot differential kryptanalys och drog slutsatsen att den är immun under vissa antaganden. Inga framgångsrika linjära eller algebraiska svagheter har rapporterats. Från och med 2007 kan den bästa attacken som tillämpas på alla nycklar bryta IDEA reducerad till 6 omgångar (hela IDEA -krypteringen använder 8,5 omgångar). Observera att en "paus" är en attack som kräver mindre än 2 128 operationer; 6-omgångens attack kräver 2 64 kända klartexter och 2 126,8 operationer.
Bruce Schneier tänkte mycket på IDEA 1996 och skrev: "Enligt min mening är det den bästa och säkraste blockalgoritmen som är tillgänglig för allmänheten just nu." ( Applied Cryptography , 2nd ed.) Men 1999 rekommenderade han inte längre IDEA på grund av tillgängligheten av snabbare algoritmer, vissa framsteg i dess kryptanalys och patentfrågan.
2011 bröts hela 8,5-omgången IDEA med hjälp av en träff-i-mitten attack. Oberoende 2012 bröts hela 8,5-runda IDEA med hjälp av en smalcykelattack , med en minskning av kryptografisk styrka på cirka 2 bitar, liknande effekten av den tidigare cykelattacken på AES ; denna attack hotar dock inte säkerheten för IDEA i praktiken.
Svaga nycklar
Det mycket enkla nyckelschemat gör IDEA till en klass med svaga nycklar ; vissa nycklar som innehåller ett stort antal 0 bitar ger svag kryptering. Dessa är i praktiken lite oroande, eftersom de är så sällsynta att de är onödiga för att undvika att uttryckligen slumpmässigt generera nycklar. En enkel fix föreslogs: XORing av varje undernyckel med en 16-bitars konstant, till exempel 0x0DAE.
Större klasser av svaga nycklar hittades 2002.
Detta är fortfarande försumbart att vara ett problem för en slumpmässigt vald nyckel, och några av problemen åtgärdas av den konstanta XOR som föreslogs tidigare, men papperet är inte säkert om alla är det. En mer omfattande redesign av IDEA -nyckelschemat kan vara önskvärd.
Tillgänglighet
En patentansökan för IDEA ingavs först i Schweiz (CH A 1690/90) den 18 maj 1990, sedan inlämnades en internationell patentansökan enligt patentsamarbetsfördraget den 16 maj 1991. Patent beviljades så småningom i Österrike , Frankrike , Tyskland , Italien , Nederländerna , Spanien , Sverige , Schweiz , Storbritannien , (European Patent Register entry for European patent nr 0482154 , inlämnat 16 maj 1991, utfärdat 22 juni 1994 och gick ut 16 maj 2011), United States ( US Patent 5,214,703 , utfärdat den 25 maj 1993 och gick ut den 7 januari 2012) och Japan (JP 3225440) (gick ut den 16 maj 2011).
MediaCrypt AG erbjuder nu en efterträdare till IDEA och fokuserar på sin nya chiffer (officiell version maj 2005) IDEA NXT , som tidigare hette FOX.
Litteratur
- Hüseyin Demirci, Erkan Türe, Ali Aydin Selçuk, A New Meet in the Middle Attack on the IDEA Block Cipher, 10th Annual Workshop on Selected Areas in Cryptography , 2004.
- Xuejia Lai och James L. Massey, Ett förslag till en ny blockkrypteringsstandard , EUROCRYPT 1990, s. 389–404
- Xuejia Lai och James L. Massey och S. Murphy, Markov-chiffer och differentialkryptoanalys, Advances in Cryptology-Eurocrypt '91 , Springer-Verlag (1992), s. 17–38.
