International datakrypteringsalgoritme - International Data Encryption Algorithm
 En krypteringsrunde af IDEA
| |
| Generel | |
|---|---|
| Designere | Xuejia Lai og James Massey |
| Stammer fra | PES |
| Efterfølgere |
MMB , MESH , Akelarre , IDEA NXT (FOX) |
| Chiffer detaljer | |
| Nøgle størrelser | 128 bit |
| Blokstørrelser | 64 bits |
| Struktur | Lai – Massey -ordningen |
| Runder | 8.5 |
| Bedste offentlige kryptoanalyse | |
| Nøglen kan gendannes med en beregningskompleksitet på 2 126,1 ved hjælp af smalle cykler . Dette angreb er beregningsmæssigt hurtigere end et fuldt brute-force-angreb, men ikke i 2013 beregningsmæssigt muligt. | |
I kryptografi , Den International Data Encryption Algorithm ( IDEA ), oprindeligt kaldt Forbedret Foreslået Encryption Standard ( Ipes ), er en symmetrisk-key blok cipher designet af James Massey af ETH Zürich og Xuejia Lai og blev første gang beskrevet i 1991. Algoritmen var hensigten som en erstatning for datakrypteringsstandarden (DES). IDEA er en mindre revision af en tidligere cipher Proposed Encryption Standard (PES).
Chifferet blev designet under en forskningskontrakt med Hasler Foundation, som blev en del af Ascom-Tech AG. Chifferet blev patenteret i en række lande, men var frit tilgængeligt til ikke-kommerciel brug. Navnet "IDEA" er også et varemærke . De sidste patenter udløb i 2012, og IDEA er nu patentfrit og dermed helt gratis til alle anvendelser.
IDEA blev brugt i Pretty Good Privacy (PGP) v2.0 og blev inkorporeret, efter at den originale chiffer, der blev brugt i v1.0, BassOmatic , viste sig at være usikker. IDEA er en valgfri algoritme i OpenPGP -standarden.
Operation
IDEA opererer på 64-bit blokke ved hjælp af en 128-bit nøgle og består af en række på 8 identiske transformationer (en runde , se illustrationen) og en output-transformation ( halvrunden ). Processerne for kryptering og dekryptering ligner hinanden. IDEA får meget af sin sikkerhed ved at sammenflette operationer fra forskellige grupper - modulær addition og multiplikation og bitvis eXclusive OR (XOR) - som på en eller anden måde er algebraisk "uforenelige". Mere detaljeret er disse operatører, der alle beskæftiger sig med 16-bit mængder,:
- Bitvis XOR (eksklusiv OR) (markeret med en blå cirkel plus ⊕ ).
- Tilføjelse modulo 2 16 (markeret med en grøn boks plus ⊞ ).
- Multiplikationsmodul 2 16 + 1, hvor hele-nul-ordet (0x0000) i input tolkes som 2 16 , og 2 16 i output tolkes som hel-nul-ordet (0x0000) (betegnet med en rød cirkel prik ⊙ ).
Efter de 8 runder kommer en sidste “halvrunde”, outputtransformationen illustreret herunder (swap mellem de to midterste værdier annullerer swap i slutningen af den sidste runde, så der ikke er nogen netto swap):
Struktur
IDEAs overordnede struktur følger Lai – Massey -ordningen . XOR bruges til både subtraktion og addition. IDEA bruger en nøgleafhængig halvrunde funktion. For at arbejde med 16-bit ord (hvilket betyder 4 input i stedet for 2 for 64-bit blokstørrelsen), bruger IDEA Lai – Massey-skemaet to gange parallelt, hvor de to parallelle runde funktioner er vævet sammen med hinanden. For at sikre tilstrækkelig diffusion byttes to af delblokkene efter hver runde.
Nøgleplan
Hver runde bruger 6 16-bit undertaster, mens halvrunden bruger 4, i alt 52 i 8,5 runder. De første 8 undertaster udtrækkes direkte fra nøglen, hvor K1 fra første runde er de nederste 16 bits; yderligere grupper på 8 nøgler oprettes ved at dreje hovednøglen til venstre 25 bits mellem hver gruppe på 8. Det betyder, at den i gennemsnit roteres mindre end én gang i en runde i alt 6 rotationer.
Dekryptering
Dekryptering fungerer som kryptering, men rækkefølgen af runde nøgler er omvendt, og undersøglerne til de ulige runder er omvendt. For eksempel erstattes værdierne for undernøglerne K1 – K4 med inversen af K49 – K52 for den respektive gruppeopgave, K5 og K6 for hver gruppe bør erstattes af K47 og K48 for dekryptering.
Sikkerhed
Designerne analyserede IDEA for at måle dets styrke mod differential kryptanalyse og konkluderede, at den er immun under visse forudsætninger. Ingen vellykkede lineære eller algebraiske svagheder er blevet rapporteret. Fra 2007 kunne det bedste angreb, der blev anvendt på alle nøgler, bryde IDEA reduceret til 6 runder (den fulde IDEA -chiffer bruger 8,5 runder). Bemærk, at en "pause" er ethvert angreb, der kræver mindre end 2 128 operationer; 6-runde angrebet kræver 2 64 kendte klartekster og 2 126,8 operationer.
Bruce Schneier tænkte meget på IDEA i 1996 og skrev: "Efter min mening er det den bedste og mest sikre blokalgoritme, der er tilgængelig for offentligheden på nuværende tidspunkt." ( Applied Cryptography , 2. udg.) I 1999 anbefalede han imidlertid ikke længere IDEA på grund af tilgængeligheden af hurtigere algoritmer, nogle fremskridt i kryptanalysen og spørgsmålet om patenter.
I 2011 blev hele 8,5-runde IDEA brudt ved hjælp af et møde-i-midten-angreb. Uafhængigt i 2012 blev hele 8,5-runde IDEA brudt ved hjælp af et smalcyklisk angreb , med en reduktion af kryptografisk styrke på ca. 2 bits, svarende til effekten af det tidligere biclique-angreb på AES ; dette angreb truer imidlertid ikke IDEAs sikkerhed i praksis.
Svage nøgler
Den meget enkle nøgleplan gør IDEA til en klasse af svage nøgler ; nogle nøgler, der indeholder et stort antal 0 bits, producerer svag kryptering. Disse er i praksis lidt bekymrede, da de er tilstrækkeligt sjældne til, at de er unødvendige til eksplicit at undgå, når de genererer nøgler tilfældigt. Der blev foreslået en simpel løsning: XORing af hver undernøgle med en 16-bit konstant, f.eks. 0x0DAE.
Større klasser af svage nøgler blev fundet i 2002.
Dette er stadig af ubetydelig sandsynlighed for at være en bekymring for en tilfældigt valgt nøgle, og nogle af problemerne er løst af den konstante XOR, der blev foreslået tidligere, men papiret er ikke sikkert, om de alle er det. Et mere omfattende redesign af IDEA -nøgleplanen kan være ønskeligt.
Tilgængelighed
En patentansøgning om IDEA blev først indgivet i Schweiz (CH A 1690/90) den 18. maj 1990, derefter blev der indgivet en international patentansøgning i henhold til traktatsamarbejdet om patenter den 16. maj 1991. Patenter blev til sidst udstedt i Østrig , Frankrig , Tyskland , Italien , Holland , Spanien , Sverige , Schweiz , Det Forenede Kongerige , (European Patent Register entry for European patent nr. 0482154 , indgivet 16. maj 1991, udstedt 22. juni 1994 og udløbet 16. maj 2011), United Stater ( amerikansk patent 5.214.703 , udstedt 25. maj 1993 og udløb 7. januar 2012) og Japan (JP 3225440) (udløbet 16. maj 2011).
MediaCrypt AG tilbyder nu en efterfølger til IDEA og fokuserer på sin nye chiffer (officiel udgivelse i maj 2005) IDEA NXT , som tidligere blev kaldt FOX.
Litteratur
- Hüseyin Demirci, Erkan Türe, Ali Aydin Selçuk, Et nyt møde i det midterste angreb på IDEA Block Cipher, 10. årlige workshop om udvalgte områder inden for kryptografi , 2004.
- Xuejia Lai og James L. Massey, Et forslag til en ny blokkrypteringsstandard , EUROCRYPT 1990, s. 389–404
- Xuejia Lai og James L. Massey og S. Murphy, Markov-chiffer og differential kryptanalyse, Advances in Cryptology-Eurocrypt '91 , Springer-Verlag (1992), s. 17–38.
