Index calculus method based on smooth numbers of ±1 over Zp*

Abstract

The paper presents a variant of ICM on integer field when the factors of the group are known and small. This is achieved through the properties of Smooth numbers of ±1 over Z ∗ p . The ICM has two steps, such as a precomputation and an individual logarithm computation. The pre-computation step is to compute the logarithms of a subset of a group and the individual logarithm step is to find the DLP using the pre-computed logarithms.The algorithm presented in the paper for ICM is a combination of Pohlig-Hellman, which is the popular attack on the groups of order with all small factors and the traditional ICM. In the present study we show the substantial performance improvement of ICM for the problems of size upto ≈ 150 bits on Pentium 4 machine. The analysis presented in the paper is considered as useful to recover ephemeral keys used in the cryptosystems like text book ElGamal and Chang and Chang three party password key exchange protocol to name a few. One way of recovering the ephemeral key is to solve the DLP. Since the ephemeral keys are dynamic and change for every session, once the discrete logarithms of a subset of a group is known, the DLP for the ephemeral key can be obtained by using the individual logarithm step. Therefore, the ephemeral keys are recovered by using the individual logarithm step proposed in the present study