1-Amaliy mashg’ulot Mavzu: Klassik shifrlar. Sezar va Vijener algoritmi

1-Amaliy mashg’ulot

Mavzu: Klassik shifrlar. Sezar va Vijener algoritmi

Ishdan maqsad: Shifrlash algoritmlari bilan tanishish, sezar va Vijener algoritmlari haqida ma’lumotga ega bo’lish.

Nazariy qism

Klassik maxfiy kriptotizimlarga siljitish shifrini ham olishimiz mumkin. Siljitish shifri ikki turga bo’linadi. Ular oddiy va murakkab siljitish shifrlaridir. Oddiy siljitish shifrida alfavit bo’yicha siljigan harflar bilan shifrlanayotgan matn harflari alfavitga mos ravishda almashtirish orqali shifrlash amalga oshiriladi. Bir turli almashtirish shifri oddiy siljitish shifrining bir qismi hisoblanadi.

Oddiy almashtirishli shifr. Almashtirish usullari sifatida quyidagi usullarni keltirish mumkin: Sezar usuli, Affin tizimidagi Sezar usuli, tayanch so’zli Sezar usuli va boshqalar.

Sezar shifri oddiy siljitish shifrining bir qismi hisoblanadi. Bu shifrni rimlik imperator Gole Yuliy Sezar o’ylab topgan. SHifrlashda matnning har bir harfi boshqa harf bilan quyidagi qoida asosida almashtiriladi. Harflarni almashtirishda kelayotgan yozuv harflarini K-ga siljitib almashtiriladi. Bu erda K–butun son hisoblanib uni quyidagicha ifodalash mumkin. K=K (modm), m -alfavit soni. Yuliy Sezar bevosita k = 3 bo’lganda ushbu usuldan foylangan.

Sezar usulining kamchiligi bu bir xil harflarning o’z navbatida, bir xil harflarga almashishidir.

Masalan, matn sifatida T₀=KOMPUTER so’zini va K=3 deb oladigan bo’lsak Sezar usuli natijasida quyidagi shifrlangan yozuv hosil bo’ladi:

T₁ = NRPSXWHU.

Murakkab almashtirishli shifr. Murakkab almashtirishli shifr ko’p alfavitli bo’lib, shifrlashda keluvchi matnning har bir harfi o’zining oddiy almashtirish shifri kabi shifrlanadi. Ko’p alfavitli almashtirishda alfavit ketma-ketligi va tsiklidan foydalaniladi.

A-alfavitli almashtirishda kiruvchi axborotning X₀-harfi V₀-alfavitning Y₀-harfi bilan almashtiriladi, X₁-harfi esa V₁-alfavitning Y₁-harfi bilan almashtiriladi, X_r-1-harfi V_r-1-alfavitning Y_r-1-harfi bilan almashtiriladi va hokazo.

Ko’p alfavitli almashtirishning r=4 bo’lgan hol uchun umumiy ko’rinishi quyidagi jadvalda keltirilgan.

Kiruvchi harflar	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9
Alfavit almashtirish	B0	B1	B2	B3	B0	B1	B2	B3	B0	B1

Bu usul bilan shifrlangan matnni ochishda yetarli qiyinchiliklar tug’diradi, endi k-kalit bir-necha marotaba o’zgaradi. Gamma shifri ixtiyoriy ko’rinishda xar bir shifrlanayotgan bo’lakni o’zgartiradi. Bunda dushman har bir matn bo’lagini qanday qilib ochishni bunday shifrlashda himoyalanganlik darajasi foydalaniyotgan V_j-alfavit ketma-ketligiga bog’liqdir. Ko’p alfavitli almashtirish shifrini Leon Batist Al’bert kriptografiyaga kiritdi.

Vijenerning shifrlash tizimi. Birinchi bo’lib Vijener tizimi 1586-yilda chop etilgan va u ko’p alfavitli tizimga nisbatan yuqoriroq o’rinda turadi. Blez Vijener o’zini XVI asrning fransuz diplomati deb hisoblaydi. U kriptografiya tizimiga, ya’ni uning rivojlanishiga o’z hissasini qo’shgan. Vijener tizimi Sezar shifrlash tizimiga qaraganda mukammalroq hisoblanib, unda kalit harfidan harfga almashtiriladi. Bunday ko’p alfavitli almashtirish shifrini shifrlash jadvali orqali ifodalash mumkin. Quyidagi jadvalda Vijenerning ingliz alfaviti uchun mos keluvchi jadval ko’rsatilgan.


Bu jadvaldan matnni shifrlash va uni ochish uchun ishlatiladi. Jadvalning ikkita kirishi bo’lib:

• 
  Yuqori qatordagi xarflardan kiruvchi ochiq yozuv uchun foydalaniladi.
  
• 
  Chap ustundan esa kalit harflaridan foydaniladi.
  

Misol uchun kalit ketma-ketligini r-deb olaylik, u holda kalit r-alfavitli r-satrdan iborat bo’ladi.

π=(π₀, π₁,…,π_r-1);

Vijenerning shifrlash tizimida ochiq matn x=(x₀,x₁,…,x_n-1) va shifrlangann matn y=(y₀,y₁,…,y_n-1) ko’rinishga ega. π=(π₀, π₁,…,π_r-1) kalit yordamida quyidagicha munosabatda bo’ladi.

x=(x₀,x₁,…,x_n-1) y= (y₀,y₁,…,y_n-1);

(y₀,y₁,…,y_n-1)=(π₀(x₀),π₁(x₁),…,π_n-1(x_n-1));

Yuqoridagi ifodadan ma’lumki Vijener jadvali orqali shifrlashda matnning (axborotning) har bir harfiga mos keluvchi kalitning har bir harfi orqali ularning ustun va satrlari kesishmasiga mos keluvchi harflar olinadi. Agar o’zbek – kiril alfaviti ishlatilsa, Vijener matritsasi [36x36] o’lchamga ega bo’ladi. Masalan, Agar kalit sifatida so’zi tanlangan bo’lsa, shifrlash matritsasi beshta qatordan iborat bo’ladi.

ABVGDEYoJZIYKLMNOPRSTUFXTSCHSHЬ’EYuYaO’QG’H_ KLMNOPRSTUFXTSCHSHЬ’EYuYaO’QG’H_ABVGDEYoJZIY O’QG’H_ABVGDEYoJZIYKLMNOPRSTUFXTSCHSHЬ’EYuYa ZIYKLMNOPRSTUFXTSCHSHЬ’EYuYaO’QG’H_ABVGDEYoJ ABVGDEYoJZIYKLMNOPRSTUFXTSCHSHЬ’EYuYaO’QG’H_

Misol. K= kaliti yordamida T= dastlabki matni shifrlansin.

Ochiq matn	B	A	Y	R	A	M	_	K	U	N	I
Kalit	K	O’	Z	A	K	O’	Z	A	K	O’	Z
SHifrlangan matn	L	O’	S	R	K	Z	J	K	O’	I	R

T₁=LO’SR_KZJK_O’IR_*

Vernamning shifrlash usuli. Vernamning shifrlash tizimi modul qiymati m=2 bo’lgan Vijener shifrlash tizimining bir qismi hisoblanib, 1926-yilda bu usulning aniq ko’rinishi ishlab chiqiladi.Gilbertom Vernam AT&SSHA firmasi homiyligi ostida kiruvchi matn sifatida ikkilik sanoq sistemasidan foydalandi. SHifrlashda birinchi ingliz alfavitidagi(A,B...Z) matnning har bir harfi 5-bit bo’lakli ((b₀,b₁…b₄) Bado raqami bilan kodlanadi. Ixtiyoriy ketma-ketlikdagi ikkilik kalitlar k₀, k₁, k₂, avval kitobsimon lentaga yoziladi. Quyidagi rasmda uzatilayotgan axborotni Vernam usuli orqali shifrlash ko’rsatilgan.

Kiruvchi matn

Shifrlashda X-kiruvchi matn ikkilik ko’rinishiga o’tkaziladi va ikkilik modul ostida ikkilik ketma-ketlikdagi k-kalit bilan shifrlash amalga oshiriladi. U shifrlangan yozuv:


Shifrni ochishda yozuvdagi har bir ikkilik modul ostidagi belgilar k-kalit ketma-ketligi bilan tuziladi.


k

k=x;

k=x

y

Vernam ishlab chiqqan bu tizimni aylanali lenta yordamida tekshirgan, uzatgich va qabul qilgichlarni ko’rinishda bir xil yoki shunga o’xshagan kalit ketma-ketligidan foydalangan. Vernam shifrlash tizimining kamchiligi uzatuvchi orqali qabul qilish tomoniga kalit ketma-ketligini qanday uzatish edi. CHunki dushman kalitni olsa, u yuborgan shifrlangan matnni bemalol ochib o’qiy oladi. SHuning uchun xam Vernamning shifrlash tizimi etarli emasligi sababli buni hal kilish uchun shifrlashni gammalashtirish usuliga o’tilgan.

Gammalash usuli bilan shifrlash. Gammalashtirish ham kriptografik akslantirishda keng qo’llaniladi. Aslida gammalashtirish, Vijener shifri hamda cheksiz kalitdan foydalanish bir-biriga juda o’xshash.

Gammalashtirishda tasodifiy sonlar generatori yordamida gamma generatsiya qilinadi va u ochiq matnga qayta tiklanadigan usulda (masalan, 2 ga modulь bo’yicha qo’shish) qo’shiladi.

Ma’lumotlarni deshifrlash jarayoni shifr gammasini ma’lum kalit yordamida qaytadan generatsiya qilish va bu gammani shifrlangan ma’lumotdan olib tashlash bilan amalga oshiriladi.

Agar shifr gammasida takrorlanuvchi bitli ketma-ketlik mavjud bo’lmasa shifrlangan matnni ochish juda qiyin. Umuman olganda, shifr gammasi har bir shifrlanadigan so’z uchun tasodifiy ravishda o’zgarishi kerak. Agar gamma uzunligi butun shifrlanadigan matn uzunligidan oshib ketsa va ochiq matnning hech qanday qismi ma’lum bo’lmasa, u holda shifrni faqat mumkin bo’lgan kalitlarni to’la ko’rib chiqish bilan ochish mumkin. Bu holda kriptobardoshlilik kalit uzunligi bilan o’lchanadi.

Agar raqibga ochiq matnning bo’lagi va unga mos keluvchi shifrogrammasi ma’lum bo’lsa gammalashtirish usuli kuchsiz bo’lib qoladi. Modulь bo’yicha oddiy ayirish orqali tasodifiy sonlar kema-ketligi qismi olinadi va bu qism bo’yicha butun ketma-ketlik tiklanadi. Raqiblar buni ochiq matnning tashkil etuvchilari asosida taxmin bilan topishlari ham mumkin. Quyida amaliyotda qo’llash mumkin bo’lgan gamma generatsiyasining keng tarqalgan usullari qaraladi. Gamma shifri quyidagi ko’rinishdagi ketma-ketlikda olinadi.

G⁽ⁱ⁾sh

SHifrlashni quyidagi ko’rinishda yozish mumkin.


Bu yerda:

T⁽ⁱ⁾sh i-shifrlangan matn;

G⁽ⁱ⁾sh i-gamma shifri bo’ladi;

T⁽ⁱ⁾0 i-ochiq matn bo’ladi;

M-(ochiq) matnni sifat darajasi.

SHifrni ochishda qayta gamma shifridan foydalaniladi:

Bu usul bilan shifrlangan matnni ochishda yetarli qiyinchiliklar tug’diradi, endi k-kalit bir-necha marotaba o’zgaradi. Gamma shifri ixtiyoriy ko’rinishda xar bir shifrlanayotgan bo’lakni o’zgartiradi. Bunda dushman xar bir matn bo’lagini qanday qilib ochishni bilmaydi. Chunki dushman har bir turdagi kalitni topishi uchun ancha vaqt ketadi. Bu holatda shifrlangan matn bardoshliligi ko’pligiga bog’liq bo’ladi.