LLL算法快速入门与理解:
友情链接:
–>格基规约算法:数学基础
–>格攻击理论
–>格密码速通
这几篇是我认为写的比较好,适合人看的,其他的要么冗余信息量大,要么专业术语过多,实在令人感到头疼和烦恼。
前言:把复杂的东西先用起来,然后再细细讲解概念。
那么再开始介绍这个算法和作用之前我们先看一个视频–>>bilibili
视频通过动画通俗易懂地讲解了施密特约化是如何进行的,我们通过输入一组向量->得到了这组向量的约化基。
而这个就是LLL算法的核心思想:输入一组基->得到一组约化基
(约化基就姑且先当做视频当中所得到的坐标轴上面的向量就好,后面会有展示)
Part1:了解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的影响),原因稍后给出,所以题目的运算就等价于:
A∗M=E∗A′∗M=C其中通过LLL算法后A’直接被约掉:变成: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 = "")
|
如果我们手上有一本蓝色小本本(线性代数教材),可以拿着线代教材的标准推导(求解正交矩阵的特征向量、特征值那一章)与上述程序进行比较,这里直接给出结论:并无差异。
到这里,我们就对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] '''
|
直接找题目的数学关系:
Maski∗m+noisei=ci(modq)其中我们得到了四组这样构造的关系式展开式子:Maski∗m+noisei+ki∗q=ciki、noisei、m未知
很显然像这种关系式,我们没办法利用高斯消元法去求解他们。在此之前我们先列一下总体式子看看特征,再考虑下手:
Mask0∗m+noise0+k0∗q=c0Mask1∗m+noise1+k1∗q=c1Mask2∗m+noise2+k2∗q=c2Mask3∗m+noise3+k3∗q=c3(Maski,q,ci已知)
根据线代教材的矩阵乘法一段,我们试着去将已知信息和未知信息分开来,去构造一个矩阵乘:
[m,1,k1,k2,k3,k4]⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡Mask1−cp000Mask2−c0p00Mask3−c00p0Mask4−c000p⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=[noise1,noise2,noise3,noise4]
这时候,总体的抽象形式变成了:
v∗B=w我们将B定义为L(B),也就是格基
可以发现 v向量 像是某种系数一样,通过与格基B内的元素进行线性组合得到 向量w。
看着比较迷糊,接下来给出一些定义,如图所示:
(二维下的格基与格空间)
L=i=1∑nbi⋅Z={i=1∑ntibi∣ti∈Z}L被称之为格
- 格基:那一小块F张成的东西。
- 格空间:散落在坐标系中的小点。(也就是由格基线性组合张成的集合)
- 向量:指向某个点的箭头。(具有长度和方向)
重复再写一遍式子:
v∗B=w我们将B定义为L(B),也就是格基
在这个式子中,v向量就是对格基B上的元素进行线性组合,去张成其他点(例如向量w)。
那么考虑这样一种情况,如果这个张成的点的向量长度足够小(而w恰恰正是那条!),我们是否可以规约出来?
例如图下所示:
(假设红色那条为最短向量,此时他为格空间的最短向量)
此时的情况是二维的,但为了方便理解,我直接了当地说:
- 格基B就是灰色部分。
- 向量v没有绘出。
- 向量w是由向量v与格基B线性组合成的红色箭头。
当我们对B进行规约的时候,极大概率是可以规约出红色那条的。这是二维情况下的直观理解,其他维度大抵同理吧。
这个概率是多少呢?根据高斯启发式可知,大致比这个期望值小就行。
高斯启发式:GH(L)=2πendet(L)1/n
那么回到题目:我们对构造的矩阵进行LLL规约,得到的就是这条比较小的向量(图为二维情况下,但大致意思同)
也就是说我们可以直接通过构造吧noice向量给解出来!此时再代回原式子进行求解就行。
再来拓展一些技巧(配平),根据题目直接构造式子通俗易懂,但如果我们想要直接规约出flag呢?该如何进行:
像这样在B的最后一列再加个1就好:
[m,1,k1,k2,k3,k4]⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡Mask1−cp000Mask2−c0p00Mask3−c00p0Mask4−c000p100000⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=[noise1,noise2,noise3,noise4,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]))
|
回到基本的实战中:
把这个例子2的基本参数换成RSA该有的东西,拿去和维纳攻击的那个例子作比较,其实就差不多是等价的了,在开头的博客链接里面有示例。大致上理解了以上东西,再去学构造也差不多了。
未完待续,先玩会星穹铁道。