The subset search algorithm: A new attack on the discrete logarithm problem over finite fields and elliptic curves

The security of the new information society that exchange data via modern intelligent communication systems is nowadays very essential because of public connectivity and the related threads (espionage or sabotage etc.). Many security product and specially cryptographic systems (e.g., RSA, ElGamal, Diffie-Hellman, Elliptic Curves cryptosystems, etc. ) was invented to encrypt and decrypt data, where the security of such cryptosystems are based on the apparent intractability of solving some number theoretic problems (e.g., The Discrete Logarithm Problem, Integer Factorization Problem, Diffie-Hellman Problem, Quadratic Residuosity Problem, Knapsack problem, etc.). Such problems are generally considered as being difficult to solve if the associated parameters are carefully chosen. The Discrete Logarithm Problem (DLP) on finite fields can be defined as followed: If we assume Zp (denotes the set of integers {0, 1, 2, ...., p - 1}, where addition and multiplication are performed modulo p) is a finite cyclic group of order p, where α a generator of Zp and β∈Zp, then the Discrete Logarithm of β to the base α, denoted loga β, is the unique integer x, 0 ≤ x ≤ p-1, such that β = αx. Many years this problem was studied but no known polynomial-time algorithm for solving the Discrete Logarithm Problem (DLP) has been found. This study introduce a new attack on the Discrete Logarithm Problem over finite fields- ( F*2f, F*pf, F ≥ 1, p prime) and elliptic curves groups; this attack is more significant on elliptic curves groups, where the group size is much more smaller compared to finite fields groups because there is no known sub-exponential algorithm for computing the discrete logarithm problem on elliptic curves unlike the discrete logarithm problem over finite fields. This attack is similar to Shanks Baby-step Giant-step algorithms but contains some differences, e.g., the new algorithm requires 50% less memory usage and thus the discrete logarithm can be found faster. The Shank Baby-step Giant-step algorithm is consider as the one of the best algorithms of solving the DLP over elliptic curves, this fact give the new attack a cryptographic importance. © 2006 Asian Network for Scientific Information.