International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Daniel R. L. Brown
Kristian Gjøsteen
Download:
URL: http://eprint.iacr.org/2007/048
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13330,
  title={A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Random number generation, Elliptic curve cryptography},
  url={http://eprint.iacr.org/2007/048},
  note={ kristian.gjosteen@math.ntnu.no 13559 received 30 Jan 2007, last revised 15 Feb 2007},
  author={Daniel R. L. Brown and Kristian Gjøsteen},
  year=2007
}