Cryptology ePrint Archive: Report 2017/055
A Probabilistic Baby-Step Giant-Step Algorithm
Prabhat Kushwaha and Ayan Mahalanobis
Abstract: In this paper, a new algorithm to solve the discrete logarithm problem is presented which is similar to the usual baby-step giant-step algorithm. Our algorithm exploits the order of the discrete logarithm in the multiplicative group of a finite field. Using randomization with parallelized collision search, our algorithm indicates some weakness in NIST curves over prime fields which are considered to be the most conservative and safest curves among all NIST curves.
Category / Keywords: public-key cryptography / Discrete logarithm problem, baby-step giant-step algorithm, NIST curves over prime fields, parallelized collision search.
Date: received 25 Jan 2017
Contact author: prabkush at gmail com; prabhatkk@students iiserpune ac in
Available format(s): PDF | BibTeX Citation
Version: 20170131:151129 (All versions of this report)
Short URL: ia.cr/2017/055
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]