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

*Daniel R. L. Brown and Kristian Gj{\o}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.

**Category / Keywords: **secret-key cryptography / Random number generation, Elliptic curve cryptography

**Date: **received 30 Jan 2007, last revised 15 Feb 2007

**Contact author: **kristian gjosteen at math ntnu no

**Available format(s): **PDF | BibTeX Citation

**Note: **This paper subsumes eprint:2006/117.

**Version: **20070219:214623 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]