Kriptografiya”fanidan loyiha ishi bajardi: Nuraliyev Shuxrat 072-20 Nuriddinov Xusniddin 072-20 toshkent 2023

|
Kriptografiya”fanidan loyiha ishi bajardi: Nuraliyev Shuxrat 072-20 Nuriddinov Xusniddin 072-20 toshkent 2023
|
bet | 1/3 | Sana | 13.01.2024 | Hajmi | 0,71 Mb. | | #136773 |
Bog'liq Loyiha ishi
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TОSHKЕNT AХBОRОT TЕХNОLОGIYALARI UNIVЕRSITЕTI
“Kriptografiya”fanidan
Bajardi:Nuraliyev Shuxrat 072-20
Nuriddinov Xusniddin 072-20
TOSHKENT 2023
Mavzu:Faktorizatsiyalash muammosini bartaraf etuvchi algoritmlari dasturiy modulini ishlab chiqish Quyida berilgan shifr matni RSA shifrlash algoritmi asosida rasshifrovkalash.
Berilgan:shifr matn c=194699093426627941391799396439883597046604330516206714902 74162053008128349816033069247844970800863920955661712219866
59036695909081027033072506462163959673274173495815656734192
72952219844543096877847672771808441931988700622407913032027
38054115477138201099392091672934450078062438509784548210810
385639731494 7527381565904894782921374911825451607
Modul qiymati
N=35219656916824983498941562978713515100033928371344802082 22044475395775256080676591555740447187285422213492644065626
15487165251895509139075621688493447805478090729096096693340
62922357950595315551488502253167629538113218305350658689256
02454064437684917336623081577969436526999043044518113279691
3932904941185 478344783047790284034086549612594449881
Ochiq kalit: e = 65537
Berilgan matnni RSA asosida rasshifrovkalash uchun quyidagi ketma-ketlikdagi amallarni bajaramiz:
1. Dastlab 𝑁 modulni faktorlarga ajratamiz.
Faktorlarga ajratishning Ferma, Pollard, Lenster, Leman va boshqa shu kabi usullari mavjud.
Biz bulardan Pollard usulidan foydalandik. Ushbu usul Pollard- algorim yoki p –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga va tug’ilgan kun paradoksiga asoslanadi. U ikki sonning
ko’paytmasidan tashkil topgan sonlarning faktorlash muammosini yechishda samarali. Uning murakkabligi 𝑂(1/4 ) orqali baholanadi. Unda F(x)=(x2+1)modN va F(x)=(x2+3) funksiyadan foydalaniladi.
Ushbu usul algoritmi:
Dastlab tub ko’paytuvchilarga ajralishi kerak bo’lgan N sonini olamiz
xi=F(xi-1) va yi=F(F(yi-1)) kabi funksiyalardan foydalanamiz, i- bu yerda 1 dan boshlanadi x0=2 y0=2 deb hisoblanadi
3 xi va yi larni undan oldingi qiymatlarga qarab topib ketavermiz va har safar EKUB(|xi- yi|,N) ni topib boramiz.
Bu jarayonlarni EKUB(|xi- yi|,N)!=1 bo’lgancha davom ettiramiz. 1 dan boshqa son chiqsa bu amallar to’xtatiladi.
F(x)=(x2+1)modN va F(x)=(x2+3) ikkala funksiya uchun ham shunday davom ettiriladi. Topilgan ekub(|xi- yi|,N) lar N sonining tub ko’paytuvchilari bo’ladi
Bizning vazifamizda modul qiymat N=35219656916824983498941562978713515100033928371344802082 22044475395775256080676591555740447187285422213492644065626
15487165251895509139075621688493447805478090729096096693340
62922357950595315551488502253167629538113218305350658689256
02454064437684917336623081577969436526999043044518113279691
3932904941185478344783047790284034086549612594449881
1.1-rasm
1.2-rasm
p = 11365151311
q=309891667546360778046499718781557673007508350025387550972 83935099874494368539398248190559855426859456913152610693175
44145147650076096193873381229578315162636471554990075867196
95388646379943612802538799856438000556182989347185636332581
02374809972161903728331994734226873919699484452540196186494
86619663112858167628758971855278811478871
Endi yopiq kalit d ni topish kerak bo’ladi. Buning uchun kengaytirilgan evklid algoritmidan foydalanamiz, ya’ni quyidagi formula orqali:
|
| |