Ephemeral key recovery using index calculus method

Abstract

Thepresentstudyinvestigates the problem of retrieving the ephemeral keys, which are used in the Discrete Logarithm Problem (DLP) based public key cryptosystems. The ephemeral key can be retrieved by solving the mathematical hard problem, namely DLP. The DLP defined over a prime field Z∗ p is considered in the present study. An efficient way of computing the DLPforretrieving the ephemeral key by using a newvariant ofIndex Calculus Method (ICM) when the factors of p − 1 are known and small is proposed. The PohligHellman is the best known method to solve the DLP on the prime field with factors of p−1 are small, whiletheICMisanefficientmethodforageneralDLP.TheICMhastwosteps,such as apre-computation andanindividuallogarithmcomputation. Inthepre-computationstep, the logarithmsofelementsofasubsetofagroup,whichisknownasafactorbaseiscomputed and in the individual logarithm step the DLP is computed with the help of pre-computed logarithms of factor base. Since the ephemeral keys are dynamic and changes for every session, once the logarithms of a subset of a group is known, the DLP for the ephemeral key can beobtained byusingtheindividual logarithm step. Therefore, an efficient way of solving the individual logarithm step is presented based on the newly proposed pre-computation method and the performance is analyzed on a comprehensive set of experiments. From the experimental results, it is observed that the individual logarithm (computation) step outperforms the Pohlig-Hellman method on some special cases. The property of generators of prime field is the main motivation for the current study.