|
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish. Ishdan maqsad
|
| Sana | 13.05.2024 | | Hajmi | 4,35 Kb. | | #228453 |
Bog'liq Mavzu Diskret logarifmlash muammosini bartaraf etuvchi dasturiy-hozir.org
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish. Ishdan maqsad
3-amaliy ish
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.
Ishdan maqsad: Diskret logarifmlash muammosi haqida haqidagi nazariy va amaliy bilim ko‘nikmalarni shakllantirish.
Nazariy qism
Chekli maydonda diskret logarifmlash muammosi. chekli siklik guruh berilgan boʼlsin va . Tenglikdan х nomalum butun sonni topish lozim va .
.
Bu yerda, butun son asosga ko’ra ning diskret logarifmi asosida hisoblanadi va u quyidagiga teng bo’ladi:
Misol: chekli siklik guruh berilgan boʼlsin va . Tenglikdan x nomalum butun sonni topish lozim.
.
va,
Diskret logorifmlash muammosiga qarshi xujumlar. Koʼpchilik ochiq kalitli kriptotizimlar siklik guruhdagi diskret logarifmning hisoblash murakkabligiga asoslangan. Yaʼni, toʼp lamda uchun ni hsoblash lozim:
Bu yerda, ayni bir guruhga tegishli. Diskret logarifmlash muammosiga qaratilgan hujumlar aynan uning hisoblash murakkabligiga asoslanadi. RSA algoritmi esa, faktorlash muammosiga asoslanadi.
Qoʼpol kuch hujumi (Brute-Force). Ushbu usul diskret logarifmni hisoblashning eng oson yoʼlini izlashga qaratilgan. soning darajasi soniga teng boʼlgancha quyidagicha hisoblanadi:
Tasodifiy x logarifmga ehtimolli x qiymatlarning yarmini hisoblash orqali erishishimiz mumkin. Бу kompleks natijasini berishi mumkin. Bu yerda, guruhning oʼlchami.
Ushbu hujumi oldini olish uchun guruh oʼlchamini katta tanlash lozim. Diffi-Helman kalitlarni almashish algoritmini oladigan boʼlsak, diskret logarifmni hisoblashning yarmiga teng boʼladi. Bu esa, hozirgi hisoblash texnologiyalari rivojlangan bir vaqtda ehtimoli mavjud.
Shenksning katta va kichik qadami (Baby-Step/ Giant-Step). Koʼp maʼlumolardan qoʼpol kuch qidiruvi uchun sarflanadigan vaqtni kamaytirishga qaratigan. qiymatini ikkita ifoda orqali tasvirlashga qaratilgan.
,
бу ерда .
qiymati G guruhning kvadrat ildizi asosida hisoblanadi. Unda diskret logarifmni quyidagicha ifodalashimiz mumkin:
Аlgoritmning maqsadi va ni hisoblashga qaratilgan.
ni hisoblashga qaratilgan. ning barcha qiymatlarini hisoblaymiz va saqlab qoʼyamiz. Bu yerda, . Bu kichik qadam hisoblanib, qadamlarini oʼz ichiga oladi.
Katta qadamda esa, boʼlishi mumkin boʼlgan barcha sonlarini hisoblaydi. Bu yerda, .
kichik qadamda hisoblangan va saqlangan. juftligi uchun tenglik oʼrinli boʼlsa,
Agar guruh tartibiga ega boʼlsa, unda kichik qadam asosida hisoblashlar va hotira talab etiladi.
Polig-Xelman algoritmi. Ushbu algoritm G guruhdagi diskret logarifmning hisoblash tezligi oshirish maqsadida qoʼllaniladi. ord(g) g elementini saralashni amalga oshirishini hisobga olsak, , quyidagi tenglikni hisobga olish lozim. ва бўлса, унда .
Isboti. . Bu yerda, ni saralash koʼpi bilan bo’ladi. Agar bo’lsa, ga teng va q soni g sonining saralangani sanaladi hamda mos holda, yoki shartlarni qanoatlantirilishi lozim.
Ushbu holatda qoldiqlar haqidagi xitoy teoremasidan foydalanish lozim. Аgar, barcha holatlar uchun va bo’lsa, unda
ва koʼrinishida ifodalanadi. Аlgoritmning hisoblash vaqti saralangan guruhdagi sonlarning tublik ehtimoliga bogʼliq. Ushbu hujumdan himoyalanish uchun oʼlchamidagi katta sonlardan foydalanish lozim. Аlgoritmning ahamiyatli jihati shundaki, u guruhdagi tub sonlarning faktorlash muammosini aniqlashga qaratilgan. Ushbu holatda elleptik egri chiziqlar samarali, ammo siklik guruhlarni saralash oson hisoblanadigan jarayon emas.
Topshiriq
Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.
Nazorat savollari
Diskret logarifmlash muammosini izohlang.
Diskret logarifmlashga qaratilgan qanday hujumlar mavjud.
Polig – Xelman algoritmi qanday maqsadda qo’llaniladi.
http://hozir.org
|
| |
