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$).

A visual of the PRNG can be seen below (source). You may recognize it as Dual_EC_DBRG. You can ignore the $\phi$ function and the additional input.

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 - 0x8fc4b1d886a3ac3d3ae3c13722bc5eead9d1dd5eda876ca59b8c33ebeb6e2616

What 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.

Solution