Ochiq kalitlarni shifrlash algoritmi

RSA algoritmini namoyish qilish

RSA algoritmiga asoslangan shifrlashga misol


Diffi va Xellman maxfiy uslubli bir tomonli funksiyaning aniqlanishiga asoslanib, maxfiy aloqa tizimi foydalanuvchilari uchun, o‘zlarining ochiq kalitli kriptosistema strukturasini (tuzilishini) taklif etdilar. har bir i-foydalanuvchi biror Z_i butun sonni (daraja ko‘rsatkichini) tanlaydi va uni maxfiy saqlaydi. So‘ngra, bu Z_i asosida E_Zi algoritm tuzib ochiq ma’lumotlar kitobiga bu algoritmni joylashtiradi. Bundan tashqari Z_i asosida maxfiy saqlanadigan D_Zi algoritmni ham tuzadi va uni sir tutadi. Agarda j-foydalanuvchi i-foydalanuvchiga X maxfiy ma’lumotni uzatmoqchi bo‘lsa, u holda j-foydalanuvchi ochiq ma’lumotlar kitobidan E_Zi algoritmni olib, uslub bilan kriptogrammani tuzib (hosil qilib), i-foydalanuvchiga jo‘natadi. Maxfiy ma’lumotni kriptogramma ko‘rinishida qabul qilib olgan i- foydalanuvchi  o‘zining maxfiy D_Zi algoritmidan foydalanib uslub bilan ochiq matnni hosil qiladi. Agarda f_z haqiqatan ham maxfiy uslubli bir tomonli funksiya bo‘lsa, u holda bu funksiya asosida qurilgan algoritm shak-shubhasiz amaliy bardoshlilikni ta’minlaydi. Diffi va Xellman, agarda bir tomonli f_z funksiyaning aniqlanish sohasidagi daraja ko‘rsatkichining barcha  qiymatlari to‘plami bilan, aynan shu funksiyaning qiymatlari to‘plami ustma-ust tushsa, ya’ni f_z funksiyaning aniqlanish sohasi bilan qiymatlar sohasi bir xil to‘plamni tashkil etsa, bunday bir tomonli funksiya asosida raqamli  imzo olish mumkin. Agarda i-foydalanuvchi aloqa tizimi bo‘yicha maxfiy bo‘lmagan X ma’lumotni barcha foydalanuvchilarga etkazib, bu maxfiy bo‘lmagan ma’lumotni jo‘natuvchini ma’lumotni qabul qilib oluvchilar tomonidan behato aniqlashlari uchun, o‘zining maxfiy algoritmi  asosida raqamli imzo qo‘yadi. har bir foydalanuvchi ochiq algoritm E_Zi ni bilgan holda  ni oladi, lekin i-foydalanuvchidan boshqa foydalanuvchi X ma’lumotni  kriptogramma ko‘rinishidagi raqamli imzo ifodasiga o‘tkaza olmaydi, chunki faqat i-foydalanuvchining o‘zigina ochiq algoritm asoslangan f_z funksiyaga teskari bo‘lib, maxfiy algoritm asosini tashkil etuvchi f^-1_z ni hisoblay oladi. o‘z-o‘zidan tushinarliki, agarda i-foydalanuvchi j-foydalanuvchiga maxfiy ma’lumotni ham raqamli imzo bilan jo‘natishi mumkin. Buning uchun, i-foydalanuvchi j-foydalanuvchining f_z funksiyaga asoslangan ochiq algoritmi (ochiq shifrlash kaliti) E_Zi dan foydalanib, jo‘natilishi kerak bo‘lgan ma’lumotni shifrlaydi. Bu shifrlangan ma’lumotni qabul qilib olgan j-foydalanuvchi o‘zining f^-1_z funksiyaga asoslangan maxfiy D_Zi deshifrlash algoritmi bilan ochadi.

1976 yilda Diffi va Xellman o‘zlarining «Kriptologiyada yangi yo‘nalish» ilmiy ishlarida bir tomonli funksiya sifatida aniqlangan diskret darajaga ko‘tarish funksiyasini taklif qilib, diskret logarifmni hisoblashning amaliy jihatdan murakkabligiga asoslangan edilar. 1978 yilda esa, Massachusets texnologiya institutining olimlari: R.L. Rivest, A. SHamir, L. Adlman, o‘zlarining ilmiy maqolasida birinchi bo‘lib maxfiy uslubli va haqiqatan ham bir tomonli bo‘lgan funksiyani taklif etdilar. Bu maqola «Raqamli imzolarni qurish uslublari va ochiq kalitli kriptosistemalar» 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 nazaryasidan ba’zi ma’lumotlar kerak bo‘ladi.

Musbat butun bo‘lgan i va n sonlarining 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 n uchun Eyler funksiyasi  n dan katta bo‘lmagan EKUB(i,n) =1 shartni qanoatlantiruvchi barcha i sonlarining sanog‘ini bildiradi. Misol uchun: va xokazo. Ihtiyoriy tub son p uchun , hamda  deb qabul qilingan.  Bundan tashqari, ihtiyoriy p va q tub sonlari uchun ushbu

ifoda o‘rinli bo‘ladi. Misol uchun Buyuk matematik olim Eyler(1707-1783) teoremasiga ko‘ra ihtiyoriy musbat butun x va n (0 sonlari uchun EKUB(x,n)=1 shartini qanoatlantiruvchi tenglik bajariladi. Misol uchun: EKUB(5,6)=1 va Sonlar nazariyasi kursidan ma’lumki: agarda, e va m butun sonlar 0 va EKUB(m,e)=1 shartlarni qanoatlantirsa, u holda 0 tengsizlikni va tenglikni qanoatlantiruvchi yagona d butun son mavjud bo‘lib, EKUB(m,e) ni topishning «kengaytirilgan» Evklid algoritmidan foydalanib d ni topish 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 ko‘rinishida aniqlanadi. Bu erda: x- musbat butun son bo‘lib, n=pq sondan katta emas; n=pq, ya’ni p va q tub sonlari uchun butun e soni dan kichik va EKUB(e,)=1. SHifrlashning E_z ochiq algoritmini asosini tashkil etuvchi  funksiya qiymatlarini yuqoridagi ifoda bilan hisoblashni osongina kvadratga ko‘tarish va ko‘paytirish amallariga keltirish mumkin. E_z  algoritmni ochiq kalitlar kitobiga kiritish, n va e sonlarini foydalanuvchilar uchun ochiq e’lon qilish demakdir va bunda n sonining ko‘paytuvchilari bo‘lgan p va q tub sonlari maxfiy tutiladi. Teskari funksiya quyidagiko‘rinishda bo‘lib, bu erda d soni n sonidan kichik va ushbu 

tenglikni qanoatlantiradi. p,q,e –sonlaridan iborat{p,q,e}=z parametrlar to‘plami  tenglik bilan aniqlangan bir tomonli funksiyaning kriptografik maxfiylik uslubi xossasining asosini tashkil etadi. Maxfiy D_z deshifrlash algoritmining asosini tashkil etuvchi teskari f^-1_z funksiyaning qiymatlarini hisoblash ham kvadratga ko‘tarish va ko‘paytirish amallari orqali amalga oshiriladi va bunda daraja ko‘rsatkichi bo‘lgan d soni EKUB(e,)) ni hisoblashning Evklid algoritmi bo‘yicha aniqlanadi. YUqorida  ifoda bilan aniqlangan funksiyaning  ifoda bilan funksiyaga haqiqatan ham teskari funksiya ekanligi quyidagicha ko‘rsatiladi. Butun sonlar arifmetikasidan ma’lumki, biror butun Q sonida tenglik o‘rinli bo‘ladi. YUqoridagi va tengliklarga va Eyler teoremasidagi  ifodaga ko‘ra tenglikka ega bo‘lamiz. Demak,  tenglikni qanoatlantiruvchi d va e sonlari uchun: biror x sonlarning n modul bo‘yicha d darajaga ko‘tarish amali, shu x sonlarni xuddi shu n modul bo‘yicha e darajaga ko‘tarish amaliga teskari ekan. Endi nima uchun Rivest, SHamir va Adlman yuqorida  ifoda bilan aniqlangan f^-_z(x)   funksiyani n va e sonlarini bilgan holda, unga teskari f^-1_z(y)funksiyani hisoblash mumkin emasligini ta’kidlaganliklarini ko‘rib chiqamiz. Bundan tashqari p va q tub sonlarini qanday qilib tanlanganda, raqib tomonning bu sonlarni bila olmasligini ham ko‘rib chiqamiz.
Raqib tomonga n va e sonlari ma’lum bo‘lsin. Agarda raqib tomon n sonini tub bo‘lgan p va q sonlarining ko‘paytmasidan iborat, ya’ni n=pq ko‘rinishida ifodalay olsa, u holda maxfiylik parametri z={p,q,e} ni to‘la aniqlagan holda, ma’lumotlar kriptogrammasini, ma’lumotni haqiqatan ham olishi kerak bo‘lgan foydalanuvchi kabi, qiyinchiliksiz deshifrlash imkoniyatiga ega bo‘ladi. SHuning uchun RSA kriptosistemasining bardoshlilik darajasi n sonini tub bo‘lgan p va q sonlarining ko‘paytmasiga yoyishning qiyinlik darajasiga ekvivalentdir, ya’ni teng kuchlidir. Agarda p va q sonlarining uzunligi 100 dan ortiq o‘nli raqamdan iborat bo‘lsa, hozirgi zamonaviy hisoblash tehnikalaridan foydalanilganda, n sonini tub ko‘paytuvchilarga ajratish uchun sarflanadigan vaqt etarli darajada ko‘p bo‘lib, bunday tub ko‘paytuvchilarga ajratish bilan shug‘ullanishining amaliy jihatdan maqsadga muofiq emasligi kelib chiqadi.
YUqoridagi mulohazalardan tabiiy ravishda, «etarli darajada katta bo‘lgan p va q tub sonlarini qanday aniqlash mumkin?”, degan savol tug‘iladi. Bunday savolga javob topish uchun CHebeshev teoremasiga murojaat qilamiz: biror butun m sonidan kichik bo‘lgan barcha butun sonlar to‘plamidan tanlab olingan biror sonni, tub son bo‘lish ehtimolligi (Ln(m))^-1 qiymatga yaqin.
Misol uchun 10100 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 10100  dan kichik bo‘lgan barcha butun musbat toq sonlar to‘plamida amalga oshirilayotgan bo‘lsa. Toq sonlardan tub sonlarni farqlash Ferma teoremasiga asoslanadi: biror p tub sonidan katta bo‘lmagan butun musbat son uchun  tenglik o‘rinlidir.
Misol uchun, 24=1(mod5) yoki 34=1(mod5). Bu keltirilgan  munosabat EKUB(5,6)=1 va 5²=1(modn) munosabatning xususiy holidir. Agarda r sonining tub yoki tub emasligini tekshirmoqchi bo‘lsak, shu r sonidan kichik bo‘lgan butun musbat  b sonini olib  tenglikni bajarilishini tekshirish kifoya:
- tenglik bajarilsa r tub son bo‘lishi mumkin, chunki  yoki  munosabat p ning yoki r sonining tub bo‘lishini zaruriy sharti;
- tenglik bajarilmasa r tub son emas.
SHunday qilib, agarda  munosabat o‘rinli bo‘lmasa qat’iy holda r soni tub emas, deb ayta olamiz. Ammo,  munosabat o‘rinli bo‘lsa, faqat, r soni tub bo‘lishi mumkin, lekin  qat’iy holda r tub son, deb tasdiqlay olmaymiz.
SHuning uchun, r soni etarli darajada katta bo‘lib, tasodifiy olingan mumkin qadar ko‘p butun musbat   sonlari uchun  munosabat bajarilsa  r sonining tub ekanligiga shunchalik ko‘p darajada ishonch hosil qilish mumkin. Agarda b ning yuzta qiymatida  munosabat o‘rinli bo‘lsa, u holda r sonining tub bo‘lmasligi xodisasining ehtimoli qiymati  ga teng bo‘ladi.
YUqorida keltirilgan algoritmdan bugungi kunda ham biror r sonining tubligini aniqlashda foydalanib kelinmokda har qanday ochiq kalitli kriptosistemaning bardoshliligi ochiq matnga yoki uning biror qismiga mos keluvchi kriptogramma ma’lum bo‘lganda, ya’ni shifrlash algoritmi E_z  ma’lum bo‘lganda, to‘la shifr matnni (kriptogrammani) deshifrlash imkoniyati qanchalik murakkabligi bilan baholanadi.
YUqorida ko‘rib o‘tilgan Diozfi va Xellmanning bir tomonli funksiyasi hamda RSA bir tomonli funksiyasi etarli darajada ochiq kalitli  kriptosistemalarninig xossalarini ochib beradi. Bu bir tomonli funksiyalardan tashqari ham ko‘plab bir tomonli funksiyalar kriptologiya sohasidagi ilmiy nashryotlarda e’lon qilingan. Ularning ba’zilari etarli darajada kriptosistemalar talablariga javob bermagan. SHuni ta’kidlaymizki, hozirgacha ochiq nashryotda hech kim tomonidan haqiqatan ham bir tomonli bo‘lgan yoki maxfiy uslubli bir tomonli bo‘lgan funksiya e’lon qilingan emas.