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

Download 0,71 Mb.
bet	1/3
Sana	13.01.2024
Hajmi	0,71 Mb.
	#136773

1 2 3

Bog'liq
Loyiha ishi

Mavzu: Faktorizatsiyalash muammosini bartaraf etuvchi algoritmlari dasturiy modulini ishlab chiqish

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

LOYIHA ISHI

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)=(x²+1)modN va F(x)=(x²+3) funksiyadan foydalaniladi.
Ushbu usul algoritmi:

Dastlab tub ko’paytuvchilarga ajralishi kerak bo’lgan N sonini olamiz
x_i=F(x_i-1) va y_i=F(F(y_i-1)) kabi funksiyalardan foydalanamiz, i- bu yerda 1 dan boshlanadi x₀=2 y₀=2 deb hisoblanadi

3 x_i va y_i larni undan oldingi qiymatlarga qarab topib ketavermiz va har safar EKUB(|x_i- y_i|,N) ni topib boramiz.

Bu jarayonlarni EKUB(|x_i- y_i|,N)!=1 bo’lgancha davom ettiramiz. 1 dan boshqa son chiqsa bu amallar to’xtatiladi.
F(x)=(x²+1)modN va F(x)=(x²+3) ikkala funksiya uchun ham shunday davom ettiriladi. Topilgan ekub(|x_i- y_i|,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:

Download 0,71 Mb.

1 2 3

Download 0,71 Mb.