O’zbekiston respublikasi raqamli texnologiyalari vazirligi muhammad al-xorazmiy nomidagi tоshkеnt aхbоrоt tехnоlоgiyalari univеrsitеti

Download 4,63 Mb.
bet	1/3
Sana	18.05.2024
Hajmi	4,63 Mb.
	#243339

1 2 3

Bog'liq
shifrlash

Qabul qildi
RSA algoritmi

O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI
VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TОSHKЕNT AХBОRОT TЕХNОLОGIYALARI UNIVЕRSITЕTI

«Kriptologiya» kafеdrasi

LOYIHA ISHI

Mavzu: Shor algoritmi yordamida RSA ni buzish
5330500 – “Axborot xavfsizligi” yo`nalishi
Bajardi:711-21AXu guruh talabasi Raxmatov Bexzod
Qabul qildi:Mardiyev Ulug’bek

Toshkеnt - 2024
Shor algoritmi, katta sonlarni faktorlarga ajratish uchun ishlatiladigan kvant algoritmi keng qo'llaniladigan ochiq kalit kriptotizimi RSA uchun jiddiy xavf tug'diradi. RSA o'z xavfsizligini ta'minlash uchun katta yarim asosiy sonlarni faktoring qilish qiyinligiga tayanadi.RSA standart kriptografik algoritmdir. Usul ommaga ma'lum, ammo uni buzish juda qiyin. U shifrlash uchun ikkita kalitdan foydalanadi. Ochiq kalit ochiq va mijoz undan tasodifiy seans kalitini shifrlash uchun foydalanadi. Shifrlangan kalitni tutib olgan har bir kishi uni parolini ochish uchun ikkinchi kalitdan, shaxsiy kalitdan foydalanishi kerak. Aks holda, bu shunchaki axlat. Seans kaliti shifrlangandan so'ng, server undan keyingi xabarlarni tezroq algoritm bilan shifrlash va shifrini ochish uchun foydalanadi. Shunday qilib, biz shaxsiy kalitni xavfsiz saqlasak, aloqa xavfsiz bo'ladi.
RSA shifrlash oddiy fikrga asoslanadi: asosiy faktorizatsiya. Ikki tub sonni ko'paytirish juda oddiy, ammo uning natijasini faktorlarga ajratish qiyin. Masalan, 507,906,452,803 uchun qanday omillar mavjud? Javob: 566 557 × 896 479.

Murakkablikdagi ushbu assimetriyaga asoslanib, biz xabarni shifrlash uchun ikkita tub sonning mahsulotiga asoslangan ochiq kalitni tarqatishimiz mumkin. Ammo asosiy omillarni bilmasdan, biz xabarni asl maqsadiga ko'ra shifrlay olmaymiz. 2014-yilda WraithX Amazon EC2-da 7600 dollarlik byudjetdan va 696 bitli raqamni faktorizatsiya qilish uchun o‘z resurslaridan foydalangan. Biz bir oy yoki bir yil ichida katta byudjetga ega 1024 bitli kalitni buzishimiz mumkin. Bu halokatli, chunki ochiq kalitga ega bo'lgan SSL sertifikatlari 28 oy davom etadi. Yaxshiyamki, asosiy faktorizatsiya muammosining murakkabligi kalit uzunligi bilan eksponent ravishda o'sib boradi. Shunday qilib, biz juda xavfsizmiz, chunki biz allaqachon 2048 bitli kalitlarga o'tdik.Ammo siz taxmin qilganingizdek, uning murakkabligining la'nati Shor algoritmi tomonidan hal qilingan. Shor algoritmi 1994 yilda nashr etilgan. Ungacha kvant hisoblash ko'proq qiziqish uyg'otadi. Shor algoritmining kiritilishi haqiqatan ham ohangni o'zgartiradi. Klassik kompyuterlar tomonidan samarali hal etilmaydigan haqiqiy muammoni hal qiladi. Bu investitsiyalarni jalb qiladigan paradigmaning o'zgarishi. Biz algoritmlarni “bajarish” oracle funktsiyasi bilan muhokama qilgan bo'lsak-da, Shor algoritmi haqiqiy kelishuvdir. Biz shunchaki qubitlarga ega kvant kompyuterini kutmoqdamiz.Shor algoritmi bilimning ko'plab fanlarini o'z ichiga oladi. Biz har tomonlama bo'lishga harakat qilamiz va sizga o'zingiz yoqtirgan tezlikda davom etishingizni tilaymiz. Ammo biz amalga oshirishning har bir tafsilotini ko'rib chiqmaymiz, chunki bizda ko'p narsa bor.
RSA algoritmi
Quyida RSA algoritmi keltirilgan. Hozircha bizning so'zlarimizni qabul qilishingiz mumkin, agar biz asosiy faktorizatsiyani qanday samarali qilishni bilsak, RSA tarix bo'ladi.

Biroq, biz yuqoridagi bir nechta atamalarni tushunishimiz kerak. Eng katta umumiy bo'luvchi ( gcd ) ikkita son orasidagi eng katta bo'luvchini topadi. Masalan,

Ikkita son umumiy omillarga ega bo'lmasa, birgalikda tub son hisoblanadi.

“ mod ” dasturchilarga tanish boʻlgan modul operatori (masalan, 14 % 10 = 4). Keling, ba'zi modul hisoblarini ko'rib chiqaylik.

Download 4,63 Mb.

1 2 3

Download 4,63 Mb.