Namangan davlat universiteti fizika-matematika fakulteti amaliy matematika kafedrasi

n-talik A=(a₁,a₂, ,,, , a_n) vektor tez usuvchan deyiladi, agar ikkinchi elementdan boshlab, har bir element o`zidan avval kelgan elementlarning yig’indisidan katta bo`lsa, ya`ni
<sub> </sub>.
Barcha imkoniyatlarni ko’rib chiqishda A vektorni o’ngdan chapga qarab bir marta ko’rib chiqish yetarli. Berilgan k (ryukzak o’lchami) uchun biz dastlab k>a shartni tekshiramiz. Agar u o’rinli bo’lmasa, a<sub>p</sub> izlanayotgan yig’indiga kirmaydi, aks holda kiradi. Bu narsa qolgan barcha elementlarning k dan kichik yig’indini beradi.
<sub> </sub>
ni aniqlaymiz. Endu yuqoridagi jarayonni k<sub>1</sub> va a<sub>n-1</sub> uchun takrorlaymiz. Shunday qilib, biz a<sub>1</sub> gacha boriladi. Masalaning algoritmi ko‘rsatadiki, ihtiyoriy k soni uchun ryukzak masalasi A vector tez o’suvchan bo’lganda bittadan ko’p bo’lmagan yechinmi berishi mumkin.
Agar kriptosistema asosi sifatida tez o’suvchan A vektor olinsa, qayta shifrlash masalasi kriptoanalitik uchun ham, ma’lumotni qabul qiluvchi rasmiy tomon uchun ham nihoyatda osonlashadi. Buning oldini olish uchun biz A vektorni shunday “chayqatamizki”, natijaviy B vector tez o’suvchan bo’lmay, ryukzak haqidagi oddiy vektorga aylanadi. “Chayqatish” uchun biz modul bo’yicha ko’paytirish amalidan foydalanamiz.
Biri butun <sub> </sub> sonini tanlab olamiz. A vector tez o’suvchan bo’lani uchun m soni A dagi ementlardan kattaroq bo’ladi. Bu m bilan o’zaro tub bo’lgan boshqa t butun sonini olamiz. m va t sonlar modul va ko’paytuvchi bo’ladi. t ni bu usulda tanlash tt<sup>-1</sup>=1 shartni qanoatlantiruvchi butun t<sup>-1</sup> topilishini kafolatlaydi. Uni t ga teskari element deb ataladi. Teskari elementni t va m lar orqali osongina topish mumkin bo’ladi. .
Endi ta<sub>i</sub> (i=1, 2, …, n) ko’paytirishni bajaramiz va hosil bo’lgan sonlarni m modul bo’yicha keltiramiz. b<sub>i</sub> — ta<sub>i</sub> (i=1, 2, …, n) ni m modul bo’yicha eng kichik musbat qoldig’i hamda natijaviy vector B = (b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>) bo’lsin. Bu vektor shifrlash n-razryadli shifrlash kaliti bo’lib xizmat qiladi. Shifrlash algoritmi esa yuqorida keltirilgan.
t, t<sup>-1</sup> va m sonlari mahfiy saqlanadi. Kriptoanalitik oldida turgan vaziyatni tahlil qilishdan avval qaralayotgan misolga qaytaylik.
Biz yuqorida ko’rgan (endilikda B bilan belgilangan)
V = (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)
vector tez o’suvchan
A = (1, 3, 5, 11, 21, 44, 87, 175, 349, 701)
vektorni t = 1590 va t = 43 sonlarga modul bo’yicha ko’paytirish orqali hosil qilingan. Bu holatni batafsil ko’qib chiqamiz.
B ning dastlabki besh elementi A ning mos elementlarini 43 ga oddiy ko’paytirish yo’li bilan hosil qilingan. Ularni m modul bo’yicha keltirish shart emas. (Amalda dastlabki sonlarning kichik bo’lmasligi zarur. Qolgan elementlar quyidagi hisoblashlardan so’ng olingan:
4344=1892=1590+302
4387=3741=21590+561
43175=7525=41590+1165
43349=15007=91590+697
43701=30143=181590+1523
Shuni alohida ta’kidlash joizki, t va m lar o’zaro tub. Haqiqatdan ham,
4337=1591=1 (mod 1590)
Demak, t<sup>-1</sup>=37.
Endi rasmiy qabul qiluvchi uchun qayta shifrlahning oson yo’lini qidiramiz. Dastlab, A vector tez o’suvchan bo’lib, B vector undagi xar bir elementni t (mod m) ga ko’paytirib hosil qilingan vaziyatni ko’raylik. Rasmuy qabul qiluvchi t<sup>-1</sup> va m ni biladi. U A vektorni B ochiq kalitdan topa oladi. Shifrlangan matnning butun sondan iborat bo’lgan c' blogini olganidan so’ng, rasmuy qabul qiluvchi t<sup>-1</sup>c’ ni hisoblab, uning eng kichik musbat qoldig’i s (mod m) ni topadi. Qayta shifrlash vaqtida u A va c yordamida aniqlanadigan ryukzak masalasini osongina hal qiladi. Bu salaning yechimi n bitli yagona ketma-ketlikdan iborat bo’ladi. Shuningdek, u boshlang’ich ma’lumotning to’g’ri blogi bo’ladi, chunki B va c’ bilan aniqlanadigan ryukzakni yig’ishtirish masalasining ihtiyoriy p’ yechimi p ga teng bo’lishi kerak. Haqiqatdan ham,
<sub> </sub>
Shuni alohida ta’kidlash joizki, Ar' < t, chunki t > a<sub>1</sub> + a<sub>2</sub> +.. . + a<sub>p</sub>. Bu shuni anglatadiki, yuqoridagi tenglikni s = Ar' tenglama ko’rinishida qayta yozish mumkin, chunki A va s lar bilan aniqlanadigan masala bir nechta yechimga ega bo’la olmaydi va shuning uchun r' = r.
Demak, rasmiy qabul qiluvchi shiftrlangan
(2557, 3503, 2413, 1161, 2031, 2213)
matnni “qo’lda” qayta shifrlashi mumkin. t<sup>-1</sup>=37 ga ko’paytirib, birinchi sonni hosil qilinadi:
37  2557 = 94609 = 59  1590 + 799 = 799 (mod 1590)
37  3503 = 129611 = 81  1590 + 821 = 621 (mod 1590)
37  2413 = 89281 = 56  1590 + 241 = 241 (mod 1590)
37  1161 = 42957 = 27 1590 + 27 = 27 (mod 1590)
37  2031 = 75147 = 47  1590 + 417 = 417 (mod 1590)
37  2213 = 81881 = 51  1590 + 791 = 791 (mod 1590).
Shunday qilib, biz quyidagi oltiltikni hosil qildik:
(799, 621, 241, 27, 417,791) .
A = (1, 3, 5, 11, 21, 44, 87, 175, 349, 701) .
799 soni va tez o’suvchan A vector 10-razryadli 0001001001 ketma-ketlikni beradi. Haqiqatdan ham 799 > 701 bo’lgani uchun oxirgi bit 1 ga teng bo’lishi lozim. Endi A dagi sonlar 799-701 = 98 ayirma bilan solishtiriladi. O’ngdan chapga qarab 98 dan kichik son 87. Navbatdagi 98-87=11 ayirmadan kichik son 11. Yakunda 11-11 ayirmaga teng son 0 ga teng. Demak, 11, 87 va 701 larning A dagi o’rni mos ravishda 4, 7, va 10 ga, ya’ni 0001001001 teng..
Shunday qilib, 621,..., 791 sonlar keyingi beshta 10-razryadli ketma-ketliklarni beradi. Hosil qilingan barcha ketma-ketliklarni qayta kodlab, rasmiy qabul qiluvchi boshlang’ich matnga ega bo’ladi:
BITIRUV ISHI
Ryukzak haqidagi tez o’suvchan vektorga asoslangan kriptosistema oshiq kalitli shifrlash usullariga yorqin namuna bo’la oladi.
Biz endi ma`lumotlarni shifrlashning ryukzak usulining matematik apparatini ko`raylik.