Lattice exercise-1

[NPUCTF2020]babyLCG

from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag


class LCG:
    def __init__(self, bit_length):
        m = getPrime(bit_length)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a': a, 'b': b, 'm': m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("key", "w")
    f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter


def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)


def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    encrypt(rand_iter)


if __name__ == "__main__":
    main()

分析源码，我们可以知道，这道题给了我们20个LCG的输出，但只是输出的高位，后面的加密部分则是继续调用LCG，作为AES的参数。所以我们只需要通过给出的LCG高位输出，求出其中一个状态，就可以得到flag了。

我们对第一组和第二组输出进行分析，把每个输出划分成高位$(hi)$和低位$(li)$

通过化简，我们得到了最后一行式子，其中$l_1,l_2$​是未知数，我们记$A_1=a,B_1=ah_1+b-h_2$​​，那么式子就写成了$A_1l_1+B_1+k_1m=l_2$​​，我们模仿引入中的方法，补几个恒等式，先看一下目前我们能得到的矩阵

我们需要补出两个恒等式，同时，需要在右边的结果中再补上$l_1$，很容易想到的是$l_1=l_1$

这是还需要一个恒等式，而且要让0和$l_1,k_1$相乘，所以我们只需要在中间填上一个常数，这里我选择m(也有别的师傅选2^64的，只要满足Hermite定理就可以了)

a=107763262682494809191803026213015101802
b=153582801876235638173762045261195852087
m=226649634126248141841388712969771891297
h1=7800489346663478448<<64
h2=11267068470666042741<<64
A=a
B=a*h1+b-h2
M=matrix([[A,1,0],
          [B,0,m],
          [m,0,0]])
M.LLL()
[-11530711086177576267 -7584688652922652412 0]
[-12162326968771299382 11656017549012022539 0]
[1510343526611795913 6524632084338656352 226649634126248141841388712969771891297]

那么可以看到，最后一行得到的才是我们构造出来的结果。

显然这种方法有一点局限，毕竟给了20组数，我们只用了两组。所以我们继续推导关系，把所有未知低位，表示成第一组输出的未知低位。

于是我们就可以通过递推的关系，知道$A_i=aA_{i-1},B_{i}=aB_{i-1}+ah_{i}+b-h_{i+1}$​，那么由20组数据，​我们就可以写出如下式子

需要注意的是，这里我们的最后一列补的是$2^{64}$​​​而不是m，是因为我们需要让构造出的向量更小，从而让LLL生成的第一行向量，就是所要求的向量。这里也可以用1来填，只要让构造出的向量够小，并且LLL后自己方便找到所在的一行就可以了。当然也可以用m，不过这样求出来就是最后一行了。

最后贴一下完整代码

b=153582801876235638173762045261195852087
a=107763262682494809191803026213015101802
m=226649634126248141841388712969771891297
l=[]
A=[a]
B=[]
f=open('old','r')
for line in f:
   l.append(int(line.strip())<<64)
B.append((a*l[0]+b-l[1])%m)
for i in range(1,19):
    A.append(a*A[-1] % m)
    B.append((a*l[i]+a*B[i-1]+b-l[i+1])%m)
M=matrix(ZZ,21,21)
for i in range(19):
    M[i,i]=m
    M[19,i]=A[i]
    M[20,i]=B[i]
M[19,19]=1
M[20,20]=2^64
#1和m都可以
M.LLL().str()
v=M.LLL()[0]
print(v)
l1 = v[-2]
s1=l[0]+l1
seed = (s1-b)*inverse_mod(a,m)%m
print(seed)

from Crypto.Util.number import *
from Crypto.Cipher import AES


class LCG:
    def __init__(self):
        b = 153582801876235638173762045261195852087
        a = 107763262682494809191803026213015101802
        m = 226649634126248141841388712969771891297
        seed = 73991202721494681711496408225724067994
        self._key = {'a': a, 'b': b, 'm': m}
        self._state = seed

    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state

    def export_key(self):
        return self._key


rand_iter = LCG()
for i in range(20):
    rand_iter.next()
key = rand_iter.next() >> 64
key = (key << 64) + (rand_iter.next() >> 64)
key = long_to_bytes(key).ljust(16, b'\x00')
iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
cipher = AES.new(key, AES.MODE_CBC, iv)
f = open("ct", "rb")
c = f.read()
m = cipher.decrypt(c)
print(m)