International Data Encryption Algorithm (IDEA) — opis, budowa i zastosowania

Budowa i zasada działania

IDEA to konstrukcja rundowa składająca się z ośmiu pełnych rund oraz jednej pół-rundy wyjściowej (w sumie 8,5 rundy). Każda pełna runda korzysta z sześciu subkluczy, a pół-runda z czterech, co daje łącznie 52 subklucze po 16 bitów każdy. Subklucze są pozyskiwane z klucza głównego przez przesunięcia (rotacje) o 25 bitów w celu wygenerowania kolejnych grup kluczy; po wykonaniu kilku obrotów uzyskuje się wszystkie potrzebne subklucze.

Głównym źródłem siły kryptograficznej IDEA jest mieszanie operacji z różnych struktur algebraicznych: arytmetyka modulo 2^16 (dodawanie), arytmetyka modulo 2^16+1 (mnożenie z zaleceniem traktowania zera w specjalny sposób) oraz operacja bitowego XOR. Te trzy rodzaje operacji są celowo „algebraicznie niekompatybilne”, co utrudnia zastosowanie prostych metod analizy algebraicznej. W praktycznej implementacji IDEA wykorzystuje proste operacje arytmetyczne i bitowe, co czyni go efektywnym w oprogramowaniu i na sprzęcie bez specjalnych instrukcji kryptograficznych.

Historia i status prawny

IDEA jest ewolucją wcześniejszych koncepcji, w tym szyfru znanego jako PES (Proposed Encryption Standard) — stąd początkowa nazwa IPES (Improved PES). W latach 90. szyfr zyskał popularność między innymi dzięki włączeniu go do programu Pretty Good Privacy (PGP) w wersji 2.0, po porzuceniu słabszego algorytmu użytego wcześniej. IDEA był objęty ochroną patentową w wielu krajach i w pewnych okresach wymagał licencji do zastosowań komercyjnych; licencję na dystrybucję i komercyjne wykorzystanie obsługiwała firma MediaCrypt. Patenty dotyczące IDEA wygasały około 2010–2011 roku, co wpłynęło na spadek ograniczeń prawnych dotyczących jego stosowania.

Bezpieczeństwo i analiza kryptograficzna

Przez długi czas IDEA była uważana za szyfr odporny na klasyczne ataki kryptograficzne. Analizy z lat 90. wykazały dużą odporność na liniowe i różnicowe metody analizy, o ile nie przyjmowano specjalnych, ograniczających założeń. Badania wskazały istnienie pewnych klas tzw. słabych kluczy, jednak ich występowanie jest na tyle rzadkie, że zwykle nie ma istotnego wpływu praktycznego. Z punktu widzenia kryptanalizy akademickiej, najlepsze znane ataki do pewnego stopnia redukują liczbę rund — do około 6 rund — co jednak nie przekłada się na złamanie pełnej wersji 8,5 rundy w warunkach praktycznych przy użyciu wszystkich możliwych kluczy.

W literaturze kryptologicznej pojawiały się okresowe kontrowersje dotyczące analizy oraz efektywności w porównaniu z nowszymi algorytmami. Znany praktyk i autor popularnych opracowań na temat kryptografii publicznie wypowiadał się o IDEA jako o jednym z najlepszych algorytmów dostępnych w pewnym momencie, lecz z czasem rekomendacje uległy zmianie ze względu na rozwój alternatyw (szybszych i o korzystniejszych właściwościach implementacyjnych) oraz kwestie patentowe.

Zastosowania, zalety i ograniczenia

IDEA był szeroko stosowany w aplikacjach wymagających szyfrowania symetrycznego, zwłaszcza w oprogramowaniu do ochrony poczty elektronicznej i plików (np. w PGP) oraz w systemach, gdzie 64-bitowy blok i 128-bitowy klucz były akceptowalnym kompromisem. Do zalet IDEA należą solidna konstrukcja algorytmiczna, prostota implementacji oraz relatywnie dobra wydajność na sprzęcie bez specjalnych akceleratorów. Główne ograniczenia to: mniejszy w porównaniu z niektórymi współczesnymi standardami blok (64 bity → podatność na problemy z powtórzeniami IV przy dużych ilościach danych), kwestie patentowe historycznie ograniczające adopcję oraz fakt, że nowsze algorytmy (np. te wybrane w konkursie AES) oferują lepszą wydajność i większe bloki/klucze.

Charakterystyka w skrócie

• Rodzaj: szyfr blokowy
• Rozmiar bloku: 64 bity
• Rozmiar klucza: 128 bitów
• Liczba rund: 8 pełnych + 0,5 rundy
• Liczba subkluczy: 52 × 16 bitów
• Główne operacje: dodawanie modulo 2^16, mnożenie modulo 2^16+1, XOR

Przykłady i kontekst historyczny

W praktyce IDEA funkcjonował jako jedna z ważniejszych opcji szyfrowania w erze sprzed powszechnego wdrożenia AES. Jego zastosowanie w PGP przyczyniło się do rozpowszechnienia tego algorytmu poza środowiskiem akademickim. Po upływie ochrony patentowej, IDEA stał się częściej rozważany przez implementatorów systemów kryptograficznych, choć wielu z nich wybrało nowsze standardy ze względu na większe bloki, dłuższe klucze i lepszą wydajność w sprzętach współczesnych.

Przydatne odnośniki

• Kryptografia — wprowadzenie
• Szyfr blokowy — definicja
• Projektanci IDEA — szczegóły
• ETH Zurych — kontekst akademicki
• Data Encryption Standard (DES)
• PES — wcześniejsze konstrukcje
• Informacje o patentach
• Warunki niekomercyjnego użycia
• Znak towarowy IDEA
• Licencjonowanie i MediaCrypt
• Pretty Good Privacy (PGP)
• Parametry bloku 64-bit
• Klucz 128-bitowy — znaczenie
• Proces szyfrowania i deszyfrowania
• Kombinacja operacji algebraicznych
• Dodawanie modulo
• Operacja XOR
• Subklucze 16-bitowe
• Analiza różnicowa
• Analiza liniowa
• Klasy słabych kluczy
• Stan badań kryptograficznych (do 2007)
• Porównania z innymi algorytmami
• Dalsze analizy i publikacje

Opis powyżej ma charakter syntetyczny i porządkujący; osoby zainteresowane implementacją lub głębszą analizą matematyczną powinny sięgnąć do literatury specjalistycznej i oryginalnych publikacji naukowych oraz specyfikacji protokołów wykorzystujących IDEA.