Namangan davlat universiteti fizika-matematika fakulteti amaliy matematika kafedrasi

Ta`rif-1. Ryukzak vektori deb n (n3) ta tartiblangan natural sonlardan tashkil topgan A = (a₁,...,a_n) 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 echimi 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.

Odatda ryukzak masalasi qo`yilganda, (A, ) ma`lumotlar uchun masala echimga ega bo`lishini aniqlashga to`g’ri keladi. Kriptografiyada qo`llanayotgan variantda esa shunday echim mavjud degan nuqtai-nazardan deb hisoblanadi. Masala NP-to`liq masalalar sinfiga kiradi.

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. Bu masalani boshqacha qilib,

_{ }

ko`rinishida ham yozish mumkin. Masalan, n=6 va A=(3, 41, 5, 1, 21, 10) bo`lsin. U holda ikkilik (1, 1, 0, 0, 1, 0) va (1, 0, 1, 1, 0, 1) bloklar mos ravishda 65 va 19 tarzida shifrlanadi. Berilgan A vektor uchun shifrlangan matn 81 dan kichik bo`lgan sonlardan tashkil topadi va xar bir matnga faqat bitta shifrlangan matn mos keladi.

A=(14, 28, 56, 82, 90, 132, 197, 284, 341, 455) bo`lgan vektor uchun =515 ga mos keluvchi shifrlangan matn ikkita boshlang’ich matnga mos keladi:

f(0, 1, 1, 0, 1, 0, 0, 0, 1, 0)=28+56+90+341=515

f(1, 0, 0, 1, 1, 1, 1, 0, 0, 0)=14+82+90+132+197=515

Ammo, =517 uchun (1, 1, 1, 0, 1, 1, 1, 0, 0, 0) vektor yagona boshlang’ich matn bo`ladi:

f(1, 1, 1, 0, 1, 1, 1, 0, 0, 0)=14+28+56+90+132+197=517. мкита

Qayta shifrlashning bir qiymatli bo`lishi uchun A ryukzak vektori har bir  da barcha (A, ) boshlang’ich ma`lumotlar uchun bittadan ortiq echimga ega bo`la olmaydi. Bunday ryukzak vektorlarini in`ektiv deb ataladi. CHunki, 1-misolda qaralgan A vektor yordamida hosil qilingan funktsiya in`ektivdir.