2
$\begingroup$

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!

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

1 Answer 1

2
$\begingroup$

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
Qy = 0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046

n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

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

  1. You start with a seed.
  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 &= outmask

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

It produces output like this

be58a87ed729a0585d9af5e845e604c7ec2783f2b40b9dbba8cc36d9e3f0
230ce69cca1336e5d70dfca682665d0c2176d040ec693d8c6c936bf7a546
94ffaad3700ac9651c933280b9f46abf15f6b2402aec8b9c634a750add48
e206ecd890a0f00a067ad7626fd9b352561fc8a5550fccb42d80f9032fde
96c844ba91a7a8b67b5ef4b3c7920fcd62f5bd4ce0f850a2d1ff65070328
36d4f3f653b6515e3c58f51863189b92eca2bbd4321acb21ea5c448d784c
...
$\endgroup$
1
  • $\begingroup$ I believe the nonce I am provided with would be the seed you mentioned. Also, I think my mistake is in the EC multiplication you mentioned. I am not familiar with how proper EC multiplication is done (multiply an elliptic curve point with an integer). What I did was I took the x-coord of P/Q and multiplied it directly with the nonce. $\endgroup$
    – Nosticlov
    Feb 12 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.