{k}ShifrLabAxborotlarni himoyalash usullari
0/0

RSA algoritmi

Dunyodagi eng mashhur va keng tarqalgan ochiq kalitli algoritm. Nomi mualliflari — Rivest, Shamir, Adleman familiyalarining bosh harflaridan olingan. Xavfsizligi katta sonni tub ko'paytuvchilarga ajratish qiyinligiga asoslangan.

Turi: nosimmetrikAsos: faktorlash muammosiKalit: 2048–4096 bitQo'llanishi: shifrlash + imzo
✏️ Sodda tilda

Ikki tub sonni ko'paytirish oson: 37 × 41 = 1517. Endi aksincha: 1517 qaysi ikki sonning ko'paytmasi? Bir oz o'ylash kerak. Endi tasavvur qiling, son 1517 emas, 617 ta raqamdan iborat. Uni ko'paytuvchilarga ajratish uchun barcha kompyuterlar milliardlab yil ishlashi kerak. RSA egasi p va q ni biladi (yopiq kalit), hamma esa faqat ko'paytmani — n ni (ochiq kalit) biladi.

📜 Qanday yaratilgan?

Diffi va Xellmanning 1976 yilgi maqolasini o'qigan MIT olimlari bir yil davomida ochiq kalitli funksiya izlashdi: Rivest va Shamir g'oyalar taklif qilar, Adleman ularni buzar edi. 1977 yil aprelida, Fisih bayramida bir oz sharob ichgandan so'ng, Rivest tun bo'yi uxlay olmay, algoritmni yozib qo'ydi. 1977 yil avgustida Martin Gardner Scientific American jurnalida RSA ni yoritdi va o'quvchilarga 129 xonali n bilan shifrlangan iborani taklif qildi (mukofot 100$). Rivest uni ochishga 40 kvadrillion yil ketadi degan, ammo 1993–94 yillarda 20 mamlakatdan 600 ko'ngilli 1600 kompyuterda 8 oyda ochishdi: «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE». 1982 yilda mualliflar RSA Data Security kompaniyasini tuzdi; 1993 yildan PKCS#1 standarti (RFC 2313, 2437, 3447).

Algoritm

Kalitlarni yaratish

  1. Ikkita katta tub son p va q tanlanadi.
  2. Modul hisoblanadi: n = p·q.
  3. Eyler funksiyasi: φ(n) = (p−1)(q−1).
  4. φ(n) bilan o'zaro tub bo'lgan e tanlanadi (amalda ko'pincha e = 65537).
  5. d = e⁻¹ mod φ(n) hisoblanadi, ya'ni e·d mod φ(n) = 1.

🔓 Ochiq kalit

(e, n) — hammaga e'lon qilinadi.

🔐 Yopiq kalit

d (va p, q, φ(n)) — sir saqlanadi.

Shifrlash va ochish

Xabar ikkilik ko'rinishga o'tkaziladi va L bitli bloklarga ajratiladi (L < log₂(n+1)); har bir blok 0 dan n−1 gacha bo'lgan son Mᵢ sifatida qaraladi.

ShifrlashCᵢ = Mᵢe mod n
OchishMᵢ = Cᵢd mod n
💡 Nega bu ishlaydi?

e·d = 1 + k·φ(n) bo'lgani uchun Cd = Me·d = M·(Mφ(n))k. Eyler teoremasiga ko'ra Mφ(n) ≡ 1 (mod n), demak Cd ≡ M. Hujumchi d ni topishi uchun φ(n) ni bilishi kerak, buning uchun esa n ni p va q ga ajratishi kerak.

Kitobdagi misol

p = 37, q = 41 → n = 1517, φ = 36·40 = 1440, e = 11 → d = 11⁻¹ mod 1440 = 131. M = «BESH» → ASCII 66, 69, 83, 72 (L = 8 bit). C₁ = 66¹¹ mod 1517 = 763 … Shifrmatn: {763, 1441, 821, 1097}.

ℹ Mustaqil ish mashqlari haqida

Mashqlarda faqat n va e berilgan. Laboratoriya p, q maydonlari bo'sh bo'lsa, n ni avtomatik faktorlaydi — bu aynan hujumchi qiladigan ish. Kichik n uchun bir zumda; real RSA-2048 uchun esa imkonsiz.

Kuchli va zaif tomonlari

Afzalliklari

  • Kalitni maxfiy yetkazish shart emas
  • N foydalanuvchi uchun 2N kalit
  • Ham shifrlash, ham raqamli imzo
  • 45+ yildan beri buzilmagan

Kamchiliklari

  • Sekin (2 GHz da 512 bit bilan ~30 KB/s) — shuning uchun asosan kalitlarni shifrlashda ishlatiladi
  • Bir tomonlamaligining matematik isboti yo'q
  • Ochiq kalitni almashtirish (MITM) — sertifikat kerak
  • Kvant kompyuteri (Shor algoritmi) buzishi mumkin
⚠ «Darslik RSA» xavfli!

Bu yerdagi kabi har bir harfni alohida shifrlash xavfsiz emas: bir xil harflar bir xil shifrmatn beradi (BESH misolida ham shunday) va chastota tahlili ishlaydi. Real tizimlarda xabarga tasodifiy to'ldiruvchi (OAEP padding) qo'shiladi.