linkedin facebook linkedin facebook nod32

RSA 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<x<n) 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<e<m va EKUB(m,e)=1 shartlarni qanoatlantirsa, u holda 0<d<m 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 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 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 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 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  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 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 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  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 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.
RSA algoritmi bo‘yicha kalitlarni taqsimlash protokoliga xulosaviy izohlar. Banklar tizimida qaysi shaxs qaysi shaxs bilan o‘zaro to‘lov amallari bajarganligini, bank bila almasligini ta’minlovchi, RSA bir tomonli funksyasiga asoslangan tartib va qoidalarni boshqarish kriptosistemasi mavjud. Bu kriptosistemani kalitlarni taqsimlash tartib va qoidalarini boshqarish kriptosistemasi uchun ham qo‘llash mumkin. Tartib va qoidalarni  boshqarish masalalari, kriptosistemalariga doir kriptologik ilmiy izlanishlar hozirda, zamonaviy, bardoshli kriptografik sistemalarni yaratishda keng va jadal rivojlanib bormoqda. Bu sohada RSA bir tomonli funksiyasidan foydalanishning qulayligi o‘zini har tomonlama oqlab kelmoqda.
RSA algoritmini qo‘llanishiga doir kichik bir misol keltiramiz.
Misol: Uchta harfdan iborat bo‘lgan “CAB” ma’lumotini shifrlaymiz. 
Biz qulaylik uchun kichik tub sonlardan foydalanamiz  Amalda esa mumkin qadar katta tub sonlar bilan ish ko‘riladi.

  • Tub bo‘lgan r=3 va q=11 sonlarini tanlab olamiz.
  • Ushbu n=pq=3*11=33 sonini aniqlaymiz. So‘ngra,  sonini topamiz, hamda bu son bilan 1 dan farqli biror umumiy bo‘luvchiga ega bo‘lmagan d sonini, misol uchun d=3 sonini,  olamiz.
  • YUqorida keltirilgan de=1(modn) shartni qanoatlantiruvchi e sonini 3e=1 (mod 20) tenglikdan topamiz. Bu son e= 7
  • SHifrlanishi kerak bo‘lgan  «CAB» ma’lumotini  tashkil etuvchi harflarni: A®1, V®2, S®3 mosliklar bilan sonli ko‘rinishga o‘tkazib olib, bu ma’lumotni musbat butun sonlarning, ketma-ketligidan iborat deb qaraymiz. U holda ma’lumot (3,1,2)ko‘rinishda bo‘ladi  va uni {e;n}={7;33} ochiq kalit bilan  bir tomonli funksiya bilan shifrlaymiz:

x=3da                  SHM1=(37)(mod33)=2187(mod33)=9,
x=1da                  SHM2=(17) (mod33)=1,
x=2da                  SHM3=(27) (mod33)=128(mod33)=29

  • Bu olingan shifrlangan (9,1,29) ma’lumotni maxfiy {d;n}={3;33} kalit bilan  ifoda orqali deshifrlaymiz: 

y=9 da       OM1=(93) (mod33)=729(mod33)=3,
y=1 da       OM2=(13) (mod33)=1(mod33)=1,
y=29 da     OM3=(293) (mod33)=24389(mod33)=2.
SHunday qilib, kriptosistemalarda RSA algoritmining qo‘llanishi quyidagicha: har bir foydalanuvchi ikkita etarli darajada katta bo‘lmagan p va q tub sonlarni tanlaydilar va yuqorida keltirilgan algoritm bo‘yicha d va e tub sonlarini ham tanlab oladi. Bunda n=pq bo‘lib, {e;n} ochiq kalitni {d;n}esa maxfiy kalitni tashkil etadi. Ochiq kalit ochiq ma’lumotlar kitobiga kiritiladi. Ochiq kalit bilan shifrlangan shifrmatnni shu kalit bilan deshifrlash imkoniyati yo‘q bo‘lib, deshifrlashning maxfiy kaliti faqat shifr ma’lumotining xaqiqiy egasigagina ma’lum.

5066 marta o`qildi.

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
счетчик посещений