Kriptografik usullar

Amaliy mashg’ulot № 9
Mavzu:Ryukzak algoritmi yordamida shifrlash.
1. Ryukzak masalasi qo’yilishi. Ruykzak masalasi mohiyati quyidagicha: Har xil m₁, m₂, m₃,...,m_n og’irlikdagi n ta obyekt(jism, modda, narsa ) bor. Ularni ichidan bir nechtasini tanlab ryukzakka solamiz. Ryukzakka solingan obyektlar umumiy og’irligi oldindan aniqlangan S ga teng. Agar S mavjud bo’lsa, u ryukzak masalasini yechimi deyiladi.
Masalani matematik formula orqali quyidagich ifodalaymiz:
S = b₁*m₁+ b₂*m₂+ b₁*m₃+...+ b_n *m_n , bu yerda, b_i qiymati 1 ga teng, agarda m_i obyekt ryukzakka solingan bo’lsa, o ga teng bo’ladi, agarda u ryukzakka solinmagan bo’lsa.
1-Misol. Obyekt og’irliklari 1,5,6,11,14 va 20 ga teng bo’lsin. Agar ruyzak sig’imi 22 ga teng bo’lsa, unga o’g’irliklari 5,6 va 11 ga teng uchta obyektni solish mumkin. Lekin ryukzak sig’imi 24 teng bo’lsa, u holda umumiy o’girliklari 24 ga teng obyektlar to’plami mavjud emas.

	1-variant						2-variant						3-variant
Ochiq matn	1	1	1	0	0	1	0	1	0	1	1	0	0	1	1	0	0	0
Ryukzak	1	5	6	11	14	20	1	5	6	11	14	20	1	5	6	11	14	20
Shifrlangan matn	1+5+6+20=32						5+11+14=30						5+6=11

1-jadval
Jadvaldan ko’rinib turibdiki, obyektlar soni qancha ko’p bo’lsa, variantlar soni shuncha ko’p bo’ladi.
Ta`rif-1. Ryukzak vektori deb n (n  3) ta tartiblangan natural sonlardan tashkil topgan A = (a<sub>1</sub>,...,a<sub>n</sub>) vektorga aytiladi.
Ta`rif-2. Ryukzak masalasining boshlang’ich ma`lumotlari deb (A, ) juftlikka aytiladi. Bu erda A - ryukzak vektori,  - natural son. (A, ) ma`lumotlar uchun ryukzak masalasining yechimi deb A ning shunday qism to`plamiga aytiladiki, uning elementlari yig’indisi  ga teng bo`ladi. Bu yig’indida A ning har bir elementi faqat bir marta ishtirok etadi.
A ryukzak vektoridan faqat ikkilik sanoq sistemasidagi sonlardan tashkil topgan S matn blogini shifrlash uchun foydalaniladi. Unda S ning bir soniga A vektorning mos o`rinlarida turgan elementlari yig’indisi olinadi. Agar bu yig’indini  bilan belgilasak, ryukzak masalasi A dan foydalanib  ni, yoki  dan foydalanib A topish masalasiga keladi.
Misol-2. n=10 bo`lsin. Quyidagi tez o`suvchan vektorni ko`raylik:
A = (103, 107, 211, 430, 863, 1718, 3449, 6907, 13807, 27610) .
A ning komponentalari umumiy yig’indisi S=103+107+211+430+863+1718+3449+6907+ +13807+27610=55205 dan 2 birlikka katta bo`lgan m=55207 modulini olaylik. Shuningdek, t=25236 ko`paytuvchini shunday tanlaymizki, (t, m)=1 bo’lsin. Haqiqatdan ham, 1061 * 25236 - 1 = 485 * 55207. Bu ifodadan u = 1061 .
Kuchli modul bo`yicha ko`paytirish natijasida quyidagi vektorga ega bo`lamiz: t*a<sub>i</sub> = b<sub>i</sub> +c<sub>i</sub> *m, bu yerda i=1,2,..10. B=(4579, 50316, 24924, 30908, 27110,17953, 32732,16553, 22075, 53620) .
Masalan,
25236  103 = 4579 + 47  55207 va 1061  4579 = 103 + 88  55207 ,
25236  1718 = 17953 + 785  55207 va 1061  17953 = 1718 + 345  55207 ,
2523627610 = 53620 + 1262055207 va 1061  53620 = 27610+103055207.
B vektor shifrlashning ochiq kaliti hisoblanadi. A, t, u va m lar esa maxfiy kalitni tashkil qiladi. Albatta, m va t larni bilgan kishi qolgan miqdorlarni ham hisoblab topishi mumkin.
Ochiq B kalitdan foydalanib, “BITIRUV MALAKAVIY ISHI HIMOYASI” matnini shifrlaymiz. Buning uchun matnni raqamlar yordamida kodlab olamiz. Unda “bo`sh joy” belgisi - 0, qolgan harflar esa lotin alifbesida turgan o`rniga qarab, 1-26 bo`lgan qiymatlarni oladi. Raqamli kodlarni ikkilik sanoq sistemasida ifodalaymiz. Bunda 1-misol uchun yozilgan jadvaldan foydalanamiz.
B vektor uzunligi 10 ga teng bo`lgan ikkitalik bloklarni shifrlashga mo`ljallangani uchun biz matnni ikkitadan harfli bloklarga ajratamiz. Quyidagi jadvalda ana shu bloklar, ularning ikkilik sanoq sistemaisdagi ifodasi va blokning 10 lik sanoq sistemasidagi shifri keltirilgan.

BI	00010 01001	117260	Y	11001 00000	82005
TI	10100 01001	115855	IS	01001 10011	171074
RU	10010 10101	123613	HI	01000 01001	136668
V	10110 00000	60411	H	00000 01000	32732
MA	01101 00001	155970	IM	01001 01101	180331
LA	01100 00001	128860	OY	01111 11001	237563
KA	01011 00001	161954	AS	00001 10011	120758
VI	10101 01001	142965	I	01001 00000	77426

2-jadval
B vektor elementlari soni 10 ta bo’lgani uchun matn 2 harf birgalikda shifrlanadi. Agar B vektor elementlari soni 15 ta bo’lsa, matn 3 harf birgalikda shifrlanadi.
Bizning misolda, B vektor elementlari soni 10 ta bo’lgani uchun matn 2 harf birgalikda shifrlanadi. 2-jadval birinchi ustunida harflar juftligi, ikkinchi ustunida juftlikdagi har bir harfni 1-jadvalga mos 5 ta 0 va 1 bilan almashtiramiz. Uchinchi ustun esa, ikkinchi ustundagi mos 0 va 1 lar ketma ketligi va B vektor elementlari qiymatidan foydalanib hisoblaymiz. 3- ustunda berilgan matnni shifri hosil qilinadi.
Masalan, BI→00010 01001 → 0*b₁+0*b₂+0*b₃+1*b₄+ 0 *b₅+ 0 *b₆+ 1 *b₇+ 0 *b₈+ 0 *b₉+ 1 *b₁₀ =1*30908+1*32732+1*53620= 117260
Endi, shifrni ochish masalasini ko’rib chiqamiz. Buning uchun m=55207 va u=1061 lardan foydalanamiz. Birinchi sonni, ya`ni 117260 ni quyidagicha yozib olamiz: 1061 * 117260 = 2253 * 55207 + 31489 . Endi ryukzak masalasini (A, 31489) boshlang’ich ma`lumotlar uchun yechamiz. 3-jadvalni A verktorning komponentalari ustuni A vector elementlari kamayish tartibida to’ldiriladi. Qaralayotgan son ustuni birinchi satriga 31489 kiritiladi. So’ngra, bu son shu satrning A verktorning komponentalari ustunidagi 1-son 27610 bilan taqqoslanadi (31489>27610). Agar u A ning qaralayotgan komponentasidan kichik bo`lmasa, Harflar blogi kodi ustuniga mos 1-satriga 1 ni yozamiz. Endi u sonni A verktorning komponentalari ustunidagi 1-sondan ayiramiz (31489-27610=3879). Ayirma natijasini Qaralayotgan son ustuni ikkinchi satriga kiritamiz. Masalan, Qaralayotgan son ustuni 2-satridagi 3879 soni A verktorning komponentalari ustunidagi 2-satridagi 13807 dan kichik bo’lgani uchun Harflar blogi kodi ustuniga 2-satriga 0 kiritildi va A verktorning komponentalari ustunidagi 3-satriga undan yuqori satrda turgan(3879) sonni qayta kiritamiz. Ushbu amallarning natijasida quyidagi jadval hosil bo’ladi.