0%

LLL-Analyse

LLL算法快速入门与理解:

友情链接:

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

–>格攻击理论

–>格密码速通

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

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

吐槽.png

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

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

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

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

Part1:了解LLL算法

  • LLL算法核心是什么?
  • LLL算法怎么发挥作用?
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
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的影响),原因稍后给出,所以题目的运算就等价于:

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

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

1
2
3
4
5
6
7
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解方程

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]
'''

直接找题目的数学关系:

Maskim+noisei=ci(modq)其中我们得到了四组这样构造的关系式展开式子:Maskim+noisei+kiq=cikinoiseim未知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未知

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

Mask0m+noise0+k0q=c0Mask1m+noise1+k1q=c1Mask2m+noise2+k2q=c2Mask3m+noise3+k3q=c3(Maski,q,ci已知)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,k1,k2,k3,k4][Mask1Mask2Mask3Mask4ccccp0000p0000p0000p]=[noise1,noise2,noise3,noise4][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]

这时候,总体的抽象形式变成了:

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

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

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

偷图高手.png(二维下的格基与格空间)

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

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

重复再写一遍式子:

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

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

那么考虑这样一种情况,如果这个张成的点的向量长度足够小(而w恰恰正是那条!),我们是否可以规约出来?

例如图下所示:

Lattice-kkxr.png(假设红色那条为最短向量,此时他为格空间的最短向量)

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

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

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

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

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

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

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

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

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

[m,1,k1,k2,k3,k4][Mask1Mask2Mask3Mask41cccc0p00000p00000p00000p0]=[noise1,noise2,noise3,noise4,m][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求解未知数的一些办法(根据构造的不同我们还是可以求出很多东西的,这里就不细讲了)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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该有的东西,拿去和维纳攻击的那个例子作比较,其实就差不多是等价的了,在开头的博客链接里面有示例。大致上理解了以上东西,再去学构造也差不多了。

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