LCGs

Posted on Edited on In Symbols count in article: 5.6k Reading time ≈ 5 mins.

The LCG algorithm is applied to the generation of pseudo random numbers.
$$
X_{n + 1} \equiv (a X_{n} + b) \mod m
$$

The LCG defines three variables——multiplier a, increment b, and modulus m, which decide the generator.

Reference

ctf-lcg

Solving Formula

targets formulae
$X_{n+1} \rightarrow X_{n}$ $X_{n}\equiv a^{-1}(X_{n+1} - b) \mod m$
$\rightarrow a$ $a \equiv (X_{n+2} - X_{n+1})(X_{n+1} - X_{n})^{-1} \mod m$
$\rightarrow b$ $b \equiv (X_{n+1} - X_{n}) \mod m$
$\rightarrow m$ $t_{n} = X_{n + 1} - X_{n}$
$m = gcd((t_{n+1}\cdot t_{n-1} - t_n\cdot t_n), (t_n\cdot t_{n-2} - t_{n-1}\cdot t_{n-1}))$

Proofs

formula 1

$$
X_{n+1} \equiv a X_{n} + b \mod m
$$

$$
aX_{n} \equiv X_{n+1} - b \mod m
$$

$$
X_{n} \equiv a^{-1} (X_{n+1} - b) \mod m
$$

How to calculate $a^{-1}$? We can use Extended Euclidean algorithm.

1
2
3
4
import gmpy2
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]
# <==> MMI = lambda a, n: gmpy2.gcdext(a, n)[1]
# <==> gmpy2.invert(a, n)

formula 2

$$
X_{n + 2} \equiv aX_{n + 1} + b \mod m
$$

$$
X_{n+1} \equiv aX_{n} + b \mod m
$$

$$
X_{n+2} - X_{n+1} \equiv a(X_{n + 1} - X_{n}) \mod m
$$

$$
a \equiv (X_{n+2} - X_{n+1})(X_{n+1} - X_{n})^{-1} \mod m
$$

formula 3

$$
X_{n + 1} \equiv aX_{n} + b \mod m
$$

$$
b \equiv X_{n+1} - aX_{n} \mod m
$$

formula 4

Define that $t_n \equiv X_{n +1} - X_{n} \mod m$.
$$
t_n \equiv (aX_{n} + b) - (aX_{n-1} + b) \mod m
$$

$$
t_n \equiv a(X_{n} - X_{n-1}) \mod m
$$

$$
\Longrightarrow t_n \equiv at_{n-1} \mod m
$$

Thus, we can make the deduction by followings.
$$
t_{n+1}\cdot t_{n-1} - t_{n}\cdot t_{n} \mod m
$$

$$
\rightarrow a\cdot t_{n} \cdot a^{-1} \cdot t_{n} - t_n\cdot t_n \mod m
$$

$$
\Longrightarrow 0 \mod m
$$

$$
\Longrightarrow t_{n+1}\cdot t_{n-1} - t_{n}\cdot t_{n} | m
$$

Similarly, it can be concluded that $t_{n}\cdot t_{n-2} - t_{n-1}\cdot t_{n-1} | m$
$$
\Longrightarrow m = gcd ((t_{n+1}\cdot t_{n-1} - t_{n}\cdot t_{n}), (t_{n}\cdot t_{n-2} - t_{n-1}\cdot t_{n-1}))
$$

Applications

lcg_1

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
flag = b'Spirit{***********************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = 33477128523140105764301644224721378964069
print("seed = ",seed)
for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed^plaintext
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)

solution

known: 

1
2
3
4
5
6
7
8
seed = (a * seed + b) % n
a
b
n
---10---> seed
ciphertext = seed ^ plaintext

=> plaintext = ciphertext ^ seed

exp: 

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

seed = 
a = 
b = 
n = 
c = 
for i in range(10):
    seed = (a*seed + b) % n
plaintext = seed ^ c
print(long_to_bytes(plaintext))

lcg_2

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
flag = b'Spirit{*****************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed

print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)

solution

known:

1
2
3
4
5
6
7
8
9
seed = plaintext
seed = (a * seed + b) % n
a
b
n
---10---> seed
ciphertext = seed

use formula 1

exp:

1
2
3
4
5
6
a_ = invert(a, n)

seed = c
for i in range(10):
    seed = (a_ * (seed - b)) % n
print(long_to_bytes(seed))

lcg_3

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
flag = b'Spirit{*********************}'
plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
seed = getPrime(length)
n = getPrime(length)

b = plaintext

output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)
ciphertext = seed

print("a = ",a)
print("n = ",n)
print("output1 = ",output[6])
print("output2 = ",output[7])

solution

known:

1
2
3
4
5
6
a
n
output = (a * seed + b) % n
	-> output1 = output[6]
	-> output2 = output[7]
b = plaintext

exp:

1
2
3
# formula 3
b = (output2 - a*output1) % n
print(long_to_bytes(b))

lcg_4

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
flag = b'Spirit{********************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)


print("n = ",n)
print("output = ",output)

solution

known:

1
2
n
seed = (a * seed + b) % n   ---> output

target: 

1
2
3
to solve out a, b
a  <---  formula 2
b  <---  formula 3

exp:

1
2
3
4
5
6
7
8
# solve out a
a = invert(output[1] - output[0], n) * (output[2] - output[1]) % n
a_ = invert(a, n)
# solve out b
b = (output[1] - a * output[0]) % n
# solve out the initial seed
plaintext = a_ * (output[0] - b) % n
print(long_to_bytes(plaintext))

lcg_5

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
flag = b'Spirit{****************************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("output = ",output)

solution

known:

1
seed = (a * seed + b) % n   ---> output

target:

1
2
3
4
5
to solve out a, b, m

m  <--- formula 4
a  <--- formula 2
b  <--- formula 3

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# solve out n
t = [output[i + 1] - output[i] for i in range(len(output) - 1)]
def T(i):
    return t[i + 1] * t[i - 1] - t[i] * t[i]

ns = []
for i in range(len(output) - 3):
    ns.append(int(gcd(T(i), T(i+1))))
    # print(ns)

for n in ns:
    try:
        # solve out a
        a = invert(output[1] - output[0], n) * (output[2] - output[1]) % n
        a_ = invert(a, n)

        # solve out b
        b = (output[1] - a * output[0]) % n

        # solve out the initial seed
        plaintext = a_ * (output[0] - b) % n

        print(long_to_bytes(plaintext))
    except:
        pass

lcg_6

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
flag = b'Spirit{*****************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

output = []
for i in range(10):
    seed = (seed*a+b)%n
    output.append(seed>>64)
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("output = ",output)
-------------THE END-------------