International

International Journal of Network Security, Vol.5, No.2, PP.213–219, Sept. 2007

DES-8 ning kriptotahlili uchun genetik algoritm

Hasan Mohammed Hasan Husein¹, Bayoumi I. Bayoumi², Fathy Saad Holail³,

Bahaa Eldin M. Hasan⁴, va Mohammed Z. Abd El-Mageed⁵
(Asosiy muallif: Hasan Mohammed Hasan Husein)

Tadqiqotlarni Rivojlantirish Markazi Milliy Mudofaa Kengashi¹

Shams Universitetining ilmiy fakulteti matematika bo‘limi ²
Milliy Mudofaa Kengashining Ilmiy-tadqiqotlarni rivojlantirish markazining Ilmiy tadqiqotlar bo'limi boshlig'i³
Ilmiy tadqiqotlar boʻlimi, Tadqiqotlarni rivojlantirish markazi, Milliy Mudofaa Kengashi⁴ Kompyuter fanlari boʻlimi, Muhandislik fakulteti, Al-Azhar Universiteti, Nasr shahri, Qohira, Misr⁵


(2005 yil 10 dekabrda olingan; qayta ko'rib chiqilgan va 2006 yil 10 yanvarda qabul qilingan)

Abstrakt

Turli xil kriptosistemalar qidirish uchun to'liq texnikadan foydalanadi, yetishmayotgan belgi, kalit bo'sh joy. Bunday qidiruv texnikasi hisoblash uchun yetarli bo'lishi uchun boshqarilishi kerak. Bu yerda genetik algoritm, GA, asosiy kalitni topish uchun DESga o'xshash tizimlarning kriptanalizasi uchun taklif qilingan. Asosiy pastki bo'shliqqa tegishli kalitlarning dastlabki populyatsiyasini shakllantirish orqali aniq kalitni olish uchun genetik algoritm yondashuvi qabul qilingan. Muvofiqlik funksiyasiga ta'sir ko'rsatishi mumkin bo'lgan nazorat parametrlarini dinamik o'zgartirish orqali oldindan yetuk konvergentsiyaning (mahalliy minimal) oldini olish mumkin. Ushbu maqolada birinchi marta sakkiz raundli DESni buzishning yangi usuli ishlab chiqilgan. Uning ishlashi to'liq qidiruv va differensial kriptoanalizga, DK qaraganda ancha tezdir. Yangi usul mavjud DK texnikasi o'rniga turli xil DES-ga o'xshash tizimlarga qo'llanilishi mumkin.


Kalit so'zlar: DESga o'xshash, differensial kriptotahlil, genetik algoritm, muvofiqlik funksiyasi

xaritalashni anglatadi. Algoritm quyidagi amallarni bajaradi:

1. 
   Tasodifiy ravishda boshlang'ich populyatsiyani yaratish.
   
2. 
   Joriy populyatsiyadagi har bir shaxs uchun moslikni hisoblash.
   
3. 
   Har bir shaxsning tanlanish ehtimolini uning mosligiga mutanosib bo'lishini aniqlash.
   
4. 
   Selektsiya, krossover va mutatsiya bilan ifodalangan genetik operatorlar orqali nasl berish uchun oldingi joriy populyatsiyadan individlarni ehtimollik bilan tanlab, keyingi joriy populyatsiyani yaratish.
   
5. 
   Qoniqarli yechim olinmaguncha 2-bosqichni takrorlash.
   

Holland [3] GA operatorlarining (tanlash, krossover va mutatsiya) avloddan keyingi +1 ga o‘tishda H sxemasining kutilayotgan soniga (H, t) ta’sirini tahlil qildi. Ushbu muhokamani [3] da topish mumkin. Holland sxemasi teoremasi quyidagicha ifodalanishi mumkin:
^{m(H, t+ 1)≥m(H, t) fH (t) [1−P} c ^{δ(H) −o(H)P} m^],

1. 
   Kirish ^{f¯(t) l−1}
   

^{Bu yerda f}H^{(t) H sxemasini ifodalovchi satrning moslik}

Genetik algoritmlar (GA) Holland [4] tomonidan tabiiy tanlanish va genetikaning evolyutsion g'oyalariga bog'liq bo'lgan adaptiv evristik qidiruv usuli sifatida tushuntirilgan. Genetik algoritmning asosiy maqsadi eng zo'rning omon qolishi tamoyilini hisobga olgan holda tabiiy evolyutsiya jarayonini simulyatsiya qilishdir. U odatda qidiruv maydoni nisbatan katta bo'lgan va klassik qidiruv usullari bilan samarali o'tib bo'lmaydigan holatlarda qo'llaniladi. Bu, asosan, yechimi bir-biriga bog'liq bo'lmagan ko'plab o'zgaruvchilarni baholashni talab qiladigan muammolarga tegishli. Chunki GA tasodifiy qidiruv maydonini muammoni hal qilish mumkin bo'lgan boshqariladigan qidiruv maydoniga aqlli
qiymatini bildiradi; f¯(t) populyatsiyadagi barcha ^{qatorlar bo'yicha o'rtacha moslik qiymatini bildiradi; P}C ^{va P}m ^{mos ravishda krossover va mutatsiya ehtimolini, l} sxema uzunligini bildiradi; δ (H) sxema H ning birinchi va oxirgi o'rnatilgan satr pozitsiyalari orasidagi masofa sifatida o'lchanadigan sxema H uzunligini bildiradi; o(H) sxema H tartibini bildiradi, sxema H ning belgilangan qator pozitsiyalari soni bilan belgilanadi.
Bu shuni anglatadiki, muvofiqlik funksiyasi yaxshiroq nasldan foydalanilganda kuchayadi. Bu fakt, shuningdek, genetik algoritmlarning ulkan bo'shliqlarni samarali qidirish qobiliyati GA ni kriptoanalizda foydalanish uchun tabiiy nomzod sifatida qabul qiladi.

Darhaqiqat, ular yaqinda mos ravishda oddiy almashtirish, transpozitsiya va knapsack shifrlarining kriptotahlilida muvaffaqiyatli qo'llanildi [7, 10, 11].
DES-ga o'xshash tizimlar katta kalit maydoniga ega bo'lganligi sababli va an'anaviy qidiruv algoritmlari yordamida shifrlash kalitini topish mumkin emasligi sababli, GA-ga asoslangan evolyutsion yondashuvni ko'rib chiqish kerak.