6
$\begingroup$

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.

$\endgroup$

migrated from security.stackexchange.com Apr 3 '15 at 12:18

This question came from our site for information security professionals.

  • 3
    $\begingroup$ 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. $\endgroup$ – fgrieu Apr 3 '15 at 13:10
  • $\begingroup$ 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 ? $\endgroup$ – Gravian Apr 3 '15 at 14:59
  • $\begingroup$ @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:[16]] yields Unsatisfiable. $\endgroup$ – Thomas M. DuBuisson Apr 3 '15 at 16:36
  • $\begingroup$ @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. $\endgroup$ – Thomas M. DuBuisson Apr 3 '15 at 16:39
  • 2
    $\begingroup$ @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. $\endgroup$ – fgrieu Apr 3 '15 at 17:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.