IDEA — tarptautinis duomenų šifravimo algoritmas (blokinis šifras)
Kriptografijoje Tarptautinis duomenų šifravimo algoritmas (angl. International Data Encryption Algorithm, IDEA) yra 1991 m. sukurtas Xuejia Lai ir Jameso Massey (ETH Ciurichas) blokinis šifras, skirtas pakeisti duomenų šifravimo standartą. IDEA kilęs iš ankstesnio šifro Proposed Encryption Standard (PES), bet buvo patobulintas; todėl pradinis pavadinimas buvo IPES (patobulintas PES). Algoritmas buvo skirtas būti saugiu ir palyginti paprastu įgyvendinti programiniuose ir aparatūros sprendimuose.
Struktūra ir veikimo principas
IDEA operuoja su 64 bitų blokais, kurie skaidomi į keturis 16 bitų žodžius. Raktas yra 128 bitų ilgio. Šifravimo procesą sudaro aštuoni pilni transformacijų raundai (rounds) ir viena išvesties transformacija (half-round), t. y. iš viso 8,5 raundų. Kiekviename pilname raunde naudojama po 6 16 bitų subraktas, o galutinėje (pusiau) transformacijoje — 4 subraktai; iš viso — 52 subraktai.
Pagrindinis IDEA saugumo principas yra skirtingų algebrai įvairesnių operacijų perskirstymas: modulinė daugyba (mod 65537, kur vertė 0 priskiriama 65536), modulinė sudėtis (mod 2^16) ir bitų išskirtinė OR (XOR). Šios operacijos sąmoningai parinktos būti „algebriškai nesuderinamos“, todėl sudėtinga jas visas kartu analitiškai išspręsti.
Vieno raundo eiga (santrumpa ir supaprastinimas): blokas = X1,X2,X3,X4 (po 16 bitų). Pirmiausia taikomos operacijos su keturiais subraktais: X1 × K1 (mod 65537), X2 + K2 (mod 2^16), X3 + K3 (mod 2^16), X4 × K4 (mod 65537). Po to apskaičiuojami tarpinius mišinius dydžiai: t0 = (X1 ⊕ X3) × K5 (mod 65537), t1 = ((X2 ⊕ X4) + t0) (mod 2^16) × K6 (mod 65537), ir gauti t0,t1 sugrąžinami, kad modifikuotų X1..X4 per papildomus XOR veiksmus. Po kiekvieno pilno raundo viduryje vyksta žodžių (16 bitų) permainos (swap), o po aštunto raundo atliekama galutinė (pusiau) transformacija su likusiomis 4 subraktomis.
Raktų tvarkymas (key schedule)
Iš 128 bitų raktų generuojami 52 16 bitų subraktai. Pirmieji aštuoni subraktai gaunami tiesiogiai iš pradinio rakto: K1 yra mažiausi šešiolika bitų, o K8 — didžiausi šešiolika bitų. Tolimesnės subraktų grupės gaunamos pasukant pagrindinį raktą į kairę po 25 bitus tarp grupių; atlikus šešis tokius pasukimus gaunami visi reikalingi subraktai.
Iššifravimui naudojami dešifravimo subraktai, gauti iš šifravimo subraktų tam tikra permutacija: multiplicatyviniai subraktai (naudojami daugybai mod 65537) pakeičiami savo multiplicatyvine inverse mod 65537, o adiciniai subraktai (naudojami sudėčiai) — į savo adicinę inversiją mod 2^16; be to, subraktų eilė apverčiama pagal atvirkštinį šifravimo proceso tvarkos principą. Tokiu būdu iššifravimo ir šifravimo procesai yra simetriški ir labai panašūs.
Saugumas ir kriptoanalizė
Autoriai ir vėlesni tyrinėtojai išsamiai analizavo IDEA atsparumą diferencinei kriptoanalizei ir kitoms atakoms. Iki šiol nėra patikimų pranešimų apie sėkmingas praktines linijines ar diferencines atakas prieš pilną 8,5 raundo IDEA, tačiau rasta tam tikrų silpnų raktų klasių (pvz., Daemen ir kt., 1994). Šios raktų klasės yra labai retos ir lengvai išvengiamos atsitiktinai parenkant raktą, todėl praktiškai jos neturi didelės reikšmės.
Per metus atlikta pažanga kriptoanalizėje: iki 2007 m. geriausios atakos galėjo pažeisti iki 6 raundų IDEA, bet ne visą 8,5 raundų versiją. Papildomai — 64 bitų blokų dydis yra mažesnis už šiuolaikinius rekomenduojamus 128 bitų blokus, todėl IDEA nebėra pageidautiniausias pasirinkimas naujiems sistemų projektams, kuriuose reikia didelio atsparumo ilgiems duomenų srautams prieš pakartotinius blokų pasikartojimus.
Istorija ir praktinis naudojimas
IDEA buvo pasirinktas ir plačiai naudojamas programoje "Pretty Good Privacy" (PGP) versijoje 2.0, pakeitus ankstesnį nesaugesnį "BassOmatic" šifrą. IDEA taip pat gali būti naudojamas su OpenPGP standartu. Dėl gero saugumo ir palyginti paprasto įgyvendinimo IDEA ilgą laiką buvo laikomas vienu iš patikimų viešai prieinamų blokinių algortimų.
Patentai ir teisinė padėtis
IDEA buvo patentuotas keliose šalyse; komerciniam naudojimui reikėdavo licencijos. Pavadinimas "IDEA" taip pat buvo prekės ženklas, o patentai ir licencijos 2000–ųjų dešimtajame dešimtmetyje ribojo plačią komercinę platinimą. Anksčiau visame pasaulyje licenciją turėjo bendrovė "MediaCrypt". Patentuoto laikotarpio pabaiga (2010–2011 m.) leido šiek tiek platesnį laisvą naudojimą; atkreiptina dėmesį, kad teisinė padėtis gali skirtis priklausomai nuo jurisdikcijos ir konkrečių licencinių susitarimų.
Privalumai ir trūkumai
- Privalumai: gerai ištirtas ir ilgai patikrintas algoritmas; palyginti stiprus prieš klasines atakas iki pilnos versijos; paprastas raktų ir blokų apdorojimas 16 bitų žodžiais.
- Trūkumai: 64 bitų blokas yra šiandien laikomas mažesnio saugumo problemų šaltiniu dideliems duomenų srautams; lėtesnis už kai kuriuos modernesnius blokus (pvz., AES) įgyvendinimus aparatūroje ar programose, kurios optimizuotos 8 arba 32 bitų žodžiams; ankstesnės patento ir licencijavimo kliūtys.
1996 m. Bruce'as Schneieris rašė: "Mano nuomone, šiuo metu tai yra geriausias ir saugiausias visuomenei prieinamas blokinis algoritmas." (Applied Cryptography, 2nd ed.). Tačiau vėliau (apie 1999 m.) jis nurodė, kad dėl atsiradusių greitesnių kriptografinių algoritmų, pažangos kriptoanalizėje ir patentų problemų jis neberekomenduoja IDEA kaip pirmojo pasirinkimo naujiems projektams.
Apibendrinant: IDEA yra istoriškai svarbus ir gerai ištirtas blokinis šifras, turintis savų privalumų, tačiau šiuolaikinėse sistemose dažnai renkamas modernesnis algoritmas (pvz., AES) dėl geresnio našumo, didesnio bloko dydžio ir platesnio pripažinimo. Visgi IDEA vis dar gali būti tinkama esamoms sistemoms, kur jos savybės atitinka reikalavimus.


IDEA šifravimo raundas naudojant šešis dalinius raktus
Klausimai ir atsakymai
K: Kas yra Tarptautinis duomenų šifravimo algoritmas (IDEA)?
A: IDEA yra blokinis šifras, kurį 1991 m. sukūrė Xuejia Lai ir James Massey iš Ciuricho ETH. Jis turėjo pakeisti duomenų šifravimo standartą ir jį sudaro aštuonios identiškos transformacijos (raundai) ir viena išvesties transformacija (pusiau raundas).
K: Kaip veikia IDEA?
A: IDEA veikia 64 bitų blokais, naudojant 128 bitų raktą. Iš viso ji atlieka 8,5 raundų. Šifravimo ir iššifravimo procesai yra panašūs. IDEA saugumas iš esmės užtikrinamas perkeičiant skirtingų grupių operacijas - modulinę sudėtį ir daugybą bei bitų išskirtinį OR (XOR) - kurios pasirinktos taip, kad būtų "algebriniu požiūriu nesuderinamos". Kiekviename iš aštuonių raundų naudojami šeši daliniai raktai, o pusės raundo - keturi; iš viso 52 daliniai raktai. Kiekvieno dalinio rakto ilgis yra 16 bitų.
K: Ar IDEA yra patentuota?
A: Taip, ji yra užpatentuota keliose šalyse, tačiau ją gali naudoti bet kas nekomerciniais tikslais. Pavadinimas "IDEA" taip pat yra apsaugotas prekių ženklu, kurio patentų galiojimo laikas baigiasi 2010-2011 m. Šiuo metu "MediaCrypt" licenciją yra suteikusi visame pasaulyje.
K.: Ar IDEA buvo naudojama programoje "Pretty Good Privacy" (PGP)?
A.: Taip, jis buvo naudojamas PGP v2 versijoje po to, kai buvo nustatyta, kad v1 versijoje naudotas šifras "BassOmatic" yra nulaužiamas. Šiandien jį taip pat galima naudoti su "OpenPGP" standartu.
K.: Ar buvo pranešta apie kokią nors sėkmingą ataką prieš IDEA?
A: Kol kas nepranešta apie sėkmingas linijines ar diferencines atakas prieš šį algoritmą; tačiau buvo rasta keletas silpnų raktų klasių, tačiau jos tokios retos, kad saugiai naudojant algoritmą jų galima lengvai išvengti. Nuo 2007 m. geriausia ataka, taikoma visiems raktams, gali sulaužyti IDEA, jei ji sumažinama iki 6 raundų (pilna versija naudoja 8 raundus).
Klausimas: Ką Bruce'as Schneieris sakė apie IDEA?
A.: 1996 m. jis rašė, kad tai buvo "geriausias ir saugiausias tuo metu prieinamas blokinis algoritmas"; tačiau 1999 m. jis jo neberekomendavo dėl to, kad atsirado greitesnių algoritmų, taip pat dėl tam tikros pažangos kriptoanalizės srityje ir dėl su jo naudojimu susijusių patentų klausimų.