Sa algoritmiga asoslangan shifrlashga misol Muallif: Mengliyev sh. Qo`shilgan sana: 2014-08-06 rsa algoritmiga asoslangan shifrlashga misol


Download 95.54 Kb.
bet1/2
Sana03.11.2023
Hajmi95.54 Kb.
#1743276
  1   2
Bog'liq
SA algoritmiga asoslangan shifrlashga misol


SA algoritmiga asoslangan shifrlashga misol

Muallif: Mengliyev SH.
Qo`shilgan sana: 2014-08-06
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 Zi butun sonni (daraja ko‘rsatkichini) tanlaydi va uni maxfiy saqlaydi. So‘ngra, bu Zi asosida EZi algoritm tuzib ochiq ma’lumotlar kitobiga bu algoritmni joylashtiradi. Bundan tashqari Zi asosida maxfiy saqlanadigan DZi 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 EZi 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 DZi algoritmidan foydalanib  uslub bilan ochiq matnni hosil qiladi. Agarda fz 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 fz funksiyaning aniqlanish sohasidagi daraja ko‘rsatkichining barcha  qiymatlari to‘plami bilan, aynan shu funksiyaning qiymatlari to‘plami ustma-ust tushsa, ya’ni fz 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 EZi 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 fz funksiyaga teskari bo‘lib, maxfiy algoritm asosini tashkil etuvchi f-1z 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 fz funksiyaga asoslangan ochiq algoritmi (ochiq shifrlash kaliti) EZi dan foydalanib, jo‘natilishi kerak bo‘lgan ma’lumotni shifrlaydi. Bu shifrlangan ma’lumotni qabul qilib olgan j-foydalanuvchi o‘zining f-1z funksiyaga asoslangan maxfiy DZi 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 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 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 Ez ochiq algoritmini asosini tashkil etuvchi  funksiya qiymatlarini yuqoridagi ifoda bilan hisoblashni osongina kvadratga ko‘tarish va ko‘paytirish amallariga keltirish mumkin. Ez 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 tub sonlari maxfiy tutiladi. Teskari funksiya quyidagi ko‘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 Dz deshifrlash algoritmining asosini tashkil etuvchi teskari f-1z funksiyaning qiymatlarini hisoblash ham kvadratga ko‘tarish va ko‘paytirish amallari orqali amalga oshiriladi va bunda daraja ko‘rsatkichi bo‘lgan 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 esonlari uchun: biror x sonlarning modul bo‘yicha d darajaga ko‘tarish amali, shu xsonlarni 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-1z(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 sonini tub bo‘lgan va 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 nsonini 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, nsonini 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 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 52=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 sonining tub bo‘lishini zaruriy sharti;
- tenglik bajarilmasa tub son emas.
SHunday qilib, agarda  munosabat o‘rinli bo‘lmasa qat’iy holda soni tub emas, deb ayta olamiz. Ammo,  munosabat o‘rinli bo‘lsa, faqat, r soni tub bo‘lishi mumkin, lekin qat’iy holda tub son, deb tasdiqlay olmaymiz.
SHuning uchun, soni etarli darajada katta bo‘lib, tasodifiy olingan mumkin qadar ko‘p butun musbat  sonlari uchun  munosabat bajarilsa rsonining 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 Ez 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. 

Download 95.54 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling