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}
```
