Cryptology ePrint Archive: Report 2005/460

One-Time HNP or Attacks on a Flawed El Gamal Revisited

Tomas Rosa

Abstract: We present a modification of the well-known hidden number problem (HNP) which we refer to as a one-time HNP (OT-HNP). We also present an algorithm for solving such a problem together with its formal analysis. We show then that carefully designed instances of OT-HNP can be used to break certain flawed implementations of public key schemes efficiently. We work, for instance, with Nguyen’s attack on El Gamal’s signature scheme in the GNU Privacy Guard of version 1.2.3. The technique employed there was not based on HNP, since it was supposed that more than one signature would be necessary, which seemed to be a wastage. We will see, however, that by using OT-HNP one signature is still far enough, while retaining certain elegance of the HNP approach. We also present an experimental confirmation of this result.

Category / Keywords: public-key cryptography / cryptanalysis, digital signatures, implementation, lattice techniques

Publication Info: Worskshop MKB 2005, December 1st - 2nd, Prague, CZ,

Date: received 16 Dec 2005

Contact author: t_rosa at volny cz

Available format(s): PDF | BibTeX Citation

Version: 20051231:145734 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]