Oqim shifri yoki Oqimli shifr — bu simmetrik shifr bo‘lib, unda ochiq matnning har bir belgisi shifrmatn belgisiga nafaqat foydalaniladigan kalitga, balki uning ochiq matn oqimidagi o‘rniga ham bog‘liq holda aylantiriladi. Oqimli shifr simmetrik shifrlashga boshqacha yondashadi — u blokli shifrlardan farq qiladi.
Tarixi
Oqimli shifrlarning siljitish(ingl.) registrlariga asoslangan turlari urush yillarida, elektronika paydo bo‘lishidan ancha oldin keng qo‘llanilgan. Ularni loyihalash va amalga oshirish oson bo‘lgan.
1965-yilda Norvegiya hukumatining bosh kriptografi Ernst Selmer ketma-ket siljitish registrlari nazariyasini ishlab chiqdi. Keyinchalik Solomon Golomb, matematik hamda AQSH Milliy xavfsizlik agentligi xodimi, «Shift Register Sequences» («Siljitish registrlari ketma-ketliklari») nomli kitobni yozib, unda o‘zining va Selmerning ushbu sohadagi asosiy yutuqlarini bayon etdi.
Oqimli shifrlarning keng ommalashishiga Klod Shennonning 1949-yilda nashr etilgan ishi sabab bo‘ldi. Unda Shennon Vernam shifrining (bir martalik bloknot deb ham ataladi) mutlaq kriptografik mustahkamligini isbotladi. Vernam shifrida kalit uzunligi uzatilayotgan xabarning uzunligiga teng bo‘ladi. Kalit gamma sifatida ishlatiladi va agar kalitning har bir biti tasodifiy tanlansa, shifrni buzish imkonsiz bo‘ladi (chunki ochiq matnning barcha mumkin bo‘lgan variantlari bir xil ehtimollikka ega). Hozirga qadar ko‘plab oqimli shifrlash algoritmlari yaratilgan, jumladan: A3, A5, A8, MUGI, PIKE, RC4, SEAL.
Oqimli shifrlarda gamma qo‘shish rejimi
Oqimli shifrning eng sodda amalga oshirilishi rasmda ko‘rsatilgan. Gamma generatori kalit oqimini (gamma) hosil qiladi: . Ochiq matn bitlari oqimini deb belgilaymiz. Unda shifrmatn bitlari oqimi XOR: amali yordamida olinadi, bunda .
Deshifrlash ayni gamma va shifrlangan matn o‘rtasida XOR amalini bajarish orqali amalga oshiriladi: .
Ko‘rinib turibdiki, gamma bitlari ketma-ketligi davriy bo‘lmasa va tasodifiy tanlansa, shifrni buzish imkonsiz. Biroq bu shifrlash rejimining kamchiliklari ham bor. Jumladan, uzatiladigan xabarlar uzunligiga yaqin uzunlikdagi kalitlardan amalda foydalanish qiyin. Shu sababli odatda qisqaroq kalit (masalan, 128 bit) ishlatiladi. Uning yordamida psevdotasodifiy gamma ketma-ketligi hosil qilinadi (u Golomb postulatlariga mos kelishi kerak). Tabiiyki, gammaning psevdotasodifiyligi oqimli shifrga hujum qilishda ishlatilishi mumkin.
Oqimli shifrlarning tasnifi
Masalan, oqimli shifrlarning gamma qo‘shish rejimida aloqa kanali orqali uzatish paytida shifrmatnning bitta belgisi buzildi, deb faraz qilaylik. Bunda buzilmagan barcha belgilar to‘g‘ri deshifrlanadi, faqat bitta belgi yo‘qoladi. Endi aloqa kanali orqali uzatilayotganda shifrmatnning bir belgisi butunlay yo‘qolganini tasavvur qilaylik. Bu yo‘qolgan belgidan keyingi matnning barchasi noto‘g‘ri deshifrlanishiga olib keladi.
Oqimli shifrlash tizimlari ishlatiladigan deyarli barcha ma’lumot uzatish kanallarida xalaqitlar mavjud. Shu sababli axborot yo‘qolishining oldini olish uchun matnni shifrlash va deshifrlashni sinxronlashtirish muammosi hal qilinadi. Ushbu muammoning yechilish usuliga ko‘ra shifrlash tizimlari sinxron va o‘z-o‘zini sinxronlashtiruvchi tizimlarga bo‘linadi.
Sinxron oqimli shifrlar
Ta’rif:
Sinxron oqimli shifrlar (SOSh) — kalitlar oqimi ochiq matn va shifrmatndan mustaqil hosil qilinadigan shifrlardir.
Shifrlashda kalit oqimi generatori deshifrlashdagi kalit oqimi bitlari bilan bir xil bitlarni ishlab chiqaradi. Shifrmatnning bir belgisi yo‘qolsa, ikkala generator o‘rtasidagi sinxronlik buziladi va xabarning qolgan qismini deshifrlab bo‘lmaydi. Bunday vaziyatda jo‘natuvchi va qabul qiluvchi ishni davom ettirish uchun qayta sinxronlashishi zarur.
Odatda sinxronlashtirish uzatilayotgan xabarga maxsus markerlarni kiritish orqali amalga oshiriladi. Natijada uzatish vaqtida belgi yo‘qolsa, navbatdagi marker qabul qilingunga qadargina deshifrlash noto‘g‘ri bo‘ladi.
Sinxronlashtirish kalit oqimining hech bir qismi qayta takrorlanmaydigan tarzda bajarilishi kerak. Shu sababli generatorni avvalgi holatiga qaytarish maqsadga muvofiq emas.
SOSh afzalliklari:
- xatolarning tarqalish ta’siri yo‘q (faqat buzilgan bit noto‘g‘ri deshifrlanadi);
- shifrmatnga belgi kiritish yoki undan belgi o‘chirishni aniqlash imkonini beradi, chunki bunday o‘zgarishlar sinxronlikni buzadi va aniqlanadi.
SOSh kamchiliklari:
- shifrlangan matnning ayrim bitlarini o‘zgartirishga zaif. Agar tajovuzkorga ochiq matn ma’lum bo‘lsa, u bitlarni o‘ziga kerakli shaklda deshifrlanadigan qilib o‘zgartirishi mumkin.
O‘z-o‘zini sinxronlashtiruvchi oqimli shifrlar
Ushbu g‘oya 1946-yilda AQSHda patentlangan.
Ta’rif:
O‘z-o‘zini sinxronlashtiruvchi oqimli shifrlar (asinxron oqimli shifrlar, AOSh) — kalit oqimi kalit va shifrmatnning belgilangan sondagi belgilariga bog‘liq funksiya orqali hosil qilinadigan shifrlardir.
Demak, kalit oqimi generatorining ichki holati shifrmatnning oldingi N ta bitiga bog‘liq funksiya hisoblanadi. Shu bois deshifrlovchi kalit oqimi generatori N ta bitni qabul qilgach, shifrlovchi generator bilan avtomatik sinxronlashadi.
Bu rejim quyidagicha ishlaydi: har bir xabar N bitli tasodifiy sarlavha bilan boshlanadi; sarlavha shifrlanadi, uzatiladi va deshifrlanadi; deshifrlash natijasi noto‘g‘ri bo‘ladi, ammo shu N bitdan keyin ikkala generator sinxronlashadi.
AOSh afzalliklari:
- Ochiq matn statistikasini aralashtirish. Ochiq matnning har bir belgisi keyingi shifrmatnga ta’sir qilgani sababli, ochiq matnning statistik xususiyatlari butun shifrmatnga tarqaladi. Shuning uchun AOSh ochiq matndagi ortiqchalikdan foydalanadigan hujumlarga SOShga nisbatan chidamliroq bo‘lishi mumkin.
AOSh kamchiliklari:
- xatoning tarqalishi (shifrmatndagi har bir noto‘g‘ri bit ochiq matnda N ta xatoga sabab bo‘ladi);
- qayta uzatish hujumlariga sezgir bo‘ladi.
Chiziqli teskari aloqali siljitish registrlariga (CTASR) asoslangan oqimli shifrlar
Nazariy asoslar
Kriptografiyada chiziqli siljitish registrlaridan foydalanishning bir necha sababi bor:
- kriptografik algoritmlarning yuqori ishlash tezligi
- deyarli barcha hisoblash qurilmalarida apparat darajasida amalga oshirilgan eng sodda qo‘shish va ko‘paytirish amallaridan foydalanish
- yaxshi kriptografik xususiyatlar (hosil qilinadigan ketma-ketliklarning davri katta va statistik xususiyatlari yaxshi bo‘ladi)
- chiziqli tuzilma tufayli algebraik usullar bilan oson tahlil qilinishi
Ta’rif: Chiziqli teskari aloqali siljitish registri uzunligi L bo‘lib, u quyidagicha raqamlangan L ta katakdan iborat: . Har biri 1 bitni saqlay oladi, bitta kirish va bitta chiqishga ega; shuningdek, sinxronlash signali (clock) ma’lumotlarning siljishini boshqaradi. Har bir vaqt birligida quyidagi amallar bajariladi:
- Quyidagi katakning tarkibi: — chiqish ketma-ketligining bir qismini hosil qiladi;
- raqami bo‘lgan katakdagi ma’lumot raqami bo‘lgan katakka o‘tkaziladi; bu quyidagi qiymatlarning barchasi uchun o‘rinli: , .
- raqami bo‘lgan katakning yangi tarkibi teskari aloqa biti bilan belgilanadi; bu bit kataklar bitlarini belgilangan koeffitsiyentlar bilan 2 moduli bo‘yicha qo‘shish orqali hisoblanadi. .
Birinchi bosqichda:
Ikkinchi bosqichda:
Quyidagi munosabat CTASR ishlashini umumiy ko‘rinishda ifodalaydi:
Agar barcha kataklarga nolga teng bitlar yozilsa, tizim faqat nollardan iborat ketma-ketlik hosil qiladi. Noldan farqli bitlar yozilsa, yarim cheksiz ketma-ketlik olinadi. Bu ketma-ketlik quyidagi koeffitsiyentlar bilan aniqlanadi:
Endi davrining bunday tizimda qanday qiymat olishini ko‘rib chiqaylik:
Noldan farqli holatlar soni: Demak, .
Ilgari uchragan holat yana paydo bo‘lishi bilan jarayon takrorlana boshlaydi. Yuqoridagi registr holatlarining o‘zgarishi chiziqli ayirmali tenglama bilan ifodalanadi. Barcha hadlarni tenglikning bir tomoniga o‘tkazamiz:
.
Quyidagicha belgilaymiz: . U holda:
Bu ko‘phadning muhim xususiyati — keltiriluvchanligidir.
Ta’rif:
Ko‘phad keltiriluvchan deyiladi, agar uni shu maydondagi koeffitsiyentlarga ega, darajasi kichikroq ikki ko‘phadning ko‘paytmasi sifatida ifodalash mumkin bo‘lsa (bizning holatda koeffitsiyentlar ikkilik). Bunday ifodalash imkonsiz bo‘lsa, ko‘phad keltirilmas deb ataladi.
Agar ko‘phad keltirilmas va primitiv bo‘lsa, davr maksimal mumkin bo‘lgan davrga teng bo‘ladi, ya’ni
Misol:
Primitiv keltirilmas ko‘phadni olaylik: Bu ko‘phadni quyidagicha yozish mumkin: — noldan farqli koeffitsiyentlar turgan darajalar ko‘rsatilgan.
Boshlang‘ich holatda kataklarga qiymatlarini yozib, generator davrining uzunligini aniqlaymiz:
| Teskari aloqa | Katak 0 | Katak 1 | Katak 2 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 |
Generator davri quyidagicha: Generator chiqishida quyidagi ketma-ketlik olinadi:
2 moduli bo‘yicha ayrim primitiv ko‘phadlarga misollar keltiramiz:
Chiziqli murakkablik
Ikkilik ketma-ketlikning chiziqli murakkabligi CTASR ishini tavsiflovchi eng muhim ko‘rsatkichlardan biridir. Shu sababli bu masalaga batafsilroq to‘xtalamiz.
Chiziqli murakkablikka ta’rif berishdan oldin ayrim belgilashlarni kiritamiz.
— cheksiz ketma-ketlik bo‘lib, uning hadlari:
— uzunligi bo‘lgan chekli ketma-ketlik; uning hadlari:
CTASR quyidagi ketma-ketlikni hosil qiladi, deb aytiladi: , agar shunday boshlang‘ich holat mavjud bo‘lsaki, CTASR chiqish ketma-ketligi bilan mos kelsa. Xuddi shunday, CTASR quyidagi chekli ketma-ketlikni hosil qiladi: , agar shunday boshlang‘ich holat mavjud bo‘lsaki, CTASR chiqish ketma-ketligining dastlabki hadi quyidagi ketma-ketlik hadlariga mos kelsa: .
Nihoyat, cheksiz ikkilik ketma-ketlikning chiziqli murakkabligiga ta’rif beramiz.
Ta’rif:
Chiziqli murakkablikcheksiz ikkilik ketma-ketlikning quyidagicha aniqlanadigan sonidir:
- Agar nollardan iborat ketma-ketlik bo‘lsa, unda
- Agar quyidagini hosil qiladigan CTASR mavjud bo‘lmasa: , unda ning qiymati cheksizlikka teng.
- Aks holda, quyidagi ketma-ketlikni hosil qiladigan eng qisqa CTASR uzunligiga teng: .
Ta’rif:
Chekli ikkilik ketma-ketlik ning chiziqli murakkabligi bilan belgilanadi. U chiqish ketma-ketligining dastlabki hadi quyidagiga mos keladigan eng qisqa CTASR uzunligiga teng: .
Chiziqli murakkablik xususiyatlari:
Faraz qilaylik, va — ikkilik ketma-ketliklar. U holda:
1. Har qanday uchun qismketma-ketlikning chiziqli murakkabligi quyidagi tengsizliklarni qanoatlantiradi:
2. faqat va faqat — nollardan iborat va uzunligi quyidagiga teng bo‘lgan ketma-ketlik: .
3. faqat va faqat .
4. Agar – davriy ketma-ketlik bo‘lib, uning davri ga teng bo‘lsa, unda
5.
Chekli ikkilik ketma-ketlikning chiziqli murakkabligini aniqlashning samarali usuli — Berlekamp–Messey algoritmi.
CTASRga asoslangan oqimli shifrlar. Murakkablashtirish
Afsuski, CTASRning chiqish ketma-ketligini oson bashorat qilish mumkin. Masalan, chiqish ketma-ketligining 2L ta belgisi ma’lum bo‘lsa, chiziqli tenglamalar tizimini yechib, registrning boshlang‘ich holatini osongina topish mumkin («Chiziqli teskari aloqali siljitish registrlariga asoslangan oqimli shifrlar» bo‘limiga qarang).
Kriptografik maqsadlarda qo‘llanadigan CTASR chiqish ketma-ketligi quyidagi xususiyatlarga ega bo‘lishi kerak, deb hisoblanadi:
- katta davr
- yuqori chiziqli murakkablik
- yaxshi statistik xususiyatlar
CTASRning chiziqli xususiyatlarini yo‘qotib, bunday tizimlarning kriptografik mustahkamligini oshiradigan kalit oqimi generatorlarini loyihalashning bir nechta usuli mavjud:
1. bir necha CTASR chiqishlarini birlashtiruvchi nochiziqli funksiyadan foydalanish
2. yagona CTASRning har bir katagi tarkibi uchun nochiziqli filtrlovchi funksiyadan foydalanish
3. bir CTASR chiqishidan boshqa bir (yoki bir nechta) CTASRning sinxronlash signalini boshqarishda foydalanish.
Generatorlarning nochiziqli kombinatsiyasi
Ma’lumki, har qanday Bul funksiyasi ni 2 moduli bo‘yicha qo‘shish bilan turli darajadagi ko‘paytmalar sifatida ifodalash mumkin; ular mustaqil o‘zgaruvchilardan, tuzilgan. Bu ifoda funksiyaning algebraik normal shakli deyiladi . Funksiyaning nochiziqlilik darajasi deb uning algebraik normal shaklidagi hadlarning eng katta darajasi olinadi.
Masalan, Bul funksiyasi ning nochiziqlilik darajasi 3 ga teng. Bul funksiyasining maksimal nochiziqlilik darajasi o‘zgaruvchilar soniga teng
Endi faraz qilaylik, bizda ta chiziqli teskari aloqali siljitish registri bor, ularning uzunliklari juft-jufti bilan farq qiladi va ikkidan katta. Barcha registrlar nochiziqli funksiya orqali birlashtirilgan, rasmda ko‘rsatilganidek. funksiya algebraik normal shaklda berilgan. U holda kalit oqimining chiziqli murakkabligi .
Agar lar juft-jufti bilan o‘zaro tub sonlar bo‘lsa, kalit oqimi davrining uzunligi: . Masalan, agar bo‘lsa, unda . Kalit oqimining davr uzunligi esa .
Misol (Geffe generatori):
Bu generatorda nochiziqli usulda birlashtirilgan uchta CTASR ishlatiladi. Ularning uzunliklari juft-jufti bilan o‘zaro tub sonlardir.
Ushbu generatorning nochiziqli funksiyasini quyidagicha yozish mumkin:
Davr uzunligi:
Chiziqli murakkabligi:
Geffe generatori kriptografik jihatdan zaif, chunki CTASR 1 va CTASR 3 generatorlari holatlari haqidagi ma’lumot uning chiqish ketma-ketligida aks etadi. Buni tushunish uchun quyidagi belgilarni kiritamiz: vaqt momentida CTASR 1, 2, 3 va kalit oqimining tegishli chiqish bitlarini bildiradi. U holda korrelyatsiya ehtimoli hisoblanadi. Bunda birinchi ketma-ketlik — , unga nisbatan taqqoslanadigan ketma-ketlik esa — :
Xuddi shunday,
Shuning uchun Geffe generatorining davri uzun va chiziqli murakkabligi yetarlicha yuqori bo‘lsa-da, u korrelyatsion hujumlarga duchor bo‘lishi mumkin.
Nochiziqli filtrli generatorlar
Har bir katakning chiqishi muayyan nochiziqli Bul filtrlash funksiyasining kirishiga uzatiladi . Faraz qilaylik, filtrlovchi funksiya darajasi ga teng bo‘lsa, kalit oqimining chiziqli murakkabligi .
Sinxronlash signalini boshqarishga asoslangan generatorlar
Generatorlarning nochiziqli kombinatsiyalarida va nochiziqli filtrli generatorlarda barcha CTASRlardagi ma’lumot siljishi yagona sinxronlash signali orqali boshqariladi.
Ko‘rib chiqilayotgan turdagi generatorlarning asosiy g‘oyasi — bitta registrning sinxronlash signalini boshqa registrning chiqish ketma-ketligi orqali boshqarib, CTASRga asoslangan kalit oqimi generatorlari ishiga nochiziqlilik kiritishdir.
Sinxronlash signalini boshqarishga asoslangan generatorlarning 2 turi bor:
1. o‘zgaruvchan qadamli generator
2. siquvchi generator.
O‘zgaruvchan qadamli generator
Asosiy g‘oya:
CTASR 1 registridan boshqa ikkita — CTASR 2 va CTASR 3 registrlaridagi bitlar siljishini boshqarishda foydalaniladi.
Ishlash algoritmi:
1. CTASR 1 registri tashqi sinxronlash signali bilan sinxronlashtiriladi.
2. Agar CTASR 1 registrining chiqishida bir qiymati bo‘lsa, CTASR 2 registriga sinxronlash signali beriladi, CTASR 3 esa oldingi chiqish bitini takrorlaydi (boshlang‘ich vaqtda CTASR 3 ning oldingi chiqish biti 0 deb olinadi).
3. Agar CTASR 1 registrining chiqishida nol bo‘lsa, CTASR 3 registriga sinxronlash signali beriladi, CTASR 2 esa o‘zining oldingi chiqish bitini takrorlaydi (boshlang‘ich vaqtda CTASR 2 ning oldingi chiqish biti ham 0 deb olinadi).
4. O‘zgaruvchan qadamli generatorning chiqish bitlari ketma-ketligi bitlar bo‘yicha istisnoli YOKI (XOR) amalini CTASR 2 va CTASR 3 registrlarining chiqish ketma-ketliklariga qo‘llash orqali olinadi.
O‘zgaruvchan qadamli generatorlar xavfsizligini oshirish:
- CTASR 1, CTASR 2, CTASR 3 registrlarining uzunliklari juft-jufti bilan o‘zaro tub sonlar qilib tanlanishi kerak
- bu registrlarning uzunliklari bir-biriga yaqin bo‘lishi kerak.
Siqish generatori
CTASR 1 boshqaruvchi registridan CTASR 2 chiqishini boshqarishda foydalaniladi. Algoritm:
- CTASR 1 va CTASR 2 registrlari umumiy sinxronlash signali bilan sinxronlashtiriladi;
- Agar CTASR 1 ning chiqish biti 1 ga teng bo‘lsa, generator chiqishi CTASR 2 registrining chiqish biti bilan shakllanadi;
- Agar CTASR 1 ning chiqish biti 0 ga teng bo‘lsa, CTASR 2 registrining chiqish biti tashlab yuboriladi.
Siqish generatori sodda, masshtablanadigan va yaxshi himoya xususiyatlariga ega. Uning kamchiligi — tegishli choralar ko‘rilmasa, kalitni generatsiyalash tezligi doimiy bo‘lmasligidir.
Siqish generatori xavfsizligini oshirish uchun:
- CTASR 1 va CTASR 2 registrlarining uzunliklari o‘zaro tub sonlar bo‘lishi kerak;
- CTASR 1 va CTASR 2 registrlari o‘rtasida yashirin ulanishdan foydalanish maqsadga muvofiq.
Oqimli va blokli shifrlarning asosiy farqlari
Mavjud maxfiy kalitli shifrlarning aksariyatini aniq ravishda oqimli yoki blokli shifrlarga kiritish mumkin. Biroq ularning nazariy chegarasi ancha noaniq. Masalan, blokli shifrlash algoritmlari oqimli shifrlash rejimida ham ishlatiladi (misol: DES algoritmining quyidagi rejimlari: CFB va OFB).
Oqimli va blokli shifrlar o‘rtasidagi asosiy farqlarni nafaqat xavfsizlik va qulaylik, balki ularning dunyo miqyosida o‘rganilishi nuqtayi nazaridan ham ko‘rib chiqamiz:
- oqimli shifrlarning blokli shifrlardan eng muhim ustunligi — yuqori shifrlash tezligi bo‘lib, u kiruvchi axborot tezligi bilan taqqoslanadi; shu tufayli qayta ishlanayotgan ma’lumotlar oqimining hajmi va bit kengligidan qat’i nazar, deyarli real vaqt rejimida shifrlash ta’minlanadi.
- sinxron oqimli shifrlarda (blokli shifrlardan farqli ravishda) xatolar tarqalishi kuzatilmaydi: deshifrlangan ketma-ketlikdagi buzilgan elementlar soni shifrlangan ketma-ketlikdagi buzilgan elementlar soniga teng bo‘ladi. Bu ketma-ketlik aloqa kanalidan keladi.
- oqimli kalit tuzilmasida kriptotahlilchiga kalit haqida qo‘shimcha ma’lumot olish imkonini beradigan zaif joylar bo‘lishi mumkin (masalan, kalit davri qisqa bo‘lsa, kriptotahlilchi aniqlangan kalit qismlaridan keyingi shifrmatnni deshifrlashda foydalanishi mumkin).
- Oqimli shifrlar blokli shifrlardan farqli o‘laroq, ko‘pincha chiziqli algebra yordamida hujumga uchrashi mumkin (chunki ayrim chiziqli teskari aloqali siljitish registrlarining chiqishlari korrelyatsiyaga ega bo‘lishi mumkin). Oqimli shifrlarni buzishda chiziqli va differensial tahlil ham ancha muvaffaqiyatli qo‘llanadi.
Endi dunyodagi holat haqida:
- blokli shifrlarni tahlil qilish va buzishga oid aksariyat ishlarda DES standartiga asoslangan shifrlash algoritmlari ko‘rib chiqiladi; oqimli shifrlar uchun esa yagona ustuvor tadqiqot yo‘nalishi yo‘q, ularni buzish usullari juda xilma-xil.
- oqimli shifrlar ishonchliligi mezoni bo‘lgan talablar majmui belgilangan (chiqish ketma-ketliklarining uzun davrlari, Golomb postulatlari, nochiziqlilik); blokli shifrlar uchun esa bunday aniq mezonlar mavjud emas.
- oqimli shifrlarni tadqiq etish va ishlab chiqish bilan asosan Yevropa kriptografiya markazlari, blokli shifrlar bilan esa Amerika markazlari shug‘ullanadi.
- oqimli shifrlar bo‘yicha tadqiqotlar blokli shifrlarga nisbatan jadalroq rivojlanmoqda; so‘nggi vaqtlarda DES algoritmlari sohasida sezilarli kashfiyotlar bo‘lmagan, oqimli shifrlar sohasida esa ko‘plab muvaffaqiyat va muvaffaqiyatsizliklar kuzatilgan (avval mustahkam deb hisoblangan ayrim sxemalar keyingi tadqiqotlarda ixtirochilarning umidini oqlamagan).
Oqimli shifrlarni loyihalash
Rayner Ryuppelga ko‘ra oqimli shifrlarni loyihalashning to‘rtta asosiy yondashuvi mavjud:
- Tizim nazariyasiga asoslangan yondashuv kriptotahlilchi uchun ilgari o‘rganilmagan murakkab muammoni yaratishga asoslanadi.
- Murakkablik nazariyasiga asoslangan yondashuv murakkab, ammo ma’lum muammoga asoslanadi (masalan, sonlarni ko‘paytuvchilarga ajratish yoki diskret logarifmlash).
- Axborot nazariyasiga asoslangan yondashuv ochiq matnni kriptotahlilchidan yashirishga intiladi: deshifrlash uchun qancha vaqt sarflanishidan qat’i nazar, kriptotahlilchi yagona aniq yechimni topa olmaydi.
- Tasodifiylashtirilgan yondashuv juda katta hajmli vazifani yaratishga asoslanadi; shu bilan kriptograf deshifrlash masalasini jismonan bajarib bo‘lmaydigan holga keltirishga harakat qiladi. Masalan, kriptograf biror maqolani shifrlashi, kalit sifatida esa maqolaning qaysi qismlari shifrlashda ishlatilganini ko‘rsatishi mumkin. Kriptotahlilchi kalitni tasodifan topmaguncha maqola qismlarining barcha mumkin bo‘lgan tasodifiy kombinatsiyalarini tekshirishiga to‘g‘ri keladi.
Rayner Ryuppelning oqimli tizimlarni loyihalashga oid nazariy mezonlari:
- chiqish ketma-ketliklarining uzun davrlari;
- yuqori chiziqli murakkablik;
- diffuziya — ichki tuzilmalardagi ortiqcha axborotni tarqatish, statistik xususiyatlarni butun matnga yoyish;
- kalit oqimining har bir biti kalit bitlarining aksariyatini murakkab qayta ishlash natijasi bo‘lishi kerak;
- mantiqiy funksiyalar uchun nochiziqlilik mezoni.
Hozirgacha bu mezonlarning oqimli shifrlash tizimi xavfsizligi uchun zarur yoki yetarli ekanligi isbotlanmagan. Shuni ham ta’kidlash kerakki, agar kriptotahlilchi cheksiz vaqt va hisoblash quvvatiga ega bo‘lsa, bunday raqibdan himoyalangan yagona amalga oshiriladigan oqimli shifr — bir martalik bloknotdir.
Kriptotahlil. Oqimli shifrlarga hujumlar
Oqimli shifrlarning barcha kriptotahlil usullari odatda kuch ishlatishga asoslangan («qo‘pol kuch» hujumi), statistik va tahliliy turlarga ajratiladi.
To‘liq qidiruv hujumlari
Bu turga barcha mumkin bo‘lgan variantlarni to‘liq tekshiruvchi hujumlar kiradi. To‘liq tekshiruv murakkabligi muammoning barcha mumkin bo‘lgan yechimlari soniga (xususan, kalitlar yoki ochiq matnlar fazosi o‘lchamiga) bog‘liq. Bunday hujumlar oqimli shifrlash tizimlarining barcha turlariga qo‘llanadi. Shifrlash tizimlarini ishlab chiquvchilar boshqa buzish usullariga nisbatan aynan shu turdagi hujum eng samarali bo‘lib qoladigan tarzda tizim yaratishga intiladi.
Statistik hujumlar
Statistik hujumlar ikki kichik turga bo‘linadi:
- shifrlash gammasining statistik xususiyatlarini kriptotahlil qilish usuli: kriptotizimning chiqish ketma-ketligini o‘rganishga qaratilgan; kriptotahlilchi turli statistik testlar yordamida ketma-ketlikning keyingi biti qiymatini tasodifiy tanlashdan yuqoriroq ehtimol bilan aniqlashga urinadi.
- ketma-ketlik murakkabligini kriptotahlil qilish usuli: kriptotahlilchi gammaga o‘xshash, ammo amalga oshirish osonroq bo‘lgan ketma-ketlikni hosil qilish usulini topishga urinadi.
Ikkala usul ham chiziqli murakkablik tamoyilidan foydalanadi.
Tahliliy hujumlar
Bunday hujumlarda kriptotahlilchiga generator tavsifi, ochiq matn va unga mos shifrlangan matn ma’lum, deb faraz qilinadi. Kriptotahlilchining vazifasi ishlatilgan kalitni (registrlarning boshlang‘ich holatini) aniqlashdir. Sinxron oqimli shifrlarga qo‘llanadigan tahliliy hujumlar turlari:
- korrelyatsion
- «vaqt–xotira» muvozanati
- inversion
- «taxmin qil va aniqlagin»
- kalitni yuklash va qayta ishga tushirishga qaratilgan
- XSL hujumi
Korrelyatsion hujumlar
Oqimli shifrlarni buzishda eng keng tarqalgan hujumlar hisoblanadi.
Ma’lumki, agar nochiziqli funksiya generatorning ichki qismlari haqidagi axborotni chiqishga o‘tkazsa, kriptotizimni buzish uchun zarur bo‘lgan ish hajmini sezilarli darajada kamaytirish mumkin. Shu bois registrlarning boshlang‘ich holatini tiklash uchun korrelyatsion hujumlar kriptotizim chiqish ketma-ketligi bilan registrlar chiqish ketma-ketliklari o‘rtasidagi korrelyatsiyani o‘rganadi.
Korrelyatsion hujumlarning quyidagi kichik turlari mavjud:
- Asosiy korrelyatsion hujumlar
- Kichik vaznli juftlikni tekshirishga asoslangan hujumlar
- Quyidagilardan foydalanishga asoslangan hujumlar: o‘ramli kodlar
- Quyidagi texnikadan foydalanadigan hujumlar: turbo-kodlar
- Chiziqli ko‘phadlarni tiklashga asoslangan hujumlar
- Tezkor korrelyatsion hujumlar.
- Asosiy korrelyatsion hujumlar

Buni Zigentalerning «ajrat va buzib och» usuliga asoslangan korrelyatsion hujumi misolida ko‘rib chiqamiz. U bir xil uzunlikdagi ikkita ikkilik ketma-ketlik orasidagi Hemming masofasi tushunchasiga asoslanadi va kombinatsiyalovchi generatorlarga nisbatan qo‘llanadi.
j-chi chiziqli siljitish registrining (chiqish ketma-ketligi {x(j)}) shifr gammasiga {g} ta’sirini aniqlash uchun generatorning bir qismi ikkilik simmetrik kanal (ISK) sifatida modellashtiriladi. Hujum algoritmi ikki bosqichdan iborat (ba’zan fazalar deb ataladi):
- korrelyatsiya ehtimolini hisoblash kombinatsiyalovchi funksiya asosida bajariladi; so‘ng ikkinchi bosqichga o‘tiladi.
- registrning boshlang‘ich holatlarini birma-bir tekshirish. Bu bosqichda gamma parchasining tegishli parcha bilan korrelyatsiyasi bor-yo‘qligi o‘zaro korrelyatsiya funksiyasini hisoblash orqali aniqlanadi. Natija chegaraviy qiymat bilan solishtiriladi: .
Taqqoslash muvaffaqiyatli bo‘lsa, faza to‘g‘ri deb olinadi va keyingi registrga o‘tiladi — . Aks holda, faza noto‘g‘ri deb olinib, ga o‘tiladi. Algoritm natijasida gammaga axborot kiritadigan holatlar olinadi.
Endi chegaraviy qiymatni tanlash va muvaffaqiyatli kriptotahlil uchun zarur gamma bitlarining soni haqida: Kerakli ehtimollarni belgilaymiz: «yolg‘on signal» va haqiqiy boshlang‘ich holatni o‘tkazib yuborish .
Masalan, ni tanladik, bunda — registr uzunligi. Shu shartlardan izlanayotgan chegaraviy qiymat va bitlar sonini aniqlaymiz: va .
- Juftlikni tekshirish uchun kichik vaznli tenglamalarga asoslangan hujumlar
Bunday hujumlarga Mayyer va Shtaffelbaxning tezkor korrelyatsion hujumini misol qilish mumkin. U filtr-generatorlarga ham, kombinatsiyalovchi generatorlarga ham qo‘llanadi va shu turdagi boshqa barcha tezkor korrelyatsion hujumlar uchun asos hisoblanadi. Hujum g‘oyasi chiziqli registrning teskari aloqa ko‘phadi uchun juftlikni tekshirish tenglamalaridan foydalanishga asoslangan.
- Tezkor korrelyatsion hujumlar
Tezkor korrelyatsion hujumlar deganda hisoblash murakkabligi to‘liq qidiruv hujumlarinikidan ancha kam bo‘lgan hujumlar tushuniladi.
Bunday hujumlar ikkilik simmetrik kanaldagi dekodlash muammosini kriptotahlil muammosiga keltiradi va tasodifiy chiziqli kodni dekodlash sifatida modellashtiriladi. Asosiy korrelyatsion hujumlar kabi bu turda ham quyidagi tushuncha qo‘llanadi: Hemming masofasi.
«Vaqt–xotira» muvozanati
Bu hujumning maqsadi qurilma sxemasi va shifrlash ketma-ketligining bir parchasi ma’lum bo‘lgan holda siljitish registrining boshlang‘ich holatini tiklash (kalitni topish)dir. Hujum murakkabligi shifr o‘lchami va qo‘lga kiritilgan gamma uzunligiga bog‘liq.
U ikki bosqichdan iborat:
- barcha mumkin bo‘lgan «holat–chiqish» juftliklari yozilgan katta lug‘atni tuzish;
- siljitish registrining boshlang‘ich holatini taxmin qilish, chiqish ketma-ketligini hosil qilish, qo‘lga kiritilgan chiqish ketma-ketligini tekshirish va uni hosil qilingan natija bilan solishtirish. Moslik topilsa, taxmin qilingan holat katta ehtimol bilan boshlang‘ich holat bo‘ladi.
Bunday hujumlarga Stiv Bebbijning hujumi va Biryukov–Shamir hujumi misol bo‘ladi.
«Taxmin qil va aniqlagin»
Bu hujum kriptotahlilchiga gamma, teskari aloqa ko‘phadi, sxema chiqishlari orasidagi registr siljishlari soni va filtrlovchi funksiya ma’lum degan farazga asoslanadi. U uch bosqichdan iborat:
- registrning ayrim kataklari qiymatini taxmin qilish;
- kriptotahlilchi biladigan ma’lumotlarga tayangan holda registrning barcha kataklari qiymatini aniqlash;
- chiqish ketma-ketligini hosil qilish; u gamma bilan mos kelsa, birinchi bosqichdagi taxmin to‘g‘ri bo‘lgan; mos kelmasa, 1-bosqichga qaytiladi.
Algoritm murakkabligi generator tuzilishi va taxminlar soniga bog‘liq.
Adabiyotlar
- Ryabko B. Ya., Fionov A. N. Axborotni himoyalashning kriptografik usullari. — Moskva. — Goryachaya Liniya–Telekom nashriyoti, 2005. — ISBN 5-93517-265-8.
- Bryus Shnayer. Amaliy kriptografiya, ikkinchi nashr: C tilidagi protokollar, algoritmlar va dastlabki kod (muqovali). — John Wiley & Sons, Inc. — Xorijiy adabiyotlar nashriyoti, 1996. — ISBN 0471128457.
- A. Menezes, P. van Orshot, S. Vanstoun. Amaliy kriptografiya bo‘yicha qo‘llanma. — CRC Press, Inc. — 1997.
- Ma’ruzalari E. M. Gabidulin, Moskva fizika-texnika instituti, 2009-yil.
Havolalar
- Mett J. B. Robsho. Oqimli shifrlar: texnik hisobot TR-701 (ingl.), 2.0-versiya, RSA Laboratories, 1995.
- Oqimli shifrlar. Chet ellardagi ochiq kriptologiya natijalari.. Oqimli shifrlarni yaratish va kriptotahlil qilish bo‘yicha 1997-yilgacha bo‘lgan xorijiy tadqiqotlarning eng to‘liq jamlanmasi va tarjimasi.
- V. S. Anashin, A. Yu. Bogdanov, I. S. Kijvetov. eSTREAM: tezkor va mustahkam oqimli shifrlar.
- J. A. Rids va N. J. A. Sloun. Siljitish registrlarini sintez qilish.
- A. V. Yakovlev, A. A. Bezbogov, V. V. Rodin, V. N. Shamkin. Axborotni kriptografik himoyalash.
- Kompyuter axborotini himoyalash usullari va vositalari. O‘quv qo‘llanma.
- Ehtimollik oqimli shifrlash tizimining umumiy sxemasi
- eSTREAM: Lox-Ness maxluqining farzandi
- A. A. Menyashev, V. A. Monarev, B. Ya. Ryabko, A. N. Fionov. Statistik hujum.
- S. Doroshenko, A. Fionov, A. Lubkin, V. Monarev, B. Ryabko, Yu. I. Shokin. Blokli va oqimli shifrlarga eksperimental statistik hujumlar (mavjud bo‘lmagan havola).
- Yu. V. Stasev, A. V. Potiy, Yu. A. Izbenko. Oqimli shifrlarni kriptotahlil qilish usullarini tadqiq etish.