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,Valiyev
Mansurxon,Komiljonov Yusufbek,Zokirjonov Diyorbek
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.
