Algoritm nomi - Методы и средства защиты информации

Algoritm nomi
|
Muallif
|
Blok hajmi
|
Kalit uzunligi
|
IDEA
|
Xuejia Lia va Jeyms Massi
|
64 bit
|
128 bit
|
CAST128
|
|
64 bit
|
128 bit
|
BlowFish
|
Bryus Shnayer
|
64 bit
|
128 - 448 bit
|
GOST
|
Tadqiqot instituti ***
|
64 bit
|
256 bit
|
Ikki baliq
|
Bryus Shnayer
|
128 bit
|
128 - 256 bit
|
MARS
|
IBM korporatsiyasi
|
128 bit
|
128 - 1048 bit
|
Agar shifrlangan ma'lumotlar blokini xabar mazmunli bo'lgunga qadar barcha mumkin bo'lgan kalitlarni sinab ko'rish orqali o'qish mumkin bo'lsa, kriptografik algoritm ideal darajada kuchli deb ataladi. Ehtimollar nazariyasiga ko'ra, kerakli kalit barcha kalitlarning yarmini qidirgandan so'ng 1/2 ehtimollik bilan topiladi, keyin N uzunlikdagi kalit bilan ideal darajada kuchli kriptoalgoritmni buzish uchun o'rtacha 2 ta N -1 tekshiruvi kerak bo'ladi. Shunday qilib, umumiy holatda, blokli shifrning kuchi faqat kalit uzunligiga bog'liq va uning o'sishi bilan eksponent ravishda ortadi. Agar kalitlar maxsus yaratilgan ko'p protsessorli tizimda qidiriladi deb hisoblasak ham, diagonal parallelizm tufayli 1 ta kalitni tekshirish uchun atigi 1 soat sikli kerak bo'lsa, 128 bitli kalitni buzish uchun zamonaviy texnologiya kamida 10 21 yil vaqt oladi. kalit. Tabiiyki, yuqorida aytilganlarning barchasi faqat ideal darajada kuchli shifrlarga tegishli bo'lib, ular, masalan, yuqori darajadagi ishonchlilik bilan yuqoridagi jadvalda keltirilgan algoritmlardir.
Ushbu shartga qo'shimcha ravishda, ideal xavfsiz kriptografik algoritmlar ularga rioya qilishlari kerak bo'lgan yana bir juda muhim talabga bo'ysunadi. Agar blokning asl va shifrlangan qiymatlari ma'lum bo'lsa, ushbu transformatsiyani amalga oshirish uchun ishlatiladigan kalitni ham faqat to'liq qidirish orqali topish mumkin. Chetdan kuzatuvchi manba matnning bir qismini biladigan vaziyatlar hamma joyda uchraydi. Bular elektron shakllardagi standart yozuvlar, fayl formatlarining sobit sarlavhalari, matnda keng tarqalgan uzun so'zlar yoki baytlar ketma-ketligi bo'lishi mumkin. Ushbu muammodan kelib chiqqan holda, yuqoridagi talab ortiqcha emas va birinchisi kabi kuchli kriptografik algoritmlar tomonidan ham qat'iy bajariladi.
Shunday qilib, Z=EnCrypt(X, Key) kuchli blokli shifrlash funksiyasiga quyidagi shartlar qo'yiladi:
EnCrypt funktsiyasi teskari bo'lishi kerak.
Ma'lum Z blokidan X xabarini o'qishning boshqa usullari bo'lmasligi kerak, faqat kalitlarni to'liq qidirishdan tashqari.
Ma'lum bo'lgan X xabarni Z xabariga aylantirish uchun qaysi kalit ishlatilganligini aniqlashning kalitlarni to'liq qidirishdan tashqari boshqa usuli bo'lmasligi kerak.
Keling, blokli kriptografik algoritmlarni ishlab chiquvchilar ushbu uchta shartni bir vaqtning o'zida juda yuqori darajadagi ishonchlilik bilan bajarishga erishish usullarini ko'rib chiqaylik.
Blok kriptografik algoritm tomonidan ma'lumotlar ustida bajariladigan barcha harakatlar o'zgartirilgan blok uning bit sig'imiga mos keladigan diapazondan manfiy bo'lmagan butun son sifatida ko'rsatilishi mumkinligiga asoslanadi. Masalan, 32 bitli ma'lumotlar bloki 0..4'294'967'295 (2 32 ) oralig'idagi raqam sifatida talqin qilinishi mumkin. Bundan tashqari, kengligi odatda "ikkining kuchi" bo'lgan blokni kichikroq diapazondagi bir nechta mustaqil nomanfiy raqamlar sifatida ko'rib chiqish mumkin (yuqorida muhokama qilingan 32 bitli blok 0 diapazonidan 2 ta mustaqil raqam sifatida ham ko'rsatilishi mumkin. .65535 (2 16 ) yoki 0..255 diapazonidan 4 ta mustaqil son shaklida).
Blok kriptoalgoritmi ma'lum bir sxema bo'yicha ushbu raqamlar bo'yicha quyidagi amallarni bajaradi (bu operatsiyalarning belgilari chap tomonda algoritmlarning grafik diagrammalarida keltirilgan):
Bijektiv matematik funktsiyalar
|
|
Qo'shish
|
X'=X+V
|
|
Eksklyuziv OR
|
X'=X XOR V
|
|
Ko'paytirish moduli 2 N +1
|
X'=(X*V) mod (2 N +1)
|
|
Ko'paytirish moduli 2 N
|
X'=(X*V) mod (2 N )
|
Bit siljishi
|
|
Arifmetik chapga siljish
|
X'=X SHL V
|
|
Arifmetik o'ngga siljish
|
X'=X SHR V
|
|
Chapga tsiklik siljish
|
X'=X ROL V
|
|
O'ngga tsiklik siljish
|
X'=X ROR V
|
Jadvallarni qidirish
|
|
S-box
|
X'=Jadval[X,V]
|
Jadvalni almashtirish S-box - bitlar guruhini boshqa bitlar guruhiga solishtiradigan amal - oraliq natija odatda jadval yordamida o'zgartirilganda (masalan, oraliq natijaning har ikki bayti uchun mos keladigan yangi qiymat mavjud) Ular uchun jadvaldan tanlanadi.S -qutilari bir-biriga oʻxshash boʻlmasligi kerak.Masalan, turli S-qutilaridan bir xil chiqish qiymatini beruvchi kirish qiymatlari soni minimal boʻlishi kerak.
Ushbu transformatsiyalarning har biri uchun V parametri bo'lishi mumkin:
belgilangan raqam (masalan, X'=X+125);
kalitdan olingan raqam (masalan, X'=X+F(Key));
blokning mustaqil qismidan olingan raqam (masalan, X 2 '=X 2 +F(X 1 )).
Oxirgi variant yaratuvchisidan keyin Feistel tarmog'i deb ataladigan sxemada qo'llaniladi.
Blokda bajariladigan amallar ketma-ketligi, yuqoridagi V variantlari kombinatsiyasi va F funksiyalarining o‘zi har bir aniq blok kriptoalgoritmining “nou-xau”sini tashkil qiladi. Yilda bir yoki ikki marta butun dunyo bo'ylab tadqiqot markazlari kriptoanalitiklarning shiddatli hujumi ostida bir necha yil ichida barqaror kriptografik algoritm maqomiga ega bo'ladigan yoki (bu juda tez-tez sodir bo'ladi) shafqatsiz ravishda tushib ketadigan yana bir blokli shifrni nashr etadi. kriptografiya tarixida.
Blok algoritmlarining xarakterli xususiyati asosiy materialdan takroriy va bilvosita foydalanishdir. Bu, birinchi navbatda, asl va shifrlangan matnlar ma'lum bo'lganda, kalitga nisbatan teskari dekodlashning mumkin emasligi talabi bilan bog'liq. Ushbu muammoni hal qilish uchun yuqoridagi transformatsiyalar ko'pincha asosiy qiymatning o'zidan yoki uning qismidan emas, balki asosiy materialning ba'zi, ba'zan qaytarib bo'lmaydigan (bijektiv bo'lmagan) funktsiyasidan foydalanadi. Bundan tashqari, bunday transformatsiyalarda bir xil blok yoki kalit element qayta-qayta ishlatiladi. Bu funksiyaning X qiymatiga nisbatan invertillik sharti bajarilsa, funksiyani Key kalitiga nisbatan qaytarilmas holga keltirish imkonini beradi.
Axborot paketini kodlash jarayonida alohida blokni shifrlash yoki shifrini ochish operatsiyasi ko'p marta (ba'zan yuz minglab martagacha) bajarilganligi sababli kalitning qiymati va demak, V i ( Kalit ) funktsiyalari. ) o'zgarishsiz qoladi, ba'zida bu qiymatlarni bir marta oldindan hisoblash va ularni kalit bilan birga RAMda saqlash tavsiya etiladi. Ushbu qiymatlar faqat kalitga bog'liq bo'lganligi sababli, ular kriptografiyada kalit material deb ataladi. Shuni ta'kidlash kerakki, ushbu operatsiya hech qanday tarzda kalit uzunligini yoki umuman algoritmning kriptografik kuchini o'zgartirmaydi. Bu erda faqat oraliq natijalarni keshlash orqali hisoblash tezligini optimallashtirish amalga oshiriladi. Ta'riflangan harakatlar deyarli ko'p blokli kriptoalgoritmlarda uchraydi va kalitlarni rejalashtirish deb ataladi.
13. _ _ Feishtel tarmog'i (Feistel - turli manbalarda turli yo'llar bilan)
Feishtel tarmog'i (Feistel loop) - bu matnning bir qismidan hisoblangan qiymat boshqa qismlarga qo'shiladigan teskari matnni o'zgartirish usuli. Ko'pincha tarmoq strukturasi shifrlash va shifrni ochish uchun bir xil algoritmdan foydalaniladigan tarzda ishlab chiqilgan - yagona farq asosiy materialdan foydalanish tartibida.
Feishtel tarmog'i shifrlangan blokning joriy qismini bir xil blokning boshqa mustaqil qismidan hisoblangan ba'zi funksiyalar natijasi bilan aralashtirishning yuqorida tavsiflangan usulining keyingi modifikatsiyasidir. Ushbu uslub keng tarqaldi, chunki u kalitdan va dastlabki ma'lumotlar blokining materialidan qayta foydalanish talabini ta'minlaydi.
Klassik Feishtel tarmog'i quyidagi tuzilishga ega:
1-rasm.
Dastlabki blokdan hosil bo'lgan mustaqil axborot oqimlari tarmoq tarmoqlari deb ataladi. Klassik sxemada ulardan ikkitasi mavjud. V i miqdorlari tarmoq parametrlari deb ataladi, ular odatda asosiy materialning funktsiyalari hisoblanadi. F funktsiyasi generator deb ataladi. Yaratuvchi funktsiyaning yagona hisob-kitobidan va uning natijasini boshqa tarmoqqa o'z joylarini almashtirgan holda qo'yishdan iborat bo'lgan harakat Feishtel tarmog'ining tsikli yoki aylanishi (inglizcha raund) deb ataladi. Optimal turlar soni 8 dan 32 gacha. Muhimi shundaki, raundlar sonini ko'paytirish har qanday blokli shifrning kriptoanalizga kriptografik qarshiligini sezilarli darajada oshiradi. Ehtimol, bu xususiyat Feishtel tarmog'ining bunday faol tarqalishiga ta'sir qilgandir - axir, aytaylik, algoritmning zaif nuqtasi aniqlansa, algoritmning o'zini qayta yozmasdan turlar sonini 4-8 ga oshirish deyarli har doim etarli bo'ladi. Ko'pincha turlar soni algoritmni ishlab chiquvchilar tomonidan belgilanmaydi, lekin faqat ushbu parametrning oqilona chegaralari (albatta pastroq va har doim ham yuqori emas) ko'rsatilgan.
Kalit belgilangan uzunlikka ega. Biroq, blok o'lchami, masalan, 128 bit bo'lgan kamida 8 shifrlash tsikli bo'ylab harakatlanayotganda, hatto XOR orqali oddiy qo'shilganda ham, kalitning 8 * 128 = 1024 biti talab qilinadi, chunki har biriga bir xil qiymatni qo'sha olmaysiz. tsikl - bu shifrni zaiflashtiradi. Shuning uchun, kalit bitlar ketma-ketligini olish uchun ular tsiklik kalitlarni yaratish uchun maxsus algoritmni o'ylab topadilar (kalitlar jadvali) . Ushbu algoritmning ishlashi natijasida shifrlash kalitining boshlang'ich bitlaridan ma'lum uzunlikdagi bitlar massivi olinadi, ulardan tsiklik kalitlar ma'lum qoidalarga muvofiq tuziladi. Har bir shifrda siklik kalitlarni yaratish uchun o'z algoritmi mavjud.
Darhol savol tug'iladi: bu sxema qayta tiklanadimi? Shubhasiz ha. Feishtel tarmog'i F ishlab chiqaruvchi funktsiya sifatida qaytarib bo'lmaydigan transformatsiyadan foydalanilgan taqdirda ham, bu holda butun zanjir tiklanadigan xususiyatga ega . Buning sababi, Feishtel tarmog'ining teskari o'zgarishi uchun F -1 funktsiyasini hisoblash kerak emas .
Bundan tashqari, ko'rish oson, Feishtel tarmog'i nosimmetrikdir. O'zining takrorlanishi bilan qaytariladigan XOR operatsiyasidan foydalanish va filiallarning oxirgi almashinuvini inversiyasi bir xil Feishtel tarmog'i bilan blokni dekodlash imkonini beradi, lekin V i parametrlarining teskari tartibi bilan . E'tibor bering, Feishtel tarmog'ining o'zgarmasligi uchun turlar soni juft yoki toq bo'lishi muhim emas. Yuqoridagi ikkala shart (XOR operatsiyasi va oxirgi almashinuvni yo'q qilish) saqlanib qolgan sxemaning ko'pgina ilovalarida to'g'ridan-to'g'ri va teskari o'zgarishlar bir xil protsedura bo'yicha amalga oshiriladi, unga Vi miqdorlar vektori sifatida uzatiladi. asl yoki teskari tartibda parametr .
Kichkina o'zgartirishlar bilan Feishtel tarmog'ini mutlaqo nosimmetrik qilish mumkin, ya'ni u bir xil operatsiyalar to'plamidan foydalangan holda shifrlash va shifrni ochish funktsiyalarini bajaradi. Matematik tilda bu "EnCrypt funktsiyasi DeCrypt funktsiyasi bilan bir xil" deb yozilgan. Agar kriptoalgoritmning kirish va chiqish ma'lumotlari bloklari nuqtalar bilan belgilangan holat grafigini ko'rib chiqsak, klassik Feishtel tarmog'i uchun ba'zi bir qo'zg'almas kalit bilan biz 2a-rasmda ko'rsatilgan rasmga ega bo'lamiz va ikkinchi holatda, har bir juft nuqta rasmda ko'rsatilganidek, noyob ulanishga ega bo'ladi. 2b. Xuddi shunday xususiyatlarga ega Feishtel tarmog'ining modifikatsiyasi 3-rasmda ko'rsatilgan. Ko'rib turganimizdek, uning asosiy hiylasi tsiklning ikkinchi yarmida asosiy ma'lumotlarni teskari tartibda qayta ishlatishdir. Ammo shuni ta'kidlash kerakki, aynan shunday sxemaning yetarlicha o'rganilmagan o'ziga xosligi (ya'ni shifrlangan matnni teskari o'zgartirishlar orqali zaiflashtirish potentsiali) tufayli u kriptografik algoritmlarda juda ehtiyotkorlik bilan qo'llaniladi.
2-rasm.
3-rasm.
Ammo Feishtel tarmog'ini ko'proq filiallar uchun o'zgartirish ko'proq qo'llaniladi. Bu, birinchi navbatda, kodlangan bloklarning katta o'lchamlari (128 yoki undan ortiq bit) bilan 64 va undan yuqori modulli matematik funktsiyalar bilan ishlash noqulay bo'lishi bilan bog'liq. Ma'lumki, bugungi kunda protsessorlar tomonidan qayta ishlanadigan ma'lumotlarning asosiy birliklari bayt va ikkita 32 bitli mashina so'zidir. Shuning uchun, 4 ta filialga ega Feishtel tarmog'i blokli kriptoalgoritmlarda tez-tez uchraydi. Uni o'zgartirishning eng oddiy printsipi 4a-rasmda ko'rsatilgan. Filiallar o'rtasida ma'lumotni tezroq aralashtirish uchun (va bu ko'p sonli filiallarga ega Feishtel tarmog'ining asosiy muammosi), "2-toifa" va "3-toifa" deb nomlangan ikkita o'zgartirilgan sxema qo'llaniladi. Ular 4b va 4c-rasmlarda ko'rsatilgan.
4-rasm.
Feishtel tarmog'i kriptografik transformatsiya sxemasi sifatida o'zini ishonchli isbotladi va uni deyarli har qanday zamonaviy blokli shifrda topish mumkin. Kichik o'zgartirishlar odatda shifrlangan blok ustidagi qo'shimcha boshlang'ich va yakuniy transformatsiyalarga (inglizcha atama oqartirish) tegishli. Odatda "eksklyuziv OR" yoki qo'shimcha orqali amalga oshiriladigan bunday o'zgartirishlar kirish matnining dastlabki tasodifiyligini oshirish uchun mo'ljallangan. Shunday qilib, Feishtel tarmog'idan foydalangan holda blokli shifrning kriptografik kuchi F funktsiyasi va kalitdan Vi ni hisoblash qoidasi bilan 95% ga aniqlanadi . Ushbu funktsiyalar kriptografiya sohasidagi mutaxassislar tomonidan tobora ko'proq tadqiqot ob'ekti hisoblanadi.
14. _ _ TEA blokli shifr
TEA blok algoritmi kuchli kriptoalgoritmlarni amalga oshirishning eng osonlaridan biriga misol sifatida keltirilgan.
Keling, amalga oshirish uchun eng oson, ammo tan olingan kuchli kriptografik algoritmlardan birini ko'rib chiqaylik - TEA (Tiny Encryption Algorithm).
Algoritm parametrlari:
Blok hajmi - 64 bit;
Kalit uzunligi 128 bit.
Algoritm har biri 32 bitli ikkita filialga ega Feishtel tarmog'idan foydalanadi. F hosil qiluvchi funksiya teskari. Feishtel tarmog'i eksklyuziv OR dan ko'ra arifmetik qo'shishni qoplamali operatsiya sifatida qo'llash tufayli assimetrikdir.
Quyida kriptoalgoritmning PASCAL dasturlash tilidagi kodi keltirilgan.
tip TLong2=massiv [0.. 1] ning longint;
TLong2x2=massiv[0.. 1] / TLong2;
const Delta=$9E3779B9;
var kaliti:TLong2x2;
EnCryptRouting protsedurasi (var ma'lumotlar);
var y,z,sum:longint; a:bayt;
boshlanishi
y:=TLong2(ma'lumotlar)[0];z:=TLong2(ma'lumotlar)[1];sum:=0;
a uchun:=0 dan 31 gacha
boshlanishi
inc(sum,Delta);
inc(y,((z shl 4)+key[0,0]) xor (z+sum) xor ((z shr 5)+key[0,1]));
inc(z,((y shl 4)+key[1,0]) xor (y+sum) xor ((y shr 5)+key[1,1]));
oxiri;
TLong2(ma'lumotlar)[0]:=y;TLong2(ma'lumotlar)[1]:=z
oxiri;
Algoritmning ishlash diagrammasi 5-rasmda ko'rsatilgan.
5-rasm .
TEA kripto algoritmining o'ziga xos xususiyati uning o'lchamidir. Amaliyotlarning soddaligi, jadvallarni almashtirishning yo'qligi va 32-bitli protsessor arxitekturasi uchun optimallashtirish uni ASSEMBLER tilida juda oz miqdordagi kodda amalga oshirish imkonini beradi. Algoritmning kamchiliklari Feishtel tsiklini 32 marta takrorlash zarurati tufayli yuzaga kelgan biroz sekinlikdir (bu jadvalni almashtirishning yo'qligi sababli "ma'lumotlarni yaxshilab aralashtirish" uchun zarur).
Blok shifrlari yordamida xabarni autentifikatsiya qilish.
Xo'sh, qanday qilib blokli shifr yordamida xabarning haqiqiyligini tekshirish mumkin? Juda oddiy.
Yuboruvchi A ma'lum bir xabarni yubormoqchi (a 1 ,..,a t ) . U uni faqat o'zi va qabul qiluvchiga ma'lum bo'lgan maxfiy kalit bilan shifrlaydi, so'ngra hosil bo'lgan shifrlangan matndan u k bitli oxirgi blok b tni oladi ( k yetarli darajada katta bo'lishi kerak).
Yuboruvchi A xabarni (a 1 , .., a t , b t ) qabul qiluvchiga aniq matnda yoki uni boshqa kalit bilan shifrlagan holda yuboradi.
Qabul qiluvchi B xabarni qabul qilib, (a 1 , .., a t , b t ) shifrlaydi (a 1 ,..,a t ) xuddi shu sirda A (kelishuv boʻlishi kerak) bilan bir xil rejimda. kalit (faqat u va A) biladi.
|