Rsa shifrlash algoritmi ochiq kalitli rsa kriptotizimi hisoblanadi. Ochiq kalitli kriptotizim (asimmetrik kriptotizim) 70 yillar ikkinchi yarmida ishlab chiqilgan

Topshiriq №1
RSA shifrlash algoritmi ochiq kalitli RSA kriptotizimi hisoblanadi. Ochiq kalitli kriptotizim (asimmetrik kriptotizim) 70 yillar ikkinchi yarmida ishlab chiqilgan. Asimmetrik shifrlash tizimlarida ikkita kalit ishlatiladi. Axborot ochiq kalit yordamida deshifrlanadi.
Asimmetrik kriptizimlarda funksionallashtirish prinsiplari:

• 
  Foydlanuvchi A ikkita kalit ishlab chiqadi, ochiq va yopiq, kalit himoyalanmagan kanal orqali B foydalanuvchiga yuboradi;
  
• 
  Foydalanuvchi B, foydalanuvchi A ning ochiq kalit bilan ma’lumotni shifrlaydi;
  
• 
  Foydalanuvchi B shifrlangan ma’lumotni himoyalanmagan kanal orqali foydalanuchi A ga yuboradi;
  
• 
  Foydalnuvchi A shifrlangan ma’lumotni qabul qilib, o’zining yopiq kaliti bilan ma’lumotni deshifrlaydi (qayta ochadi);
  

Ikkala juft kalitlar (ochiq va yopiq kalitlar) maxsus algoritmlar yordamida ishlab chiqaladi. Hech qaysi kalit bir-biridan foydalanilgan holda ishlab chiqilmaydi.
1978 – yilda Massachusets texnologiya institutining olimlari R.L Rivest, A.Shamir, L.Adlman o’zlarining ilmiy maqolasida birinchi bo’lib maxfiy uslubli va haqiqatdan ham, bir tomonli bo’lgan funksiyani taklif etadilar. Bu maqola “Raqamli imzolarni qurish uslublari va ochiq kalitli kriptotizimlar” deb atalib, ko’proq autentifikatsiya masalalariga qaratilgan.
Hozirgi kunda, bu yuqorida nomlari keltirilgan olimlar taklif etgan funksiyani shu olimlarning sharafiga RSA bir tomonli funksiyasi deyiladi. Bu funksiya murakkab bo’lmay, uning aniqlanishi uchun elementar sonlar nazariyasidan ba’zi ma’lumotlar kerak bo’ladi.
Musbat butun bo’lgan I va n sonlarning eng katta umumiy bo’luvchisini (EKUB) (I,n) deb belgilaymiz. Misol uchun: EKUB (12,18)=6,
EKUB (9,27)=9. Har qanday musbat butun son uchun Elyer funksiyasi φ(n), n dan katta bo’lmagan EKUB (I,n)=1 shartni qanoatlantiruvchi barcha I sonlarning sanog’ini bildiradi. Misol uchun: φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2 va hokazo. Ihtiyoriy tub son r uchun φ(1)=p-1, hamda φ(1)=1 deb qabul qilingan. Bundan tashqari, ihtiyoriy r va q tub sonlari uchun ushbu
φ(p q)=(p-q)(q-1) (1)
ifoda o’rinli bo’ladi. Misol uchun φ(6)= φ(2x3)1*2=2
Buyuk matematik olim Eyler (1707-1783) teoremasiga ko’ra ixtiyor musbat butun x va n (0n)=1 shartini qanoatlantiruvchi =1(modn) tenglik tenglik bajariladi. Misol uchun:
EKUB(5,6)=1 va =1(modn) (2)
Sonlar nazariyasi kursidan ma’lumki: agarda, ye va m butun sonlar 0De=1(mod n) (3)
Tenglikni qanoatlantiruvchi yagona d butun son mavjud bo’lib, EKUB (m, e) ni topishning “kengaytirilgan” Evklid algortimidan foydalanib d ni toppish mumkin.
Yuqorida keltirilgan ma’lumotlardan foydalanib, maxfiy uslubli RSA bir tomonli funksiyasini aniqlanishini ko’rib chiqamiz. Bu funksiya biror n soni moduli bo’yicha diskret darajaga ko’tarish funksiyasi, ya’ni
= (mod n) (4)
ko’rinishida aniqlanadi. bu yerda x - musbat buitun son bo’lib, n=rq sondan katta emas; n=rq, ya’ni r va q tub sonlari uchun φ(n)=(p-q)(q-1); butun ye soni φ(n) dan kichik va EKUB (e φ(n))=1. shifrlashning Y ochiq algoritmini asosini tashkil etuvchi y= (x) funksiya qiymatlarini ifoda bilan hisoblashni osongina kvadratga ko’tarish va ko’paytirish amallariga keltirish mumkin. Y algoritmini ochiq kalitlar kitobiga kiritish, n va ye sonlarini foydalanuvchilar uchun ochiq e’lon qilish demakdir va bunda n sonining ko’paytuvchilari bo’lgan r va q tub sonlari maxfiy tutiladi. Teskari funksiya quyidagi
(y)= (mod n) (5)
ko’rinishida bo’lib, bu yerda q soni n sonidan kichik va ushbu
de=1(mod n) (6)
tenglikni qanoatlantiradi.
r, q, ye – sonlaridan iborat r, q, ye =z parametrlar to’plami tenglik bilan aniqlangan bir tomonli funksiyaning kriptografik maxfiylik uslubi xossasining asosini tashkil etadi. Maxfiy deshifrlash algoritmining asosini tashkil etuvchi teskari funksiyasining qiymatlarini hisoblash ham kvadratga ko’tarish va ko’paytirish amallari orqali amalga oshiriladi va bunda daraja ko’rsatkichi bo’lgan d soni EKUB (e φ(n)) ni hisoblashning Evklid algoritmi bo’yicha aniqlanadi. Yuqorida () ifoda bilan aniqlangan funksiyaning (4) ifoda bilan aniqlangan funksiyaga haqiqatan ham, teskari funksiya ekanligi quyidagicha ko’rsatiladi. Butun sonlar arifmetikasidan ma’lumki, biror butun Q sonida
de=1(mod(n))= φ(n)*Q+1 (7)
tenglik o’rinli bo’ladi. Yuqorida (4) va (7) tengliklarga va Eyler teoremasidagi (4) ifodaga ko’ra (8)
(y)= mod (n)=( (mod n)= φ(n)*Q+1mod n=xφ(n)Q(mod n)=(mod n) (8)
tenglikka ega bo’lamiz. Demak (6) tenglikni qanoatlantiruvchi d va ye sonlari uchun: biror xn modul bo’yicha d darajaga ko’tarish amali amali shu x sonlarni xuddi shu n modul bo’yicha ye darajaga ko’tarish amaliga teskari ekan. Endi nima uchun Rivest, Shamir va Adlman yuqorida (4) ifoda bilan aniqlangan (x) funksiyani n va ye sonlarini bilgan holda, unga teskari funksiyani hisoblash mumkin emasligini ta’kidlaganliklarini ko’rib chiqamiz. Bundan tashqari r va q tub sonlarni bila olmasligini ham ko’rib chiqamiz.
Raqib tomonga n va ye sonlari ma’lum bo’lsin. Agarda raqib tomon n sonini tub bo’lgan r va q sonlarining ko’paytmasidan iborat, ya’ni n=pq ko’rinishida ifodalay olsa, u holda maxfiylik parametri z= r, q, ye ni to’la aniqlangan holda, ma’lumotlar kriptogrammasini, ma’lumotni, haqiqatan ham, olishi kerak bo’lgan foydalanuvchi kabi qiyinchiliksiz deshifrlash imkoniyatiga ega bo’ladi. Shuning uchun RSA kriptotizimining bardoshlik darajasi n sonini tub bo’lgan r va q sonlarining ko’paytmasiga yoyishning qiyinlik darajasiga ekvivalentdir, ya’ni teng kuchlidir. Agarda r va q sonlarining uzunligi 100 dan ortiq o’ni raqamdan iborat bo’lsa, hozirgi zamonaviy hisoblash texnikalaridan foydalanilganda, n sonini tub ko’paytuvchilarga ajratish uchun sarfalanadigan vaqt yetarli darajada ko’p bo’lib, bunday tub ko’paytuvchilarga ajratish bilan shug’ullanishining amaliy jihatdan maqsadga muvofiq emasligi kelib chiqadi.
Yuqoridagi mulohazalardan tabiiy ravishda “yetarli darajada katta bo’lgan r va q tub sonlarini qanday aniqlash mumkin?”, degan savol tug’iladi. Bunday savolga javob toppish uchun Chebushev teoremasiga murojat qilamiz: biri butun m sonidan kichik bo’lgan barcha butun sonlar to’plamidan tanlab olingan birir sonni, tub son bo’lish ehtimolligi qiymatga yaqin. Misol uchun dan kichik bo’lgan barcha musbat butun sonlar to’plamidan tanlab olingan biror sonni tub son bo’lish ehtimolligi = ≈ qiymatga ega. Bu ehtimollik qiymati ikki barobar ko’payadi, agarda bu tanlab olish faqat dan kichik bo’lgan barcha butun musbat toq sonlar to’plamida amalga oshirilayotgan bo’lsa. Toq sonlardan tub sonlarni farqlash Ferma teoremasiga asoslanadi: birir r tub sonidan katta bo’lmaganbutun musbat son uchun
= 1 (mod (p)) (9)
tenglik o’rinlidir.
Misol uchun, =1(mod 5 ) yoki =1 (mod 5). Agarda r sonining tub yoki tub emasligini tekshirmoqchi bo’lsak, shu p sonidan kichik bo’lgan butun musbat b sonini olib
= 1 (mod (r)) (10)
tenglik bajarilishini tekshirish kifoya:

• 
  tenglik bajarilsa p tub son bo’lishi mumkin, chunki (9) yoki (10) munosabat r ning yoki p sonining tub bo’lishini zaruriy sharti;
  
• 
  tenglik bajarilmas p tub son emas.
  

Shunday qilib, agarda (10) munosabat o’rinli bo’lmasa, qat’iy holda p soni tub emas, deb ayta olamiz. Ammo (8) munosabat o’rinli bo’lsa, faqat p soni tub bo’lishi mumkin, lekin qat’iy holda p tub son, deb tasdiqlay olmaymiz.
Shuning uchun, p soni yetarli darajada katta bo’lib, tasodifiy olingan mumkin qadar ko’p butun musbat b(1 =
Yuqorida keltirilgan algoritmdan bugungi kunda ham birir r sonining tubligini aniqlashda foydalanib kelinmoqda. Har qanday ochiq kalitli kriptotizimning bardoshliligi ochiq matnga yoki uning birir qismiga mos keluvchi kriptogramma ma’lum bo’lganda, ya’ni shifrlash algoritmi ma’lum bo’lganda, to’la shifr matni (kriptogrammani) deshifrlash imkoniyati qanchalik murakkabligi bilan hisoblanadi.