LLL-Analyse

LLL算法快速入门与理解：

友情链接：

–>格基规约算法：数学基础

–>格攻击理论

–>格密码速通

这几篇是我认为写的比较好，适合人看的，其他的要么冗余信息量大，要么专业术语过多，实在令人感到头疼和烦恼。

前言：把复杂的东西先用起来，然后再细细讲解概念。

那么再开始介绍这个算法和作用之前我们先看一个视频–>>bilibili

视频通过动画通俗易懂地讲解了施密特约化是如何进行的，我们通过输入一组向量->得到了这组向量的约化基。

而这个就是LLL算法的核心思想：输入一组基->得到一组约化基

（约化基就姑且先当做视频当中所得到的坐标轴上面的向量就好，后面会有展示）

Part1:了解LLL算法

• LLL算法核心是什么？
• LLL算法怎么发挥作用？

from random import randrange
from Crypto.Util.number import getPrime,bytes_to_long
from secret import flag
assert len(flag) % 4 == 0

length = len(flag)//4
m = [bytes_to_long(flag[i*length:(i+1)*length]) for i in range(4)]
p = getPrime(int(128))

def MakeMask(n,p):
    upper = identity_matrix(n)
    low = identity_matrix(n)
    for i in range(n-1):
        for j in range(i+1, n):    
            upper[i, j] = randrange(1, p)
            low[j, i] = randrange(1, p)
    result = upper * low
    assert det(result) == 1
    return result

def Matrix2List(x):return [list(i) for i in x]

noise = [[randrange(1, p) for i in range(4)] for _ in range(4)]
noise[0] = m
M = matrix(noise)
A = MakeMask(4,p)
C = A*M

print(f'p={p}')
print(f'C={Matrix2List(C)}')
'''
p=198880159035681668071031460916089145469
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
'''

先观察题目：

• 生成了一个矩阵A：由上三角矩阵与下三角矩阵相乘构成。
• 生成了一个矩阵M：第一行是我们的目标flag，其余行都是一些随机数(noise)。
• 将矩阵A与矩阵M相乘，得到矩阵C。

其中p与矩阵C已知，p相当于给矩阵内的数值定了一个上界。

题目公式：A*M=C

如果我们的线代学的足够好，就知道这个矩阵A不就是一个正交矩阵吗？(det(A) == 1)

而正交矩阵的特征值皆为正负1。当正交矩阵经过LLL算法，就是通过了我们刚才所看的施密特约化，柏分柏得到如下结论：

• 正交矩阵通过LLL算法输出的结果一定得到类似图下的结果(对角线上的元素为正负1)。

![EW8V{HAR_{_)0DSWJFWF]MTC.png](/upload/EW8V%7BHAR}_)0DSWJFWF%5DMTC.png)

（如图所示）

那么本质上，因为M的第一行数值(向量短)比较小，彼此间近乎线性无关(不太会受到LLL的影响)，原因稍后给出，所以题目的运算就等价于:

$$A*M=E*A'*M=C\\\\ \text{其中通过LLL算法后A'直接被约掉：}\\\\ \text{变成：}LLL(C)=LLL(E*A'*M)=E*M$$

所以第一行我们就可以直接拿到flag。

C = [[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
C = Matrix(ZZ,C)
res = C.LLL()

for i in res[0]:
    print(str(long_to_bytes(abs(i)))[2:-1],end = "")
##0xGame{8e4d5924dc4cd78f11c1eeb99e991ab3}

如果我们手上有一本蓝色小本本(线性代数教材)，可以拿着线代教材的标准推导（求解正交矩阵的特征向量、特征值那一章）与上述程序进行比较，这里直接给出结论：并无差异。

到这里，我们就对LLL算法是什么有了一个初步的了解：输入一组向量(也就是一组矩阵)，得到一组约化基。其核心就是施密特约化！其流程正如开头视频所展示。

Part2:初步应用LLL解方程

接下来我们看看怎么应用到实战中，并如何进行构造规约，来看一个例子：

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

m = bytes_to_long(flag)
q = getPrime(512)
assert m.bit_length() == 318

def encrypt(m):
	mask,noise = getPrime(511),getPrime(50)
	mask_.append(mask)
	noise_.append(noise)
	c = (mask*m + noise)%q
	return c

noise_,mask_  =[[] for _ in range(2)]
c_ = [encrypt(m) for i in range(4)]

print(f'q = {q}\nmask = {mask_}\nc_ = {c_}')

'''
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]
'''

直接找题目的数学关系：

$$Mask_i*m+noise_i=c_i(modq)\\\\ \text{其中我们得到了四组这样构造的关系式}\\\\ \text{展开式子}：Mask_i*m+noise_i+k_i*q=c_i\\\\k_i、noise_i、m未知$$

很显然像这种关系式，我们没办法利用高斯消元法去求解他们。在此之前我们先列一下总体式子看看特征，再考虑下手：

$$Mask_0*m+noise_0+k_0*q=c_0\\\\ Mask_1*m+noise_1+k_1*q=c_1\\\\ Mask_2*m+noise_2+k_2*q=c_2\\\\ Mask_3*m+noise_3+k_3*q=c_3\\\\ (Mask_i,q,c_i已知)$$

根据线代教材的矩阵乘法一段，我们试着去将已知信息和未知信息分开来，去构造一个矩阵乘：

$$[m,1,k_1,k_2,k_3,k_4]\left[ \begin{matrix} Mask_1 & Mask_2 & Mask_3 & Mask_4 \\\\ -c & -c & -c &-c \\\\ p & 0 & 0 & 0 \\\\0 & p & 0 & 0\\\\0 & 0 & p & 0\\\\0 & 0 & 0 & p \end{matrix} \right] \\\\=[noise_1,noise_2,noise_3,noise_4]$$

这时候，总体的抽象形式变成了：

$$v*B=w\\\\ \text{我们将B定义为}\mathcal{L}(B)\text{，也就是格基}$$

可以发现 v向量 像是某种系数一样，通过与格基B内的元素进行线性组合得到 向量w。

看着比较迷糊，接下来给出一些定义，如图所示：

(二维下的格基与格空间)

$$\mathcal{L}=\sum^{n}_{i=1}{ b_i} · Z=\{\sum^{n}_{i=1}t_ib_i|t_i∈Z\}\\\\ \mathcal{L}\text{被称之为格}$$

• 格基：那一小块F张成的东西。
• 格空间：散落在坐标系中的小点。(也就是由格基线性组合张成的集合)
• 向量：指向某个点的箭头。(具有长度和方向)

重复再写一遍式子：

$$v*B=w\\\\ \text{我们将B定义为}\mathcal{L}(B)\text{，也就是格基}$$

在这个式子中，v向量就是对格基B上的元素进行线性组合，去张成其他点（例如向量w）。

那么考虑这样一种情况，如果这个张成的点的向量长度足够小（而w恰恰正是那条！），我们是否可以规约出来？

例如图下所示：

(假设红色那条为最短向量，此时他为格空间的最短向量)

此时的情况是二维的，但为了方便理解，我直接了当地说：

• 格基B就是灰色部分。
• 向量v没有绘出。
• 向量w是由向量v与格基B线性组合成的红色箭头。

当我们对B进行规约的时候，极大概率是可以规约出红色那条的。这是二维情况下的直观理解，其他维度大抵同理吧。

这个概率是多少呢？根据高斯启发式可知，大致比这个期望值小就行。

$$\text{高斯启发式：}GH(\mathcal{L})= \sqrt{\frac{n}{2\pi e}}\mathrm{det}(\mathcal{L})^{1/n}$$

那么回到题目：我们对构造的矩阵进行LLL规约，得到的就是这条比较小的向量(图为二维情况下，但大致意思同)

也就是说我们可以直接通过构造吧noice向量给解出来！此时再代回原式子进行求解就行。

再来拓展一些技巧（配平），根据题目直接构造式子通俗易懂，但如果我们想要直接规约出flag呢？该如何进行：

像这样在B的最后一列再加个1就好：

$$[m,1,k_1,k_2,k_3,k_4]\left[ \begin{matrix} Mask_1 & Mask_2 & Mask_3 & Mask_4 & 1 \\\\ -c & -c & -c &-c & 0 \\\\ p & 0 & 0 & 0 & 0 \\\\0 & p & 0 & 0 & 0 \\\\0 & 0 & p & 0 & 0 \\\\0 & 0 & 0 & p & 0 \end{matrix} \right] \\\\=[noise_1,noise_2,noise_3,noise_4,m]$$

这样我们就可以在最短向量的第五个位置，找到flag。

以上就是LLL求解未知数的一些办法（根据构造的不同我们还是可以求出很多东西的，这里就不细讲了）

那么这里写出脚本验证结论：

from Crypto.Util.number import *
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]

c = [i for i in c_]
mask.append(1)
mask.append(0)
tmp = [[0 for i in range(len(c)+2)] for _ in range(len(c))]
tmp.append(mask)

for i in range(len(c)):
    tmp[i][i]=q
c.append(0)
c.append(pow(2,341))
tmp.append(c)

tmp =matrix(ZZ,tmp) 
tmp = tmp.LLL()
print(long_to_bytes(-tmp[0][4]))
#b'0xGame{19255b5c7b19c790e28d87c8a8bb1d33}'

回到基本的实战中：

把这个例子2的基本参数换成RSA该有的东西，拿去和维纳攻击的那个例子作比较，其实就差不多是等价的了，在开头的博客链接里面有示例。大致上理解了以上东西，再去学构造也差不多了。

未完待续，先玩会星穹铁道。