A New Method for Computing DLP Based on Extending Smooth Numbers to Finite Field for Ephemeral Key Recovery

Abstract

In this paper, new algorithms to solve certain special instances of the Discrete Logarithm Problem (DLP) is presented. These instances are generally considered hard in literature. If a cryptosystem is based on a prime p such that p − 1 is either 2q with q a prime; or 2ρ where ρ = γ1γ2...γkq with γs being small prime factors and q a large prime factor, and the exponent is chosen in the middle of the group (or a prime-order subgroup), we show that it is vulnerable. In other words, the attacks proposed in this paper are analogous to the attacks for factoring large numbers when the factors lie near the square-root. The main idea is to generalize the concept of a smooth number and extend it over factor bases and multiplicative groups Z∗ p. We show that for careful selection of factor bases, patterns form in the distribution of such generalized smooth numbers which may be exploited in the attacks. Our algorithms are empirically tested on several hundred problems with sizes ranging from 100– 1024 bits and the average running times show the performance of the newly developed attacks. Also, the key recovery attack proposed on Chang and Chang novel three party simple key exchange protocol is mounted by recovering the ephemeral keys. The ephemeral keys are recovered by solving DLP using the new algorithms proposed in the present study.