# Generating pseudorandom numbers using Dual_EC_DRBG

I am currently learning about the Dual_EC_DRBG protocol and I am stuck at the calculation of the initial state with the point P. For context, I am using the secp256k1 curve with a = 0 and b = 7. I have two points P and Q provided to me already. I am also using a nonce that will initialise the state.

From my understanding, I first take the x value of P then multiply it with the nonce value. With this new value I multiply it with the x value of Q. Afterwards I remove the first 16 digits from the value and I get the generated number. Assume all values are in hexadecimal form. However, I am unable to get the correct solution. I think there is some issues in the multiplication, any help is appreciated. Thank you!

• you do realize Dual_EC_DRBG was backdoored by NSA and is not reputable as a source [independent of your actual question] Feb 12 at 16:37
• and you need to provide more details probably for the question to be answered properly [first digits, etc, these need to be defined] Feb 12 at 16:38
• Does the backdoor in Dual_EC_DRBG work like that? Feb 12 at 18:30

First, you need the curve constants and the P and Q points. In this example I've used P-256, but it should work similarly with secp256k1.

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc  # -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

Px = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Py = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

Qx = 0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192



The algorithm you described in the question is close, but a little different from implementations I've seen in the wild.

2. You do an EC multiplication of point $$P$$ and the seed. The $$X$$ coordinate of the resulting point becomes the new seed.
3. Then you do an EC multiplication of the point $$Q$$ with the seed. The $$X$$ coordinate of this point is going to be the output of DUAL_EC_DRBG.
4. But before you output the data, you chop off the first 16 bits.

Assuming you already have a function that can multiply an elliptic curve point with an integer, you can generate numbers like this. In this example, ec_point_int_mul takes in a point $$(X, Y)$$ and and int $$N$$, and returns a new point $$(X, Y)$$.

seed = 0xd530b913e6f2ef88b21616fd34a603f203d0578c

outsize = p.bit_length() - 16  # Chop off first 16 bits
outmask = (1 << outsize) - 1

for it in range(25):
seed, _ = ec_point_int_mul(Px, Py, seed)
if it == 0: continue  # Do not output first iteration
r, _ = ec_point_int_mul(Qx, Qy, seed)

# r is the generated data.
print(hex(r)[2:])


It produces output like this

be58a87ed729a0585d9af5e845e604c7ec2783f2b40b9dbba8cc36d9e3f0
230ce69cca1336e5d70dfca682665d0c2176d040ec693d8c6c936bf7a546