IDEA — tarptautinis duomenų šifravimo algoritmas (blokinis šifras)

IDEA — 64 bitų blokinis šifras su 128 bitų raktu: PGP istorija, 8,5 raundų struktūra ir stipri, algebrai nesuderinama saugumo architektūra.

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.

Klausimai ir atsakymai

K: Kas yra Tarptautinis duomenų šifravimo algoritmas (IDEA)?

K: Kaip veikia IDEA?

K: Ar IDEA yra patentuota?

K.: Ar IDEA buvo naudojama programoje "Pretty Good Privacy" (PGP)?

K.: Ar buvo pranešta apie kokią nors sėkmingą ataką prieš IDEA?

Klausimas: Ką Bruce'as Schneieris sakė apie IDEA?

Paieška pagal raidę