LatticeNotes5

huangx607087学习格密码的笔记5

0. About

这个笔记接着之前发布的笔记4，继续往后面扩展新的内容。

12.格约简算法

12x01 2维高斯格约简

假如我们已知v1,v2是格L中的一组基底，假设v1的长度小于v2，（如果不小于，则交换两向量的长度）。那么我们可以用以下的脚本逐步约简二维格中最短向量的长度。

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
26
27
28
29
30
31
32
33
from Crypto.Util.number import *
from math import sqrt
def sgn(x):
    if x==0:
        return 0
    if x>0:
        return 1
    if x<0:
        return -1
def vecmul(veca,vecb):
    assert len(veca)==len(vecb) 
    s=0
    for i in range(len(veca)):
        s+=veca[i]*vecb[i]
    return s
def getans (veca,vecb):
    print(veca,vecb)
    if vecmul(vecb,vecb)<vecmul(veca,veca):
        tmp=veca
        veca=vecb
        vecb=tmp
    print(veca,vecb)
    m=int(vecmul(veca,vecb)/vecmul(veca,veca)+0.5*sgn(vecmul(veca,vecb)))
    if(m==0):
        return veca,vecb
    for i in range(len(vecb)):
        vecb[i]-=m*veca[i]
    return getans(veca,vecb)
a=[66586820,65354729]
b=[6513996,6393464]
A,B=getans(a,b)
print(A,B)
#[2280, -1001] [-1324, -2376]
PYTHON

12x02 LLL格约简算法

高斯的晶格约简算法给出了在维数的晶格中找到最短非零向量的有效方法，但随着维数的增加，最短向量问题变得更加困难。 随着LLL算法的发表，1982年取得了重大进展。 在本节中，我们给出了LLL算法的完整描述，在下一节中，我们简要描述了它的一些推广。

当我们得到格的一个基底时，我们肯定希望对于任意两个不同的基向量，使得越接近越好。或者在更好的基上的向量尽可能短，首先是我们可以找到的最短向量，然后是长度尽可能慢地增加的向量，直到我们到达基中的最后一个向量。

前面的笔记，我提到过这样一个式子

其中是格的基本域。而如果基越正交，那么不等号两边就越接近。而为了能够得到一个更好的基底，我们可以使用施密特正交化的方法取得正交基。不过这里出现了一个问题：因为施密特正交化的方法中：由

注意到里面有这样一项并且这一项不能保证是整数。所以进行施密特正交化后的基与原来的基之间的转换出现了非整数的系数。而实际上，基与基的行列式是相同的。不过如果出现了这样两个条件，就说明被约简了一次：

UPD 2021.2.9：原来这里的公式改成了图片，因为在网页上公式显示异常。

关于LLL算法一些其他的原理，以后会不定期补充。Sagemath中自带了矩阵的LLL计算，很方便。

以下是用Sagemath中的LLL算法计算矩阵的对应矩阵的。可以看出，最短的向量在第一行，的确断了不少。

当然，同一个矩阵使用LLL算法后，可能会算得不同的结果。如下图的矩阵，也是经过LLL算法的一个答案。不过计算一下，可以看出与的行列式绝对值相同，例子中均为。并且，因此中的向量基的确更加正交。但中的值约为。查看源码可知，Sagemath中的条件的判断参数是，而使用的参数是。因此，LLL算法对其使用的参数具有比较高的依赖性。。也有用做的，不过无论如何，最上面一行的值总是一样的（至多差一个倍）

12x03 使用LLL解决apprCVP问题：

我们在笔记3中解释了，如果晶格L具有正交基，那么SVP和CVP都很容易求解。 LLL算法不返回正交基，但它确实产生了一个基向量是准正交的基，即它们之间是合理正交的。 因此，我们可以将LLL算法与Babai算法相结合，形成一种求解APRCVP的算法。

这个算法很简单，先求出中的向量作为基底，然后在Babai算法中使用LLL约简基进行计算。

13.LLL在密码分析中的应用

13x01 回顾笔记1中的同余密码系统

当我们知道时，就可以使用高斯约简向量和，计算约简后的向量为和。最短的向量为前者。因此，成功破解。

13x02 回顾笔记1中背包密码中的LLL算法破解

涉及到的理论可以参见笔记1中的相关内容

下图展示了LLL在前两个例子中的体现

13x03 回顾笔记3中的GGH公钥密码系统

攻击此密码系统，可以将向量组约简。得到，密文

此时高达。因此我们很快就找到了答案为

所以最后的答案是。考虑到原来，因此调换顺序，成功破解明文为

13x04 回顾笔记4中的NTRU算法

在笔记4中我们举的那个例子里，在的情况下，我们算得的表达式为

然后，我们可以构造下图的矩阵

同样地，我们可以使用LLL算法。算出结果后，将其对半分开，考虑到LLL算法有的时候会相差一个负号或者出现旋转的问题，因此，我们有行答案符合条件，并且这行互为旋转。

以用红色标出来的第一行为例：此时的。

不过，我们可以给乘上，那么有，。刚好与之前Alice和Bob所计算的结果是一样的，因此攻击者计算出来的也可以作为解密密钥使用。

14.例题选讲[UPDATE 2021.2.20]

14x01 NPUCTF2020[BABYLCG]

update 2021.2.8

STEP 1 读取题目

我们先来看一下题目：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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()
PYTHON

线性同余生成器简称LCG，就是通过的线性方程迭代产生随机数，随机数比较有规律可循。

题目给出的同时，还给出了连续个产生的数字，不过我们知道的只有它们的最高位，低的位不知道。

STEP 2 初步分析，确定构建格矩阵的法则

为了简便，我们可以先从两个数字开始，假设我们已知的是高位部分是，未知的低位部分是，那么我们可以得到

去掉同余号，可以得到下面的式子，其中也是未知量

如果我们对这个式子进行移项，那就有

很显然，我们建立了与之间的递推关系。因此，我们要建立向量和矩阵，使得。而想要建立矩阵和向量，就要保证等式右边有几个未知数，向量就至少要有几维，并且两个向量要覆盖到所有的未知量。而矩阵中的数字，只能是已知量，并且还要覆盖到题目给出的所有参数。因为到时候直接放入Sagemath中进行LLL算法的是所有元素均为已知量的矩阵而不是带有未知数向量。

STEP 3 从理论走向实践

根据刚刚总结的理论，我们有确定了等号右边有个未知数，因此向量维数至少是。然而，构造维的向量很困难，因为我们上面关于的表达式实际上应该写成这个样子：

不要小看这个的作用，因为这样我们直接就重构了表达式为。而是已知量，与全部无关。故我们必须要构建三维的向量，并彻底确定。矩阵的第一列为，向量的第一个分量为。

因此，下图就表示我们构建格的雏形了。

此时，未知量已经全部被包含，已知量也全部被包含，没有什么必要的东西了。不过注意到一个问题：实际上是最后对矩阵M约简时的最短向量（这个很重要）。而相对于来讲，我们更希望知道的时，因此我们就让的第二个分量为，完善了矩阵。

为了让最后一个数字尽可能地简单，我们可以把这个矩阵的第三列的前两个数全填成。这样求最短向量的时候，最后一维也就是个固定的常数了。不过问题来了：矩阵右下角的那个数字真的可以随便取吗？

当然不是

我们在笔记2的时候就讲过Hermite定理：维数为的每一个格中都包含一个长度不超过的向量。这里，假如右下角这个数是。那么很容易计算，其中是模数，位。也就是说，最短向量一定小于。因此提高的值准确度更高。以下就是当很大和较小时解出来的值。如果算出来的中有一个时负数，那就只能换一组数据了 （直接去绝对值即可，Upd by shallow）

因此，我们就恢复了一个数的低位。一旦这个数的低位被恢复，那我们就恢复了被省略掉的低位，获得了一个状态，那我们就立刻地推出了所有的答案了，flag也就解出来了。

4. Reference

因为自己的做法确实有些局限性，为了获得更普遍的方法，我还是跟shallow大佬讨论了以下这道题的做法，但我可能还是太菜了，思考了两小时都没能实现这个做法。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
shallow 2021/2/6 20:14:05
这题给了你这么多数据，肯定不可能只用三个就做的
shallow 2021/2/6 20:14:21
我当时这题用的hnp的思路写的来着。。
huangx607087 2021/2/6 20:14:46
我用三个做出来了
shallow 2021/2/6 20:14:55
az
huangx607087 2021/2/6 20:15:04
不过调了几次参数
shallow 2021/2/6 20:15:49
那没事了
shallow 2021/2/6 20:23:36
负的直接绝对值就行
shallow 2021/2/6 20:23:46
刚刚算了一下界居然真的够。。
huangx607087 2021/2/6 20:24:15
那，大佬能说一下你当时是怎么做的吗
shallow 2021/2/6 20:25:34
把每个d表示成ad0 + b
shallow 2021/2/6 20:25:52
然后一排全a，第二排全b，剩下地方对角线填n
shallow 2021/2/6 20:26:03
LLL完剩下的就全是di了
huangx607087 2021/2/6 20:26:14
好的，谢谢了，我过会试一下
huangx607087 2021/2/6 22:03:59
n就是他给出来的20个高位吗
huangx607087 2021/2/6 22:07:03
（不好意思我理解失误）
shallow 2021/2/6 22:07:30
n的是那个p
shallow 2021/2/6 22:07:35
就是模
shallow 2021/2/6 22:09:00
随便吧
shallow 2021/2/6 22:09:01
都可以
huangx607087 2021/2/6 22:09:05
OK
shallow 2021/2/6 22:09:15
20×22也可以，22×22也可以
huangx607087 2021/2/6 22:13:11
OK
DNS

14x02 ACTF2021 [hashgame]

Updated 2021.2.20

1.读取题目：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import os
from Crypto.Util.number import *
from binascii import hexlify, unhexlify
banner = '''
               _  ___        _   _           _      ____                      
 _ __ ___   __| |/ _ \      | | | | __ _ ___| |__  / ___| __ _ _ __ ___   ___ 
| '_ ` _ \ / _` | (_) |_____| |_| |/ _` / __| '_ \| |  _ / _` | '_ ` _ \ / _ \\
| | | | | | (_| |\__, |_____|  _  | (_| \__ \ | | | |_| | (_| | | | | | |  __/
|_| |_| |_|\__,_|  /_/      |_| |_|\__,_|___/_| |_|\____|\__,_|_| |_| |_|\___|
'''
def md9(m):
    n, N = 32, 2**256
    h = 69444099843545663157429813687097031070079259699713394209624552060334679683924
    g = 91404868204801963538299172115753433950696139669081509476098772951762196709558
    assert(isinstance(m, bytes) and len(m) == n)
    for x in m:
        h = ((h + x) * g) % N
    return long_to_bytes(h)
def challenge():
    for i in range(5):
        m1 = input("> ")
        m2 = input("> ")
        try:
            m1, m2 = unhexlify(m1), unhexlify(m2)
            if m1 != m2:
                if md9(m1) != md9(m2):
                    print("Failed!")
                    return
                else:
                    print("{} win!".format(i+1))
            else:
                print("Foolish try!")
                return
        except:
            print("Something your input is wrong!")
            return
    flag = os.environ.get('FLAG')
    print("Win!Here is the flag: {}".format(flag))
def main():
    print(banner)
    challenge()
if __name__ == '__main__':
    main()
PYTHON

Step 2：初步分析，构造矩阵

对于题目中给出的计算，我们可以进行简单地化简,在阅读题目要求后，我们可以理解为：题目要求我们找两组数字，每组数字个，并且数组和数组不能完全相同。最后就是找到满足条件的组数字，使得

很显然地，我们可以约去两边的，等式变成了

然后将模式写成等式，得

然后我们可以合并一下两边：

可以顺带进行移项

观察化简后的式子，其中未知量是和，已知量是。因此我们应该建立相应的递推式。

为了简化表达，我们先假设的取值从到缩减成到来模拟构造矩阵。

在只有组差值的情况下，并且我们最后要求出来的是的值，因此，必须是我们构造矩阵中的一个子矩阵。并且也是未知的，因此我们矩阵中还要加一个元素。这样我们的向量就是维行向量，最后我们期望得到的内容就是前个参量，而又因为。因此我们矩阵需要增加至列。最后一列为列向量，负号扔给。而最后我们得到的向量就是，向量的最后一列必须是。

所以我们可以尝试构造一个这样的矩阵及其计算方式。

我们到最后只需要找到尾数是的那一列，那么就成功了。

但这样好像是失败了（，因为LLL算法后结出来的最后的结果不为。

看来，这里的计算应该是跟上面那个例子除了相同的问题。

Step 3：构造并调整矩阵

因此我们现在就需要对上面的矩阵进行调整。因为最短向量总是小于。当格对应的矩阵不是方阵的时候，我们规定格的行列式。而当太小的时候，就会导致最后解出来的向量更短，导致计算错误。因为：

这就意味着符合条件时，最后一个参数会被微小提升，来缓解其他分量的负担，向量长度变小了，但却不是我们想要的结果。

因此我们就要扩大。而我们又想保持住等号右边的向量的形式，因此我们就需要对矩阵最右边一列所有数字同时乘上一个数（不取模），然后这样格的行列式就会提升到原来的倍（如果构造出的是规模是，则就是方阵，最右边乘上就会导致矩阵行列式提升到原来的倍）。而向量的长度，提升倍数将会小于倍。

因此，我们最后期望得到的矩阵计算是这样的，而在这道题中，取多就够了，然而我还是取了为了保险。

构造矩阵运行了一下，可以发现，向量的所有分量都小于。然后我们就可以构造一段模板和一段变化过的就行了。

这里有个问题：解出来的值有正有负，这个时候我们可以把所有正数都基于作为模板，负数基于作为模板。例如，假如解出来的前个数字是，那么我们组就构造，组构造。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
#Sagemath 9.1
from Crypto.Util.number import *
from os import urandom
mod=2^256
K,n=2^700,32
g=91404868204801963538299172115753433950696139669081509476098772951762196709558
M=[[0 for _ in range(n+2)]for __ in range(n+1)]
for i in range(n+1):
    ge=ZZ(pow(g,n-i,mod))
    M[i][i]=1
    M[i][n+1]=ZZ(ge*K)
M[n][n+1]=ZZ(K*mod)
M=matrix(M)
A=M.LLL()
B,D=A[0],[]
for i in B:
    if i<0:
        D.append(255)
    else:
        D.append(0)
B=list(B)
print(B,len(B))
print(D,len(D))
s,t="",""
def padhex(x,l):
    s=hex(x)[2:]
    return '0'*(l-len(s))+s
for i in range(32):
    s+=padhex(D[i],2)
    t+=padhex(B[i]+D[i],2)
print(s)
print(t)
'''
b=[64, -39, 118, 7, 39, -3, 102, -7, -9, -9, -32, -48, 69, 58, 120, 133, 23, -197, 53, 23, -41, -45, 61, -101, 26, 2, -74, -57, 24, -23, -60, 52, -16, 0] 34
d=[0, 255, 0, 0, 0, 255, 0, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 255, 0, 0, 255, 255, 0, 255, 0, 0, 255, 255, 0, 255, 255, 0, 255, 0] 34
s=00ff000000ff00ffffffffff0000000000ff0000ffff00ff0000ffff00ffff00
t=40d8760727fc66f8f6f6dfcf453a7885173a3517d6d23d9a1a02b5c618e8c334
'''
PYTHON

4.Reference

一开始自己想的是构造的矩阵，想分出，构造从递推出的想法，不过发现这样做构造矩阵并不可以。可能是因为这种构造下，和孤立，导致直接出解。也就是说，这样由于是构造的方阵，可以直接使得LLL之后的向量结果，每一行的行向量都是单位矩阵中对应行向量的某个整数的倍数，直接构造出了的完全正交基……。

这件事还是暴露了一个严重的问题就是：huangx607087 is a feiwu

15.总结

到这里为止，格密码的5篇笔记全部投放完毕。由于最后一篇限于时间，没有过多地提及LLL算法的原理，仅仅是简单地提了一下LLL算法的使用方法，和解决了之前所抛出来的几个问题。后面主要就是将这些算法应用到CTF中的题目里去。可能会投放Notes6。但Notes6大概率会属于ExpLog。

以后有可能会对LLL算法的相关原理进行补充。

CTFSeason2
#Notes
LatticeNotes5
http://example.com/2021/02/06/LatticeNotes5/
作者
huangx607087
发布于
2021年2月6日
许可协议