Kasiski tekshiruvi - Kasiski examination - Wikipedia

Yilda kriptanaliz, Kasiski tekshiruvi (shuningdek, Kasiskining sinovi yoki Kasiskiy usuli) hujum qilish usuli hisoblanadi polyalphabetic almashtirish shifrlari kabi Vigenère shifri.[1][2] Bu birinchi tomonidan nashr etilgan Fridrix Kasiski 1863 yilda,[3] ammo mustaqil ravishda kashf etilgan ko'rinadi Charlz Babbig 1846 yildayoq.[4][5]

U qanday ishlaydi

Polyalphabetic yilda almashtirish shifrlari bu erda almashtirish alifbosi a yordamida tanlanadi kalit so'z, Kasiski tekshiruvi kriptanalizatorga kalit so'zning uzunligini aniqlashga imkon beradi. Kalit so'zning uzunligi aniqlangandan so'ng, kriptanalizator shifrlangan matnni bir qatorga qo'shadi n ustunlar, qaerda n - bu kalit so'zning uzunligi. Keyin har bir ustunni a-ning shifrlangan matni sifatida ko'rib chiqish mumkin monoalfabetik almashtirish shifri. Shunday qilib, har bir ustunga hujum qilish mumkin chastota tahlili.[6] Xuddi shunday, qaerda a rotor oqim shifri mashina ishlatilgan, bu usul alohida rotorlar uzunligini ayirishga imkon berishi mumkin.

Kasiski imtihonida takrorlanadigan belgilar qatorini qidirishni o'z ichiga oladi shifrlangan matn. Tekshiruv muvaffaqiyatli o'tishi uchun iplar uchta belgidan iborat bo'lishi kerak. So'ngra, satrlarning ketma-ket paydo bo'lishi orasidagi masofa, kalit so'z uzunligining ko'paytmasi bo'lishi mumkin. Shunday qilib, takrorlanadigan satrlarni topish kalit so'zning mumkin bo'lgan uzunliklarini toraytiradi, chunki biz olishimiz mumkin eng katta umumiy bo'luvchi barcha masofalarning.

Ushbu testning bajarilishining sababi shundaki, agar takrorlangan satr Oddiy matn, va mos keladigan belgilar orasidagi masofa kalit so'z uzunligining ko'paytmasi bo'lib, kalit so'z harflari satrning har ikkala paydo bo'lishi bilan bir xilda joylashgan bo'ladi. Masalan, ochiq matnni ko'rib chiqing:

kripto kriptografiya uchun qisqa.

"kripto"bu takrorlangan satr va hodisalar orasidagi masofa 20 ta belgidan iborat. Agar biz oddiy matnni 6 ta belgidan iborat kalit so'z bilan tekislasak"abcdef"(6 20 ga bo'linmaydi):

abcdefabcdefabcdefabcdefabcdefabckripto qisqa kriptografiya.

birinchi instansiyasi "kripto"qatorlar bilan"abcdef"va ikkinchi instansiya" bilan "cdefab". Ikki misol turli xil shifrlangan matnlarga shifrlanadi va Kasiski imtihonida hech narsa aniqlanmaydi. Ammo 5 belgidan iborat kalit so'z bilan"abcde"(5 20 ga bo'linadi):

abcdeabcdeabcdeabcdeabcdeabcdeabckripto qisqa kriptografiya.

ikkala voqea "kripto"bilan saf tortish"abcdea"Ikkala misol bir xil shifrlangan matnga shifrlanadi va Kasiski tekshiruvi samarali bo'ladi.

Ipga asoslangan hujum

Kasiski imtihonidan foydalanishning qiyinligi takrorlangan satrlarni topishda yotadi. Bu qo'lda bajarish juda qiyin vazifa, ammo kompyuterlar buni ancha osonlashtirishi mumkin. Biroq, hali ham ehtiyotkorlik talab etiladi, chunki ba'zi bir takrorlangan satrlar tasodif bo'lishi mumkin, shuning uchun ba'zi takrorlanadigan masofalar chalg'itishi mumkin. To'g'ri uzunlikni topish uchun kriptanalizator tasodiflarni istisno qilishi kerak. Keyin, albatta, natijada monoalfabetik shifrlangan matnlar kriptoanaliz qilinishi kerak.

  1. Kriptanalizator takrorlangan harflar guruhlarini qidiradi va har bir takrorlangan guruh boshlari orasidagi harflar sonini hisoblaydi. Masalan, agar shifrlangan matn bo'lsa FGXTHJAQWNFGXQ, orasidagi masofa FGX guruhlar 10. Tahlilchi matndagi barcha takrorlangan guruhlar uchun masofalarni qayd etadi.
  2. Keyingi tahlilchi omillar bu raqamlarning har biri. Agar ushbu faktoringlarning ko'pchiligida biron bir raqam takrorlansa, ehtimol bu kalit so'zning uzunligi bo'lishi mumkin. Buning sababi shundaki, takroriy guruhlar shunchaki tasodifga qaraganda bir xil harflar yordamida bir xil harflar bilan shifrlanganda paydo bo'ladi; bu, ayniqsa, uzun mos keladigan simlar uchun to'g'ri keladi. Kalit harflar kalit uzunligining ko'paytmalarida takrorlanadi, shuning uchun 1-qadamda ko'rsatilgan masofalarning aksariyati kalit uzunligining ko'paytmalari bo'lishi mumkin. Odatda umumiy omil aniq ko'rinadi.
  3. Kalit so'zning uzunligi ma'lum bo'lgach, Babrij va Kasiskiyning quyidagi kuzatuvi o'ynaydi. Agar kalit so'z bo'lsa N uzun harflar, keyin har biri Nth harfi kalit matnning xuddi shu harfi yordamida shifrlangan bo'lishi kerak. Har bir guruhlash Nth harfi birgalikda, tahlilchiga ega N har biri bitta alfavit o'rnini bosuvchi yordamida shifrlangan "xabarlar" va keyinchalik har bir qismga hujum qilish mumkin chastota tahlili.
  4. Hal qilingan xabar yordamida tahlilchi kalit so'z nima ekanligini tezda aniqlay oladi. Yoki qismlarni echish jarayonida tahlilchi xabarni buzishda yordam berish uchun kalit so'z haqidagi taxminlardan foydalanishi mumkin.
  5. Interaktiv qiluvchi kalit so'zni bilgandan so'ng, ushbu bilim yordamida shu kalitdan foydalanadigan boshqa xabarlarni o'qish uchun foydalanish mumkin.

Superpozitsiya

Vigenère shifrini hal qilish uchun Kasiski aslida "superimpozitsiya" dan foydalangan. U yuqoridagi kabi kalit uzunligini topishdan boshladi. So'ngra u xabarning bir nechta nusxasini oldi va har biriga kalit uzunligidan chapga siljigan holda bir-birining ustiga qo'ydi. Keyin Kasiski har birini kuzatdi ustun bitta alifbo bilan shifrlangan harflardan iborat edi. Uning usuli yuqorida tavsiflangan usulga teng edi, lekin tasavvur qilish osonroq.

Zamonaviy polifalitik shifrlarga qarshi hujumlar asosan yuqorida tavsiflangan bilan bir xil, yaxshilanishi bilan tasodifni hisoblash. Takrorlanadigan guruhlarni qidirish o'rniga, zamonaviy tahlilchi xabarning ikki nusxasini olib, boshqasining ustiga yotar edi.

Zamonaviy tahlilchilar kompyuterlardan foydalanadilar, ammo bu tavsif kompyuter algoritmlari amalga oshiradigan printsipni aks ettiradi.

Umumlashtirilgan usul:

  1. Tahlilchi pastki xabarni bitta harfni chapga, so'ngra yana bitta harfni chapga va boshqalarni o'zgartiradi, har safar butun xabarni ko'rib chiqib, yuqoridagi va pastki xabarda bir xil harf paydo bo'lishini hisoblaydi.
  2. "Tasodiflar" soni pastki xabarni kalit uzunligining ko'paytmasi bilan almashtirganda keskin o'sib boradi, chunki u holda qo'shni harflar bir xil alfavitdan foydalangan holda bir xil tilda joylashgan.
  3. Kalit uzunligini topib, kriptanaliz yuqorida aytib o'tilganidek davom etadi chastota tahlili.

Adabiyotlar

  1. ^ Rodriges-Klark, Doniyor, Kasiski tahlili: kodni buzish, olingan 30 noyabr 2014
  2. ^ R. Morelli, R. Morelli, Tarixiy kriptografiya: Vigenere shifri, Trinity kolleji Hartford, Konnektikut, olingan 4 iyun 2015
  3. ^ Kasiski, F. W. 1863. Die Geheimschriften und die Dechiffrir-Kunst. Berlin: E. S. Mittler und Sohn
  4. ^ Franksen, O. I. 1985 janob Babbining sirlari: shifr haqidagi ertak - va APL. Prentice Hall
  5. ^ Singx, Simon (1999), Kodlar kitobi: Qadimgi Misrdan kvant kriptografiyasiga qadar maxfiylik fani, London: To'rtinchi hokimiyat, p. 78, ISBN  1-85702-879-1
  6. ^ Kasiski usuli, Michigan Texnologik Universiteti, olingan 1 iyun 2015