Paper 2005/460

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

Tomas Rosa


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Worskshop MKB 2005, December 1st - 2nd, Prague, CZ,
cryptanalysisdigital signaturesimplementationlattice techniques
Contact author(s)
t_rosa @ volny cz
2005-12-31: received
Short URL
Creative Commons Attribution


      author = {Tomas Rosa},
      title = {One-Time {HNP} or Attacks on a Flawed El Gamal Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2005/460},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.