Lattice exercise-1 · To1in's Blog

Lattice exercise

[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[&#39;a&#39;] * self._state + self._key[&#39;b&#39;]) % self._key[&#39;m&#39;]
    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[&#39;a&#39;] * self._state + self._key[&#39;b&#39;]) % self._key[&#39;m&#39;]
    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)

[NPUCTF2020]babyLCG

讨论