Exploit a backdoor in an elliptic curve based PRNG
Suppose we have a random number generator that works as follows:
- Choose two points, $P$ and $Q$, that are on NIST curve P-256 (see page 8 of this doc).
- Initialize the PRNG with a random seed $t$.
- To generate random bits do the following:
- Calculate the point $A$ resulting from point multiplication of $(t * P)$ on P-256. Set $s$ equal to the $x$ coordinate of $A$.
- Calculate the point $B$ resulting from point multiplication of $(s * Q)$ on P-256. Set $r$ equal to the $x$ coordinate of $B$.
- Output the $30$ lowest order bytes of $r$. These are the PRNGs output.
- Set $t$ equal to $s$ (in other words, the next time random bits are generated $t$ will have the value of $s$).
For this problem the values of $P$ and $Q$ are as follows:
P = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5) Q = (0xd19761748936051e5fb436f5c383a2ca6fbd1e61f227a3d70f44d73311781b32, 0xdc4c729f6de383957f62d1318197757cd2015ae6f27066ef9990fcf6d4319d82)
I've actually hidden a backdoor in this PRNG, namely that there exists a $d$ such that $d * Q = P$. The value of this $d$ is:
d = 0x561021d34971c6b5da29dbefb21413a469a751356392133a4a78981fb51f3a01
Let's say that you observe the following $32$ bytes as output from the PRNG (you may assume these are the first $32$ bytes it has output since being seeded):
PRNG output - 0x8fc4b1d886a3ac3d3ae3c13722bc5eead9d1dd5eda876ca59b8c33ebeb6e2616What are the next $28$ bytes that the PRNG will output? Submit your answer in lowercase hex, no leading $0x$. You may find section 2 of this paper and section 5 of this paper helpful.