Research Article
Improvements to Shank`s Baby-step Giant-step Algorithm
Department of Computer Information Systems, Al-Ahliyya Amman University, Al Salt Road, POBox: 1 83, Amman 19328, Jordan
The dramatically growing number of the internet users, services and the demand for connectivity to the Internet resources has forced standards organizations (e.g., IAB, IETF, IETG, etc.)[1-4] to specify a huge set of security protocols, algorithms and applications that provides security services (confidentiality, authentication, integrity, etc.) which meets the need for secure communication.
There is no single mechanism that will provide all the security services just listed before or perform all the function, however, we can note at this point that here is one particular element that underlies most of the security mechanisms in use: cryptographic techniques or generally cryptography (science of data encryption and decryption).
Cryptography has a old and fascinating history. Kahns book The Codebreaker[5] describes a 4000 years historical overview from its limited use by the Egyptians until the twentieth century where it played a central role in war telecommunication. Today Cryptography enables you to securely store sensitive information or transmit it across insecure networks so that it cannot be read by anyone except the intended recipient. By using a powerful tool such as encryption we gain privacy, authenticity, integrity and limited access to data.
Cryptographic systems can be divided in conventional cryptography systems and public key cryptography systems. In conventional cryptography, also called secret-key or symmetric-key encryption, one key is used both for encryption and decryption. The development of computers and communications systems in the 1960s brought with many such cryptographic systems like Data Encryption Standard (DES), Triple Data Encryption Standard (3DES), Advanced Encryption Standard (AES), The International Data Encryption Algorithm (IDEA), Blowfish, RC5, CAST, etc.
Diffie and Hellman[6] published new directions in cryptography. This paper introduced the revolutionary concept of public-key cryptography and solved many weaknesses and problems in private key cryptography e.g., key distribution and key management problem, user authentication, etc. Upon this, many public key cryptographic systems (e.g., RSA, ElGamal[7], Diffie-Hellman, Elliptic Curves (EC), Digital Signature Algorithm (DSA), etc.) were developed and the security of such cryptosystems are based on apparently difficult mathematical number theory problems like the discrete logarithm problem over finite fields, the discrete logarithm problem over elliptic curves, integer factorization problem, Diffie Hellman problem, Quadratic residuosity problem, etc.
PROBLEM DEFINITION
If p is a prime number, then Zp denotes the set of integers {0, 1, 2, ., p-1}, where addition and multiplication are performed modulo p. It is well-known that there exists a non-zero element α∈Zp such that each non-zero element in Zp can be written as a power of α; such an element α is called a generator of Zp. A group is called cyclic if such an element α exists.
A Field is a nonempty set F of elements with two operations + (called addition) and A (called multiplication) satisfying the following axioms: for all a, b, c ∈ F,
• | F is closed under + and i.e., a + b and aAb are in F; |
• | Commutative laws: a + b = b + a, a·b = b·a; |
• | Associative laws: (a + b) + c = a + (b + c), a· (b·c) = (a·b)·c; |
• | Distributive law: a·(b + c) = a·b + a·c. |
Furthermore, two distinct identity elements 0 and 1 (called the additive and multiplicative identities, respectively) must exist in F satisfying
• | a + 0 = a for all a∈F; |
• | a·1 = a and a·0 = 0 for all a∈F; |
• | For any a in F, there exists an additive inverse element (a) in F such that a + (a) = 0; |
• | For any a≠0 in F, there exists a multiplicative inverse element a-1 in F such that a·a-1 = 1. |
Finite field of prime order or prime power q is commonly denoted Fq or GF(q) (for Galois field) and because Zm is a field if and only if m is a prime, we denote the field Zm by Fm. This is called a prime field.
Now the Discrete Logarithm Problem can be defined as followed: If we assume Zp is a finite cyclic group of order p, where, α a generator of Zp and y∈Zp. Then the discrete logarithm of y to the base α, denoted logαy, is the unique integer x, 0≤x≤ p-1, such that y = αx[8].
The Discrete Logarithm Problem (DLP) in Zp has been the object of much study. The problem is generally regarded as being difficult if field parameters are carefully chosen. In particular, there is no known polynomial-time algorithm for the Discrete Logarithm problem. There are two types of algorithms for solving the discrete logarithm problem. Special-purpose algorithms[9] attempt to exploit special features of the prime p. In contrast, the running times of general-purpose algorithms (e.g., exhaustive search, Shanks Baby step Giant step, Pohlig Hellman[10], Pollards rho algorithm[11], Index Calculus method, Number field Sieve etc.) depend only on the size of p. The fastest general-purpose algorithms known for solving the discrete logarithm problem are based on a method called the index-calculus and the best current algorithm known for the DLP is the number field sieve[12]. To thwart these attacks, p should have at least 150 digits and p-1 should have at least one large prime factor. The utility of the discrete logarithm problem in a cryptographic setting is that finding discrete logs is (probably) difficult, but the inverse operation of exponentiation can be computed efficiently (e.g., the square-and-multiply method), this property is known in number theory as trapdoor or one-way function.
In this paper I describe improvements to Shanks baby-step giant-step algorithm[13] for computing the discrete logarithm x of an element y (where, y = αx mod p, y∈Zp, α generator of and p is prime).
SHANKS BABY-STEP GIANT-STEP ALGORITHM
The Baby-Step Giant-Step Algorithm for finding the discrete logarithm x in finite fields Zp (where, α generator of a cyclic group Zp of order p, an element, αx = β, β∈Zp) can be described as followed:
• | Set m _←|p| | |
• | Construct a table with entries (j,αj) for 0≤j<m. Sort this table by second component. | |
• | Compute α-m and set γ←β | |
• | For i from 0 to m-1 do the following: | |
i | Check if γ is the second component of some entry in the table | |
ii | If γ = αj then return (x = im + j). | |
iii | Set γ←γ*α-m |
This algorithm require storage for O(p) group elements, If we assume p = 10 300 ≈ 21000, follows that m = 10150.This means with 10150 pair of elements. If we assume that each entry (j,αj) cost 250 Bytes, we would need 2,5*10143 Gigabytes memory. A comparison: The universe contains 1077 Atoms.
The table takes O(p) multiplications to construct and O(p l g(p)) comparison to sort. After having constructed the table, step 4 takes O(p) multiplication and O(p) table look-ups.
Thus the algorithm can be implemented to run in O(p) time.
IMPROVEMENTS TO SHANKS ALGORITHM
List length : m (list length) can be assigned other values than Shanks step 1 propose. m can be assigned the maximum number of elements that can fits in user memory.
We set:
Then
Where, 0 < s < m
After (a + 1) iterations we get:
(a + 1)m = am + m > am + s = p |
This means that more than p elements of F*p will be tested, but:
am < am + s = p |
The maximum number of iteration is
Thus, the required number of iteration for algorithm determination is contrary proportional to the length of the table
THE SEARCHING ALGORITHM
The Shanks algorithm F*p makes at each for-iteration log2 (m+1) checks with a given element γ thus it is important that the table length equals a Mersenne-number Mn= 2n 1
A Mersenne List Ln (n>1) of length 2n-1 with sorted elements have the following properties:
• | Each Mersenne list has a middle element. His index is at 2n-1. |
• | All element right (left) from the middle element build also Mersenne list Ln-1 |
• | All 2n-1 Elements right (left) from the middle element are bigger (smaller) than the middle element |
The maximum number of searching step in a Mersenne List Ln requires maximum n steps.
Table STRUCTURE
Instead of storing two entries in proposed Shanks table (step 2), I suggest using one dimension array, this will allow saving 50% of memory usage and enable us working with longer table.
MODIFIED SHANKS ALGORITHM: The Modified Shanks Algorithm for finding the discrete logarithm x in finite fields Zp (where,α generator of a cyclic group Zp of order p, an element β, αx = β, β∈Zp) can be described as followed:
Step 1: | Choose m as described in 5.1 | |
Step 2: | Construct a one dimension array A1 with entry | |
Step 3: | Sort this table by αj. | |
Step 4: | Compute α-m and set γ←β | |
Step 5: | For i from 0 to m-1 do the following: | |
5.1 | Calculate jx out of A1 | |
5.2 | Check if γ is equal in the array A1 (using binary search) | |
5.3 | If then return (x = im + jx). | |
5.4 | Set γ←γ*α-m |
THE FIELDS WITH THE CHARACTERISTIC 2
Fields of characteristic 2 are often used because of many suitable properties. First they enable easily implementation in hardware. AND, OR, XOR, operation on {1, 0} alphabet can be done fast, Addition and Subtraction are identical, Quadratic operation can be done very fast and they also enable efficient usage of memory bits.
Let p be a prime number and let f∈Z+. The field (unique up to isomorphism) with pf elements is called the Galois field of order q = pf, denoted by GF (pf).
If q = 2f is the order of a field Fq, then all fields elements are polynomials of the form:
Where, each and ai ∈{0,1} a generator of Fq. These polynomials can then be stored on computer in the form:
Each ai require only one bit, thus for storing of one Fq field element, f bits will be required and for sorting these element we could consider their binary form.
THE FIELDS OF ORDER q = pf (where, p>2, f >1)
If q = pf is the order of a field Fq, then all elements are polynomials of the form:
Where, each ai ∈ {0,1, ,p-1}and α a generator of Fq. These polynomials can then be stored on computer in the form:
Where, each ai would require [log2p] bits, thus for storing one Fq field element f*[log2p] bits are required. And for sorting fields element we could consider their binary form.
The security of public-key cryptographic systems is often based upon a single computationally hard problem (e.g. the discrete logarithm problem) however; they will no longer be secure if the corresponding hard problem is solved in the future.
Recently Quantum computers are often discussed as one of the most long-term threads to discrete logarithm cryptographic systems. Such machines could compute the discrete logarithm problem in polynomial time[14].
This technology is still at the beginning and thus it is expected that many years are needed to build such machine.
Second thread comes from Special purpose hardware devices for solving the discrete logarithm problem. It is unlikely that this approach will have impact, due to Pomerance experiment[15] of using internet computing power of some idle systems to solve factorization problems.
Other threads concern general purpose algorithms. The best known algorithm for solving the discrete logarithm problem for any finite field groups is the index calculus method, unfortunately it can not be transformed for elliptic curves groups, the best known algorithm for any other finite abelian group (such as elliptic curves) one can use the Pollard techniques[16], Shanks Baby step Giant step algorithm[17].
This study discussed new improvements that makes Shanks algorithm practically (using appropriate table length) and faster (using Mersenne list) with up to 50% less memory usage, it can also be implemented on finite fieldsand other abelian groups e.g. elliptic curves, this attack is much more significant on elliptic curves groups, where the group size is much more smaller compared to finite fields groups, but the calculation of the discrete logarithm x in F*p where, p have alt least 150 digits and p-1 have at least one large prime factor, will stay hard.
Many years of study did not show new algorithms for solving the discrete logarithm problem in general, but maybe in future new mathematic insights will allow the definition of new attacks that can generally solve the Discrete Logarithm Problem in reasonable time and for any given parameter.