Rossiya Federatsiyasi Ta'lim va fan vazirligi Oliy kasbiy ta'lim davlat ta'lim muassasasi

2 EL-GAMAL SXEMASI ALGORITMINI HIMOYA QILISh

Avvalroq biz ElGamal elektron raqamli imzo algoritmi diskret logarifm masalasiga asoslanganligi va uning ayrim modifikatsiyalari faktorizatsiya muammosi bilan bog‘liqligini aytib o‘tgan edik. Keling, ushbu muammolarning har birini batafsil ko'rib chiqaylik, shuningdek ularni hal qilishning mavjud usullarini tavsiflaymiz.

2.1 Diskret logarifm masalasi

ElGamal algoritmining kriptografik kuch omillaridan biri bu eksponensial funktsiyani invertatsiya qilishning yuqori hisoblash murakkabligidir. Shu bilan birga, eksponensial funktsiyaning o'zi juda sodda tarzda hisoblanadi, diskret logarifmni hisoblash algoritmlari esa yuqori hisoblash murakkabligiga ega.
Diskret logarifm masalasini tasvirlaylik.
G qandaydir guruh, b esa uning elementlari bo‘lsin. b elementining a asosiga diskret logarifmi b \u003d a ^{x tengligi to'g'ri bo'lgan har qanday butun x sondir} . E'tibor bering, b ning a asosiga diskret logarifmi, agar b a tomonidan yaratilgan kichik guruhning elementi bo'lsa, aniqlanadi. Agar a cheksiz tartibli element bo'lsa, u holda bu logarifm yagona aniqlanadi va agar a ning tartibi chekli bo'lsa va m ga teng bo'lsa, u holda logarifm m ga karrali bo'lgan davrgacha aniqlanadi.Diskret logarifm masalasi. G guruhi a asosiga qandaydir diskret b logarifmini topishdir.
Diskret logarifmni topishning turli usullari mavjud, ulardan ba'zilari universaldir, boshqalari esa ma'lum bir guruhning o'ziga xos xususiyatlaridan foydalanadi. Keling, ulardan ba'zilarini ko'rib chiqaylik.
Go‘dakning qadami – devning qadami. Diskret logarifmni hisoblash usuli "Chaqaloq qadami - gigant qadami" birinchilardan bo'lib, bu muammoni nafaqat sanab o'tish orqali hal qilish mumkinligini isbotladi.
“Bolaning qadami - devning qadami” diskret logarifmini hisoblash usulini batafsilroq yozamiz . Ikkita sonni oling m, K E Z lmk > p. Ikki qator raqamlarni hisoblaymiz:

a, d a, d ² a, ... ,d ^T - ¹ a (mod p) d ^t , d ^2t

'1' endi shunday i va j, h'r0 g ^L a = g ^Ĉm va x = jm - E ni topamiz.
P modulini hisoblang: