Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Worskshop MKB 2005, December 1st - 2nd, Prague, CZ, http://www.buslab.cz/mkb/index.html.en
- Keywords
- cryptanalysisdigital signaturesimplementationlattice techniques
- Contact author(s)
- t_rosa @ volny cz
- History
- 2005-12-31: received
- Short URL
- https://ia.cr/2005/460
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/460,
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{https://eprint.iacr.org/2005/460}},
url = {https://eprint.iacr.org/2005/460}
}
