linkedin facebook linkedin facebook nod32

Ochiq kalitli RSA kriptosistemasi

Muallif: Mengliyev Sh.

Qo`shilgan sana: 2015-05-16

Ochiq kalitli RSA kriptosistemasi

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, Y=fZi(x) uslub bilan kriptogrammani tuzib (hosil kilib), i – foydalanuvchiga jo‘natadi. Maxfiy ma’lumotni kriptogramma ko‘rinishida qabul qilib olgan i - foy­dalanuvchi o‘zining maxfiy algoritmidan f-1Zi(Y)=X 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. Dif¬fi va Xellman, agarda bir tomonli fZ funksiyaning aniqlanish sohadagi darajada 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 imlo mumkin deydi. Agarda (i - foydalanuvchi aloqa tizimi bo‘yicha maxfiy bo‘lmagan ma’lumotni barcha foydalanuvchilarga etkazib, bu maxfiy bo‘lmagan ma’lumotni jo‘natuvchini ma’lumotni qabul kilib oluvchilar tomonidan behato aniqlashlari uchun o‘zining maxfiy algoritmi Y=f-1Zi asosida raqamli imzo qo‘yadi. Har bir foydalanuvchi ochiq algoritm Ezi ni bilgan holda fZi-1(Y)=X ni oladi, lekin i - foydalanuvchidan boshqa foy­dalanuvchi X ma’lumotni Y=f-1Zi(X) kriptogramma ko‘rinishidagi raqamli imzo ifodasiga o‘tkaza olmaydi, chunki faqat i - foydalanuvchining o‘zigina ochiq algoritm asoslangan fZi funksiyaga teskari bo‘lib, maxfiy algoritm asosini tashkil etuvchi f-1Zi ni hisoblay oladi. O‘z-o‘zidan tushunarliki, agarda i – foydalanuvchi i - foydalanuvchiga maxfiy ma’lumotni ham raqamli imzo bilan jo‘natish mumkin. Buning uchun, i – foydalanuvchi j –foydalanuvchining fZi funksiyaga asoslangan ochiq algoritmi (ochiq shifrlash kaliti) EZi dan foydalanib, jo‘natilishi kerak bo‘lgan ma’lumotni shifrlaydi. Bu shifrlangan ma’lumotlarni qabul qilib olgan j - foydalanuvchi o‘zining f-1Zi funksiyaga asoslangan maxfiy DZi deshifrlash altoritmi bilai ochadi. 1976 yilda Diffi va Xellman o‘zlarining "Kriptologiyada yangi yo‘nalish" [6] ilmiy ishlarida bir tomonli funksiya sifatida (15) ifoda bilan aniqlangan diskret darajaga ko‘tarish funksiyasini taklif qilib, (16) ifodadagi 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 hag‘ig‘atan 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 nazariyasidan ba’zi ma’lumotlar kerak buo‘adi. 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 kanday musbat butun son uchun Eyler funksiyasi φ(n) n dan katta bo‘lmagan EKUB(I, n)=1 shartni qanoatlantiruvchi barcha i sonlarining sanog‘ini bildiradi. Misol uchun: φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4 φ(6)=2 va xokazo. Ixtiyoriy tub son r uchun φ(1)=P-1 hamda φ(1)=1 deb qabul qilingan. Bundan tashqari, ixtiyoriy r va q tub sonlari uchun ushbu φ(p,q)=(p-1)(q-1) ifoda o‘rinli bo‘ladi. Misol uchun φ(6)=φ(2x3)=1*2=2 Buyuk matematik olim Eyler(1707-1783) teoremasiga ko‘ra ixtiyoriy musbat butun x va n (0<x<n) sonlari uchun EKUB(x,n)=1 shartini qanoatlantiruvchi xφ(n)=1(mod n) tenglik bajariladi. Misol uchun: EKUB(5,6)=1 va 52=1(mod n)

Sonlar nazariyasi kursidan ma’lumki: agarda, e va m butun sonlar 0<e<m va EKUB(m, e)q1 shartlarni qanoatlantirsa, u holda 0<d<m tengsizlikni va

d=1(mod n) (1)

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 anniqlanishini ko‘rib chiqamiz. Bu funksiya biror n soni moduli bo‘yicha diskret darajaga ko‘tarish funksiyasi, ya’ni

fZ(x)=xe(mod n) (2)

ko‘rinishida aniqlanadi. Bu erda: x- musbat butun son bo‘lib, n=rqsondan katta emas; n=r, yaьni r va q tub conlari uchun φ(n)=(p-1)(q-1) butun e soni φ(n) dan kichik va EKUB(e, φ(n))=1 SHifrlashning Ez ochiq algoritmini asosini tashkil etuvchi y=fz(x) funksiya qiymatlarini (2) 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 r va q tub sonlari maxfiy tutiladi. Teskari funksiya quyidagi

fzi-1(y)=yd(mod n) (3)

ko‘rinishda bo‘lib, bu erda q soni n sonidan kichik va ushbu

de=1(mod n) (4)

tenglikni qanoatlantiradi. r, q, e - sonlaridan iborat { r, q, e }qz parametrlar to‘plami (2) tenglik bilan aniqlangan bir tomonli funksiyaning kriptografik maxfiylik uslubi xossasining asosini tashkil etadi. Maxfiy Dz deshifrlash algoritimining asosini tashkil etuvchi teskari F-1Zi 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 φ(n)) ni hisoblashning Evklid algoritmi bo‘yicha aniqlanadi. YUqorida (3) ifoda bilan aniqlangan funksiyaning (2) ifoda bilan aniqlangan funksiyaga haqiqatan ham, teskari funksiya ekanligi quyidagicha ko‘rsatiladi. Butun sonlar arifmetikasidan ma’lumki, bi¬ror butun Q sonida

de=1(mod(n))=φ(n)*Q+1 (5)

tenglik o‘rinli bo‘ladi. YUqoridagi (2) va (5) tengliklarga va Eyler teoremasidagi (2) ifodaga ko‘ra

f-1Ziydmod(n)=(xe)d(mod(n))=φ(n)*Q+1modn=xφ(n)*Qx(modn)=x(modn) (6) 

tenglikka ega bo‘lamiz. Demak, (4) tenglikni qanoatlantiruvchi d va e sonlari uchun: biror x<n 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 (2) ifoda bilan aniqlangan fz(x) funksiyani n va e sonlarini bilgan holda, unga teskari f-1Zi(x) funksiyani hisoblash mumkin emasligini ta’kidlaganliklarini ko‘rib chiqamiz. Bundan tashqari r va q tub sonlarini kanday 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 r va q sonlarining ko‘paytmasidan iborat, yaьni nqpq ko‘rinishida ifodalay olsa, u holda maxfiylik parametri zq{ r, q, e }ni to‘la aniqlangan holda, ma’lumotlar kriptogrammasini, ma’lumotni, xaqiqatan ham, olishi kerak bo‘lgan foydalanuvchi kabi qiyinchiliksiz deshifrlash imkoniyatiga ega bo‘ladi. SHuning uchun RSA kriptosistemasining bardoshlilik 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‘nli raqamdan iborat bo‘lsa, hozirgi zamonaviy hisoblash texnikalaridan 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 muvofiq emasligi kelib chiqadi. YUqoridagi mulohazalardan tabiiy ravishda "etarli darajada katta bo‘lgan r va q tub conlarini qanday aniqlash mumkin?", degan savol tug‘iladi. Bunday savolga javob topish uchun CHebo‘shev teoremasiga murojaat qilamiz: biror butun m sonidan kichik bo‘lgan barcha butun sonlar to‘plamidan tanlab olingan biror sonni, tub son bo‘lish ehtimolligi (In 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 r tub sonidan katta bo‘lmagan butun musbat son uchun

bp-1=1(mod(p)) (7)

tenglik o‘rinlidir.

Misol uchun 24q1(mod5) yoki 34q1(mod5) Bu keltirilgan (7) munosabat (1) munosabatniig xususiy holidir. Agarda r sonining tub yoki tub emasligini tekshirmoqchi bo‘lsak, shu r sonidan kichik bo‘lgan butun musbat b sonini olib

br-1=1(mod(r)) (8)

tenglik bajarilishini tekshirish kifoya:

tenglik bajarilsa r tub son bo‘lishi mumkin, chunki (7) yoki (8) munosabat r ning yoki r sonining tub bo‘lishini zaruriy sharti;

tenglik bajarilmasa r tub son emas.

SHunday qilib, agarda (8) munosabat o‘rinli bo‘lmasa, katьiy holda r soni tub emas, deb ayta olamiz. Ammo, (8) 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 b(1<b<r) sonlari uchun (8) munosabat bajarilsa, r sonining tub ekanligiga shunchalik ko‘p darajada ishonch hosil qilish mumkin. Agarda b ning yuzta qiymatida (8) munosabat o‘rinli bo‘lsa, u holda r sonining tub bo‘lmaslmgm hodisasining ehtimoli qiymati

YUqorida keltirilgan algoritmdan bugungi kunda ham biror r sonining tubligini aniqlashda foydalanib kelinmoqda.

Har qanday ochiq kalitli kriptosistemanint 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

Ochiq kalitli kriptosistemalar haqida izoh

Yuqorida ko‘rib o‘tilgan Diffi va Xellmannnng bir tomonli funksiyasi hamda RSA bir tomonli funksiyasi yetarli darajada ochiq kalitli kriptosistemalarning xossalarini ochib beradi. Bu bir tomonli funksiyalardan tashqari ham ko‘plab bir tomonli funksiyalar kriptologiya sohasidagi ilmiy nashrlarda e’lon qilingan. Ularning ba’zilari yetarli darajada kriptosistemlar 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.

846 marta o`qildi.

Foydalanuvchi ismi: JAMSHID
Qo`shilgan sana: 2016-06-06

Kriptografiya haqida to`liqroq va aniq ma`lumotlar yo`qmi ? Oldindan rahmat.

Parol:
Eslab qolish.


Ro`yhatdan o`tish

testing

+998915878681

Siz o`z maxsulotingizni 3D reklama ko`rinishda bo`lishini xohlaysizmi? Unda xamkorlik qilamiz.

3D Reklama


Рейтинг@Mail.ru
Рейтинг@Mail.ru

Besucherzahler
счетчик посещений