{k}ShifrLabAxborotlarni himoyalash usullari
0/0

Ryukzak (Merkle–Hellman) algoritmi

Birinchi ochiq kalitli shifrlash tizimi (1978). U qiyin «ryukzakni to'ldirish» masalasini oson masala sifatida yashiradi — va kriptografiya tarixidagi eng mashhur «yiqilish»lardan biriga uchragan.

Turi: nosimmetrikAsos: ryukzak (subset-sum) masalasiHolati: buzilgan (1982)
✏️ Sodda tilda

Sizda 1, 2, 4, 8 kg li toshlar bor, ryukzak og'irligi 11 kg. Qaysi toshlar solingan? Oson: eng og'iridan boshlab — 8 sig'adi (3 qoldi), 4 sig'maydi, 2 sig'adi (1 qoldi), 1 sig'adi. Javob: 8+2+1. Lekin toshlar 22, 5, 21, 25 kg bo'lsa va ryukzak 47 kg bo'lsa? Endi tanlab ko'rishga to'g'ri keladi! Ryukzak shifri xuddi shu: hamma «qiyin» toshlarni (ochiq kalit) ko'radi, lekin faqat egasi ularni «oson» toshlarga aylantirish sirini (yopiq kalit) biladi.

Ryukzak masalasi

S hajmli ryukzak va w = (w₁, w₂, …, wₙ) og'irlikdagi toshlar berilgan. Qaysi toshlar solinganini ko'rsatuvchi binar vektor x = (x₁, …, xₙ), xᵢ ∈ {0, 1} ni topish kerak:

S = Σ xᵢ·wᵢ

Umumiy holda bu NP-to'liq masala. Lekin agar ketma-ketlik o'suvchi bo'lsa — har bir had oldingi barcha hadlar yig'indisidan katta: wk+1 > Σi≤k wᵢ — masala «ochko'z» usulda bir zumda yechiladi.

Kalitlarni yaratish

  1. O'suvchi ketma-ketlik w = (w₁, …, wₙ) tanlanadi.
  2. Modul q > Σ wᵢ tanlanadi.
  3. q bilan o'zaro tub r tanlanadi.
  4. Normal ketma-ketlik hisoblanadi: bᵢ = wᵢ·r mod q.

🔓 Ochiq kalit

Normal ketma-ketlik (b₁, …, bₙ) — u o'suvchi emas, «qiyin» ko'rinadi.

🔐 Yopiq kalit

O'suvchi ketma-ketlik w, modul q va r soni. Xavfsizlik uchun hadlar 200–400 bitli bo'lishi tavsiya etiladi.

Shifrlashcᵢ = Σ bⱼ·mⱼxabar n bitli bloklarga ajratiladi
Ochishr⁻¹·cᵢ mod q = Σ wⱼ·mⱼso'ng o'suvchi w bo'yicha bitlar topiladi

Kitobda shifrlash formulasida «mod q» ham yozilgan; mustaqil ish mashqlaridagi shifrmatnlar esa q dan katta (mod olinmagan). Ochish natijasi ikkala holatda bir xil, laboratoriya mod olmasdan hisoblaydi.

Kitobdagi misol: w = {2, 3, 7, 15}, q = 28, r = 11, M = «HA»

b = {22, 5, 21, 25}. «HA» = 0100 1000 0100 0001. Masalan 0100 → 22·0 + 5·1 + 21·0 + 25·0 = 5. Ochish: r⁻¹ = 11⁻¹ mod 28 = 23; 23·5 mod 28 = 3 = 3·1 → 0100.

📜 100 dollarlik garov

Ralf Merkl va Martin Xellman 1978 yilda tizimni e'lon qilgach, Merkl uni buzgan kishiga 100 dollar mukofot va'da qildi. 1982 yilda Adi Shamir (RSA dagi «S») polinomial vaqtda ishlaydigan hujum topdi: u yopiq kalitga teng bo'lmagan, lekin baribir shifrni ochadigan kalit yasadi. Merkl takroriy (ko'p bosqichli) versiyaga 1000 dollar tikdi — 1984 yilda Ernest Brikell uni ham buzdi. Algoritm patentining muddati 1997 yilda tugagan. Bu voqea muhim saboq berdi: umumiy holda qiyin masala uning maxsus holi ham qiyin degani emas.