Mavzu: Bitta almashtirishga asoslangan shifrlarni tahlil qilish

2-amaliy ish
Mavzu: Bitta almashtirishga asoslangan shifrlarni tahlil qilish
Ishning maqsadi: bitta va ko'p ma'noli ko'nikmalar, almashtirish, almashtirish bo'yicha nazariy va amaliy bilimlarni shakllantirish.
Nazariy qism
Alifbo-ma'lumotni kodlash uchun ishlatiladigan belgilarning to'liq to'plami.
Matn (xabar, ochiq ma'lumot) - alifbo belgilarining tartiblangan ketma-ketligi.
Shifrlash-asl matnni (shuningdek, oddiy matn deb ham ataladi) shifrlangan matnga aylantirish jarayoni.
Shifrni ochish-shifrlashning teskari jarayoni. Kalit asosida shifrlangan matn asl nusxaga aylantiriladi.
Kodlash-bu ma'lumotni bir tildan boshqasiga tarjima qilish (boshqa belgilar tizimida, boshqa alifboda yozish). Bunday holda, odatda kodlash-bu ma'lumotni "inson" tilidan rasmiy tilga, masalan, ikkilik kodga tarjima qilish va dekodlash-teskari o'tish.
Kalit-bu kriptografik algoritm tomonidan ishlatiladigan maxfiy ma'lumotlar xabarlarni shifrlash va parolini hal qilish.
Quyidagi" klassik " shifrlash algoritmlari mavjud:
- almashtirish(oddiy-bitta alifbo, ko'p alfavitli bitta ipli, ko'p alfavitli ko'p ipli);
- o'zgartirish (oddiy, murakkab);
- gamming (qisqa, uzun yoki cheksiz niqob bilan aralashtirish).
Ushbu usullarning har birining kalitni bilmasdan shifrlashga chidamliligi statistik tahlil orqali shifrlanishi mumkin bo'lgan shifrlangan matnning minimal miqdori bo'lgan SK indikatori yordamida miqdoriy jihatdan tavsiflanadi. Klassik ma'lumotlarni shifrlash algoritmlari.
Qaysar Shifri
Shift shifri, qaysar kodi yoki qaysar shifri sifatida ham tanilgan, shifrlashning eng oson va eng keng tarqalgan usullaridan biridir.
Qaysar shifri-bu almashtirish shifrining bir turi bo'lib, unda ochiq matndagi har bir belgi alfavitda uning chap yoki o'ng tomonidagi doimiy pozitsiyalarda joylashgan belgi bilan almashtiriladi. Masalan, 3-smenali shifrda A g bilan almashtiriladi, B D bo'ladi va hokazo.
Matematik model
Agar alfavitning har bir belgisini uning seriya raqami bilan taqqoslasak (0 bilan raqamlangan), unda shifrlash va shifrni ochish modulli arifmetik formulalar bilan ifodalanishi mumkin:
y=(x+k) mod n
x=(y-k+n) mod n,
bu erda x-oddiy matn belgisi, y-shifrlangan matnning belgisi, n-alifbo kuchi (belgilar soni), k — kalit.
Matematika nuqtai nazaridan, Sezar shifri affin shifrining alohida holatidir.
Shifr Rim imperatori Gay Yuliy Tsezar sharafiga nomlangan bo'lib, u o'z generallari bilan maxfiy yozishmalar uchun foydalangan.
Kalit yordamida shifrlash k = 3. "E" harfi uchta harfni oldinga siljitadi va "Z"harfiga aylanadi. Uchta harf oldinga siljigan qattiq belgi "E" ga aylanadi va hokazo:
Asl alifbo: ABVGDEEJJIJKLMNOPRSTUFXTSCHSHCHYYEYYA
Shifrlangan: GDEEJZIJKLMNOPRSTUFHTSCHSCHSHCHYYYAYAABV
Manba matni:
Siz bu yumshoq frantsuz rulolarini ham iste'mol qilasiz, lekin choy iching.
Shifrlangan matn asl matnning har bir harfini tegishli shifrlangan alifbo harfi bilan almashtirish orqali olinadi:
Fezya yz zy ahlsh pvenlsh chugrshchkfnlsh dtsosn,JG yeutzm Kommersant.
Afin kriptosistemasi.
Sezar tizimining umumlashtirilishi affin kriptosistemasi hisoblanadi. U ikkita a va b raqamlari bilan belgilanadi, bu erda 0<=a, b<=n-1, n - avvalgidek, alifboning kuchi. A va n raqamlari o'zaro sodda bo'lishi kerak.
Tegishli almashtirishlar:
E=Aa,b(j)=(a j+b)(mod n)
D=A-1a,b(j)=(j-b+n)*a-1(mod n)
Multiplikativ teskari qidiruvni (a-1 deb belgilangan) Evklid algoritmi bo'yicha amalga oshiring. Shubhasiz, a \ u003d 1 da affin kriptosistemasi qaysar shifriga aylanadi. A va n ning o'zaro soddaligi displeyning biektivligi uchun zarurdir, aks holda turli xil belgilarni bittaga ko'rsatish va dekodlashning noaniqligi mumkin. Afin kriptosistema kalitlari soni ishlatiladigan alifboning kuchiga bog'liq. Rus tili alifbosi uchun b koeffitsienti 33 qiymatni olishi mumkin, a koeffitsienti faqat son bilan o'zaro oddiy qiymatlardir 33: 1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32. Jami 20 ta qiymat. Ruxsat etilgan b va a ning barcha mumkin bo'lgan birikmalari 33*20=660-1=659 kalit oralig'ini beradi (1 kalit olib tashlanadi, chunki a=1 va b=33 birikmasi alifboni o'ziga aylantiradi).
Sezar shifri va afin kriptosistemasi bir alfavitli kriptosistemalar sinfiga kiradi, ya'ni tanlangan kalit uchun asl oddiy matnning ba'zi harfi har doim shifr matnida bir xil harf bilan almashtiriladi. Shuning uchun bu shifrlarni chastota kriptanalizi usuli bilan ochish mumkin. Chastotani tahlil qilish shifrlangan matnning xususiyatidan foydalanadi, unda belgilarning paydo bo'lish chastotasi ochiq matnda tegishli belgilarning paydo bo'lish chastotasiga to'g'ri keladi. Agar tegishli til matnlarida turli xil belgilarning paydo bo'lish chastotalari notekis taqsimlanganligini hisobga olsak (masalan, rus tilidagi matnlarda "a" harfining nisbiy chastotasi 0,069 va "F" harflari 0,003), u holda shifr matnidagi harflarning nisbiy paydo bo'lish chastotasini hisoblab, biz eng ko'p uchraydigan belgi deb taxmin qilishimiz mumkin. shifr matnida tez-tez uchraydigan, tegishli tildagi matnlarda eng ko'p uchraydigan belgiga mos keladi va shu bilan qaysar shifri uchun k kalitini topadi. Afin kriptosistemaning a va b parametrlarini ochish uchun siz ikkita harfning yozishmalarini topishingiz kerak bo'ladi – shifr matnida eng ko'p uchraydigan va ikkinchi eng keng tarqalgan. Sezar shifrini kalit so'z bilan chastota tahlilining samaradorligi ko'p jihatdan ishlatiladigan kalit so'z birikmasining uzunligiga bog'liq, alifboning ruxsat etilgan aks ettirishlarining umumiy soni, yuqorida aytib o'tilganidek, n!.
Keling, Affin shifridan foydalanib, "master" so'zini shifrlashga va shifrlashga harakat qilaylik. Masalan, quyidagi kalitlardan foydalanamiz: a \ u003d 5, b \ u003d 7.
M harfi 12 raqamiga ega, keyin shifrlangan raqam (5*12+7) mod 26 = 15, bu p harfiga to'g'ri keladi
A harfi 0 raqamiga ega, keyin shifrlangan raqam (5*0+7) h harfiga mos keladigan mod 26 = 7
S harfi 18 raqamiga ega, keyin shifrlangan raqam (5*18+7) mod 26 = 19, bu t harfiga to'g'ri keladi
T harfi 19 raqamiga ega, keyin shifrlangan raqam (5*19+7) y harfiga mos keladigan mod 26 = 24
E harfi 4 raqamiga ega, keyin shifrlangan raqam (5*4+7) b harfiga mos keladigan mod 26 = 1
R harfi 17 raqamiga ega, keyin shifrlangan raqam (5*17+7) mod 26 = 14, bu o harfiga to'g'ri keladi
Shifrlash natijasida phtybo qatori paydo bo'ldi
Misol (phtybo)da olingan qatorni dekodlash
a*a-1 mod n = 1
Boshlash uchun siz topishingiz kerak . a * modul 26 birlik berishi kerak. Shunday qilib, 27, 53, 79, 105 va boshqalar natijalari bizga mos keladi.chunki a \ u003d 5,bizga 5 bilan tugaydigan raqam kerak. 105 mos keladi. 105/5=21, shuning uchun =21
Shunday qilib:
P harfi 15 raqamiga ega, keyin shifrlangan raqam 21 * (15-7) mod 26 = 12 bo'ladi, bu m harfiga to'g'ri keladi
H harfi 7 raqamiga ega, keyin shifrlangan raqam 21 * (7-7) mod 26 = 0 bo'ladi, bu a harfiga to'g'ri keladi
T harfi 19 raqamiga ega, keyin shifrlangan raqam 21 * (19-7) mod 26 = 18 bo'ladi, bu s harfiga to'g'ri keladi
Y harfi 24 raqamiga ega, keyin shifrlangan raqam 21 * (24-7) mod 26 = 19 bo'ladi, bu t harfiga to'g'ri keladi
B harfi 1 raqamiga ega, keyin shifrlangan raqam 21 * (1-7) mod 26 = 4 bo'ladi, bu e harfiga to'g'ri keladi
O harfi 14 raqamiga ega, keyin shifrlangan raqam 21 * (14-7) mod 26 = 17 bo'ladi, bu r harfiga to'g'ri keladi
Bu "master" bo'lib chiqdi - bizning boshlang'ich qatorimiz.
Bigram konversiyalari
Ochiq va shifrlangan matnlarning elementlari bigramlar deb nomlangan ikki harfli bloklardir. Bu shuni anglatadiki, ochiq matn ikki harfli segmentlarga bo'linadi. Agar oddiy matn toq sonli harflardan iborat bo'lsa, unda bigramlarning butun sonini olish uchun matnning oxiriga yana bir harf qo'shamiz, uni ma'nosini buzmaslik uchun tanlaymiz, masalan, agar u bizning alifbomizda bo'lsa, bo'sh joy qo'shamiz.
Har bir bigramga uning raqamli ekvivalenti qo'shimcha ravishda beriladi. Eng oddiy usul-uni p \ U003d xn + y shaklida olish, bu erda x-bigramning birinchi harfining raqamli ekvivalenti, y-bigramning ikkinchi harfining raqamli ekvivalenti, A N-alfavitdagi harflar soni, ya'ni. bigramni n bazasi bilan sanoq tizimidagi ikki xonali butun sonning yozuvi sifatida ko'rib chiqing. n-alfavitdagi bigramlar va n dan kichik bo'lgan barcha manfiy bo'lmagan tamsayılar to'plami. yuqorida biz ushbu protseduraning N2 da alohida holatini ko'rib chiqdik.
Keyingi qadam shifrlashni o'zgartirishni tanlashdir, ya'ni. butun sonlarni almashtirish {0,1,2,..., N^2-1}. Afinaviy o'zgarishlar eng oddiy shifrlovchi o'zgarishlarga misol bo'la oladi: shifrlashda P n^2 dan kichik va≡aP + b (mod N^2) ga nisbatan qoniqtiradigan manfiy bo'lmagan butun songa aylanadi. Bu erda, avvalgidek, a raqami n bilan umumiy omillarga ega bo'lmasligi kerak (bu umumiy omillarning yo'qligini va N^2 bilan), shuning uchun teskari transformatsiya mavjud bo'lib, bu shifrni ochish usulini ko'rsatadi.
P=a^(-1) (C-b) mod n^2.
"Crypto" ochiq matni" { 2 17 24 15 19 14 } "cr { 2 17 }"
P=am + b, m = 26 bu erda a=2, b=17. P=2*26+17=69.
Bunday holda, a=157, b=580, N^2=676
C a aP + b (mod n^2) = 157*69+580 mod 676 = 11413mod676=597
597=22*26+25 22=w 25=z
M=crypto { 2 17 24 15 19 14 }
C { 22 25 6 23 21 22 } = { w z g x v w }
Parolni hal qilish
P=a^(-1) (C-b) mod n^2
a=157, b=580, N^2=26*26=676
P=〖157〗^(-1) (597-580) mod 676 = 521(597-580) mod 676 = 8857 mod 676 = 69
69=2*26+17 2=c 17=r