## Dual EC DRBG |

## Description of Dual ECThis page explains how Dual EC is defined. The authoritative description is in NIST Special Publication 800-90. ## Background on elliptic curve cryptography
Dual EC uses elliptic curves of the form
E: y There are three versions of Dual EC,
using the three curves standardized in NSA Suite B
for ECC applications.
Each curve is specified by a prime p, an elliptic curve E over
## How Dual EC worksDual EC was published with the following graphic [page 68 of SP800-90-2012] depicting the Dual EC data flow.
In this description P and Q are the two standard Dual EC points on an elliptic
curve. Scalar multiplication (see above) is denoted with an extra *,
i.e. t*P instead of tP, x(R) denotes the x-coordinate of R. For a
point R over Here are the details of how Dual EC produces an output string of any specified length. The simplest case is that the specified length fits into one block of φ output and there is no additional input. In this case the current seed s is used to produce a new seed s (used for the next Dual EC call) and an output string as follows: - Replace s with x(sP): i.e., compute sP and take the x-coordinate to obtain a new s.
- Compute r=φ(x(sQ)).
- Output the specified number of bits of r.
This is indicated in the diagram by the horizontal arrows to "Extract Bits". If the specified length is longer, but there is still no additional input, then the same steps are iterated: - Repeat the next steps until the output has the required length:
- Replace s with x(sP).
- Compute r=φ(x(sQ)).
- Append r to the output.
If there is additional input then the seed is updated at the beginning of each call: - Replace s with s⊕Hash(input) if there is additional input.
- Repeat the next steps until the output has the required length:
- Replace s with x(sP).
- Compute r=φ(x(sQ)).
- Append r to the output.
What we have described so far is the original version of Dual EC. The Dual EC standard was updated in 2007 to include a further update step [page 74 of SP800-90-2012] although the diagram in the standard was not modified to show this step: - Replace s with s⊕Hash(input) if there is additional input.
- Repeat the next steps until the output has the required length:
- Replace s with x(sP).
- Compute r=φ(x(sQ)).
- Append r to the output.
- Replace s with x(sP).
This modification to the standard affects the exploitability of Dual EC. ## Authors of this "Description of Dual EC" page (alphabetical order)- Daniel J. Bernstein, University of Illinois at Chicago and Technische Universiteit Eindhoven
- Tanja Lange, Technische Universiteit Eindhoven
- Ruben Niederhagen, Technische Universiteit Eindhoven
Last modified: 2015.07.06 |