How the NSA implemented a bookmark in a pseudo-random number generator

Based on this article.

The NSA generator is based on elliptic curves. Do not be afraid of them, especially since the essence of the algorithm and bookmarks can be described in simpler words. It will be no more difficult than to understand how the Diffie - Hellman protocol works.

Algorithm

(translation of this material)

1. It suggests that we take a prime number p and two numbers g , h which are both less than p .
2. Tells us that his state at any time can be described by a positive number s less than p
3. To execute one step of the algorithm, you need to set r = g ^s (mod p ) , s ′ = g ^r (mod p )
4. The current state is set to s ′
5. The output of the algorithm is t = h ^r (mod p )

')

Bookmark

A bookmark is a secret number e such that g = h ^e (mod p ) .
The NSA, which developed the algorithm, chose the numbers g h by generating random h and e and setting g = h ^e (mod p ) . and then publishing g, h, p but keeping e .

How to use the bookmark

Suppose the NSA has learned one of the states t of the generator. This may be, for example, an IV symmetric algorithm that is transmitted over an open channel. Or salt.
And now focus pokus

t ^e = (h ^r ) ^e = h ^re = (h ^e ) ^r = g ^r = s ′ (mod p ).

and s ′ is the next state of the algorithm. Q.E.D.

Such pies.

In the original, P is a curve, G, H are two points. The modular exponentiation operation is replaced by multiplication