|
4.2. 1-bosqich
Biz birinchi navbatda asosiy tamoyillarni tasvirlash uchun sodda va qimmat 1-bosqich algoritmini va optimallashtirilgan algoritmni tasvirlaymiz. Shuningdek, biz 2-bosqich uchun Cipher rotor sozlamalari nomzodlarini tartiblash va tayyorlash jarayonini tasvirlaymiz.
4.2.1. Oddiy 1-bosqich algoritmi
Umumiy g'oya Stamp and Chan ( 2007 ) da kiritilgan. Biz Cipher rotorlarining barcha mumkin bo'lgan konfiguratsiyasini alohida sinab ko'ramiz. Beshta Cipher rotorlari oldinga yoki teskari yo'nalishda o'rnatilishi mumkin bo'lgan o'nta rotordan tanlanadi. Shuning uchun, bor(10/5) ⋅25= 967 , 680 =219.9(105)·25=967,680=219.9bunday konfiguratsiyalar. Har bir konfiguratsiya uchun biz Cipher rotorlarining barcha mumkin bo'lgan boshlang'ich pozitsiyalarini sinab ko'ramiz - jami265= 11 , 881 , 376 =223.5..Shunday qilib, sinovdan o'tkaziladigan kombinatsiyalarning umumiy soni (beshta rotorning konfiguratsiyasi va boshlang'ich pozitsiyasi)219,9 + 23,5=243.4
Har bir boshlang'ich pozitsiyasi uchun, masalan, AAAAA yoki HJYUI, biz birinchi navbatda Cipher rotorlari birinchi shifrlangan matn belgisini to'g'ri dekodlashini tekshiramiz, ya'ni shifrlangan belgi birinchi ma'lum bo'lgan ochiq matn belgisiga mos keladi. 9 Agar bu sinov muvaffaqiyatli o'tgan bo'lsa, biz ikkinchi shifrlangan matn belgisi ham to'g'ri shifrlangan bo'lishi uchun o'sha boshlang'ich pozitsiyadan erishish mumkin bo'lgan pozitsiyalar mavjudligini yaroqli qadam naqshini qo'llash orqali tekshiramiz. Nazariy jihatdan, bor25= 32Belgining har bir shifrlash yoki parolini hal qilishdan keyin beshta shifrlash rotorlari uchun mumkin bo'lgan 5 bitli naqshlar. Biroq, Secda muhokama qilinganidek . 3 , CSP-889 modeli uchun ushbu naqshlarning faqat 30 tasi amal qiladi, CSP-2900 uchun esa faqat 31 tasi amal qiladi. Agar qadam naqshlarining hech biri ikkinchi shifrlangan matn belgisi to'g'ri shifrlangan yangi pozitsiyaga olib kelsa, biz boshlang'ich pozitsiyadan voz kechamiz. Aks holda, biz ma'lum bo'lgan barcha ochiq matn belgilarini qayta ishlamagunimizcha, uchinchi, to'rtinchi va boshqalar uchun jarayonni rekursiv ravishda takrorlaymiz.
Stamp va Chanda ( 2007), it was shown that although only 1/26 of the initial positions survive after each symbol is tested, the number of paths, that is, the sequence of positions and in-between stepping patterns so that the Cipher rotors decipher the ciphertext correctly, increases exponentially, by a factor of 30/26 = 1,154 , _ _30/26=1.154,sinovdan o'tgan har bir belgi uchun. 10 Xuddi shunday, bu raqam bir marta ortadi31/26 = 1,192 _ _31/26=1.192CSP-2900 modeli uchun. Stamp and Chan ( 2007 ) shuningdek, birlashtirilgan yo'llar kabi yo'llarga ishora qilib, bir yoki bir nechta pozitsiyalarni almashish, bir nechta yo'llar qanday birlashishi mumkinligini tasvirlaydi .
Ushbu sodda 1-bosqich algoritmining natijasi shifrlash sozlamalari va qadamlar ketma-ketligi/yo'llari to'plamidir.
4.2.2. Optimallashtirilgan 1-bosqich algoritmi 4.2.2. Optimallashtirilgan 1-bosqich algoritmi
Shifrlangan matn/ma'lum ochiq matn belgilari ketma-ketligi bo'ylab barcha mumkin bo'lgan boshlang'ich pozitsiyalarini sinab ko'rganda, bir xil shifrlangan rotor pozitsiyasiga turli (birlashtirilgan) yo'llar orqali bir necha marta erishish mumkin. Shu sababli, sodda algoritmni ( 4.2.1 -bandda) barcha 11,881,376 boshlang'ich pozitsiyalaridan shifrlangan matn/ma'lum ochiq matn belgilarining to'liq ketma-ketligi davomida oddiygina takrorlash aniq isrofgarchilik va samarasizdir.
Buning o'rniga, biz samarali chiziqli algoritm yordamida ma'lum bir shifrlangan rotor konfiguratsiyasi uchun barcha birlashtirilgan yo'llarning to'liq grafigini yaratish mumkinligini ko'rsatamiz. Bu asosiy algoritm Kenglik-Birinchi Qidiruv o'tishini yoki BFSni amalga oshiradi. 11 First, we generate a graph with n layers of nodes, n being the length of the known plaintext. Each layer i includes a node for each position of the Cipher rotors in which the ith ciphertext symbol can be decrypted to obtain the ith known-plaintext symbol, with 1 ≤ i ≤ n .1≤i≤n. Since random positions have a 1/26 probability of correctly decrypting a given ciphertext symbol, it is expected that each layer roughly contains 11,881,376/26=456,976 tugunlar.
Grafik qirralari qo‘shni qatlamlarga tegishli bo‘lgan juft tugunlarni bog‘laydi — aytaylik, biri i qatlamda, ikkinchisi i + 1 qatlamda . Biz tugunlarni chekka bilan bog‘laymiz, agar i + 1 qatlamidagi tugun Shifr rotori o‘rnini bildirsagina. i qatlamdagi tugun bilan ifodalangan joydan , yaroqli qadam naqshiga ega va ikkala holatda ham mos keladigan shifrlangan matn belgisi (mos ravishda i va i + 1) mos keladigan ochiq matn belgisiga ( i ) mos keladigan tarzda shifrlanishi mumkin. va mos ravishda i + 1).
Biz har bir qatlamning tugunlarini to'ldirish orqali grafikni qurishni boshlaymiz - bu dastlabki jarayon uchun ish omili n·11,881,376.Keyin biz birinchi qatlamdan boshlab BFS oldinga siljish bilan qatlamdan qatlamga qirralarni hosil qilamiz, qatlamning har bir pozitsiyasida barcha amaldagi qadam naqshlarini sinab ko'ramiz. Bunday jarayonning murakkabligi chiziqli, tartibda n⋅456,976⋅30n·456,976·30CSP-889 uchun (yoki n·456,976·31CSP-2900 uchun).
Soddalashtirilgan misol 9-rasmda ko'rsatilgan . Aniqlik uchun biz faqat uchta qatlamni ko'rsatamiz va har bir qatlamda i , faqat i shifrlangan matn belgisini to'g'ri hal qiluvchi Cipher rotorlari pozitsiyalarining kichik to'plamini ko'rsatamiz . Har bir chekka qadam qo'yish naqshini, ya'ni ulangan tugunlar orasidagi rotorlarni ko'rsatadi. Ko'rinib turibdiki, uchinchi qatlamdagi BBBBB bir nechta yo'llarga kiritilgan (bular birlashtirilgan yo'llar). Birinchi qatlamdagi AABBB kabi ba'zi tugunlarni davom ettirib bo'lmaydi. Ikkinchi qatlamdagi BABBB kabi boshqa tugunlarga birinchi qavatdagi tugunlarning birortasidan etib bo'lmaydi.
Figure 9. Phase 1 graph—simplified example.
To'liq hajmni ko'rsatish
Bizni faqat 1-qatlamda yaroqli boshlang‘ich pozitsiyadan boshlovchi va n -qatlamda to‘g‘ri pozitsiyada tugaydigan yo‘llar qiziqtiradi . Shuning uchun:
Biz 1-qavatdan erishib bo'lmaydigan tugunlarni olib tashlashimiz kerak. Bunga BFS-ni oldinga o'tish paytida i qatlamning barcha tugunlarini qayta ishlashdan so'ng hech qanday kiruvchi chekkasiz qoladigan i + 1 qatlamdagi har qanday tugunni o'chirish orqali erishiladi.
Do'stlaringiz bilan baham: |
