Sa algoritmiga asoslangan shifrlashga misol Muallif: Mengliyev sh. Qo`shilgan sana: 2014-08-06 rsa algoritmiga asoslangan shifrlashga misol
Download 95.54 Kb.
|
1 2
Bog'liqSA 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 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 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 esonlari uchun: biror x 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 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 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 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 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 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
ma'muriyatiga murojaat qiling