International

3 Yaratilgan to`g`ri juftliklar usuli

Ushbu usul xotirasiz yondashuvga asoslanadi va u hech qanday juftlikni saqlamasdan, mos xususiyatni qondiradigan to'g'ri juftlarni yaratish uchun fitnes funksiyasidan foydalanish mumkin degan fikrdan foydalanadi. Tegishli sonli juftlarni yaratgandan so'ng, biz bir qator pastki kalitlarni olamiz. Quyidagi teoremaga ko'ra, eng tez-tez uchraydigan pastki kalit maqsadli pastki kalit bo'ladi.

^{Teorema 2. Ω}P ^{va Ω}T ^{mos ravishda asosiy xarakteristikaning kirish va chiqish juftligi bo'lsin. U holda har qanday juft P, P ∗ shundayki, Ω}P ^{=P⊕P ∗, a bilan shifrlangan.
DES-8, to T`=T⊕T ∗ to'g'ri juftlik. Shunga ko'ra, bunday to'g'ri juftlik tomonidan berilgan muvofiqlik funksiyasini maksimal darajada oshiradi:}

Muvofiqlik

Rasm 1. 5-raund xarakteristikasi ehtimollik bilan

_T=405C0000 04000000_x


Bu yerda ^{Hd(ΩT , T)} orasidagi Hamming masofasi

va T ` esa blok uzunligi. Ushbu funktsiya DESga o'xshash tizimlarni buzish uchun genetik algoritmlar uchun fitnes funktsiyasi sifatida muvaffaqiyatli ishlatilishi mumkin.


^{Isbot. Agar P, P∗ to'g'ri juft bo'lsa, Ω}T^{=T � bo'ladi. Shuning uchun H}d^(ΩT ^{, T �) = 0. Shuningdek, H} d^(ΩT ^{, T �)
kamayganda to‘g‘ri juftlikning kutilishi ortadi.}

^{Har bir o'ng juftlik uchun Ω}P ^{=P⊕P ∗ mos keladigan T va T∗ shifrlangan matn juftligi mavjud bo'lib, T`= T⊕T ∗ farqi mavjud. 2-rasmdagi T’ ning o‘ng yarmi R’, chap tomoni esa L’. Har bir S-quti uchun K8 da sabab shartni qondiruvchi mos keladigan 6 bitli SK mavjud}


Shunday qilib, ^{T→QMuvofiqlik(Ω}T, ^T) va moslik masofalar kamayishi bilan monoton ravishda ortadi. Keyin, 1-teoremada bo'lgani kabi, bu sxemalar soni moslik ortishi bilan ortib borayotganini anglatadi va bu teoremani isbotlaydi.
Quyidagi algoritm genetik jihatdan kerakli to'g'ri juftlarni yaratish uchun ishlatilishi mumkin.

Rasm 3. 2-raund xarakteristikasi ehtimollik bilan.

4.1 YJKT algoritmi (yaratilgan juftlik kriptotahlili)


Kirish: ikkita ochiq matnning tegishli xarakteristikaga nisbatan farqi.
Chiqish: bu kalitning ba'zi bitlari. Jarayon:

1. 
   Har bir individual (xromosoma) birinchi ochiq matn P sifatida joylashgan boshlang'ich populyatsiyani yarating.
   

2) Har bir xromosoma uchun bajaring

1. 
   Ikkinchi ochiq matnni baholang P∗= ^ΩP
   

⊕P, bu erda ^ΩP - xarakterli farq.

2. 
   T`=T⊕T ∗ shifrlangan matn juftligini oling.
   
3. 
   ^{Xemming masofasini baholang H} d^(ΩT ^{, T �).}
   
4. 
   Ikki oʻlchovli jadval hosil qiling τ=<εS,ςS >,
   

bu yerda εS kutilayotgan pastki kalit va ςS unga mos keladigan hisoblagichdir. Barcha hisoblagichlarni nolga qo'ying.

5. 
   
   n
   Muvofiqlik funksiyasini hisoblang ^{Muvofiqlik(Ω}T ^{, T �) = 1− Hd (ΩT ,T ) ,}
   

bu yerda joriy populyatsiyadagi har bir shaxs uchun tizim blokining uzunligi.

6. 
   Agar muvofiqlik qiymati 0,5 dan katta bo'lsa, barcha S-qutilarga nisbatan sabab holatini sinab ko'ring.
   
7. 
   Agar sababchi shart qondirilsa
   
   1. 
      Jadvaldan har bir S-quti uchun τ pastki kalitlarini ishlab chiqing.
      
   2. 
      Oxirgi davra pastki kalitida (barcha S-qutilari bilan bog'langan) paydo bo'lishi mumkin bo'lgan barcha mumkin bo'lgan bitlarni yarating, bitta pastki kalitni tanlab, τ jadvalidagi asosiy S-quti uchun εS Bunday bitlarni σ bilan belgilang.
      
   3. 
      Har bir σ uchun mos keladigan hisoblagich ςS ni oshiring.
      
1. 
   Krossover operatsiyasini qo'llang.
   
2. 
   Agar kerak bo'lsa, mutatsiya operatsiyasini qo'llang.
   
3. 
   Keyingi populyatsiyani yarating.
   
4. 
   ^ς opt maksimal qiymatining hisoblagichini olish uchun ii-bosqichni takrorlang. Bunday hisoblagich ^σ opt bilan bog'langan, bu oxirgi tur pastki kalit uchun to'g'ri kutishdir.
   

2. 
   YJKT ning DES-8 ga qo'llanilishi
   

Bu yerda DES-8 kriptoanaliz ko'rib chiqiladi. Sakkizta S-qutining har biri uchun 64-bitli xromosomani aniqlash uchun genetik algoritm, YJKT ishlatiladi. Ikki raundli xarakteristikani qo'llash orqali ^ΩP = 1960000000000000x ehtimollik≈1/234 (3-rasmga qarang). Shunday qilib, S1, S2 va S3 qutilari uchun ^K8 da to'g'ri 18 bitni hisoblash mumkin. ^Hd^(ΩT^{,T�) Ω}P va ^FP−1(T�) ni o‘lchaydi. Birinchi uchta S-quti uchun sabab sharti qondiriladi.

5.