How the NSA introduced a bookmark into the pseudo random number generator
Based on the materials of this article.
The NSA generator is based on elliptical curves. Do not be afraid of them, especially since the essence of the algorithm and bookmarks can be described in simpler words. It won't be harder than understanding how the Diffie-Hellman protocol works
Algorithm(translation of this material)
- He suggests that we take a prime number p and two numbers g , h which are both less than p .
- Tells us that his condition at any time can be described by a positive number s less than p
- To perform one step of the algorithm, it is necessary to set r = g s (mod p ) , s ′ = g r (mod p )
- Set the current state to s ′
- Algorithm output t = h r (mod p )
The bookmark is a secret number e such that g = h e (mod p ) .
The NSA, which developed the algorithm, selected the numbers g h by generating random h and e and setting g = h e (mod p ) . and then publishing the g, h, p but leaving at an e .
How to use a bookmark
Suppose the NSA has become aware of one of the states of the generator t . This may be, for example, an IV symmetric algorithm that is transmitted over an open channel. Or salt.
And now the hocus pocus
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.
In the original, P is a curve, G, H are two points. The operation of exponentiation modulo is replaced by multiplication