Gelfond - Shanks Algorithm

The Gelfond - Shanks algorithm ( English Baby-step giant-step ; also called the algorithm of large and small steps ) - in group theory, the deterministic discrete logarithm algorithm in the mulplicative group of the residue ring modulo a prime number. It was proposed by the Soviet mathematician Alexander Gelfond in 1962 and Daniel Shanks in 1972 ^[1] ^[2] ^[3] .

The method theoretically simplifies the solution of the discrete logarithm problem, on the computational complexity of which many public-key cryptosystems are built. Refers to meeting methods in the middle .

Content

Scope

The discrete logarithm problem is of great interest for building public key cryptosystems . Cryptographic algorithms such as RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin and others are based on the assumption of extremely high computational complexity for solving this problem. In them, the cryptanalyst can get the private key by taking the discrete logarithm of the public key (known to everyone), and using it to convert the ciphertext into the message text. However, the more difficult it is to find it (the more operations you need to do to find the discrete logarithm), the more stable is the cryptosystem. One way to increase the complexity of the discrete logarithm problem is to create a cryptosystem based on a group with a large order (where the logarithm will take place modulo a large prime). In the general case, such a problem is solved by exhaustive search , the same algorithm allows in some cases to simplify finding the exponent (reduce the number of steps) when calculating modulo a prime number, in the most favorable case, by the square root of the times ^[4] , but this reduction is still not enough to solve the problem on a computer in a reasonable time (the question of solving the discrete logarithm problem in polynomial time on a personal computer remains open so far) ^[5] .

Discrete Logarithm Problem

Daniel Shanks is a mathematician who proposed the Gelfond-Shanks algorithm in 1972.

Alexander Osipovich Gelfond - a mathematician who proposed the Gelfond - Shanks algorithm in 1962.

Let a cyclic group be given $G$ ${\ displaystyle G}$ with generatrix $g$ ${\ displaystyle g}$ containing $n$ ${\ displaystyle n}$ elements. Integer $x$ ${\ displaystyle x}$ (in the range from $0$ ${\ displaystyle 0}$ before $n-1$ ${\ displaystyle n-1}$ ) is called the discrete logarithm of the element $h\in G$ ${\ displaystyle h \ in G}$ on the basis of $g$ ${\ displaystyle g}$ if the relation holds:

g^{x}=h.

{\ displaystyle g ^ {x} = h.}

The discrete logarithm problem is given $h$ ${\ displaystyle h}$ , $g$ ${\ displaystyle g}$ to determine $x$ ${\ displaystyle x}$ .

Formally, the discrete logarithm problem is posed as follows ^[6] :

{\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Output:}}\quad &x\in \mathbb {N} :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}

{\ displaystyle {\ begin {cases} {\ text {Input:}} \ quad & g, h, n \ in \ mathbb {N} \\ {\ text {Output:}} \ quad & x \ in \ mathbb {N }: \ g ^ {x} \ equiv h {\ pmod {n}} \\\ end {cases}}}

provided that $x$ ${\ displaystyle x}$ may not exist as well $n$ ${\ displaystyle n}$ can be either a prime or a compound.

Theory

The idea of the algorithm is to choose the optimal ratio of time and memory , namely, in an advanced search for the exponent.

Let a cyclic group be given $G$ ${\ displaystyle G}$ of order $n$ ${\ displaystyle n}$ group generator $\alpha$ ${\ displaystyle \ alpha}$ and some element of the group $\beta$ ${\ displaystyle \ beta}$ . The problem comes down to finding an integer $x$ ${\ displaystyle x}$ for which is executed

\alpha ^{x}=\beta \,.

{\ displaystyle \ alpha ^ {x} = \ beta \ ,.}

Gelfond - Shanks Algorithm Based on Representation $x$ ${\ displaystyle x}$ as $x=i\cdot m-j$ ${\ displaystyle x = i \ cdot mj}$ where $m=\left\lfloor {\sqrt {n}}\right\rfloor +1$ ${\ displaystyle m = \ left \ lfloor {\ sqrt {n}} \ right \ rfloor +1}$ , and brute force $1\leq i\leq m$ ${\ displaystyle 1 \ leq i \ leq m}$ and $0\leq j<m$ ${\ displaystyle 0 \ leq j <m}$ . Restriction on $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ follows from the fact that the order of the group does not exceed $m$ ${\ displaystyle m}$ , which means the indicated ranges are sufficient to obtain all possible $x$ ${\ displaystyle x}$ from a half-interval $\left[0;m\right)$ ${\ displaystyle \ left [0; m \ right)}$ . Such a representation is equivalent to equality

$\alpha ^{im}=\beta \alpha ^{j}\,.$ ${\ displaystyle \ alpha ^ {im} = \ beta \ alpha ^ {j} \ ,.}$

(one)

The algorithm precomputes $\alpha ^{im}$ ${\ displaystyle \ alpha ^ {im}}$ for different values $i$ ${\ displaystyle i}$ and saves them in a data structure that allows efficient search, and then iterates over all sorts of values $j$ ${\ displaystyle j}$ and checks if $\beta \alpha ^{j}$ ${\ displaystyle \ beta \ alpha ^ {j}}$ corresponds to some value $i$ ${\ displaystyle i}$ . Thus are the indices $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ which satisfy relation (1) and allow us to calculate the value $x=i\cdot m-j$ ${\ displaystyle x = i \ cdot mj}$ ^[7] .

Algorithm

Entrance : Cyclic group $G$ ${\ displaystyle G}$ of order $n$ ${\ displaystyle n}$ generator $\alpha$ ${\ displaystyle \ alpha}$ and some element $\beta$ ${\ displaystyle \ beta}$ .

Output : Number $x$ ${\ displaystyle x}$ satisfying $\alpha ^{x}=\beta$ ${\ displaystyle \ alpha ^ {x} = \ beta}$ .

$m$ ${\ displaystyle m}$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$ ${\ displaystyle \ left \ lfloor {\ sqrt {n}} \ right \ rfloor +1}$
Calculate $\gamma$ ${\ displaystyle \ gamma}$ ← $\alpha ^{m}$ ${\ displaystyle \ alpha ^ {m}}$ .
For anyone $i$ {\ displaystyle i} Where $0$ {\ displaystyle 0} < $i$ {\ displaystyle i} < $m$ {\ displaystyle m} :
1. Write to the table ( $i$ ${\ displaystyle i}$ , $\gamma$ ${\ displaystyle \ gamma}$ ) (see the section "Implementation")
2. $\gamma$ ${\ displaystyle \ gamma}$ ← $\gamma$ ${\ displaystyle \ gamma}$ • $\alpha ^{m}$ ${\ displaystyle \ alpha ^ {m}}$
For anyone $j$ {\ displaystyle j} Where $0$ {\ displaystyle 0} ≤ $j$ {\ displaystyle j} < $m$ {\ displaystyle m} :
1. Calculate $\alpha$ ${\ displaystyle \ alpha}$ .
2. Check if contained $\beta \alpha ^{j}$ ${\ displaystyle \ beta \ alpha ^ {j}}$ in the table.
3. If yes, return $i m$ ${\ displaystyle im}$ - $j$ ${\ displaystyle j}$ .
4. If not, continue to run cycle ^[1] ^[2] ^[7] .

Algorithm Justification

It is necessary to prove that the same elements in the tables necessarily exist, that is, there are such $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ , what $g^{mi}=\beta \cdot g^{j}=g^{x+j}$ ${\ displaystyle g ^ {mi} = \ beta \ cdot g ^ {j} = g ^ {x + j}}$ . This equality holds in the case $mi=x+j{\pmod {n}}$ ${\ displaystyle mi = x + j {\ pmod {n}}}$ , or $x=mi-j{\pmod {n}}$ ${\ displaystyle x = mi-j {\ pmod {n}}}$ . At $1\leq i\leq m$ ${\ displaystyle 1 \ leq i \ leq m}$ , $1\leq j\leq m$ ${\ displaystyle 1 \ leq j \ leq m}$ the inequality holds $0\leq mi-j\leq m^{2}-1$ ${\ displaystyle 0 \ leq mi-j \ leq m ^ {2} -1}$ . For different couples $(i_{1},j_{1})$ ${\ displaystyle (i_ {1}, j_ {1})}$ and $(i_{2},j_{2})$ ${\ displaystyle (i_ {2}, j_ {2})}$ we have $mi_{1}-j_{1}\neq mi_{2}-j_{2}$ ${\ displaystyle mi_ {1} -j_ {1} \ neq mi_ {2} -j_ {2}}$ , otherwise it would have turned out $m(i_{1}-i_{2})=(j_{1}-j_{2})$ ${\ displaystyle m (i_ {1} -i_ {2}) = (j_ {1} -j_ {2})}$ that with the indicated choice $i_{1},i_{2}$ ${\ displaystyle i_ {1}, i_ {2}}$ only possible if $i_{1}=i_{2}$ ${\ displaystyle i_ {1} = i_ {2}}$ , and therefore $j_{1}=j_{2}$ ${\ displaystyle j_ {1} = j_ {2}}$ . Thus expressions $mi-j$ ${\ displaystyle mi-j}$ accept all values ranging from $0$ ${\ displaystyle 0}$ before $m^{2}-1$ ${\ displaystyle m ^ {2} -1}$ which, due to the fact that $m^{2}>n$ ${\ displaystyle m ^ {2}> n}$ , contains all possible values $x$ ${\ displaystyle x}$ from $0$ ${\ displaystyle 0}$ before $n-1$ ${\ displaystyle n-1}$ . So for some $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ equality holds $x=mi-j{\pmod {n}}$ ${\ displaystyle x = mi-j {\ pmod {n}}}$ ^[2] .

Algorithm Estimation

Let's say you need to solve $h=ng$ ${\ displaystyle h = ng}$ where $h$ ${\ displaystyle h}$ and $g$ ${\ displaystyle g}$ - positive integers less $100$ ${\ displaystyle 100}$ . One way is to iterate over sequentially $n$ ${\ displaystyle n}$ from $one$ ${\ displaystyle 1}$ before $100$ ${\ displaystyle 100}$ comparing the value $n\cdot g$ ${\ displaystyle n \ cdot g}$ with $h$ ${\ displaystyle h}$ . In the worst case, we need $100$ ${\ displaystyle 100}$ steps (when $n=99$ ${\ displaystyle n = 99}$ ) On average, it will take $50$ ${\ displaystyle 50}$ steps. In another case, we can imagine $n$ ${\ displaystyle n}$ as $n=10a-b$ ${\ displaystyle n = 10a-b}$ . Thus, the task is to find $a$ ${\ displaystyle a}$ and $b$ ${\ displaystyle b}$ . In this case, you can rewrite the task as $h=(10a-b)g$ ${\ displaystyle h = (10a-b) g}$ or $h+bg=10ag$ ${\ displaystyle h + bg = 10ag}$ . Now we can iterate over all possible values $a$ ${\ displaystyle a}$ on the right side of the expression. In this case, these are all numbers from $one$ ${\ displaystyle 1}$ before $ten$ ${\ displaystyle 10}$ . These are the so-called big steps. It is known that one of the obtained values for $a$ ${\ displaystyle a}$ - desired. We can write all the values of the right side of the expression in the table. Then we can calculate the possible values for the left side for various values $b$ ${\ displaystyle b}$ . These are all numbers from $0$ ${\ displaystyle 0}$ before $9$ ${\ displaystyle 9}$ of which one is the desired one, and together with the correct value of the right part gives the desired result $n$ ${\ displaystyle n}$ . Thus, the task is reduced to enumerating various values of the left side and searching for them in the table. If the desired value in the table is found, then we found $b$ ${\ displaystyle b}$ , and therefore the corresponding $n=10a+b$ ${\ displaystyle n = 10a + b}$ . This illustration demonstrates the speed of the algorithm. Average performed $1.5{\sqrt {n}}$ ${\ displaystyle 1.5 {\ sqrt {n}}}$ operations. Worst case required $2{\sqrt {n}}$ ${\ displaystyle 2 {\ sqrt {n}}}$ operations ^[3] .

Example

Below is an example of solving a discrete logarithm problem with a small group order. In practice, groups with a higher order are used in cryptosystems to increase cryptographic stability .

Let it be known $5^{x}\equiv 3{\pmod {23}}$ ${\ displaystyle 5 ^ {x} \ equiv 3 {\ pmod {23}}}$ . First, create and fill in the table for the "big steps". Choose $m=5$ ${\ displaystyle m = 5}$ ← ( ${\sqrt {16}}+1$ ${\ displaystyle {\ sqrt {16}} + 1}$ ) Then $i$ ${\ displaystyle i}$ will pass from $one$ ${\ displaystyle 1}$ before $five$ ${\ displaystyle 5}$ .

$i$ ${\ displaystyle i}$	one	2	3	four	five
$5^{im}=20^{i}$ ${\ displaystyle 5 ^ {im} = 20 ^ {i}}$	20	9	nineteen	12	ten

Find a suitable value $j$ ${\ displaystyle j}$ for $3\cdot 5^{j}\ {\bmod {\ }}23$ ${\ displaystyle 3 \ cdot 5 ^ {j} \ {\ bmod {\}} 23}$ so that the values in both tables match

$j$ ${\ displaystyle j}$	one	2	3	four
$\beta \alpha ^{j}=3$ ${\ displaystyle \ beta \ alpha ^ {j} = 3}$ · $5^{j}$ ${\ displaystyle 5 ^ {j}}$	15	6	7	12

It can be seen that in the second table for $j=4$ ${\ displaystyle j = 4}$ , this value is already in the first table. We find $x=mi-j=5\cdot 4-4=16$ ${\ displaystyle x = mi-j = 5 \ cdot 4-4 = 16}$ ^[2] .

Implementation

There is a way to improve the performance of the Gelfond-Shanks algorithm. It consists in using an effective table access scheme. The best way is to use a hash table . You should hash the second component, and then search for the hash in the table in the main loop by $\gamma$ ${\ displaystyle \ gamma}$ . Since accessing and adding items to the hash table works in time $O(1)$ ${\ displaystyle O (1)}$ ( constant ), then asymptotically this does not slow down the algorithm.

The running time of the algorithm is estimated as $O({\sqrt {n}})$ ${\ displaystyle O ({\ sqrt {n}})}$ which is much better than work time $O(n)$ ${\ displaystyle O (n)}$ full enumeration of degree indicators ^[4] .

Features

The Gelfond – Shanks algorithm works for an arbitrary finite cyclic group ^[7] ^[3] .
No need to know group order $G$ ${\ displaystyle G}$ in advance. The algorithm also works if $n$ ${\ displaystyle n}$ Is the upper bound of the order of the group ^[7] .
Usually the Gelfond-Shanks algorithm is used for groups whose order is a prime . If the order is a composite number , then the use of the Polyg – Hellman algorithm ^{[7] is} recommended.
Gelfond - Shanks algorithm required $O(n)$ ${\ displaystyle O (n)}$ memory. It’s possible to choose less $m$ ${\ displaystyle m}$ in the first step of the algorithm. This increases the run time of the program to $O(n/m)$ ${\ displaystyle O (n / m)}$ . It is also possible to use the Pollard ρ-method for discrete logarithm , which works for the same time, but requires a small amount of memory ^[7] .

Notes

↑ ¹ ² D. Shanks. The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference. - University of Colorado, Boulder ,, 1972. - S. pp. 217-224. .
↑ ¹ ² ³ ⁴ I.A. Pankratova. Number-Theoretical Methods in Cryptography: A Training Manual. - Tomsk: TSU, 2009 .-- S. 90-98. - 120 s. .
↑ ¹ ² ³ V.I. Nechaev. Elements of cryptography. Fundamentals of information security theory. - M .: Higher School, 1999. - S. 61-67. - 109 p. - ISBN 5-06-003644-8 . .
↑ ¹ ² DC Terr. A modification of Shanks' baby-step giant-step algorithm . - Mathematics of Computation. - 2000. - T. 69. - S. 767–773. .
↑ Vasilenko O. N. Number-theoretic algorithms in cryptography . - Moscow: ICMMO, 2003 .-- S. 163-185. - 328 p. - ISBN 5-94057-103-4 . .
↑ Yan, Song Y. Primality testing and integer factorization in public-key cryptography . - 2. - Springer, 2009 .-- S. 257-260. - 374 p. - ISBN 978-0-387-77267-7 . .
↑ ¹ ² ³ ⁴ ⁵ ⁶ Glukhov M. M, Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Introduction to number-theoretic methods of cryptography. - 1st ed .. - St. Petersburg: Doe, 2010 .-- S. 279-298. - 400 p. with. - ISBN 978-5-8114-1116-0 . .

Literature

A.O. Gelfond, Yu.V. Linnik. Elementary methods in analytic number theory. - M .: Fizmatgiz, 1962 .-- 272 p.

[Шэнкс-1] ¹ ² D. Shanks. The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference. - University of Colorado, Boulder ,, 1972. - S. pp. 217-224. .

[Панкратова-2] ¹ ² ³ ⁴ I.A. Pankratova. Number-Theoretical Methods in Cryptography: A Training Manual. - Tomsk: TSU, 2009 .-- S. 90-98. - 120 s. .

[Нечаев-3] ¹ ² ³ V.I. Nechaev. Elements of cryptography. Fundamentals of information security theory. - M .: Higher School, 1999. - S. 61-67. - 109 p. - ISBN 5-06-003644-8 . .

[Terr-4] ¹ ² DC Terr. A modification of Shanks' baby-step giant-step algorithm . - Mathematics of Computation. - 2000. - T. 69. - S. 767–773. .

[5] Vasilenko O. N. Number-theoretic algorithms in cryptography . - Moscow: ICMMO, 2003 .-- S. 163-185. - 328 p. - ISBN 5-94057-103-4 . .

[6] Yan, Song Y. Primality testing and integer factorization in public-key cryptography . - 2. - Springer, 2009 .-- S. 257-260. - 374 p. - ISBN 978-0-387-77267-7 . .

[Глухов-7] ¹ ² ³ ⁴ ⁵ ⁶ Glukhov M. M, Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Introduction to number-theoretic methods of cryptography. - 1st ed .. - St. Petersburg: Doe, 2010 .-- S. 279-298. - 400 p. with. - ISBN 978-5-8114-1116-0 . .