April 17th, 2020

This mini-post breaks down how to solve for the constants of an Linear Congruential Generator (LCG) given:

• known power-of-two modulus (going to use 32-bit)
• three sequential outputs $(u_1,u_2,u_3)$

Recall that LCGs (with implied mod) can be written as:

$$\begin{array}{r}{u}_{i+1}=m{u}_i+c\end{array}$$

where $m$ and $c$ are (hopefully) well chosen constants. Given our known outputs we have:

$$\begin{array}{r}{u}_1=m{u}_0+c\\ u_2=m{u}_1+c\\ u_3=m{u}_2+c\end{array}$$

Let’s solve for $m$. Start by subtracting $u_3$ from $u_2$

$$\begin{array}{r}{u}_2-u_3=m(u_1-u_2)\end{array}$$

To isolate $m$ we need to move the $(u_1-u_2)$ to the other side which we can do by multiplying both sides by the modulo multiplicative inverse (denoted below by $x^{-1}$):

$$\begin{array}{r}m=(u_2-u_3){(u_1-u_2)}^{-1}\end{array}$$

We can now solve for $c$ by (choosing $u_2$ equation):

$$\begin{array}{r}c=u_2-m{u}_1\end{array}$$

and while we’re at it for the seed $\left(u_0\right)$

$$\begin{array}{r}{u}_0=m^{-1}(u_1-c)\end{array}$$

and “Bob’s your uncle”. Code given below. So the only tricky part in this simplified case is being aware of the mod inverse. This extends to other “bases” by updating the inverse function and performing the mod at each step. If the base is an unkown, then things get a bit more tricky (SEE: How to crack a Linear Congruential Generator)

uint32_t mod_inverse(uint32_t a)
{
  uint32_t x;
  x = 3*a ^ 2;
  x *= 2-a*x;
  x *= 2-a*x;
  x *= 2-a*x;
  return x;
}

typedef struct { uint32_t m; uint32_t c; uint32_t u0; } lcg_t;

void solve_lcg(lcg_t* data, uint32_t u1, uint32_t u2, uint32_t u3)
{
  uint32_t m = (u2-u3)*mod_inverse(u1-u2);
  uint32_t c = u2-m*u1;

  data->m  = m;
  data->c  = c;
  data->u0 = mod_inverse(m)*(u1-c);
}

---

Comments

---

• math (34)

• random (18)

---

---