Paper 2020/1436

Removable Weak Keys for Discrete Logarithm Based Cryptography

Michael John Jacobson Jr. and Prabhat Kushwaha

Abstract

We describe a novel type of weak cryptographic private key that can exist in any discrete logarithm based public-key cryptosystem set in a group of prime order $p$ where $p-1$ has small divisors. Unlike the weak private keys based on numerical size (such as smaller private keys, or private keys lying in an interval) that will always exist in any DLP cryptosystems, our type of weak private keys occurs purely due to parameter choice of $p$, and hence, can be removed with appropriate value of $p$. Using the theory of implicit group representations, we present algorithms that can determine whether a key is weak, and if so, recover the private key from the corresponding public key. We analyze several elliptic curves proposed in the literature and in various standards, giving counts of the number of keys that can be broken with relatively small amounts of computation. Our results show that many of these curves, including some from standards, have a considerable number of such weak private keys. We also use our methods to show that none of the 14 outstanding Certicom Challenge problem instances are weak in our sense, up to a certain weakness bound.

Note: This is a post-peer-review, pre-copyedit version of an article published in Journal of Cryptographic Engineering. The final authenticated version is available online at: https://doi.org/10.1007/s13389-020-00250-7

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. JOURNAL OF CRYPTOGRAPHIC ENGINEERING
DOI
10.1007/s13389-020-00250-7
Keywords
public-key cryptographyelliptic curve cryptosystemcryptographic protocols
Contact author(s)
prabkush @ gmail com
History
2020-11-24: last of 2 revisions
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1436,
      author = {Michael John Jacobson Jr. and Prabhat Kushwaha},
      title = {Removable Weak Keys for Discrete Logarithm Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1436},
      year = {2020},
      doi = {10.1007/s13389-020-00250-7},
      note = {\url{https://eprint.iacr.org/2020/1436}},
      url = {https://eprint.iacr.org/2020/1436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.