**Tags:** lcg crypto lll

Rating:

Truncated lcg with low bits known, which can be reduced to a hidden number problem, and finally solved by LLL.

```py

#! /usr/bin/sage

from Crypto.Cipher import AES

from Crypto.Util.Padding import unpad

p = 4420073644184861649599

a = 1144993629389611207194

b = 3504184699413397958941

out = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]

cipher = bytes.fromhex('34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b')

l = out

def lcg(s, a, b, p):

return (a * s + b) % p

def get_roll():

global seed

seed = lcg(seed, a, b, p)

return seed % 100

n = len(out)

A = [[0 for _ in range(n+1)] for _ in range(n+1)]

inv100 = pow(100,-1,p)

for i in range(n-1):

A[i][i] = p

A[n-1][i] = a**(i+1)%p

A[n][i] = (a*l[0]+b-l[1])*inv100%p if i==0 else (a*A[n][i-1] + (a*l[i]+b-l[i+1])*inv100)%p

A[n-1][n-1] = 1

A[n][n] = p//100

A = Matrix(A)

B = A.LLL()

h0 = B[0][-2]

s0 = h0*100+l[0]

seed = s0

assert([l[0]]+[get_roll() for _ in range(71)] == l)

key = bytes([get_roll() for _ in range(16)])

iv = bytes([get_roll() for _ in range(16)])

aes = AES.new(key, AES.MODE_CBC, iv)

print(unpad(aes.decrypt(cipher),16).decode())

# osu{w0uld_y0u_l1k3_f1r5t_0r_53c0nd_p1ck}

```

Original writeup (https://tiefsee5037008.github.io/posts/Osu!gaming-CTF-Writeup/#lucky-roll-gaming).