Muxammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

Bundan tashqari, n -qatlamdagi haqiqiy pozitsiyaga erishib bo'lmaydigan har qanday tugunni olib tashlashimiz kerak . Bunga qo'shimcha orqaga BFS o'tish orqali erishiladi, unda biz birinchi navbatda qatlamdan tugunlarni olib tashlaymizn − 1n−1 that have no forward edges (into nodes of layer n) and all the incoming (backward) edges into those nodes. We then repeat the process for layer n − 2 ,n−2,qatlamn − 3 ,n−3,va hokazo, biz 2-qavatga etgunimizcha.

Natijada, faqat yaroqli boshlang'ich pozitsiyasidan oldinga yetib borish mumkin bo'lgan va n qatlamga yetib boruvchi kamida bitta yo'l bo'lgan tugunlargina saqlanib qoladi.
9-rasmdagi soddalashtirilgan misolimizga qaytsak, ahamiyatsiz tugunlar va qirralarni olib tashlaganimizdan so'ng, biz 10 -rasmda ko'rsatilgan qisqartirilgan grafikni olamiz . Ushbu grafik asosida bizda to'rtta tegishli yo'l bor:
Figure 10. Phase 1 graph—simplified example after removal of irrelevant nodes.

To'liq hajmni ko'rsatish

• 
  AAAAA (01100) ABBAA (11101) BCCAB
  
• 
  AAAAA (01100) ABBAA (10011) BBBBB
  
• 
  AAABA (10000) BAABA (01101) BBBBB
  
• 
  AAABA (10000) BAABA (11000) CBABA
  

Oldinga va orqaga o'tishdan keyin turli qatlamlardagi omon qolgan pozitsiyalar (tugunlar) sonini o'lchash uchun n = 100 bo'lgan simulyatsiyalarni o'tkazdik . Ko'pgina hollarda 1-qatlam yoki n -qatlam eng ko'p pozitsiyalarga ega bo'lib, 5000 dan 60 000 tagacha pozitsiyani tashkil qiladi. ¹² Atrofdagi ichki qatlamlardan biridan / 2,n/2,pozitsiyalar soni eng past, odatda birinchi yoki oxirgi qatlamdagi pozitsiyalar sonining 1/7 qismidir.

4.2.3. Yo'llarni baholash

Simulyatsiyalardan biz grafik sek.da tasvirlangan optimallashtirilgan algoritm bilan qurilganligini kuzatdik . 4.2.2 hali ham har bir qatlamda minglab yoki o'n minglab tugunlarni o'z ichiga oladi. Ularni bog'laydigan qirralar bilan, bu tugunlar, shuningdek, haqiqiy boshlang'ich pozitsiyasi va amaldagi yakuniy pozitsiyasi o'rtasidagi juda ko'p sonli uchigacha yo'llarni ifodalaydi. Hujumimizda biz eng mumkin bo'lgan uchdan-uch yo'llarni aniqlashni, ularni tartiblashni va unchalik ishonchli bo'lmaganlarini yo'q qilishni maqsad qilganmiz. Buni amalga oshirish uchun biz grafikdagi uchdan-oxirgacha bo'lgan yo'llar bilan ifodalangan nomzodning bosqichma-bosqich ketma-ketligiga ball beramiz. Yo'lni baholash uchun ikkita umumiy yondashuv mavjud:

• 
  Berilgan grafikdagi har bir yo'lni alohida baholash. Ushbu yondashuv keng ko'lamli hisob-kitoblarni talab qiladi, chunki yo'l soni n bilan eksponent ravishda ortadi .
  
• 
  Har bir rotorning orasiga qadam qo'ygan umumiy soniga asoslanib, bir xil holatda boshlanib, bir xil holatda tugaydigan barcha (birlashtirilgan) yo'llarni bitta hisoblash bilan birgalikda baholash.
  

Birinchi yondashuv ikkinchi yondashuvga qaraganda aniqroq bo'lish potentsialiga ega, bu har bir yo'l ichidagi individual naqshlar haqidagi qimmatli ma'lumotlarni o'tkazib yuborishi mumkin (masalan, ma'lum naqsh qiymatlariga nisbatan moyillik). Boshqa tomondan, ikkinchi yondashuvni amalga oshirish osonroq va ancha arzon va bu maqolada qo'llaniladigan yondashuv. Keyinchalik Sec-da tasvirlanganidek. 4.4 , nisbatan yuqori muvaffaqiyat darajasiga erishish uchun etarlicha aniq.
Biz bir xil boshlang'ich va yakuniy pozitsiyalarga ega bo'lgan birlashtirilgan yo'llar uchun bir nechta ball olish usullarini empirik baholadik. Biz n = 100 va taqqoslash uchun tasodifiy yaratilgan yo'llar bilan ko'p sonli haqiqiy birlashtirilgan yo'llarni simulyatsiya qildik . Maqsad noto'g'ri negativlarni (FN) minimallashtirish, ya'ni haqiqiy yo'llarni istisno qilish va noto'g'ri pozitivlarni (FPs), ya'ni tasodifiy/noto'g'ri yo'lni qabul qilish o'rtasidagi optimal muvozanatga ega bo'lgan baholash usulini topish edi. FNlarning narxi butun hujum uchun umumiy muvaffaqiyat darajasining pasayishi hisoblanadi. FPlarning narxi noto'g'ri yo'llarni qayta ishlash uchun 2-bosqichga ishlov berish vaqtini oshiradi, bu esa hisoblash resurslari cheklangan (ehtimol) holatda muvaffaqiyat darajasining pasayishiga olib kelishi mumkin va 1-bosqich natijalarining hammasi ham 2-bosqichda qayta ishlanmaydi.
Birlashtirilgan yo'llarni baholashning bir nechta usullarini uzoq empirik baholashdan so'ng, biz oxir-oqibat quyidagi ball funktsiyasini tanladik:
∑r = 15pˆr⋅log(pˆr)∑r=15p̂r·jurnal(p̂r)
(1)qayerdapˆrp̂r- shifrlangan rotor r ning yo‘l bo‘ylab necha marta qadam bosganligi, yo‘lning qirralari soniga bo‘lingann - 1 ,n−1, n - yo'ldagi tugunlar soni.
It should be noted that unless for exceptional scenarios (unrealistic with our algorithm), the score of two paths that start at the same position, and end at the same position, is the same.¹³ Based on 10,000,000 simulations for model CSP-889, with n = 100, setting a (minimum) score threshold of −1.63 does not result in any FN for genuine paths. Still, it results in FPs at a ratio of 0.004 for simulated random paths.¹⁴ Similarly, a threshold of −1.50 does not result in any FPs but results in FNs at a ratio of 0.036.¹⁵
FN/FP balansiga alohida Index rotor sozlamalari va aniqrog'i, ushbu sozlamalar tegishli bo'lgan toifaga ta'sir qilishi bilan masala yanada murakkablashadi ( 3-qismga qarang).). Misol uchun, biz 1-toifadagi Index rotor sozlamalari bilan yo'l uchun o'rtacha ball -1,23 ekanligini aniqladik. 1-toifadagi indeks rotor sozlamalari simulyatsiyasi shuni ko'rsatadiki, to'g'ri yo'lni osongina aniqlash uchun -1,50 chegarasi na FN va na FPga olib kelmaydi. Boshqa tomondan, 88-toifadagi Index rotor sozlamalari bo'lgan yo'l uchun o'rtacha ball -1,49 ni tashkil qiladi. Simulyatsiyalar shuni ko'rsatadiki, −1,50 chegarasi hali ham FPga olib kelmasa ham (10 000 000 simulyatsiya uchun), bu 0,23 ga yaqin FN nisbati ancha yuqori bo'lishiga olib keladi (ya'ni 23% da to'g'ri yo'l e'tibordan chetda qolishi mumkin). holatlar, bu chegara asosida).
Ajablanarlisi shundaki, CSP-2900 modeli uchun vaziyat keskin farq qiladi va bizning hujumimiz uchun ancha qulayroqdir. 1-toifaga tegishli bo'lgan Index rotor sozlamalari bilan o'rtacha ball, eng qulay toifa - −1,06, 80-toifaga kiruvchi uchun esa -1,17, eng kam qulay. Boshqa tomondan, tasodifiy yo'llarda rotorlar qadam bosmaslikdan ko'ra bir oz ko'proq qadam bosadi. ¹⁶ CSP-2900 uchun optimal chegarani tanlash mumkin, −1,42. Optimal chegara - bu 80 indeksli rotor sozlamalari toifalarining har biri uchun hech qanday FP va hech qanday FN mavjud bo'lmasligi uchun tasodifiy yo'l va haqiqiy yo'l o'rtasida aniq farq qiladigan chegaradir. Bu amalda n bilan ekanligini bildiradi = 100, 1-bosqichdan keyin faqat bitta yo'l qoladi va 2-bosqichda faqat bitta yo'lni tekshirish kerak bo'ladi. Agar biz FNlarning kichik nisbatini qabul qilishga tayyor bo'lsak, CSP-2900 yo'llarini faqat n = 60 ta ma'lum bo'lgan ochiq matn belgilari bilan samarali baholash mumkin. −1,33 chegarasi hech qanday FP (10 000 000 simulyatsiya uchun) va FN nisbati atigi 0,001 ga olib kelmaydi.

4.2.4. Screening and preparing paths for phase 2

Sek ichida . 4.2.2 , biz ma'lum bir Cipher rotorini tanlash, tartib va ​​teskari sozlash uchun joriy boshlang'ich va amaldagi tugatish pozitsiyalari o'rtasidagi barcha mumkin bo'lgan birlashtirilgan yo'llarni o'z ichiga olgan grafikni qanday qurishimizni tasvirlab berdik. Sek ichida . 4.2.3 , biz bu yo'llarni qanday baholaganimizni tasvirlab berdik. Endi biz qanday qilib yo‘llarni ajratib olishimiz, past ballli yo‘llardan voz kechishimiz, muhim umumiy kichik yo‘llarni kichik subgraflarga birlashtirgan yo‘llarni birlashtirishimiz va bu subgraflarni 2-bosqichda qayta ishlashdan oldin tartiblashimizni tasvirlaymiz.
Grafikdan bosqichma-bosqich yo'llarni quramiz ( 4.2.2 -bandda tasvirlangan protsedura bo'yicha yaratilgan ), qatlam-qatlam. Biz 1-qavatdan boshlaymiz va har bir keyingi qatlam uchun biz oxirgi qatlam n ga yetgunimizcha, BFS traversalidan foydalanib, ushbu qatlamga olib boradigan barcha yo'llar ro'yxatini saqlaymiz .
Stamp and Chan ( 2007 ) tomonidan ta'kidlanganidek, har bir yangi qatlamni (va unga bog'liq shifrlangan matn va ochiq matn belgilarini) qayta ishlash jarayonida yo'llar soni eksponent ravishda oshadi. Nazariy jihatdan, biz shunchaki grafikda ifodalangan barcha yo'llarni qurishimiz, ularni baholashimiz va barchasini tartiblashimiz mumkin. Lekin bu samarali ham, zarur ham emas. Baholash usuli to'liq yo'llar bilan eng aniq bo'lsa-da, n = 100 qatlam bilan, uni kamroq qatlamli qisman yo'llar uchun ham hisoblash mumkin.
Shu maqsadda biz to'liq yo'lni tasniflash uchun chegaradan ko'ra ruxsat beruvchi (pastroq) chegaralardan foydalanamiz. Agar qisman yo'lning balli chegaradan past bo'lsa, biz bu qisman yo'lni qayta ishlashni to'xtatishimiz mumkin. 11 -rasmda turli uzunlikdagi qisman yo'llarni ekranlash uchun ishlatiladigan chegaralar ko'rsatilgan. Ushbu ruxsat etilgan chegaralar qisman haqiqiy yo'lni o'tkazib yuborish ehtimoli juda past (0,0000001 dan kam) bo'lishini ta'minlaydi. Ushbu chegaralardan o'tmaydigan qisman yo'llarni filtrlash nafaqat har bir qatlamdan keyingi eksponensial o'sishni sezilarli darajada kamaytiradi, balki har bir qatlamdan keyin omon qoladigan yo'llar sonini ham kamaytiradi.
11-rasm. 1-bosqich - qisman yo'llar uchun chegaralar.

Oxir-oqibat yo'llarni qabul qilish uchun yakuniy ball chegarasi (100 ta tugun bilan) hujum boshida o'rnatilgan parametrdir, odatda -1,50 (CSP-889 uchun). Bu chegara oxirigacha bo'lgan yo'llarni baholash, ehtimolligi past bo'lganlarni filtrlash, 2-bosqichda sinovdan o'tkazilishi kerak bo'lgan uchdan-uch yo'llar sonini eng yomonida bir necha mingdan ko'p bo'lmagangacha kamaytirish uchun ishlatiladi. hol, aksariyat hollarda esa kamroq.
Nazariy jihatdan, 2-bosqichda omon qolgan barcha uch-to-uch yo'llarni alohida qayta ishlash mumkin bo'lar edi. Biroq, yuqorida tavsiflanganidek, nafaqat past ehtimolli yo'llarni filtrlash mumkin, balki uni birlashtirish ham mumkin. 2-bosqichda tezroq tekshirish uchun bir nechta yo'llar birgalikda (qarangSec. 4.3.3). This additional screening and bundling is performed on the graph representing the valid positions and stepping sequences for given Cipher settings, as follows:

• 
  Biz birinchi navbatda grafikdagi omon qolgan uchdan-uchgacha yo'llarni ballari bo'yicha saralaymiz.
  
• 
  Biz faqat eng yuqori ball to'plagan 1000 ta yo'lni saqlab qolamiz va qolganlarini bekor qilamiz.
  
• 
  Bundan tashqari, yuqori darajadagi yo'ldan minus 0,2 ballga ega bo'lgan yo'llarni olib tashlaymiz.
  
• 
  Biz qolgan yo'llarni eng yuqori reytingdan eng past darajaga qadar qayta ishlaymiz. Biz bosqichma-bosqich yangi grafik quramiz, unga ishlov beriladigan yo'llarning tugunlari va qirralarini birlashtiramiz.
  
• 
  Agar yangi grafikaga qo'shilgan tugunlar soni 5000 dan oshsa, biz qolgan barcha ishlov berilmagan yo'llarni olib tashlaymiz.
  
• 
  Agar grafik 100 dan ortiq ajratilgan subgraflarni o'z ichiga olsa , biz hali qayta ishlanmagan barcha qolgan yo'llarni o'chirib tashlaymiz. Ajratilgan subgraf - bu chekkalar (yoki qirralarning ketma-ketligi) bilan bir-biriga bog'langan (to'g'ridan-to'g'ri yoki bilvosita) tugunlarni o'z ichiga olgan va boshqa ajratilgan subgrafning biron bir tuguniga ulanmagan pastki grafik.
  
• 
  Ushbu jarayonning natijasi bir yoki bir nechta ajratilgan subgraflarga ega bo'lgan grafik bo'lib, har bir subgraf bitta uchdan-uchgacha yo'lni yoki bir nechta o'zaro bog'langan yoki birlashtirilgan uchdan-uch yo'llarni ifodalaydi.
  
• 
  Har bir ajratilgan subgrafga ball beriladi, bu uning tarkibidagi eng yaxshi oxirigacha yo'lning ballidir.
  
• 
  Ajratilgan subgraflar saralanadi va 2-bosqichga kirish sifatida taklif etiladi.
  

1-bosqichda yaratilgan grafiklar topologiyasining murakkabligi ushbu grafiklarni 2-bosqichda qanday samarali qayta ishlash mumkinligiga katta ta'sir ko'rsatadi. Turli darajadagi murakkablikdagi grafiklarning rasmlari Ilovada keltirilgan. Biz bir-biridan oxirigacha bo'lgan aniq yo'llar emas, balki subgraflar bilan shug'ullanayotganimiz 2-bosqichda ko'rib chiqilgan bir qator muammolarni keltirib chiqaradi.