Movatterモバイル変換

[0]ホーム

Jump to content

Discrete logarithm

Edit links

From Wikipedia, the free encyclopedia

Problem of inverting exponentiation in groups

Discrete logarithm modulo 5, with base 2.

Inmathematics, for givenreal numbers $a {\displaystyle a}$ and $b {\displaystyle b}$ , thelogarithm $\log _{b}(a)$ is a number $x {\displaystyle x}$ such that $b^{x}=a$ . Thediscrete logarithm generalizes this concept to acyclic group. A simple example is the group ofintegers modulo a prime number (such as 5) undermodular multiplication of nonzero elements.

For instance, take $b=2$ in the multiplicative group modulo 5, whose elements are ${1,2,3,4}$ . Then: $2^{1}=2,\quad 2^{2}=4,\quad 2^{3}=8\equiv 3{\pmod {5}},\quad 2^{4}=16\equiv 1{\pmod {5}}.$ The powers of 2 modulo 5 cycle through all nonzero elements, so discrete logarithms exist and are given by: $\log _{2}1=4,\quad \log _{2}2=1,\quad \log _{2}3=3,\quad \log _{2}4=2.$

More generally, in anygroup $G {\displaystyle G}$ , powers $b^{k}$ can be defined for allintegers $k {\displaystyle k}$ , and thediscrete logarithm $\log _{b}(a)$ is an integer $k {\displaystyle k}$ such that $b^{k}=a$ . Inarithmetic modulo an integer $m {\displaystyle m}$ , the more commonly used term isindex: One can write $k=\mathbb {ind} _{b}a{\pmod {m}}$ (read "the index of $a {\displaystyle a}$ to the base $b {\displaystyle b}$ modulo $m {\displaystyle m}$ ") for $b^{k}\equiv a{\pmod {m}}$ if $b {\displaystyle b}$ is aprimitive root of $m {\displaystyle 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, along with its application, was first proposed in theDiffie–Hellman problem. Several importantalgorithms inpublic-key cryptography, such asElGamal, base their security on thehardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution,^[1] and in a generalblack box group lacks asubexponential solution at all.^[2]

Definition

[edit]

Let $G {\displaystyle G}$ be any group. Denote itsgroup operation by multiplication and itsidentity element by $1 {\displaystyle 1}$ . Let $b {\displaystyle b}$ be any element of $G {\displaystyle G}$ . For any positive integer $k {\displaystyle k}$ , the expression $b^{k}$ denotes the product of $b {\displaystyle b}$ with itself $k {\displaystyle k}$ times:^[3]

b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{factors}}}.

Similarly, let $b^{-k}$ denote the product of $b^{-1}$ with itself $k {\displaystyle k}$ times. For $k=0$ , the $k {\displaystyle k}$ ^th power is the identity: $b^{0}=1$ .

Let $a {\displaystyle a}$ also be an element of $G {\displaystyle G}$ . An integer $k {\displaystyle k}$ that solves the equation $b^{k}=a$ is termed adiscrete logarithm (or simplylogarithm, in this context) of $a {\displaystyle a}$ to the base $b {\displaystyle b}$ . One writes $k=\log _{b}a$ .

Examples

[edit]

Powers of 10

[edit]

Thepowers of 10 are

\ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .

For any number $a {\displaystyle a}$ in this list, one can compute $\log _{10}a$ . For example, $\log _{10}{10000}=4$ , and $\log _{10}{0.001}=-3$ . These are instances of the discrete logarithm problem.

Other base-10 logarithms in the real numbers are not instances of the discrete logarithm problem, because they involve non-integer exponents. For example, the equation $\log _{10}{53}=1.724276\ldots$ means that $10^{1.724276\ldots }$ . While integer exponents can be defined in any group using products and inverses, arbitrary real exponents, such as this 1.724276…, require other concepts such as theexponential function.

Ingroup-theoretic terms, the powers of 10 form acyclic group $G {\displaystyle G}$ under multiplication, and 10 is agenerator for this group. The discrete logarithm $\log _{10}a$ is defined for any $a {\displaystyle a}$ in $G {\displaystyle G}$ .

Powers of a fixed real number

[edit]

A similar example holds for any non-zero real number $b {\displaystyle b}$ . The powers form a multiplicativesubgroup $G=\{\ldots ,b^{-2},b^{-1},1,b^{1},b^{2},\ldots \}$ of the non-zero real numbers. For any element $a {\displaystyle a}$ of $G {\displaystyle G}$ , one can compute $\log _{b}a$ .

Modular arithmetic

[edit]

One of the simplest settings for discrete logarithms is the groupZ_p^×. This is the group of multiplicationmodulo theprime $p {\displaystyle p}$ . Its elements are non-zerocongruence classes modulo $p {\displaystyle p}$ , and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo $p {\displaystyle p}$ .

The $k {\displaystyle k}$ ^thpower of one of the numbers in this group may be computed by finding its ' $k {\displaystyle k}$ ^th power as an integer and then finding the remainder after division by $p {\displaystyle p}$ . When the numbers involved are large, it is more efficient to reduce modulo $p {\displaystyle p}$ multiple times during the computation. Regardless of the specific algorithm used, this operation is calledmodular exponentiation. For example, considerZ₁₇^×. To compute $3^{4}$ in this group, compute $3^{4}=81$ , and then divide $81 {\displaystyle 81}$ by $17 {\displaystyle 17}$ , obtaining a remainder of $13 {\displaystyle 13}$ . Thus $3^{4}=13$ in the groupZ₁₇^×.

The discrete logarithm is just the inverse operation. For example, consider the equation $3^{k}\equiv 13{\pmod {17}}$ . From the example above, one solution is $k=4$ , but it is not the only solution. Since $3^{16}\equiv 1{\pmod {17}}$ —as follows fromFermat's little theorem— it also follows that if $n {\displaystyle n}$ is an integer then $3^{4+16n}\equiv 3^{4}\cdot (3^{16})^{n}\equiv 3^{4}\cdot 1^{n}\equiv 3^{4}\equiv 13{\pmod {17}}$ . Hence the equation has infinitely many solutions of the form $4+16n$ . Moreover, because $16 {\displaystyle 16}$ is the smallest positive integer $m {\displaystyle m}$ satisfying $3^{m}\equiv 1{\pmod {17}}$ , these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that $k\equiv 4{\pmod {16}}$ .

Powers of the identity

[edit]

In the special case where $b {\displaystyle b}$ is the identity element $1 {\displaystyle 1}$ of the group $G {\displaystyle G}$ , the discrete logarithm $\log _{b}a$ is undefined for $a {\displaystyle a}$ other than $1 {\displaystyle 1}$ , and every integer $k {\displaystyle k}$ is a discrete logarithm for $a=1$ .

Properties

[edit]

Powers obey the usual algebraic identity $b^{k+l}=b^{k}\cdot b^{l}$ .^[3] In other words, thefunction

f\colon \mathbf {Z} \to G

defined by $f(k)=b^{k}$ is agroup homomorphism from the group of integers $\mathbf {Z}$ under additiononto thesubgroup $H {\displaystyle H}$ of $G {\displaystyle G}$ generated by $b {\displaystyle b}$ . For all $a {\displaystyle a}$ in $H {\displaystyle H}$ , $\log _{b}a$ exists.Conversely, $\log _{b}a$ does not exist for $a {\displaystyle a}$ that are not in $H {\displaystyle H}$ .

If $H {\displaystyle H}$ isinfinite, then $\log _{b}a$ is also unique, and the discrete logarithm amounts to agroup isomorphism

\log _{b}\colon H\to \mathbf {Z} .

On the other hand, if $H {\displaystyle H}$ isfinite oforder $n {\displaystyle n}$ , then $\log _{b}a$ is 0 unique only up tocongruence modulo $n {\displaystyle n}$ , and the discrete logarithm amounts to a group isomorphism

\log _{b}\colon H\to \mathbf {Z} _{n},

where $\mathbf {Z} _{n}$ denotes the additive group of integers modulo $n {\displaystyle n}$ .

The familiar base change formula for ordinary logarithms remains valid: If $c {\displaystyle c}$ is another generator of $H {\displaystyle H}$ , then

\log _{c}a=\log _{c}b\cdot \log _{b}a.

Algorithms

[edit]

Unsolved problem in computer science

Can the discrete logarithm be computed in polynomial time on a classical computer?

More unsolved problems in computer science

The discrete logarithm problem is considered to be computationally intractable. For a classical (e.g., non-quantum) computer, no efficient (polynomial-time) algorithm is yet known for computing discrete logarithms in general.

A general algorithm for computing $\log _{b}a$ in finite groups $G {\displaystyle G}$ is to raise $b {\displaystyle b}$ to larger and larger powers $k {\displaystyle k}$ until the desired $a {\displaystyle a}$ is found. This algorithm is sometimes calledtrial multiplication. It requiresrunning time linear in the size of the group $G {\displaystyle G}$ and thusexponential in the number of digits in the size of the group. Therefore, it is an exponential-time algorithm, practical only for small groups $G {\displaystyle G}$ .

More sophisticated algorithms exist, usually inspired by similar algorithms forinteger factorization. These algorithms run faster than the naïve algorithm, some of them proportional to thesquare root of the size of the group, and thus exponential in half the number of digits in the size of the group. However, none of them runs inpolynomial time (in the number of digits in the size of the group).

Baby-step giant-step
Function field sieve
Index calculus algorithm
Number field sieve
Pohlig–Hellman algorithm
Pollard's rho algorithm for logarithms
Pollard's kangaroo algorithm (aka Pollard's lambda algorithm)

There is an efficientquantum algorithm due toPeter Shor.^[4]

Efficient classical algorithms also exist in certain special cases. For example, in the group of the integers modulo $p {\displaystyle p}$ under addition, the power $b^{k}$ becomes a product $b\cdot k$ , and equality means congruence modulo $p {\displaystyle p}$ in the integers. Theextended Euclidean algorithm finds $k {\displaystyle k}$ quickly.

WithDiffie–Hellman, a cyclic group modulo a prime $p {\displaystyle p}$ is used, allowing an efficient computation of the discrete logarithm with Pohlig–Hellman if the order of the group (being $p-1$ ) is sufficientlysmooth, i.e. has no largeprime factors.

Comparison with integer factorization

[edit]

While computing discrete logarithms and integer factorization are distinct problems, they share some properties:

both are special cases of thehidden subgroup problem forfinite abelian groups,
both problems seem to be difficult (no efficient algorithms are known for non-quantum computers),
for both problems efficient algorithms on quantum computers are known,
algorithms from one problem are often adapted to the other, and
the difficulty of both problems has been used to construct variouscryptographic systems.

Cryptography

[edit]

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups $\mathbf {Z} _{p}^{\times }$ ) there is not only no efficient algorithm known for the worst case, but theaverage-case complexity can be shown to be about as hard as the worst case usingrandom self-reducibility.^[5]

At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently usingexponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries (and other possiblyone-way functions) have been exploited in the construction of cryptographic systems.

Popular choices for the group $G {\displaystyle G}$ in discrete logarithm cryptography (DLC) are the cyclic groups $\mathbf {Z} _{p}^{\times }$ (e.g.ElGamal encryption,Diffie–Hellman key exchange, and theDigital Signature Algorithm) and cyclic subgroups ofelliptic curves overfinite fields (seeElliptic curve cryptography).

While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of thenumber field sieve algorithm only depend on the group $G {\displaystyle G}$ , not on the specific elements of $G {\displaystyle G}$ whose finite $\log$ is desired. Byprecomputing these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group.^[6]

It turns out that muchinternet traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in RFC 2409.^[7] TheLogjam attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so calledexport grade.^[6]

The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large nationalintelligence agency such as the U.S.National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims inleaked NSA documents that NSA is able to break much of current cryptography.^[6]

References

[edit]

^Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1996)."Public-Key Encryption"(PDF).Handbook of Applied Cryptography (1 ed.). CRC Press. p. 294.doi:10.1201/9780429466335.ISBN 978-0-429-46633-5.
^Shoup...
^^a ^bLam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping, eds. (2001).Cryptography and Computational Number Theory. Basel: Birkhäuser Basel. pp. 54–56.doi:10.1007/978-3-0348-8295-8.eISSN 2297-0584.ISBN 978-3-0348-9507-1.ISSN 2297-0576.
^Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer".SIAM Journal on Computing.26 (5):1484–1509.arXiv:quant-ph/9508027.doi:10.1137/s0097539795293172.MR 1471990.S2CID 2337707.
^Blake, Ian F.; Garefalakis, Theo (2004-04-01)."On the complexity of the discrete logarithm and Diffie–Hellman problems".Journal of Complexity. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography.20 (2):148–170.doi:10.1016/j.jco.2004.01.002.ISSN 0885-064X.
^^a ^b ^cAdrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex;Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (2015-10-12)."Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice".Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM. pp. 5–17.doi:10.1145/2810103.2813707.ISBN 978-1-4503-3832-5.
^Harkins, D.; Carrel, D. (November 1998).The Internet Key Exchange (IKE) (Report). RFC Editor.doi:10.17487/rfc2409.

Rosen, Kenneth H. (2011).Elementary Number Theory and Its Application (6 ed.). Pearson. p. 368.ISBN 978-0321500311.
Weisstein, Eric W."Discrete Logarithm".MathWorld. Wolfram Web. Retrieved2019-01-01.

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL;KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms

v t e Computational hardness assumptions
Number theoretic	Integer factorization Phi-hiding RSA problem Strong RSA Quadratic residuosity Decisional composite residuosity Higher residuosity
Group theoretic	Discrete logarithm Diffie-Hellman Decisional Diffie–Hellman Computational Diffie–Hellman
Pairings	External Diffie–Hellman Sub-group hiding Decision linear
Lattices	Shortest vector problem (gap) Closest vector problem (gap) Learning with errors Ring learning with errors Short integer solution
Non-cryptographic	Exponential time hypothesis Unique games conjecture Planted clique conjecture

Movatterモバイル変換

Discrete logarithm

Definition

Examples

Powers of 10

Powers of a fixed real number

Modular arithmetic

Powers of the identity

Properties

Algorithms

Comparison with integer factorization

Cryptography

See also

References

Further reading