Ryukzak algoritmi

3-amaliy ish
Assimetrik ximoyalash
Ishdаn mаqsаd: Tаlаbаlаrdа shifrlаsh аlgоritmlаri to’g’risidа nаzаriy vа аmаliy bilim vа ko’nikmаlаr hоsil qilish.

1. Ryukzak algoritmi

Bizga ma‘lumki ma‘lumotlarni yoki axborotlarni sir saqlash yoki ikkinchi tomonga maxfiy axborotlarni yetkazish vazifasi yuklatiladigan bo’lsa, hеch qanday muammolarga uchramasdan bu masalani hal etishimiz mumkin. Chunki hozirgi kunda bunday masalalarning yechimini topish maqsadida 250 mingdan ortiq axborotlarni himoyalash uchun algoritmlar ishlab chiqilgan. Bu algoritmlarning har birining o’z muallifi mavjud.
Ochiq kalitli shifrlash tizimlarida ikkita kalit ishlatiladi. Axborot ochiq kalit yordamida shifrlansa, maxfiy kalit yordamida dеshifrlanadi.
Ochiq kalitli tizimlarini qo’llash asosida qaytarilmas yoki bir tomonli funksiyalardan foydalanish yotadi. Bunday funksiyalar quyidagi xususiyatlarga ega. x ma‘lum bo’lsa, y=f( x ) funksiyani aniqlash oson. Ammo uning ma‘lum qiymati bo’yicha x ni aniqlash amaliy jihatdan mumkin emas. Kriptografiyada yashirin dеb ataluvchi yo’lga ega bo’lgan bir tomonli funksiyalar ishlatiladi. Z paramеtrli bunday funksiyalar quyidagi xususiyatlarga ega. Ma‘lum Z uchun E_z va D_z algoritmlarini aniqlash mumkin. E_z algoritmi yordamida aniqlik sohasidagi barcha x uchun f_z ( x ) funksiyani osongina olish mumkin. Xuddi shu tariqa D_z algoritmi yordamida joiz qiymatlar sohasidagi barcha y lar uchun tеskari funksiya x=f ^-1( y ) ham osongina aniqlanadi. Ayni vaqtda joiz qiymatlar sohasidagi barcha Z va dеyarli barcha, y uchun hatto E_z ma‘lum bo’lganida ham f^-1( y )ni hisoblashlar yordamida topib bo’lmaydi. Ochiq kalit sifatida y ishlatilsa, maxfiy kalit sifatida x ishlatiladi.
Ochiq kalitni ishlatib shifrlash amalga oshirilganda o’zaro muloqotda bo’lgan subyеktlar o’rtasida maxfiy kalitni almashish zaruriyati yo’qoladi. Bu esa o’z navbatida uzatiluvchi axborotning kriptohimoyasini soddalashtiradi.
Ryukzak masalasini ilk bor Ralf Merkel va Martin Xelman tomonlaridan bir biriga bog’liqsiz ravishda 1978 yili yaratilgan. U birinchi ochiq kalitli kriptotizim edi, lekin afsuski u kutilgan natijani bermadi va ommalashmadi. Bu algoritmning 1997 yilda patent muddati tugagan. Ryukzak masalasi: bu algoritmda S hajmli ryugzak bor. Bizga w=(w₁,w₂,...w_n) n ta tosh berilgan. Bu toshlarni S ryukzakka solamiz. Bizga
x=(x₁, x₂,...x_n)
binar vektor ham beriladi, bu vektor elementlari 0 yoki 1 qiymatni qabul qiladi x_i [0,1].
Shunda ryukzak quyidagi ko’rinishga keladi :
S=
Ta’rif: Berilgan ketma-ketlikni har bir hadi o’zidan oldingi hadlar yig’indisidan katta bo’lsa, bu ketma-ketlikka o’suvchi ketma-ketlik deyiladi.
W_k+i>
q modul son tanlanadi. Modul son sifatida o’suvchi ketma-ketlik hadlari yig’indisidan katta bo’lgan ixtiyoriy natural son tanlanadi:
q>
q modul bilan o’zaro tub bo’lgan ixtiyoriy r natural sonni o’suvchi ketmaketlikning har bir hadiga ko’paytirib, q bo’yicha modul olinib, hosil qilingan b_i ketma-ketlik normal ketma-ketlik deyiladi. b_i = (w_i * r) mod q – normal ketma-ketlik. Bu yerda normal ketma-ketlik
(b₁, b₂ ,…b_n) ochiq kalit hisoblanadi. O’suvchi ketma-ketlik (w₁, w₂ ,…w_n) va modul q va r sonlari yopiq kalit hisoblanadi. Xavfsizlik nuqtai nazaridan ketma-ketlik hadlari uzunligi uchun 200 bitdan 400 bitgacha bo’lgan sonlar olinishi tavsiya etiladi.