# Crack linear congruential generator knowing every other word in sequence

I need to crack one of the example of linear congruential generator.

I have $X_{n+1} = (a \cdot X_n + b) \bmod m$

and I know every other word in the output sequence:

..., 3158, ..., 1888, ..., 1285, ..., 1744, ..., 253, ..., 722, ...

The question is how to get the generator parameters ($a$, $b$, $m$) ? I have read Cracking a linear congruential generator but still don't know how to break it.

• Hint: compute $X_{n+2}$ as a function of $X_n$; suprises, that's a standard LCG with the same $m$, and you know consecutive output for it. From that find $a'$, $b'$, $m$ for that other LCG using a standard method, then from that derive $a$, $b$ of the original. – fgrieu Apr 3 '15 at 13:10
• so i took a sequence: 3158, 1888, 1285, 1744, 253, 722 and compute like in security.stackexchange.com/questions/4268/…. i've got m = 28683 and then a = 34533, b = 85489 With this parameters i try to generate sequence but it is not the same as input: [1888, 1285, 1744, 19375, 16657, 6739, 12148, 17449, 21976, 1834] only first 3 items are right. am i doing something wrong ? – Gravian Apr 3 '15 at 14:59
• @Gravian That value of m is wrong (or my implementation differs from that used to generate the sample numbers). :sat \s a b -> everyOther ((lcg s a b 28683)) == [3158,1888,1285,253,722:] yields Unsatisfiable. – Thomas M. DuBuisson Apr 3 '15 at 16:36
• @Gravian How could you have used said link to compute m? The provided formula uses s_{n+1} - s_n and you only know every other s_i value, not two consecutive values. – Thomas M. DuBuisson Apr 3 '15 at 16:39
• @Gravian: hints: The algorithm you used (successfully I guess) can obtain a multiple of the actual $m$. The right $m$ is likely not too much above the highest output available. – fgrieu Apr 3 '15 at 17:31

Sometimes, rather than do cool math, the easiest approach is brute force!

#include <stdio.h>
#include <assert.h>

int main()
{
enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
M_START = 3159 };
for (int m = M_START; m < 10*M_START; ++m) {
for (int a = 2; a < m; ++a)  {
int c = X2 - ((X1 * a) % m);
if (c < 0)
c += m;
int my_x2 = (X1 * a + c) % m;
assert(my_x2 == X2);
int my_x3 = (X2 * a + c) % m;
int my_x4 = (X3 * a + c) % m;
int my_x5 = (X4 * a + c) % m;
if (my_x3 == X3 && my_x4 == X4 && my_x5 == X5) {
printf ("m=%d, a=%d, c=%d\n", m, a, c);
}
}
}

return 0;
}


This code does an exhaustive search. In less than a second, it spits out:

m=3187, a=2663, c=2627
m=6374, a=2663, c=2627


Now, this is for an LCG that just outputs the values you gave without any gaps. But we can easily do a little math to work out that if $a^2 \mod m = 2663$, then $a = 1200$, the modular square root of 2663 (in Mathematica, PowerMod[2663, 1/2, 3187]).

Likewise, we can easily find $c$. Thus, we find $m = 3187, a = 1200, c = 854$.

And thus the actual sequence (with odd-numbered items in bold) is 2679, 3158, 1111, 1888, 497, 1285, 346, 1744, 2982, 253, 1689, 722, 390, 365, 2235, 2587, 1116, 1514, 1064, 2854, …

But maybe you worry that I've used a $\mathrm{O}(n^2)$ algorithm? What if $m$ were larger? Well, I was just feeling lazy, that's all. We can easily drop the complexity to something far less. It just makes for slightly longer code:

#include <stdio.h>
#include <assert.h>

int modular_inverse(int a, int m)
{
// Based on code from http://rosettacode.org/wiki/Modular_inverse#C
int t, nt, r, nr, q, tmp;
t = 0;  nt = 1;  r = m;  nr = a % m;
while (nr != 0) {
q = r/nr;
tmp = nt;  nt = t - q*nt;  t = tmp;
tmp = nr;  nr = r - q*nr;  r = tmp;
}
if (r > 1) return -1;
if (t < 0) t += m;
return t;
}

int main()
{
enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
M_START = 3159 };

for (int m = M_START; m < 10*M_START; ++m) {
int diff0 = (X1 - X0);  if (diff0 < 0) diff0 += m;
int diff1 = (X2 - X1);  if (diff1 < 0) diff1 += m;
int diff2 = (X3 - X2);  if (diff2 < 0) diff2 += m;
int diff3 = (X4 - X3);  if (diff3 < 0) diff3 += m;
int diff4 = (X5 - X4);  if (diff4 < 0) diff4 += m;

// diff1 = a * diff0   =>   1/diff0 * diff1 = a
int inv_diff0 = modular_inverse(diff0, m);
if (inv_diff0 < 0) continue;
int a = (diff1 * inv_diff0) % m;

int my_diff1 = (a * diff0) % m;
int my_diff2 = (a * diff1) % m;
int my_diff3 = (a * diff2) % m;
int my_diff4 = (a * diff3) % m;
assert(my_diff1 == diff1);

if (my_diff2 == diff2 && my_diff3 == diff3 && my_diff4 == diff4) {
printf ("m=%d, a=%d\n", m, a);
}
}

return 0;
}


This version spits out its answer essentially instantly, taking 0.001 seconds to run the program.

m=3187, a=2663


From here, we can then figure out $c$ and then proceed as above.

BTW, if you enjoy more of a challenge, feel free to check out this question I asked a while back.