Кіріспе
Шекті топтарда экспоненталауды кері қайтару мәселесі. Математикада, берілген нақты сандар a және b үшін, logb a логарифмі – 1 = bx = a теңдеуін қанағаттандыратын x саны болып табылады. Сол сияқты, кез келген G тобында, барлық бүтін сандар k үшін bk дәрежелерін анықтауға болады, ал дискретті логарифм logb a – 1 = bk = a теңдеуін қанағаттандыратын k бүтін саны болып табылады. Сандар теориясында, көбінесе «индекс» термині қолданылады: r – m-нің түпнұсқасы болса және gcd(a, m) = 1 болса, r^x ≡ a (mod m) үшін x = indr a (mod m) (оқылысы: «m модулі бойынша r негізінде a индексі») деп жазуға болады. Дискретті логарифмдер кейбір ерекше жағдайларда жылдам есептелуі мүмкін, бірақ оларды жалпы жағдайда есептеудің тиімді әдісі әзірленбеген. Криптографияда, дискретті логарифм мәселесінің есептеу күрделілігі және оның қолданылуы алғаш рет Диффи-Хеллман мәселесінде ұсынылды. ElGamal сияқты ашық кілтті криптографиядағы бірнеше маңызды алгоритмдер, дискретті логарифм мәселесінің (DLP) мұқият таңдалған топтарда тиімді шешімі жоқ деген қатаңдық туралы болжамға негізделген қауіпсіздікті қамтамасыз етеді.
In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that 1=bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that 1=bk = a. In number theory, the more commonly used term is index: we can write x = indr a (mod m) (read "the index of a to the base r modulo m") for r x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1. Discrete logarithms are quickly computable in a few special cases, however, no efficient method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem and its application, was first proposed in the Diffie–Hellman problem. Several important algorithms in public key cryptography, such as ElGamal, base their security on the hardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.
Анықтама
G кез келген топ болсын. Оның топтық операциясын көбейту арқылы және оның сәйкестік элементін 1 деп белгілейік. b – G тобының кез келген элементі болсын. Кез келген оң бүтін сан k үшін, bk өрнегі b-нің өзін k рет көбейту нәтижесін білдіреді:
Сол сияқты, b−k b−1-дің өзін k рет көбейту нәтижесін білдіреді. k = 0 болғанда, k-шы дәреже сәйкестік элементіне тең: 1=b0 = 1. a да G тобының бір элементі болсын. 1=bk = a теңдеуін шешетін k бүтін саны a-ның b негізіндегі дискретті логарифмі (немесе осы контексте логарифм) деп аталады. Оны k = logb a деп жазады.
Белгілі бір нақты санның күштері
Осыған ұқсас мысал кез келген нөлден өзге нақты сан b үшін де орынды. Дәрежелер нөлден өзге нақты сандардың G = {…, b−3, b−2, b−1, 1, b1, b2, b3, …} көбейтуші кіші тобын құрайды. G тобының кез келген a элементе үшін logb a есептелуі мүмкін.
Модульді арифметика
Дискретті логарифмдердің ең қарапайым жағдайларының бірі – Zp× тобы. Бұл p жай саны бойынша көбейту тобы. Оның элементтері – p модулі бойынша нөлге тең емес конгруэнция кластары, ал екі элементтің топтық көбейтіндісі элементтердің кәдімгі бүтін сан көбейтуі арқылы, содан кейін p модулі бойынша қысқарту арқылы алынуы мүмкін. Бұл топтағы сандардың k-шы дәрежесін бүтін сан ретінде k-шы дәрежесін тауып, содан кейін p-ге бөлгеннен кейін қалдықты табу арқылы есептеуге болады. Егер қатыстырылған сандар үлкен болса, есептеу кезінде p модулі бойынша бірнеше рет қысқарту тиімдірек болады. Қолданылатын нақты алгоритмге қарамастан, бұл операция модульдік дәрежелеу деп аталады. Мысалы, Z17× тобын қарастырайық. Бұл топта 34-ті есептеу үшін 34 = 81 есептейміз, содан кейін 81-ді 17-ге бөліп, 13 қалдық аламыз. Осылайша, Z17× тобында 34 = 13. Дискретті логарифм – кері операция. Мысалы, 3k ≡ 13 (mod 17) теңдеуін қарастырайық. Жоғарыдағы мысалда k = 4 бір шешім, бірақ бұл жалғыз шешім емес. Ферманың кіші теоремасынан 316 ≡ 1 (mod 17) шығады, сондықтан егер n бүтін сан болса, онда 34+16n ≡ 34 × (316)n ≡ 13 × 1n ≡ 13 (mod 17) да болады. Сондықтан теңдеуде 4 + 16n түріндегі шексіз көп шешімдер бар. Сонымен қатар, 16 – 3m ≡ 1 (mod 17) шартын қанағаттандыратын ең кіші оң бүтін сан m болғандықтан, осылар ғана шешімдер. Басқаша айтқанда, барлық мүмкін шешімдер жиынтығы k ≡ 4 (mod 16) шартымен беріледі.
The kth power of one of the numbers in this group may be computed by finding its kth power as an integer and then finding the remainder after division by p. When the numbers involved are large, it is more efficient to reduce modulo p multiple times during the computation. Regardless of the specific algorithm used, this operation is called modular exponentiation. For example, consider Z17×. To compute 34 in this group, compute 34 = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 34 = 13 in the group Z17×. The discrete logarithm is just the inverse operation. For example, consider the equation 3k ≡ 13 (mod 17). From the example above, one solution is k = 4, but it is not the only solution. Since 316 ≡ 1 (mod 17)—as follows from Fermat's little theorem—it also follows that if n is an integer then 34+16n ≡ 34 × (316)n ≡ 13 × 1n ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16n. Moreover, because 16 is the smallest positive integer m satisfying 3m ≡ 1 (mod 17), these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that k ≡ 4 (mod 16).
Жеке тұлғаның өкілеттігі
b G тобының бірлік элементі 1 болған ерекше жағдайда, дискретті логарифм logb a, a 1-ден өзгеше болса, анықталмайды, ал a = 1 болса, кез келген бүтін сан k дискретті логарифм болып табылады.
Қасиеттері
Қуаттар әдеттегі алгебралық сәйкестікке бағынады: bk + l = bk b l.
Кейбір ерекше жағдайларда тиімді классикалық алгоритмдер де бар. Мысалы, p модулі бойынша қосылған бүтін сандар тобында bk қуаты bk көбейтіндісіне айналады, ал теңдік бүтін сандардағы p модулі бойынша конгруэнттілікты білдіреді. Кеңейтілген Евклид алгоритмі k-ны жылдам анықтайды. Диффи–Хельманмен циклдық топ модулі ретінде жай сан p қолданылады, егер топтың реті (p-1) жеткілікті тегіс болса, яғни үлкен жай факторлары болмаса, Полиг–Хельманмен дискретті логарифмді тиімді есептеуге болады.
Криптография
Дискретті логарифмдерді есептеу қиын болатын топтар бар. Кейбір жағдайларда (мысалы, Zp× топтарының үлкен жай реттік кіші топтары) ең нашар жағдай үшін тиімді алгоритм белгілі емес, сонымен қатар орташа жағдайдың күрделілігі кездейсоқ өзін-өзі қысқарту арқылы ең нашар жағдаймен шамалас екені көрсетілуі мүмкін. Сонымен қатар, дискретті дәрежелеудің кері мәселесі қиын емес (мысалы, дәрежелеуді квадраттау арқылы тиімді есептеуге болады). Бұл асимметрия бүтін санды факторлау мен бүтін санды көбейту арасындағы асимметрияға ұқсас. Екі асимметрия да (және басқа да бір жақты функциялар) криптографиялық жүйелерді құруда пайдаланылды. Дискретті логарифм криптографиясында (DLC) G тобы үшін танымал таңдаулар – Zp× циклдік топтары (мысалы, ElGamal шифрлауы, Diffie–Hellman кілт алмасуы және Цифрлық қолтаңба алгоритмі) және шекті өрістердегі эллиптік қисықтардың циклдік кіші топтары (Эллиптік қисық криптографиясын қараңыз). Дискретті логарифм мәселесін жалпы жағдайда шешуге арналған жалпыға белгілі алгоритм болмаса да, сандық өріс ілгіші алгоритмінің алғашқы үш қадамы тек G тобына ғана байланысты, G тобының нақты элементтеріне емес, олардың дискретті логарифмін табуға қажет. Осы үш қадамды нақты топ үшін алдын ала есептеу арқылы, сол топта нақты логарифм алу үшін алғашқы үш қадамға қарағанда есептеу жағынан әлдеқайда аз шығынға түсетін соңғы қадамды орындау жеткілікті. Logjam шабуылы осы осалдықты пайдаланып, 512 биттік жай сан реті бар топтарды пайдалануға рұқсат берген, яғни экспорттық сападағы топтарды пайдаланып, түрлі интернет-қызметтерін бұзды.