Tоshkеnt aхbоrоt tехnоlоgiyalari univеrsitеti kriptografiya 2 fanidan Loyiha ishi Bajardi: Ramazonov Asadbek, Ma’murjonov Zarifjon Mamaroziqov Muzaffar, Suyunov Davron, Tekshirdi: Mardiev Ulug’bek Toshkеnt – 2023

Ishning tartibi:

1. Sonni tub ko’paytiruvchilarga ajratib olish uchun dastlab N murakkab sonni tanlab olamiz chunki biz p va q ni topishimiz kerak.

   
   

2. Bunda biz quydagi xi=F(xi-1) va yi=F(F(yi-1)) lardan foydalanamiz buyerda i =1 dan boshlanadi va algoritimga ko’ra = =2 ga teng deb xisoblaymiz .

   
   

3. Topiladigan xi va yi larni har safar F(x)=(x^2 +1) modn yoki F(x)=(x^2 +3)modn formulaga qo’yib xi va yi larni ketma-ket topib ketvuramiz .

   
   

4. Bu jarayon toki EKUB(|xi- yi |,N)!=1 ga teng bo’lguncha davom etaveradi agarda EKUB(|xi- yi |,N)=1 bo’lib qolsa kutilgan natijaga erishulmaguncha davom etaveramiz

   
   

5. Biz qachonki natijaga erishganimizda EKUB(|xi- yi |,N) va N/ EKUB(|xi- yi |,N)

   
   

lar N sonining tub ko’paytiruvchilari bo’ladi.

1-rasm. –algoritm ko’rinishi


Bizning masalamizda N quydagicha :


N=3521965691682498349894156297871351510003392837134480208222044 4753957752560806765915557404471872854222134926440656261548716 5251895509139075621688493447805478090729096096693340629223579 5059531555148850225316762953811321830535065868925602454064437 6849173366230815779694365269990430445181132796913932904941185 478344783047790284034086549612594449881
Endi biz bu qiymatimizni Pollard algoritimi bo’yicha yozilgan python kodimizga tashlaymiz va quydagi natijalarga ega bo’lamiz:

q ning qiymati kattaroq chiqganligi sababli ekranga sig’madi !!!

Bu python kod orqali biz p va q ning quydagi natijalariga erishdik:

p = 11365151311

q=3098916675463607780464997187815576730075083500253875509728393509987449436853939824819055985542685945691315261069317544145147650076096193873381229578315162636471554990075867196953886463799436128025387998564380005561829893471856363325810237480997216190372833199473422687391969948445254019618649486619663112858167628758971855278811478871

6. Endigi navbatda olingan p va q orqali (pq)=(p-1)(q-1) ni xisoblaymiz . Bundan maqsad yopiq kalit d ni topish.

   
   

7. Yopiq kalit d ni topish uchun e*d=1mod(n) formuladan foydalanamiz.

   
   

(pq)=(p-1)(q-1)=( 11365151311-1) *( 3098916675463607780464997187815576730075083500253875509728393509987449436853939824819055985542685945691315261069317544145147650076096193873381229578315162636471554990075867196953886463799436128025387998564380005561829893471856363325810237480997216190372833199473422687391969948445254019618649486619663112858167628758971855278811478871-1) =

35219656913726066823477955198248517912218351641269718581966569244229359050819316478703464647053798236592240494964946287647207645405766257486072655471399318230757746973197779072846490753641429087689066125142241539548838299788828795784168177318566611692369014625406861165796567743053211184351659913286291698858681670189622655275114694322417819700

(n) ni qiymatini dastur yordamida ko’rsatdik

Endigi navbatda d ni topish uchun yana python orqali yozgan kodimizga murojat qilamiz. (Bizda (n) bor !)

Bizdagi dastur kodida d quydagiga teng bo’ldi:

d=27554167400666442227141693957303450858494766982053226129563024014821733167716844130988033368149127927503455252732619604292770154308098529381622644673772941142341607955151589581489206408768436053116277636059297045291783056061043667641815386051465063724351686633329050651599667636443036712929530780077330885996935857235340683948318594412214914773

8. Va nihoyat biz d maxviy kalitni topvoldik endi biz bu kalit d yordamida M ochiq matyinni topamiz . M=C^dmodN bu yerda C-shifr matnga teng, N- modul qiymat va d- maxviy kalit.

   
   

Ochiq matinimiz M quydagiga teng bo’ldi:

M=30431515518975919430432425193963944787566618852518059630422654182762651118596234745142783706157764331211451119802894375038315809730886558266723414168261712839959341364309183315402701609168849334368738491762847355545199988827316686875653614079360792080463115125422634695623332985766189474569103300961471019305145580519826740747511778114316716357