{k}ShifrLabAxborotlarni himoyalash usullari
0/0

ElGamal shifrlash algoritmi

1984 yilda misrlik olim Taher ElGamal taklif qilgan sxema. Xavfsizligi chekli maydonda diskret logarifmni hisoblash qiyinligiga asoslangan. U ham shifrlash, ham raqamli imzo uchun ishlatiladi va AQSh (DSA) hamda Rossiya (GOST R 34.10-94) imzo standartlarining asosini tashkil etadi.

Turi: nosimmetrik, ehtimolliAsos: diskret logarifm
✏️ Sodda tilda

ElGamal shifrida har safar yangi tasodifiy «niqob» (k) tanlanadi. Shuning uchun bitta xabarni ikki marta shifrlasangiz ham, ikki xil shifrmatn chiqadi — tinglovchi «bu xabarni avval ko'rganman» deb bila olmaydi. Bunday shifrlash ehtimolli shifrlash deyiladi.

Algoritm

  1. Katta tub son p tanlanadi.
  2. Foydalanuvchilar guruhi uchun umumiy g < p tanlanadi.
  3. Yopiq kalit x < p−1 tanlanadi.
  4. Ochiq kalit: y = gx mod p. (p, g, y) — ochiq.
  5. Xabar M < p bo'ladigan bloklarga ajratiladi.
  6. Tasodifiy seans kaliti 1 < k < p−1 tanlanadi.
  7. a = gk mod p, b = (yk·M) mod p. (a, b) juftligi — shifrmatn.
Shifrlasha = gk mod p,  b = yk·M mod p
OchishM = b · (ax)⁻¹ mod p
💡 Nega ishlaydi?

ax = gkx = (gx)k = yk. Demak b·(ax)⁻¹ = yk·M·(yk)⁻¹ = M. Hujumchi yk ni bilish uchun x yoki k ni topishi kerak — bu diskret logarifm masalasi.

Kitobdagi misol: p = 89, g = 11, x = 3, k = 7, M = «BBC»

«BBC» = 01000010 01000010 01000011 → 6 bitli bloklar: 010000, 100100, 001001, 000011 = {16, 36, 9, 3}. y = 11³ mod 89 = 85, a = 11⁷ mod 89 = 87 …

⚠ k ni qayta ishlatmang!

Kitob misolida barcha bloklar bitta k bilan shifrlangan (a hamma uchun bir xil). Bu o'quv uchun qulay, lekin xavfli: agar bitta blokning ochiq matni ma'lum bo'lsa, yk = b·M⁻¹ topiladi va qolgan barcha bloklar ochiladi. Real tizimda har bir blok uchun yangi tasodifiy k olinadi.

Afzalliklari

  • Ehtimolli: bir xil xabar — turli shifrmatn
  • Patentlanmagan (RSA patentlangan edi)
  • Elliptik egri chiziqlarga oson ko'chiriladi

Kamchiliklari

  • Shifrmatn xabardan 2 marta uzun (a va b)
  • Har safar sifatli tasodifiy k kerak

Nosimmetrik algoritmlar haqida xulosa

Ular simmetrik tizimlarning kamchiliklarini bartaraf etdi: kalitlarni maxfiy yetkazish zarurati yo'q, kalitlar soni foydalanuvchilar soniga kvadratik emas, chiziqli bog'liq (2N). Ammo: funksiyalarning qaytarilmasligi isbotlanmagan, ular sekinroq va qurilmalarda amalga oshirish murakkabroq, ochiq kalitlarni almashtirishdan himoyalash (sertifikatlash) zarur.