Dual_EC_DRBG is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. The name Dual_EC_DRBG stands for "Dual Elliptic Curve Deterministic Random Bit Generator".cite paper |date=2007-03 |title=Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised) |url=http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf |publisher=National Institute of Standards and Technology |format=PDF |id=NIST SP 800-90 ]


This stated purpose of including the Dual_EC_DRBG in NIST SP 800-90 is that its security is based on a hard problem from number theory. Given the importance of having secure random number generators in cryptology, in certain cases it may be desirable to sacrifice speed for security.

Subsequent to the standardization of the Dual_EC_DRBG, various researchers have reported certain security of the properties of the Dual_EC_DRBG:

* The intermediate values it generates, a sequence of elliptic curve points, should, under certain reasonable assumptions, be indistinguishable from uniformly random elliptic curve points. [http://www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf "Comments on Dual-EC-DRBG/NIST SP 800-90"] , K. Gjosteen] [ [http://eprint.iacr.org/2006/117 Conjectured Security of the ANSI-NIST Elliptic Curve RNG] ] [http://dx.doi.org/10.1007/978-3-540-74143-5_26 "A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator"] , Brown and Gjosteen, CRYPTO 2007, LNCS 4622, Springer, pp. 466-482. [http://eprint.iacr.org/2007/048 IACR ePrint version] ]

* The sequence of bits generated from the Dual_EC_DRBG, under certain parameter choices, can be distinguished from uniformly random bits, making its output unsuitable for use as a stream cipher, and arguably for more general uses. [ [http://eprint.iacr.org/2006/190 "Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator"] , Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.]

* The security requires that a certain problem be hard, but one of the recommended configurations of the Dual_EC_DRBG allows for the possibility that a key has been retained to solve this problem. See the Controversy section for more discussion.


This PRNG has been controversial because it was published in the NIST standard despite being three orders of magnitude slower than the other three standardized algorithms, and containing several weaknesses which have been identified since its standardization.cite news |date=2007-11-15 |author=Bruce Schneier |title=Did NSA Put a Secret Backdoor in New Encryption Standard? |url=http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 |publisher=Wired News ]

In August 2007, Dan Shumow and Niels Ferguson discovered that the algorithm has a vulnerability which could be used as a backdoor. Given the wide applications of PRNGs in cryptography, this vulnerability could be used to defeat practically any cryptosystem relying on it. The algorithm uses several constants which determine the output; it is possible that these constants are deliberately crafted in a way that allows the designer to predict its output. [cite conference |author=Dan Shumow, Niels Ferguson |date=2007-08 |title=On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng |url=http://rump2007.cr.yp.to/15-shumow.pdf |format=PDF |publisher=Microsoft |booktitle=CRYPTO Rump Session 2007 ]

This backdoor would work analogously to public-key encryption: the designer of the algorithm generates a keypair consisting of the public and private key; the public key is published as the algorithm's constants, while the private key is kept secret. Whenever the algorithm is being used, the holder of the private key can decrypt its output, revealing the state of the PRNG, and thereby allowing him to predict any future output. Yet for third parties, there is no way to prove the existence (or in-existence) of the private key. However, Appendix A.2 of the NIST document, which describes the weakness, does contain a method of generating a new keypair which will repair the backdoor if it exists.

ee also

* Cryptographically secure pseudorandom number generator
* Nothing up my sleeve number
* Random number generator attack


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Dual EC DRBG — алгоритм генерации псевдослучайных чисел, разработанный Агентством национальной безопасности США. Алгоритм основан на использовании эллиптических кривых. Это один из четырёх ГПСЧ, стандартизованных в NIST Special Publication 800 90.[1] Вскоре… …   Википедия

  • National Security Agency — NSA redirects here. For other uses, see NSA (disambiguation). For the Bahraini intelligence agency, see National Security Agency (Bahrain). National Security Agency Agency overview …   Wikipedia

  • Агентство национальной безопасности — National Security Agency/Central Security Service …   Википедия

  • Dual_EC_DRBG — or Dual Elliptic Curve Deterministic Random Bit Generator[1] is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and… …   Wikipedia

  • Dual_EC_DRBG — (Dual Elliptic Curve Deterministic Random Bit Generator) ist ein von der National Security Agency entwickelter und veröffentlichter kryptographisch sicherer Zufallszahlengenerator (PRNG). Das Verfahren ist eines von vier in der NIST Special… …   Deutsch Wikipedia

  • Атака на ГПСЧ — Атака на генератор псевдослучайных чисел атака, направленная на раскрытие параметров генератора псевдослучайных чисел (ГПСЧ) с целью дальнейшего предсказания псевдослучайных чисел. Содержание 1 Актуальность 2 Типы атак на ГПСЧ …   Википедия

  • Barack Obama citizenship conspiracy theories — A billboard questioning the validity of Barack Obama s birth certificate and by extension his eligibility to serve as President of the U. S.[1] The billboard is part of an …   Wikipedia

  • Cryptographically secure pseudorandom number generator — A cryptographically secure pseudo random number generator (CSPRNG) is a pseudo random number generator (PRNG) with properties that make it suitable for use in cryptography. Many aspects of cryptography require random numbers, for example: Key… …   Wikipedia

  • List of conspiracy theories — The list of conspiracy theories is a collection of the most popular unproven theories related but not limited to clandestine government plans, elaborate murder plots, suppression of secret technology and knowledge, and other supposed schemes… …   Wikipedia

  • Vela Incident — Orthographic projection centered on the Prince Edward Islands, the location of the Vela incident The Vela Incident (sometimes referred to as the South Atlantic Flash) was an unidentified double flash of light that was detected by an American Vela …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”