Guruh talbasi Maxsudov Azamxon Yunusxo’ja o’g’li

8-amaliy mashg’ulot

Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.

Faktorlash muammosini bartaraf etuvchi Pollard usuli

1. 
   RSA algoritmiga asoslangan shifrlashga misol
   

Diffi va Xellman maxfiy uslubli bir tomonli funksiyaning aniqlanishiga asoslanib, maxfiy aloqa tizimi foydalanuvchilari uchun, o‘zlarining ochiq kalitli kriptosistema strukturasini (tuzilishini) taklif etdilar. har ^{bir i-foydalanuvchi biror Z}i ^{butun sonni (daraja ko‘rsatkichini) tanlaydi va uni maxfiy saqlaydi. So‘ngra, bu Z}i ^{asosida E}Zi ^{algoritm tuzib ochiq ma’lumotlar kitobiga bu algoritmni joylashtiradi. Bundan tashqari Z}i ^{asosida maxfiy saqlanadigan D}Zi ^{algoritmni ham tuzadi va uni sir tutadi. Agarda j-foydalanuvchi i-} foydalanuvchiga X maxfiy ma’lumotni uzatmoqchi bo‘lsa, u holda j-foydalanuvchi ochiq ma’lumotlar
^{kitobidan E}Zi ^{algoritmni olib, uslub bilan kriptogrammani tuzib (hosil qilib), i-} foydalanuvchiga jo‘natadi. Maxfiy ma’lumotni kriptogramma ko‘rinishida qabul qilib olgan i- ^{foydalanuvchi o‘zining maxfiy D}Zi ^{algoritmidan foydalanib uslub bilan ochiq matnni hosil qiladi. Agarda f}z ^{haqiqatan ham maxfiy uslubli bir tomonli funksiya bo‘lsa, u holda bu funksiya} asosida qurilgan algoritm shak-shubhasiz amaliy bardoshlilikni ta’minlaydi. Diffi va Xellman, agarda bir
^{tomonli f}z ^{funksiyaning aniqlanish sohasidagi daraja ko‘rsatkichining barcha qiymatlari to‘plami bilan, aynan shu funksiyaning qiymatlari to‘plami ustma-ust tushsa, ya’ni f}z ^{funksiyaning aniqlanish} sohasi bilan qiymatlar sohasi bir xil to‘plamni tashkil etsa, bunday bir tomonli funksiya asosida raqamli imzo olish mumkin. Agarda i-foydalanuvchi aloqa tizimi bo‘yicha maxfiy bo‘lmagan X ma’lumotni barcha foydalanuvchilarga etkazib, bu maxfiy bo‘lmagan ma’lumotni jo‘natuvchini ma’lumotni qabul

qilib oluvchilar tomonidan behato aniqlashlari uchun, o‘zining maxfiy algoritmi asosida

z
^{raqamli imzo qo‘yadi. har bir foydalanuvchi ochiq algoritm E}Zi ^{ni bilgan holda ni oladi,} lekin i-foydalanuvchidan boshqa foydalanuvchi X ma’lumotni kriptogramma ko‘rinishidagi raqamli imzo ifodasiga o‘tkaza olmaydi, chunki faqat i-foydalanuvchining o‘zigina ochiq ^{algoritm asoslangan f}z ^{funksiyaga teskari bo‘lib, maxfiy algoritm asosini tashkil etuvchi f-1 ni hisoblay} oladi. o‘z-o‘zidan tushinarliki, agarda i-foydalanuvchi j-foydalanuvchiga maxfiy ma’lumotni ham raqamli ^{imzo bilan jo‘natishi mumkin. Buning uchun, i-foydalanuvchi j-foydalanuvchining f}z ^{funksiyaga asoslangan ochiq algoritmi (ochiq shifrlash kaliti) E}Zi ^{dan foydalanib, jo‘natilishi kerak bo‘lgan} ma’lumotni shifrlaydi. Bu shifrlangan ma’lumotni qabul qilib olgan j-foydalanuvchi o‘zining f^-

z Zi
¹ funksiyaga asoslangan maxfiy D deshifrlash algoritmi bilan ochadi.

2.