Paper 2007/048

A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator

Daniel R. L. Brown and Kristian Gjøsteen

Abstract

An elliptic curve random number generator (ECRNG) has been approved in a NIST standards and proposed for ANSI and SECG draft standards. This paper proves that, if three conjectures are true, then the ECRNG is secure. The three conjectures are hardness of the elliptic curve decisional Diffie-Hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem. The x-logarithm problem is shown to be hard if the decisional Diffie-Hellman problem is hard, although the reduction is not tight. The truncated point problem is shown to be solvable when the minimum amount of bits allowed in NIST standards are truncated, thereby making it insecure for applications such as stream ciphers. Nevertheless, it is argued that for nonce and key generation this distinguishability is harmless.

Note: This paper subsumes eprint:2006/117.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Random number generationElliptic curve cryptography
Contact author(s)
kristian gjosteen @ math ntnu no
History
2007-02-19: received
Short URL
https://ia.cr/2007/048
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/048,
      author = {Daniel R.  L.  Brown and Kristian Gjøsteen},
      title = {A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2007/048},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/048}},
      url = {https://eprint.iacr.org/2007/048}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.