Hermite定理

对任意nn维格LL，都存在一个非零向量v∈Lv \in L，满足

∥v∥≤ndet(L)1n \| v \| \leq \sqrt{n}det(L)^{\frac{1}{n}}

这个定理给出了nn维格LL下最短向量的长度上界。
主要用处就是决定LLL算法构造格的格大小，见下文NTRU。

还原最小多项式

原理

最小多项式的定义：设α∈F\alpha \in F，其中FF是一个域。α\alpha的最小多项式是在F[x]F[x]中次数最低的首一多项式，使得α\alpha是它的根。
下面我们利用LLL算法求α=54236.606188881754809671280151541781895183337725393\alpha=54236.606188881754809671280151541781895183337725393对应的最小多项式f(x)=x3+a2x2+a1x+a0f(x)=x^3+a_2x^2+a_1x+a_0，这里我们已知f(x)f(x)的次数为3。
已知：

α3+a2α2+a1α+a0=0\alpha^3 + a_2\alpha^2 + a_1\alpha + a_0 = 0

这里aia_i都是整数，构造如下的格：

(1,a2,a1,a0)[α3C100α2C010αC001C000]=(ϵC,1,a2,a1)(1, a_2, a_1, a_0)\begin{bmatrix} \alpha^3 C & 1 & 0 & 0 \\ \alpha^2 C & 0 & 1 & 0 \\ \alpha C & 0 & 0 & 1 \\ C & 0 & 0 & 0 \end{bmatrix}=(\epsilon C, 1, a_2, a_1)

为什么乘系数CC(?)放大系数能使我们更顺利得到结果，另一方面也能控制LLL算法是在整数格上进行
脚本实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
alpha=54236.606188881754809671280151541781895183337725393
alpha=QQ(alpha)
M=matrix(QQ,[
    [alpha**3,1,0,0],
    [alpha**2,0,1,0],
    [alpha**1,0,0,1],
    [alpha**0,0,0,0]
])
M[:,0]*=10**11
L=M.LLL()
v=L[0]
v
#(70149963488114924699986159734856445312500/126364533258555096002267702108181058661366989500513199270799915529, 1, -3, 3)

可以看出vv后面两个系数就对应a2,a1a_2,a_1，这里要注意得到的vv可能是相反的。
还有另外一种构造格的方式

(a0,a1,a2,1)[ C100α1C010α2C001α3C000]=(ϵC,a0,a1,a2)(a_0, a_1, a_2, 1)\begin{bmatrix} \ C & 1 & 0 & 0 \\ \alpha^1 C & 0 & 1 & 0 \\ \alpha^2 C & 0 & 0 & 1 \\ \alpha^3 C & 0 & 0 & 0 \end{bmatrix}=(\epsilon C, a_0, a_1, a_2)

背包问题

子集和问题

给定正整数a1,a2,…,ana_{1},a_{2},\dots,a_{n}(权重)，和一个目标整数ss，找到一个aia_{i}的子集其和为ss。也就是说，找到e1,e2,…,ene_{1},e_{2},\dots,e_{n}，使得ei∈{0,1}e_{i} \in \{0,1\}满足

∑i=1neiai=s\sum_{i=1}^{n} e_{i} a_{i} = s

为解决这样的问题，我们有两种构造格的方式。

(e1,e2,⋯ ,en,−1)⋅[1a11a2⋱⋮1ans]=(e1,e2,⋯ ,en,0)(e_1,e_2,\cdots ,e_n,-1)\cdot \left[ \begin{array}{cc} 1 & & & & a_1 \\ & 1 & & &a_2 \\ & & \ddots & & \vdots \\ & & & 1 & a_n \\ & & & & s \end{array} \right] = (e_1,e_2,\cdots,e_n,0)

或者

(e1,e2,⋯ ,en,−1)⋅[1Na11Na2⋱⋮1Nan1212⋯12Ns]=(e1−12,e2−12,⋯ ,en−12,0)(e_1,e_2,\cdots ,e_n,-1)\cdot \left[ \begin{array}{cc} 1 & & & & Na_1 \\ & 1 & & &Na_2 \\ & & \ddots & & \vdots \\ & & & 1 & Na_n \\ \frac{1}{2}&\frac{1}{2}&\cdots&\frac{1}{2}& Ns \end{array} \right] = (e_1-\frac{1}{2},e_2-\frac{1}{2},\cdots,e_n-\frac{1}{2},0)

其中N>nN > \sqrt{n}。
相对来说，第二种构造方式的普适率更高，但是也更复杂，构造完格之后经过LLL算法得到的最短向量需要+12+\frac{1}{2}之后才能得到正确的eie_i序列。

拓展

多重子集和问题

给定正整数a1,1,a1,2,…,a1,n,⋯ ,ak,na_{1,1},a_{1,2},\dots,a_{1,n},\cdots,a_{k,n}(权重)，和kk个目标整数s1,s2,⋯ ,sks_1,s_2,\cdots,s_k，找到一个aia_{i}的子集其和为sjs_j，对任意的1≤j≤k1 \le j \le k都成立。也就是说，找到e1,e2,…,ene_{1},e_{2},\dots,e_{n}，使得ei∈{0,1}e_{i} \in \{0,1\}满足

∑i=1neiaj,i=sj\sum_{i=1}^{n} e_{i} a_{j,i} = s_j

为解决这样的问题，我们构造如下格。

M=[10Na1,1Na2,1⋯Nak,110Na1,2Na2,2⋯Nak,2⋱⋮⋮⋮⋱⋮10Na1,nNa2,n⋯Nak,n1212⋯1212Ns1Ns2⋯Nsk]M=\left[ \begin{array}{ccccccccc} 1 & & & & 0 & Na_{1,1} & Na_{2,1} & \cdots & Na_{k,1} \\ & 1 & & & 0 & Na_{1,2} & Na_{2,2} & \cdots & Na_{k,2} \\ & & \ddots & & \vdots & \vdots & \vdots & \ddots & \vdots \\ & & & 1 & 0 & Na_{1,n} & Na_{2,n} & \cdots & Na_{k,n} \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & \frac{1}{2} & Ns_1 & Ns_2 & \cdots & Ns_k \end{array} \right]

则有如下关系

(e1,e2,⋯ ,en,−1)⋅M=(e1−12,e2−12,⋯ ,en−12,−12,0,0,⋯ ,0)(e_1,e_2,\cdots,e_n,-1)\cdot M=(e_1-\frac{1}{2},e_2-\frac{1}{2},\cdots,e_n-\frac{1}{2},-\frac{1}{2},0,0,\cdots,0)

模子集和问题

给定正整数a1,a2,…,ana_{1},a_{2},\dots,a_{n}(权重)，目标整数ss和模数MM，找到一个aia_{i}的子集其和为ss。也就是说，找到e1,e2,…,ene_{1},e_{2},\dots,e_{n}，使得ei∈{0,1}e_{i} \in \{0,1\}满足

∑i=1neiai≡s(modM)\sum_{i=1}^{n} e_{i} a_{i} \equiv s \pmod{M}

为解决这样的问题，我们构造如下格

M=[KM000⋯00Ka0200⋯00Ka1020⋯00⋮⋮⋮⋮⋱⋮⋮Kan−1000⋯20Ks111⋯11]M = \begin{bmatrix} KM & 0 & 0 & 0 & \cdots & 0 & 0 \\ Ka_0 & 2 & 0 & 0 & \cdots & 0 & 0 \\ Ka_1 & 0 & 2 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ Ka_{n-1} & 0 & 0 & 0 & \cdots & 2 & 0 \\ Ks & 1 & 1 & 1 & \cdots & 1 & 1 \end{bmatrix}

则有如下关系

(k,m0,m1,…,mn−1,−1)⋅M=(kKp+K∑i=0n−1aimi−c,2m0−1,2m1−1,…,2mn−1−1,−1)(k, m_0, m_1, \ldots, m_{n-1}, -1) \cdot M = \left( k Kp +K \sum_{i=0}^{n-1} a_i m_i - c, 2 m_0 -1,2 m_1 -1, \ldots, 2 m_{n-1}-1, -1 \right)

模多重子集和问题

给定正整数a1,1,a1,2,…,a1,n,⋯ ,ak,na_{1,1},a_{1,2},\dots,a_{1,n},\cdots,a_{k,n}(权重)，kk个目标整数s1,s2,⋯ ,sks_1,s_2,\cdots,s_k和模数MM，找到一个aia_{i}的子集其和为sjs_j，对任意的1≤j≤k1 \le j \le k都成立。也就是说，找到e1,e2,…,ene_{1},e_{2},\dots,e_{n}，使得ei∈{0,1}e_{i} \in \{0,1\}满足

∑i=1neiaj,i≡sj(modM)\sum_{i=1}^{n} e_{i} a_{j,i} \equiv s_j \pmod{M}

例题

knaspack 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
from random import *
from Crypto.Util.number import *
from secret import flag
assert flag[:5] == b'flag{' and flag[-1:] == b"}"
def enc(alist , p , m):
    mlen = len(m)
    m = bytes_to_long(m)
    mlist = [int(i) for i in bin(m)[2:].rjust(mlen*8 , '0')]
    c = 0
    for i in range(len(alist)):
        c += alist[i] * mlist[i]
        c %= p
    return c
def genkey(mlen , p):
    alist = []
    for i in range(mlen*8):
        alist.append(randint(1 , p))
    return alist
p = getPrime(256)
mlen = len(flag[5:-1])
alist = genkey(mlen , p)
c = enc(alist , p , flag[5:-1])
print(p)
print(c)
print(alist)
'''
p=67191628496712044464016024110365851526474838182599056919055439699452485213617
c=54238895788223589463933244676602660551946397184772803204162347611363416949577
[61326810433176735903504532187801369665128051897310851037188915019725978746103, 43402638308610858864318408646580034339413907004191718316175901840478159040957, 42390542093321519899537450474744140543751280116421146758473316901172047131113, 56896597742106081436425019617759062109485222184582367951528347447129572164322, 32570751710482195270061913348496565136250044513742519696760880386752778873811, 61758075776801948162030008526250297515986861885125372106009915817960523337712, 17901534391635152337180185094353774195005699533835434334454401202487871553155, 37224968021076601678779252418032575211293098320654003729681927583161420129989, 66632013717449804850355429413366970243474663609985952450938577489534085920003, 35974619403274260134835700925464745410923410819748863056314210975683776225104, 9355065195096066370091483642604325315610906829005526653679996673352630783897, 41395355731818926990588932383517527497979704155808220411775383743005052692706, 23228377143195316851037307484205130688971850925284408657025046032234229087847, 55034925010079541014162534680065125294995029338412015000235432834727244387402, 22796803534844622413032250267283103673778044434512326746274321710094368199795, 28423302290082670694577559430819296498654317760711594657406828398393189053464, 62943182613872170552899142178839372545496621446185159708587460802689639468234, 57162318567966209259634152418024532145350610807430203797869064329082268114479, 57939912065777353746664551422948107414867869652398396793882519108684713597583, 53313547976129054162605112594029272240399908172664152760843517176153502340370, 40891659060116869201561260394304796621829986813334341835937837483124787284194, 63388675469532937479532035764827950797595638869894722534933616276569192340616, 5291309451001335823922848355465017100090315519271072960727903957474111647305, 15033185654910297590845247559478628845985046498056740391334662815850166973634, 52932640599111761035164044171224219899522951996998752002890089124165402639516, 15610266469042786461645090053233784503935444584658166563101159837152092030116, 65603589631109965863891546418311663645475421050003755465153312312949244142449, 15908826441121881086251152268651644169035563070919049291602245715298430419030, 13069447019572043089199725838856485975679146773821075825208973047419707894107, 1236277437037979870136466726177216538630198127333826374045612936417199003166, 63556342877326296338910961864798196263122529254467607309766526773443477017384, 63345233757472721100576345352619895554610896689708423826717785179769394396119, 43506105869634664846829428537487296640801285027962409486655787711219414410762, 15980079227326178615595863297840352990586924236354053558281529650326056960399, 23988045552000522539946711241271746796489307752322153460280052083600532319999, 51448188758763744468444469208076236676232164465378520485952623055732291980710, 2601438180401574149670818552645133867489928288620839067412611182882562893934, 60876012302377278492969973549581165730767984140924243188426793750323108573836, 58420955446648378424669220500553174124077074763428789507169805555274805325395, 25198759542636003861634125287789051560304624563503474485231858634516294912703, 12172943067986147861317162186196588363589918007539817939985672245761975063601, 35414804705044313375395191213020872960798962815188335705125080299542642559842, 36289663665444618117450037244704865940062122783086873111077834035424430620717, 42305185265493925397630349758943426306129402035766861713241426912427199894631, 33262306517281860618370344625375550204619457675417202080529102937148158261677, 19419314192678574996128050074286538406007744453459115894403939626292074503381, 46708785382776306286357752455805855855026675566852683952047767131741937677437, 65370021107052349912354961121391583878637523285423299191266583970821677428472, 23243224054517002191438069648567385796722796103231872737593264390089410768312, 21283529050041576991936524061533075941062683020862436672605602811194550226811, 56701543167689673633910975168178218996624718444965993643697471301223007619325, 10864331909333253178754205786247960135254927329427180433417286207618669779512, 40856493191704046965268630831159156648711978343004641638346820697652315328448, 42226891584288722245375611487264407066916756021721368002233795483733737772380, 65818728773975419903236062747058400178345399280772690533961330688215998432450, 297316034392299988558467803058339068730040313068367648100366439092480076254, 31427675278158232490085166201920450541430649454103469195130744682506685989313, 64921142394990268221647435194358346973345440094348667052103791718906250924249, 2370831012003727302991540168976180915091512577468937825947827930972574273360, 15658676162687695673699834998705922658931894729510818203990683671777882485864, 62422115356498932214502375196459603051474916047923046241798949551149616455909, 8591599988096061698531002250910907801863223715433249579475249603148095532821, 52594109041497038420369996934114315631343717733669349155967163002785309882968, 38941620964349608101794830903256572530670059012533575884750958288725573215786]
'''

分析

这道题目构造的格不够好，建议参考上文的模子集和问题构造的格。
题目将flag的内容转换成二进制字符，作为背包加密的系数，我们的目标是把系数求出来。我们可以得到下面关系式

∑i=0n−1aimi−c=k⋅p⟺kp+∑i=0n−1aimi−c⋅1=0\begin{aligned} & \sum_{i=0}^{n-1} a_i m_i - c = k \cdot p \\ \Longleftrightarrow \quad & k p + \sum_{i=0}^{n-1} a_i m_i - c \cdot 1 = 0 \end{aligned}

下面我们构造向量格MM

M=[Kp00⋯00Ka010⋯00Ka101⋯00⋮⋮⋮⋱⋮⋮Kan−100⋯10Kc00⋯01]M = \begin{bmatrix} Kp & 0 & 0 & \cdots & 0 & 0 \\ Ka_0 & 1 & 0 & \cdots & 0 & 0 \\ Ka_1 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ Ka_{n-1} & 0 & 0 & \cdots & 1 & 0 \\ Kc & 0 & 0 & \cdots & 0 & 1 \end{bmatrix}

对应的线性关系是

(k,m0,m1,…,mn−1,−1)⋅M=(kKp+K∑i=0n−1aimi−c,m0,m1,…,mn−1,−1)(k, m_0, m_1, \ldots, m_{n-1}, -1) \cdot M = \left( k Kp +K \sum_{i=0}^{n-1} a_i m_i - c, \quad m_0, \quad m_1, \quad \ldots, \quad m_{n-1}, \quad -1 \right)

这里得到的结果向量的首项是0，后面都是0，1的序列，很大可能是构造格的最短向量，也就转换成了CVP问题，直接应用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 *
p=67191628496712044464016024110365851526474838182599056919055439699452485213617
c=54238895788223589463933244676602660551946397184772803204162347611363416949577
alist=[61326810433176735903504532187801369665128051897310851037188915019725978746103, 43402638308610858864318408646580034339413907004191718316175901840478159040957, 42390542093321519899537450474744140543751280116421146758473316901172047131113, 56896597742106081436425019617759062109485222184582367951528347447129572164322, 32570751710482195270061913348496565136250044513742519696760880386752778873811, 61758075776801948162030008526250297515986861885125372106009915817960523337712, 17901534391635152337180185094353774195005699533835434334454401202487871553155, 37224968021076601678779252418032575211293098320654003729681927583161420129989, 66632013717449804850355429413366970243474663609985952450938577489534085920003, 35974619403274260134835700925464745410923410819748863056314210975683776225104, 9355065195096066370091483642604325315610906829005526653679996673352630783897, 41395355731818926990588932383517527497979704155808220411775383743005052692706, 23228377143195316851037307484205130688971850925284408657025046032234229087847, 55034925010079541014162534680065125294995029338412015000235432834727244387402, 22796803534844622413032250267283103673778044434512326746274321710094368199795, 28423302290082670694577559430819296498654317760711594657406828398393189053464, 62943182613872170552899142178839372545496621446185159708587460802689639468234, 57162318567966209259634152418024532145350610807430203797869064329082268114479, 57939912065777353746664551422948107414867869652398396793882519108684713597583, 53313547976129054162605112594029272240399908172664152760843517176153502340370, 40891659060116869201561260394304796621829986813334341835937837483124787284194, 63388675469532937479532035764827950797595638869894722534933616276569192340616, 5291309451001335823922848355465017100090315519271072960727903957474111647305, 15033185654910297590845247559478628845985046498056740391334662815850166973634, 52932640599111761035164044171224219899522951996998752002890089124165402639516, 15610266469042786461645090053233784503935444584658166563101159837152092030116, 65603589631109965863891546418311663645475421050003755465153312312949244142449, 15908826441121881086251152268651644169035563070919049291602245715298430419030, 13069447019572043089199725838856485975679146773821075825208973047419707894107, 1236277437037979870136466726177216538630198127333826374045612936417199003166, 63556342877326296338910961864798196263122529254467607309766526773443477017384, 63345233757472721100576345352619895554610896689708423826717785179769394396119, 43506105869634664846829428537487296640801285027962409486655787711219414410762, 15980079227326178615595863297840352990586924236354053558281529650326056960399, 23988045552000522539946711241271746796489307752322153460280052083600532319999, 51448188758763744468444469208076236676232164465378520485952623055732291980710, 2601438180401574149670818552645133867489928288620839067412611182882562893934, 60876012302377278492969973549581165730767984140924243188426793750323108573836, 58420955446648378424669220500553174124077074763428789507169805555274805325395, 25198759542636003861634125287789051560304624563503474485231858634516294912703, 12172943067986147861317162186196588363589918007539817939985672245761975063601, 35414804705044313375395191213020872960798962815188335705125080299542642559842, 36289663665444618117450037244704865940062122783086873111077834035424430620717, 42305185265493925397630349758943426306129402035766861713241426912427199894631, 33262306517281860618370344625375550204619457675417202080529102937148158261677, 19419314192678574996128050074286538406007744453459115894403939626292074503381, 46708785382776306286357752455805855855026675566852683952047767131741937677437, 65370021107052349912354961121391583878637523285423299191266583970821677428472, 23243224054517002191438069648567385796722796103231872737593264390089410768312, 21283529050041576991936524061533075941062683020862436672605602811194550226811, 56701543167689673633910975168178218996624718444965993643697471301223007619325, 10864331909333253178754205786247960135254927329427180433417286207618669779512, 40856493191704046965268630831159156648711978343004641638346820697652315328448, 42226891584288722245375611487264407066916756021721368002233795483733737772380, 65818728773975419903236062747058400178345399280772690533961330688215998432450, 297316034392299988558467803058339068730040313068367648100366439092480076254, 31427675278158232490085166201920450541430649454103469195130744682506685989313, 64921142394990268221647435194358346973345440094348667052103791718906250924249, 2370831012003727302991540168976180915091512577468937825947827930972574273360, 15658676162687695673699834998705922658931894729510818203990683671777882485864, 62422115356498932214502375196459603051474916047923046241798949551149616455909, 8591599988096061698531002250910907801863223715433249579475249603148095532821, 52594109041497038420369996934114315631343717733669349155967163002785309882968, 38941620964349608101794830903256572530670059012533575884750958288725573215786]
n=len(alist)
M=matrix(ZZ,n+2,n+2)
M[0,0]=p
M[n+1,0]=c
for i in range(1,n+1):
    M[i,0]=alist[i-1]
for i in range(1,n+2):
    M[i,i]=1
M[:,0]*=2**32
v=M.LLL()[0]
v*=-1
v=list(v)
m=0
for i in v[:-1]:
    m=m*2+i
print(long_to_bytes(m))
#b'kn@Spack'

这里为了更好的使用LLL算法得到所求向量可以对矩阵MM的第一列乘上系数比如2322^{32}。

knaspack 2

题目

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
from random import *
from Crypto.Util.number import *
from secret import flag
assert flag[:5] == b'flag{' and flag[-1:] == b"}"
def enc(alist , p , m):
    mlen = len(m)
    m = bytes_to_long(m)
    mlist = [int(i) for i in bin(m)[2:].rjust(mlen*8 , '0')]
    c = 0
    for i in range(len(alist)):
        c += alist[i] * mlist[i]
        c %= p
    return c
def genkey(mlen , p):
    alist = []
    for i in range(mlen*8):
        alist.append(randint(1 , p))
    return alist
p = getPrime(256)
mlen = len(flag[5:-1])
alist = genkey(mlen , p)
c = enc(alist , p , flag[5:-1])
print(p)
print(c)
print(alist)
'''
98536890213320711958033892013472253591729456493016611497372260827973741432761
7911596336488180758952023656157299540257309322404932942027758643472951898345
[95584807798583114331438408711025267218689346683421616549299414623459550718819, 65134796795449121348799452555593019665253035224256889708017973324346974947093, 10369821535652135361088608092582209136464595667162040920002413874824929230610, 7821624743286667067964922665355828536452720508759148030822866341269596974002, 27038224125637922266615210333856364108972272305297159694124070133649825848049, 28994742964419395764925414591835033547951666312835315925899068764624820249600, 36296874205533424444245364847439039525151431977775931770898299196743570272844, 7245725716026586498806830353879684388397468862489149625720355533181424640330, 28224925975470483052196685844715423050323142201493783390955343500402939616930, 27759914136786437568704589481734991767103599838974410527287359052284910278191, 91441012573654190940028677669951675968793728081946175442239967841406505994185, 82872267232686290836776240880176600916653949073875609663671968864384573923149, 92564367494570917296787540858011211528241989767961285510937819314518612703418, 30411679560992720156054305993168261553116214023920875098889585273126544868596, 77595417975576359103014948448935868702816031862154014576856206986278470427324, 64361873016092554293694367667573068334039770828569661279434213902908689705927, 30071428269253213463960032780360547807856544584255353111947837305805688352744, 64143224775916722831767211102042819769353592832235812289884854741785784728941, 36049596864071953154393896289780741810596385086652498383920489455085596125082, 97467131975449491948949990796254959107724213480854912321052973265768525088472, 43794254433083914359306248811140983126384198445096461026193372685131129804464, 30814220572469393595024780228315178233588928097084998837753322116377805372306, 29013043577257868084786590530271291040197350048258337253177025967232952934134, 51361300098651537436085414440131677128067088456967926920593734996087832407176, 61844626764113722726006986990076250492533932865759154314679159980017975519630, 61689340416523305793934267140215931682882963949451097018559742073039269519411, 17187866939301301899369241928707272224405173373962599295643883572996944209924, 54329473874670814907839558469273974152143125983679734240266389715564734846514, 80958628129203900185507811971942774093931788545433982292746317252532166596079, 69433278366238647657894886015591147403380647156784410326898525325165629952395, 42730563799953598490635974289024235873060651964992288300202305612387963556949, 72795784416394680707567725250616623460382337947752503077081528463842140803298, 11174802800658439406316448395916695670374185105778513997028534368279511316799, 6284120167585819829949517185671479798517639386366462131609852807349031479498, 29999406576421185180433612136322861882371786894046918120547999902333302737660, 29764433573967663221345674557464130392104013060921402388829544490558157490131, 54312088528322453264786750914649140723201158441394384873586915984718285239161, 26709735961823195237702134015879274763891535328717642258296902314550245615435, 94732190888463371174385032262756789336087564646983009151925068066998040228741, 72224064346269569239095899741897645518767141054590356182715671717884140107910, 17172548128230610437606287855641661164361276061519445625877179725059980025993, 67534268255920960585792318623829583121409629250782704675854434751317433268461, 23922418192384337600217271147144920661976767124644692266859941024191054834138, 90211657547874382813246670669343826988170741316146622840476785985607023350817, 35908597468301476789046226877870517092016593502299513511214870249079946265016, 82320173681386220793113796594638468190974754075526660369758344413056122469488, 54418346032779356385665816442407272042466875969792618250675552886111112611963, 42717502437812965930768913376783822946581921669916362684158991682199236807659, 11723921994204648416761695208132493316182750252442694190952325370826773623060, 45416958443912700087578349257345324558475739107209548497801182792708795200189, 19499679714268253015993249732591116875680306361176334034519509818231312336047, 31250025165615770278330961867904560865192424076931330993826789667980194558959, 12934913785219344482380262671645067556932654444995684440538524944920430941899, 18733874446717934319914102472165683822459016990738684508357784497393224498789, 57336399090253838166755225364699876862250883856739548052014573071714141678368, 84892283342900347207309692325855351001974343440752895736193039686022665593036, 91757889343307154491193098142907071985380465968816689476707027656297693195884, 33960856697924530035869946181851390428643130610082689660740905759536594784349, 73971867223333062618760819470508908701352447931788138606755078418716745242354, 97194713764355960868970462039784791890410763089934037218181836753901291549867, 18441359254254384579439925538387469602364351490044082302887892224572364284815, 72340577444777861568601589440548220816301969509037432760942548840433544480060, 95586270130207653787118106803516752718843029402797059815100605205635056816531, 42478327464543413142980593720558574582084324630743706239418965761979341392889, 96607317740661301239336745943252074463040786933104670306807917724244014912112, 48651872206817148111480157882983423672182066751256211453119801591323403943786, 80903852829685496451380680982345222300209314357499520992192916428230451354330, 96315858690558257502315342969052385756497948280787016427212197616440200970122, 49047258620784796413469871703551413388676508814271869104352715517647732316306, 35074149787984514240946217231835560960144631086002218234406497142733193161516, 83647864862406682353122526793827896227534140439732089608548584115319708424897, 13002224653650890298987139119476867472558785282958839716751826574710332596350, 6243866228070275021910467349585955583582909455798247731282600830772638956076, 56275000100434237398399654247175460146986827271600144552113437371483253559316, 19827391328196738359447145882498539510491756754308325400394829478851614617944, 297504154638729305875158669175539300013618706286339185282534423385807366616, 43578919166483904334087559446061795447148432258599878816649154923647489342406, 66231426692285388364054036684168922896746948793850666007072133116917420705478, 76573073907903764848804035911371020881140741472438526447195910518485783808829, 89024819866706354566087734148966952368886357885837839497441580824944985189184, 29433769163662731656592449404446003121797964426305766284339154246785289582965, 15010990753204021261917616361764289665902158285790457561358765603777630928173, 11164942490143082047409665661738158422000265389777282506706017772517492966230, 33712929778562879180933330941430516467355352841038577373479130562149196410547, 93156345112691874438591909528376110349517854835464563608670150169170392923392, 57178402563079107439901834131956692628308093797492522821261660613570887618431, 95912200630234838947422170474953589699344160234548868264897424038176062802100, 65392772156978194501611597389703227606681209424641590417242038617099406725987, 45862484192615273538281601825065782911640789303952083864303530601764306131222, 38313755117691938218141637638360265932860471147051656701397398707309806114964, 20665963554052285725083908082221011873337209957650772727696455240908490550291, 62628858144025132956019033243999811747683028604516586261542682673113430409554, 13926111042214922552839909631284433663811804798781039276839517600548399327755, 37466888971972480728362458198780884184904274269114686100244905535301956760765, 3119613722763694653132776445275234380455995707306077757194674361147853909025, 53709896246274969598807833557393756808287413539064653383774812044070225159272]
'''

分析

这道题目跟上一题唯一的区别就是这里的背包更大，这个时候最好使用BKZ算法，构造格同上文模子集和问题相同

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 *
p=98536890213320711958033892013472253591729456493016611497372260827973741432761
c=7911596336488180758952023656157299540257309322404932942027758643472951898345
alist=[95584807798583114331438408711025267218689346683421616549299414623459550718819, 65134796795449121348799452555593019665253035224256889708017973324346974947093, 10369821535652135361088608092582209136464595667162040920002413874824929230610, 7821624743286667067964922665355828536452720508759148030822866341269596974002, 27038224125637922266615210333856364108972272305297159694124070133649825848049, 28994742964419395764925414591835033547951666312835315925899068764624820249600, 36296874205533424444245364847439039525151431977775931770898299196743570272844, 7245725716026586498806830353879684388397468862489149625720355533181424640330, 28224925975470483052196685844715423050323142201493783390955343500402939616930, 27759914136786437568704589481734991767103599838974410527287359052284910278191, 91441012573654190940028677669951675968793728081946175442239967841406505994185, 82872267232686290836776240880176600916653949073875609663671968864384573923149, 92564367494570917296787540858011211528241989767961285510937819314518612703418, 30411679560992720156054305993168261553116214023920875098889585273126544868596, 77595417975576359103014948448935868702816031862154014576856206986278470427324, 64361873016092554293694367667573068334039770828569661279434213902908689705927, 30071428269253213463960032780360547807856544584255353111947837305805688352744, 64143224775916722831767211102042819769353592832235812289884854741785784728941, 36049596864071953154393896289780741810596385086652498383920489455085596125082, 97467131975449491948949990796254959107724213480854912321052973265768525088472, 43794254433083914359306248811140983126384198445096461026193372685131129804464, 30814220572469393595024780228315178233588928097084998837753322116377805372306, 29013043577257868084786590530271291040197350048258337253177025967232952934134, 51361300098651537436085414440131677128067088456967926920593734996087832407176, 61844626764113722726006986990076250492533932865759154314679159980017975519630, 61689340416523305793934267140215931682882963949451097018559742073039269519411, 17187866939301301899369241928707272224405173373962599295643883572996944209924, 54329473874670814907839558469273974152143125983679734240266389715564734846514, 80958628129203900185507811971942774093931788545433982292746317252532166596079, 69433278366238647657894886015591147403380647156784410326898525325165629952395, 42730563799953598490635974289024235873060651964992288300202305612387963556949, 72795784416394680707567725250616623460382337947752503077081528463842140803298, 11174802800658439406316448395916695670374185105778513997028534368279511316799, 6284120167585819829949517185671479798517639386366462131609852807349031479498, 29999406576421185180433612136322861882371786894046918120547999902333302737660, 29764433573967663221345674557464130392104013060921402388829544490558157490131, 54312088528322453264786750914649140723201158441394384873586915984718285239161, 26709735961823195237702134015879274763891535328717642258296902314550245615435, 94732190888463371174385032262756789336087564646983009151925068066998040228741, 72224064346269569239095899741897645518767141054590356182715671717884140107910, 17172548128230610437606287855641661164361276061519445625877179725059980025993, 67534268255920960585792318623829583121409629250782704675854434751317433268461, 23922418192384337600217271147144920661976767124644692266859941024191054834138, 90211657547874382813246670669343826988170741316146622840476785985607023350817, 35908597468301476789046226877870517092016593502299513511214870249079946265016, 82320173681386220793113796594638468190974754075526660369758344413056122469488, 54418346032779356385665816442407272042466875969792618250675552886111112611963, 42717502437812965930768913376783822946581921669916362684158991682199236807659, 11723921994204648416761695208132493316182750252442694190952325370826773623060, 45416958443912700087578349257345324558475739107209548497801182792708795200189, 19499679714268253015993249732591116875680306361176334034519509818231312336047, 31250025165615770278330961867904560865192424076931330993826789667980194558959, 12934913785219344482380262671645067556932654444995684440538524944920430941899, 18733874446717934319914102472165683822459016990738684508357784497393224498789, 57336399090253838166755225364699876862250883856739548052014573071714141678368, 84892283342900347207309692325855351001974343440752895736193039686022665593036, 91757889343307154491193098142907071985380465968816689476707027656297693195884, 33960856697924530035869946181851390428643130610082689660740905759536594784349, 73971867223333062618760819470508908701352447931788138606755078418716745242354, 97194713764355960868970462039784791890410763089934037218181836753901291549867, 18441359254254384579439925538387469602364351490044082302887892224572364284815, 72340577444777861568601589440548220816301969509037432760942548840433544480060, 95586270130207653787118106803516752718843029402797059815100605205635056816531, 42478327464543413142980593720558574582084324630743706239418965761979341392889, 96607317740661301239336745943252074463040786933104670306807917724244014912112, 48651872206817148111480157882983423672182066751256211453119801591323403943786, 80903852829685496451380680982345222300209314357499520992192916428230451354330, 96315858690558257502315342969052385756497948280787016427212197616440200970122, 49047258620784796413469871703551413388676508814271869104352715517647732316306, 35074149787984514240946217231835560960144631086002218234406497142733193161516, 83647864862406682353122526793827896227534140439732089608548584115319708424897, 13002224653650890298987139119476867472558785282958839716751826574710332596350, 6243866228070275021910467349585955583582909455798247731282600830772638956076, 56275000100434237398399654247175460146986827271600144552113437371483253559316, 19827391328196738359447145882498539510491756754308325400394829478851614617944, 297504154638729305875158669175539300013618706286339185282534423385807366616, 43578919166483904334087559446061795447148432258599878816649154923647489342406, 66231426692285388364054036684168922896746948793850666007072133116917420705478, 76573073907903764848804035911371020881140741472438526447195910518485783808829, 89024819866706354566087734148966952368886357885837839497441580824944985189184, 29433769163662731656592449404446003121797964426305766284339154246785289582965, 15010990753204021261917616361764289665902158285790457561358765603777630928173, 11164942490143082047409665661738158422000265389777282506706017772517492966230, 33712929778562879180933330941430516467355352841038577373479130562149196410547, 93156345112691874438591909528376110349517854835464563608670150169170392923392, 57178402563079107439901834131956692628308093797492522821261660613570887618431, 95912200630234838947422170474953589699344160234548868264897424038176062802100, 65392772156978194501611597389703227606681209424641590417242038617099406725987, 45862484192615273538281601825065782911640789303952083864303530601764306131222, 38313755117691938218141637638360265932860471147051656701397398707309806114964, 20665963554052285725083908082221011873337209957650772727696455240908490550291, 62628858144025132956019033243999811747683028604516586261542682673113430409554, 13926111042214922552839909631284433663811804798781039276839517600548399327755, 37466888971972480728362458198780884184904274269114686100244905535301956760765, 3119613722763694653132776445275234380455995707306077757194674361147853909025, 53709896246274969598807833557393756808287413539064653383774812044070225159272]
n=len(alist)
M=matrix(ZZ,n+2,n+2)
k=1<<32
for i in range(1,n+1):
    M[i,i]=2
    M[i,0]=k*alist[i-1]
    M[n+1,i]=1
M[0,0]=k*p
M[n+1,n+1]=1
M[n+1,0]=k*c
L=M.BKZ(block_size=24)
v=list(L[0])[1:-1]
m=0
for i in v:
    if i==1:
        m=2*m+1
    else:
        m=2*m
print(long_to_bytes(m))
b'l0ngkN@SpAck'

HNP

原理

设 pp 是一个素数，设 α∈[1,p−1]\alpha \in [1, p-1] 是一个秘密整数。给定 mm 对整数 {(ti,ai)}\{ (t_i, a_i) \}，使得在 βi\beta_i 未知且满足 ∣βi∣<B|\beta_i| < B 的条件下有

βi−tiα+ai≡0(modp)\beta_i-t_i \alpha+a_i \equiv 0 \pmod{p}

我们可以将上述模等式重写成

βi=kip+tiα−ai\beta_i=k_ip+t_i \alpha-a_i

为解决这样的问题，我们构造如下格

M=[ppp⋱t1t2⋯tmBpa1a2⋯amB]M = \begin{bmatrix} p & & & & &\\ & p & & & &\\ & & p & & &\\ & & & \ddots & &\\ t_1& t_2 & \cdots &t_m & \frac{B}{p} &\\ a_1 & a_2 & \cdots &a_m & & B \end{bmatrix}

则有如下关系

(k1,k2,⋯ ,km,α,−1)⋅M=(β1,β2,⋯ ,βm,B⋅αp,−B)(k_1,k_2,\cdots,k_m,\alpha,-1)\cdot M=(\beta_1,\beta_2,\cdots,\beta_m,\frac{B \cdot \alpha}{p},-B)

根据LLL算法我们得到格M的最短向量，即可得到B⋅αp\frac{B \cdot \alpha}{p}，又B,PB,P已知，可求得α\alpha的值。
特别的是，格MM在LLL算法之后得到的第二个向量才是我们需要的向量。

例题

latticebros

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from secret import alpha
import gmpy2
from Crypto.Util.number import long_to_bytes
import random
p = 981020902672546902438782010902608140583199505022092121300069
B = 2**30
m = 30
samples = []
betas = []
f = open("samples.txt",'w')
for _ in range(m):
    t = random.randint(1, p-1)
    beta = random.randint(-B + 1, B - 1)
    a = (t * alpha - beta) % p
    samples.append((t, a))
    betas.append(beta)
f.write(str(samples))
for i in range(0,30):
    assert (betas[i]-samples[i][0]*alpha+samples[i][1])%p == 0
#flag = long_to_bytes(alpha)
#samples=[(541847931463604073209188621415697353813245102261880389530448, 293760933113243563398917466885108625646262447370201484418246), (235213326900086489464935804156966465366154623411555613791270, 660823982268225103178763707015491421784294988488272636270997), (826464884761457937459245903152143755707241416981488127320435, 428521663319038461250005113612781686761766888058391496085911), (589542000504317435156560078533519448295689695687499354390208, 155284353896000150766154807679279597476176668344402166959399), (968823371588600973965757332601758200815345862153455338808286, 870008943690791009196027169525956126827736285614393106689402), (621636099728440147413990266662022925118216803638588918660041, 265635912066749696542909843111997941904342442664219734956888), (426696569424050102229606043215592727790577655338668728275370, 279313121876980354011480010042682666651614765507190502627689), (89450479064580125731654556963306718472532905610952012502649, 465933125964565419295325650759566635253450915499965633327941), (480355476500393865742379469913983270769356894135485925662119, 894041172171871806404285309781862268351135623868845025443422), (842436524669577199024236805258573090764419350786291073287889, 345478552143958037534551648319293899442551000874041707820740), (650054674429185550652935714084022116516082323269321462104664, 441999979283903658157822753439653947343822546158589507765994), (46289431385578693366971976442426853079852982529357847290686, 625618376463384339878849844467050454204685252824782609369180), (71444185449163133531919043374545893927347050624346741281881, 955925578289311966288639224625142299309823207245807788495453), (192579726169321656812883068526498248523814846320328766176253, 626481822474054336470183912297952839011392733501646931370367), (736527635648804640774976580747540045854351230084566721853611, 276626211757586963928788091386096607703513204646314683038338), (177922521867185878959621840269164617147915792720210315529733, 541058782621716573816245900423919799500476442285991532228641), (40610451174818168154306630612571678739921107216052349044576, 727642592899858828601137105077611015328512898368636299587376), (385012983728389322601149562441674995471397288632464238356283, 353921151307105661267278594470212933060655245893209524497156), (750447975601038834764379841158092390933760641866111445401426, 391626416964965737035878375834907580903143512300198923948189), (115058604943298010958881205548782439407592353731185670266593, 491630592857258949793489206081490523001249620510479961058022), (327389234395954477946639629629085910688793716425320663599360, 24975272330009592102362429346350824580378490147041708568130), (115595274689129534885608766476695918464309130165432995990883, 757961876891952019297626599379744405302595090402128271144165), (950804723308776351161744501221236453742418549093165078282534, 20307246759635231945223392614290397512873344480184942904518), (724537610412063699714461780160573528810830178440136810747811, 149681928388378582933943374524511804362928290938917573644613), (340891278018589324130004945217960336392205386747747011263373, 683307718413135477104477081812052183267507312278283317237187), (104379682905784169840335131193505192063050242530811180817410, 715010230598797717533306270232399781090458356371977748416491), (644160326926600986730919713173510327120201404569141824224075, 127877985489410167008195578625004740882394608402141169695352), (549253388716005399852261816416312267100135940382820676807345, 210560134643237517255193955173709174155305784935427470113433), (968265711632086435506163736279856957220961064226797549228006, 273174723915971720522674140326199419265943707917542063022561), (704367622558261900937184683100177434487519780290678439135652, 959106497548134540301589019840013331842784496835379005298630)]

分析

直接如上构造格即可。

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 *
def attack(p,B,t_list,a_list):
    m=len(t_list)
    M=matrix(QQ,m+2,m+2)
    for i in range(m):
        M[i,i]=p
        M[m,i]=t_list[i]
        M[m+1,i]=a_list[i]
    M[m,m]=B/p
    M[m+1,m+1]=B
    L=M.LLL()
    v=L[1]
    alpha=p-v[-2]/B*p
    print(long_to_bytes(int(alpha)))
p=981020902672546902438782010902608140583199505022092121300069
B=2**30-1
samples=[(541847931463604073209188621415697353813245102261880389530448, 293760933113243563398917466885108625646262447370201484418246), (235213326900086489464935804156966465366154623411555613791270, 660823982268225103178763707015491421784294988488272636270997), (826464884761457937459245903152143755707241416981488127320435, 428521663319038461250005113612781686761766888058391496085911), (589542000504317435156560078533519448295689695687499354390208, 155284353896000150766154807679279597476176668344402166959399), (968823371588600973965757332601758200815345862153455338808286, 870008943690791009196027169525956126827736285614393106689402), (621636099728440147413990266662022925118216803638588918660041, 265635912066749696542909843111997941904342442664219734956888), (426696569424050102229606043215592727790577655338668728275370, 279313121876980354011480010042682666651614765507190502627689), (89450479064580125731654556963306718472532905610952012502649, 465933125964565419295325650759566635253450915499965633327941), (480355476500393865742379469913983270769356894135485925662119, 894041172171871806404285309781862268351135623868845025443422), (842436524669577199024236805258573090764419350786291073287889, 345478552143958037534551648319293899442551000874041707820740), (650054674429185550652935714084022116516082323269321462104664, 441999979283903658157822753439653947343822546158589507765994), (46289431385578693366971976442426853079852982529357847290686, 625618376463384339878849844467050454204685252824782609369180), (71444185449163133531919043374545893927347050624346741281881, 955925578289311966288639224625142299309823207245807788495453), (192579726169321656812883068526498248523814846320328766176253, 626481822474054336470183912297952839011392733501646931370367), (736527635648804640774976580747540045854351230084566721853611, 276626211757586963928788091386096607703513204646314683038338), (177922521867185878959621840269164617147915792720210315529733, 541058782621716573816245900423919799500476442285991532228641), (40610451174818168154306630612571678739921107216052349044576, 727642592899858828601137105077611015328512898368636299587376), (385012983728389322601149562441674995471397288632464238356283, 353921151307105661267278594470212933060655245893209524497156), (750447975601038834764379841158092390933760641866111445401426, 391626416964965737035878375834907580903143512300198923948189), (115058604943298010958881205548782439407592353731185670266593, 491630592857258949793489206081490523001249620510479961058022), (327389234395954477946639629629085910688793716425320663599360, 24975272330009592102362429346350824580378490147041708568130), (115595274689129534885608766476695918464309130165432995990883, 757961876891952019297626599379744405302595090402128271144165), (950804723308776351161744501221236453742418549093165078282534, 20307246759635231945223392614290397512873344480184942904518), (724537610412063699714461780160573528810830178440136810747811, 149681928388378582933943374524511804362928290938917573644613), (340891278018589324130004945217960336392205386747747011263373, 683307718413135477104477081812052183267507312278283317237187), (104379682905784169840335131193505192063050242530811180817410, 715010230598797717533306270232399781090458356371977748416491), (644160326926600986730919713173510327120201404569141824224075, 127877985489410167008195578625004740882394608402141169695352), (549253388716005399852261816416312267100135940382820676807345, 210560134643237517255193955173709174155305784935427470113433), (968265711632086435506163736279856957220961064226797549228006, 273174723915971720522674140326199419265943707917542063022561), (704367622558261900937184683100177434487519780290678439135652, 959106497548134540301589019840013331842784496835379005298630)]
t_list=[]
a_list=[]
for t,a in samples:
    t_list.append(t)
    a_list.append(a)
attack(p,B,t_list,a_list)
#b'NepCTF{c0ngr4tv!at1Ons!!}'

这里经过LLL算法之后，知道L的第二个向量即为所求的短向量，但是这里观察可以发现，向量vv的最后一个是BB而不是−B-B，所以得到的α\alpha是模pp意义下的负结果，所以需要取正数。

LLL05

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import uuid
import random
from Crypto.Util.number import *
p=getPrime(256)
F=Zmod(p)
print(p)
flag="flag{"+str(uuid.uuid4())+"}"
a=[ord(i)*getPrime(64) for i in flag]
c=random.randint(1,p)*vector(F,a)
print(c)
"""
62980779771903227230851051691602234849394507794819184914917088777039707221403
(3566121247525776674874337366082518184113777169411046964632471250620895553393, 1844063636233133891451521786124816349621721210128278517643051282314930045917, 56835654087138501208711172758295077756531630903617755145929516438511236849287, 1720522020617490067540699933956361928155523690394813356983623723622355342423, 9023248096032987318287379036905840797822729664243376166382922643953857139875, 52800790612210822212389303498396294359195317324299768619591912090411066581271, 43903537915641933965233016719739041872768795716831145363225117736749535726121, 7846328589916687705683969771756910149220780311793197295955777013566908702050, 33728363057460227791064129007654791554437064562713356865613118310548652210555, 39338780204305702764007549063675029055521747394789819675933048850851637560875, 52088769824415594439344821519902544236505910997121749264173022890516853949791, 21043266276198773362886606999248730182026564167467614370881836532806987977804, 7469361684527735284790582859841425510918045909855154847880483618541597475460, 18867044723211439627635910319789352314250529833894380939282416751757346967593, 4616456350806694829055525206242131548008135882446261857698447978383330955644, 18868371903857277933396632288979632956160361552955139769829307904085445596041, 59808576346218920883831156885980370144168125183351198498927483934572860135437, 1668517944133447224700957204683420412630996486144663911530020706859983036838, 50819796972953136887758020210639428422970954615953822280914859532020978571876, 9886835428005928895296959634412096059168272893098136717189509550703871252343, 39140285215563955351087941989624166838857311716763597818745993174100654066751, 34964457974005750284273544635950237200789726530792476403779603210496954337033, 15146125846907409222688482536690709531603408408006880897726808999360269738251, 57784418975076958268446044939345999959639264434476548187180301209347670627005, 10456135038921719360364838582469674552213666066292652377660389912643114725220, 16119774662740450873728644646768853804593920500392368569488443224696673867592, 8628228671077693803167007824359669368298906347295914199724756118489646080147, 18981934107936160626132775536605503499939234611731764109124809731617211162762, 3241397441253923074164337807225730265190373278071390294704689520875848544220, 27132812379300023847954453494367808499445934983290626667590195166120100836805, 50131557175436612139216931886981467896661096852209332666290448790791297487976, 55793068877739119693314046678033820150102553555504719859491248571885856279700, 50097335682968334229073729201621714053399738112469277088010833766488922002917, 60583533584352524046957201021281069711431381885718665166899146995759105126506, 39591961837763476038916634978140652703122208786313805854121574624111098205490, 24246009033664224364580950996082608652653198576040244287528465187940194613721, 3792802141541996907712969859647575526007995298563896592455034189974894726369, 39451054331360280831304339918552135377867257966370528626393719647790498366668, 51980644269725969550901169852972616551447072881066322244983546837016895448098, 47671383639041280781525749153929348342010096016350516598292418343175780847979, 12808664864188481878987427620105882717937598938140334893667328246759270390434, 51508920053339725524066336238660947251251646344245375347822950086454660501578)
"""

分析

构造过程就是ai⋅r≡ci(modp)a_i \cdot r \equiv c_i \pmod{p}，写成等式就是air=ci+kipa_ir=c_i+k_ip。但是我们只已知cic_i和pp，对于等式另一侧我们是不知道的，所以我们在等式两侧同时乘r−1r^{-1}。得到

ai=r−1ci+ki′pa_i=r^{-1}c_i+k_i'p

这个时候其实就挺像HNP问题了，只不过这里跟上面的HNP比起来泄露的aia_i部分都是0(不是指题目中的aia_i)。
于是我们构造如下格

M=[p000000p000000p000000⋱000000p0c0c1c2⋯cn−1Bp]M = \begin{bmatrix} p & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \\ \phantom{0} & p & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \\ \phantom{0} & \phantom{0} & p & \phantom{0}& \phantom{0} & \phantom{0} \\ \phantom{0} & \phantom{0} & \phantom{0} & \ddots & \phantom{0} & \phantom{0} \\ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & p & \phantom{0} \\ c_0 & c_1 & c_2 & \cdots & c_{n-1} & \dfrac{B}{p} \end{bmatrix}

则有如下关系

(k0,k1,⋯ ,kn−1,r−1)⋅M=(a0,a1,⋯ ,an−1,B⋅r−1p)(k_0,k_1,\cdots,k_{n-1},r^{-1})\cdot M=(a_0,a_1,\cdots,a_{n-1},\frac{B \cdot r^{-1}}{p})

如果像原来那样构造的话，底下会出现一行(0,0,⋯ ,0,0,B)(0,0,\cdots,0,0,B)这个过于简单的行会干扰LLL的准确性，所以我们索性删去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p=62980779771903227230851051691602234849394507794819184914917088777039707221403
c=[3566121247525776674874337366082518184113777169411046964632471250620895553393, 1844063636233133891451521786124816349621721210128278517643051282314930045917, 56835654087138501208711172758295077756531630903617755145929516438511236849287, 1720522020617490067540699933956361928155523690394813356983623723622355342423, 9023248096032987318287379036905840797822729664243376166382922643953857139875, 52800790612210822212389303498396294359195317324299768619591912090411066581271, 43903537915641933965233016719739041872768795716831145363225117736749535726121, 7846328589916687705683969771756910149220780311793197295955777013566908702050, 33728363057460227791064129007654791554437064562713356865613118310548652210555, 39338780204305702764007549063675029055521747394789819675933048850851637560875, 52088769824415594439344821519902544236505910997121749264173022890516853949791, 21043266276198773362886606999248730182026564167467614370881836532806987977804, 7469361684527735284790582859841425510918045909855154847880483618541597475460, 18867044723211439627635910319789352314250529833894380939282416751757346967593, 4616456350806694829055525206242131548008135882446261857698447978383330955644, 18868371903857277933396632288979632956160361552955139769829307904085445596041, 59808576346218920883831156885980370144168125183351198498927483934572860135437, 1668517944133447224700957204683420412630996486144663911530020706859983036838, 50819796972953136887758020210639428422970954615953822280914859532020978571876, 9886835428005928895296959634412096059168272893098136717189509550703871252343, 39140285215563955351087941989624166838857311716763597818745993174100654066751, 34964457974005750284273544635950237200789726530792476403779603210496954337033, 15146125846907409222688482536690709531603408408006880897726808999360269738251, 57784418975076958268446044939345999959639264434476548187180301209347670627005, 10456135038921719360364838582469674552213666066292652377660389912643114725220, 16119774662740450873728644646768853804593920500392368569488443224696673867592, 8628228671077693803167007824359669368298906347295914199724756118489646080147, 18981934107936160626132775536605503499939234611731764109124809731617211162762, 3241397441253923074164337807225730265190373278071390294704689520875848544220, 27132812379300023847954453494367808499445934983290626667590195166120100836805, 50131557175436612139216931886981467896661096852209332666290448790791297487976, 55793068877739119693314046678033820150102553555504719859491248571885856279700, 50097335682968334229073729201621714053399738112469277088010833766488922002917, 60583533584352524046957201021281069711431381885718665166899146995759105126506, 39591961837763476038916634978140652703122208786313805854121574624111098205490, 24246009033664224364580950996082608652653198576040244287528465187940194613721, 3792802141541996907712969859647575526007995298563896592455034189974894726369, 39451054331360280831304339918552135377867257966370528626393719647790498366668, 51980644269725969550901169852972616551447072881066322244983546837016895448098, 47671383639041280781525749153929348342010096016350516598292418343175780847979, 12808664864188481878987427620105882717937598938140334893667328246759270390434, 51508920053339725524066336238660947251251646344245375347822950086454660501578]
B=matrix(QQ,1,42)
for i in range(42):
    B[0,i]=c[i]
C=matrix(QQ,1,1)
C[0,0]=2**71/p
M=block_matrix([
    [p*identity_matrix(QQ,42),zero_matrix(QQ, 42, 1)],
    [B,C]
])
L=M.LLL()
a=list(L[0])[:-1]
#后面因式分解即可，与所写内容关系不大故略去。得到答案为flag{8357709e-d853-4f6e-8619-46a4c1fc6bc6}

LWE

一个LWE样本可以表示成以下形式

Am×nsn×1+em×1=bm×1(modp)A_{m \times n}s_{n \times 1}+e_{m \times 1}=b_{m \times 1} \pmod{p}

公钥：A,b,pA,b,p。
私钥：ss。
噪声向量：ee。

SLWE(搜索LWE问题)

SLWE问题也就是寻找私钥ss的过程。
为解决这样的问题构造如下格(其实就是多重HNP问题)

M=(1a1,1a2,1⋯am,11⋮⋮⋱⋮⋱a1,na2,n⋯am,n1−b1−b2⋯−bmpp⋱p)M= \begin{pmatrix} 1 & & & & a_{1,1} & a_{2,1} & \cdots & a_{m,1} \\ & 1 & & & \vdots & \vdots & \ddots & \vdots \\ & & \ddots & & a_{1,n} & a_{2,n} & \cdots & a_{m,n} \\ & & & 1 & -b_1 & -b_2 & \cdots & -b_m \\ & & & & p & & & \\ & & & & & p & & \\ & & & & & & \ddots & \\ & & & & & & & p \end{pmatrix}

对应的线性关系是

(s1,s2,⋯ ,sn,1,k1,k2,⋯ ,km)⋅M=(s1,s2,⋯ ,sn,1,e1,e2,⋯ ,em)(s_1,s_2,\cdots,s_n,1,k_1,k_2,\cdots,k_m)\cdot M =(s_1,s_2,\cdots,s_n,1,e_1,e_2,\cdots,e_m)

NTRU密码

直接见下面例题

例题

easyLattice

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag
import gmpy2
assert len(flag) == 47
f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p
print('h =', h)
print('p =', p)
"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
"""

分析

整理一下题目信息可以知道

h⋅f−k⋅p=gh \cdot f - k \cdot p =g

于是构造格

(f,−k)⋅[h1p0]=(g,f)(f,-k) \cdot \begin{bmatrix} h & 1 \\ p & 0 \end{bmatrix}=(g,f)

这就是NTRU密码最常见的构造形式。
然后我们根据Hermite定理分析一下可行性。对于格LL来说∣det⁡(L)∣=p\left| \det(L) \right| = p，这个时候最短向量的上限大概就是256位，而我们的目标短向量的长度是sqrtg2+f2≈fsqrt{g^2+f^2}\approx f，这里flag长度47，差不多是376位。显然我们的目标函数的位数超过了理论上限值，所以我们格LL的构造是不佳的，我们要经行放大。

(f,−k)⋅[h⋅K1p⋅K0]=(g⋅K,f)(f,-k) \cdot \begin{bmatrix} h \cdot K & 1 \\ p \cdot K& 0 \end{bmatrix}=(g\cdot K,f)

这里KK取什么好呢，我们可以写个脚本验证一下。

1
2
3
4
5
6
7
8
9
g=getPrime(128)
h=9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p=getPrime(512)
f=getPrime(376)
k=2**256
detbits=(gmpy2.iroot(2*p*k,2)[0]).bit_length()
vecbits=gmpy2.iroot((g*k)**2+f**2,2)[0].bit_length()
print(detbits)#385
print(vecbits)#384

差不多试探一下就可以了，最终只要满足detbits稍大于vecbits即可。所以我们取K=2256K=2^{256}。最终脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
h=9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p=11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947
k=2**256
M=matrix(ZZ,2,2)
M[0,0]=h*k
M[0,1]=1
M[1,0]=k*p
L=M.LLL()
v=L[0]
g,f=abs(v[0])//k,abs(v[1])
print(long_to_bytes(f))
#b'SICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84'

ez_ntru

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from secret import flag
import libnum
bits = 2048
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  f = random_prime(2^(3*bits//4 - 1))
  g = random_prime(2^(bits//4 - 1))
  if gcd(f, q*g) == 1:
    h = f.inverse_mod(q) * g % q
    break
r = random_prime(2^(3*bits//4 - 1))
m = libnum.s2n(flag)
assert m < 2^(bits//4)
c = (r * h + m) % q
print('q = %d' % q)
print('h = %d' % h)
print('c = %d' % c)
q=24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h=4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c=23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351

分析

整理一下题目信息得到两个式子

h⋅f−k⋅q=gc=r⋅h+m(modq)h\cdot f - k \cdot q=g \quad \quad c=r \cdot h +m\pmod{q}

难点肯定是rhrh这一项比较难处理，如果我们只是对等式两边模hh的话，rhrh确实没有了，但是cc%h的位数是2048位的，而mm小于512位，肯定是失效的。所以尝试将hh替换。

c=r⋅h+m=r⋅gf−1+m=>cf=rg+mf(modq)c=r\cdot h+m =r \cdot g f^{-1} +m => cf=rg+mf \pmod{q}

而mm的位数是小于gg的，所以两边模gg是可行且合理的。

m=(cf(modp))⋅f−1(modg)m = (cf \pmod{p}) \cdot f^{-1} \pmod{g}

这里的f−1f^{-1}是ff关于gg的逆，注意这里cfcf要先模pp。下面只要求出ff和gg，同上一题构造格

(f,−k)⋅[h⋅K1q⋅K0]=(g⋅K,f)(f,-k) \cdot \begin{bmatrix} h \cdot K & 1 \\ q \cdot K& 0 \end{bmatrix}=(g\cdot K,f) 

1
2
3
4
5
6
7
8
g=getPrime(511)
f=getPrime(1535)
p=24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
k=2**1024
detbits=(gmpy2.iroot(2*p*k,2)[0]).bit_length()
vecbits=gmpy2.iroot((g*k)**2+f**2,2)[0].bit_length()
print(detbits)#1537
print(vecbits)#1536

得到K=21024K=2^{1024}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
q = 24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h = 4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c=23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351
k=2**1024
M=matrix(ZZ,2,2)
M[0,0]=h*k
M[0,1]=1
M[1,0]=k*q
L=M.LLL()
v=L[0]
g,f=abs(v[0])//k,abs(v[1])
m=(c*f%q)*inverse(f,g)%g
print(long_to_bytes(m))
#b'flag{7c95453a-e577-40d8-9ad0-993655b83b69}'

Easy_3L

题目

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
45
46
47
48
from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h
def encrypt1(m):
    a = getPrime(250)
    b = getRandomNBitInteger(240)
    n = getPrime(512)
    seed = m
    s = [0] * 6
    s[0] = seed
    for i in range(1, 6):
        s[i] = (s[i - 1] * a + b) % n
    return s
def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c
s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])
p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)
'''
#S1=28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
#S2=1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
#S4=9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
#S5=9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
#p=25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
#h=2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
#c=20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
'''

分析

这道题目是一个线性同余生成器，但是s3s_3被加密隐藏了，所以我们先求出s3s_3。

s3=k⋅p+c−s⋅hs_3=k\cdot p + c - s \cdot h

所以构造如下格

(k,1,−s)⋅[p00c10h01]=(s3,1,−s)(k,1,-s) \cdot \begin{bmatrix} p & \phantom{0} &\phantom{0}\\ c & 1 & \phantom{0} \\ h & \phantom{0} & 1 \end{bmatrix}=(s_3,1,-s)

简单讲讲为什么这样构造吧，第一列是显然的，后面两列1的选择是因为1和ss的位数是可以估计的，但是kk是未知的。
值得注意的是，如果我们跟前两题一样把放大系数KK放在第一列

(k,1,−s)⋅[p⋅K00c⋅K10h⋅K01]=(s3⋅K,1,−s)(k,1,-s) \cdot \begin{bmatrix} p\cdot K & \phantom{0} &\phantom{0}\\ c\cdot K & 1 & \phantom{0} \\ h\cdot K & \phantom{0} & 1 \end{bmatrix}=(s_3\cdot K,1,-s)

这个时候我们再取跑求KK的脚本，会发现detbits永远小于vecbits，所以需要调整KK的位置。怎么理解呢，我们得到的目标向量是严重不平衡的两侧的ss部分显然远大于1，为了调整平衡肯定是调整中间1的部分。

(k,1,−s)⋅[p00cK0h01]=(s3,K,−s)(k,1,-s) \cdot \begin{bmatrix} p & \phantom{0} &\phantom{0}\\ c & K & \phantom{0} \\ h & \phantom{0} & 1 \end{bmatrix}=(s_3,K,-s) 

1
2
3
4
5
6
7
8
p=25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h=2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c=20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
k=2**200
M=matrix(ZZ,[[p,0,0],[c,k,0],[h,0,1]])
L=M.LLL()
print(abs(L[0][0]))
#10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606

下面就是一个完全的LCG问题。这里我们a,b,na,b,n都是未知的，下面证一下nn是怎么求的。

tn=sn+1−sn=(asn+b)−(asn−1+b)=a(sn−sn−1)=atn−1t_n=s_{n+1}-s_n=(as_n+b)-(as_{n-1}+b)=a(s_n-s{n-1})=at_{n-1}

这样就得到一个模nn意义上的等比数列，同样有一个优美的性质。

Tn=tn+1tn−1−tn⋅tn=a⋅a⋅tn−1⋅tn−1−a⋅tn−1⋅a⋅tn−1=0(modn)T_n=t_{n+1}t_{n-1}-t_n \cdot t_n=a\cdot a\cdot t_{n-1} \cdot t_{n-1}-a\cdot t_{n-1}\cdot a\cdot t_{n-1} = 0 \pmod{n}

所以我们取两个不同的TiT_i和TjT_j取个gcd就可以得到nn。

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 *
import gmpy2
s1=28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
s2=1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
s3=10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606
s4=9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
s5=9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
#求n
t1=s2-s1
t2=s3-s2
t3=s4-s3
t4=s5-s4
n=gmpy2.gcd(t3*t1-t2**2,t4*t2-t3**2)
#求a
a=t2*gmpy2.invert(t1,n)
#求b
b=(s2-a*s1)%n
#求s0
s0=(s1-b)*gmpy2.invert(a,n)%n
print(long_to_bytes(s0))
#b'DASCTF{NTRU_L0G_a6e_S1mpLe}'

Common d Attack

相关文章
该问题是针对一种特殊情况：同一个m,dm,d，生成不同的n,en,e加密得到不同的cc。
攻击的核心肯定是根据dd来下手，我们知道ed≡1(modφ(n))ed\equiv 1 \pmod{\varphi(n)}，但是我们只知道公钥n,en,e，φ(n)\varphi(n)依旧还是困难的。这里我们选择φ(n)=n−p−q+1=n−s\varphi(n)=n-p-q+1=n-s，这样能与公钥联系起来。那么得到的等式也就是

d⋅ei−k⋅ni=1−k⋅sid\cdot e_i -k\cdot n_i=1-k\cdot s_i

于是我们构造格

(d,−k0,−k1,⋯ ,−kn−1)⋅[e0e1⋯en−1Mn000000n100000⋱0⋮000nn−10]=(1−k0s0,1−k1s0,⋯ ,1−kn−1,d⋅M)(d,-k_0,-k_1,\cdots,-k_{n-1}) \cdot \begin{bmatrix} e_0& e_1 & \cdots & e_{n-1} & M \\ n_0 & \phantom{0} & \phantom{0} & \phantom{0} & 0 \\ \phantom{0} & n_1 & \phantom{0} & \phantom{0} & 0 \\ \phantom{0} & \phantom{0} & \ddots & \phantom{0} & \vdots \\ \phantom{0} & \phantom{0} & \phantom{0} & n_{n-1} & 0 \end{bmatrix} =(1-k_0s_0,1-k_1s_0,\cdots,1-k_{n-1},d\cdot M)

这里我们通常取M=niM=\sqrt{n_i},于是得到dd。

例题

题目

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
from Crypto.Util.number import *
flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)
for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = inverse(d, (p-1)*(q-1))
    c = pow(flag, e, n)
    print(f'e{i} =', e)
    print(f'n{i} =', n)
    print(f'c{i} =', c)
'''
e0=14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0=104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0=66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1=62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1=89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1=75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2=5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2=53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2=22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3=57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3=97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3=56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
'''

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
e0=14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0=104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0=66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1=62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1=89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1=75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2=5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2=53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2=22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3=57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3=97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3=56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
M=isqrt(n0)
A=matrix(ZZ,5,5,[[e0,e1,e2,e3,M],[n0,0,0,0,0],[0,n1,0,0,0],[0,0,n2,0,0],[0,0,0,n3,0]])
d=abs(A.LLL()[0][4])//M
print(long_to_bytes(pow(c0,d,n0)))
#b'NSSCTF{12514adb-2c14-4777-96ff-90e95bc2b5cb}'

HSSP

HSSP(Hidden Subset Sum Problem，隐藏子集和问题)问题大概如下：
取大素数pp，整数α1,⋯ ,αn∈Zp\alpha_1, \cdots, \alpha_n \in \mathbb{Z}_p，向量x1,⋯ ,xn∈F2m\pmb{x_1}, \cdots, \pmb{x_n} \in \mathbb{F}_2^m为m维向量，令

h=(h1,⋯ ,hm)≡∑i=1nαixi(modp)\pmb{h} = (h_1, \cdots, h_m) \equiv \sum_{i=1}^n \alpha_i \pmb{x_i} \pmod p

HSSP问题就是研究在已知h\pmb{h}和pp的情况下，如何还原出XX和α\pmb{\alpha}的问题。

原理

先补充线代里四大基本子空间的知识(列空间，行空间，零空间，左零空间)。
对于一个给定的m×nm \times n矩阵AA，如果把AA的每一列看作是基向量，张成的空间就是列空间，数学表示如下

{b∈Rm ∣ Ax=b, ∀x∈Rn}\{b \in \mathbb{R}^m\ |\ A \pmb{x} = b,\ \forall \pmb{x} \in \mathbb{R}^n\}

如果把AA的每一行看作是基向量，张成的空间就是行空间，数学表示如下

{b∈Rn ∣ xA=b, ∀x∈Rm}\{b \in \mathbb{R}^n\ |\ \pmb{x} A = b,\ \forall \pmb{x} \in \mathbb{R}^m\}

如果考虑的是这个方程Ax=0A \pmb{x}=\pmb{0}，得到的解空间就是零空间，数学表示如下

{x∈Rn ∣ Ax=0}\{\pmb{x} \in \mathbb{R}^n\ |\ A \pmb{x} = \pmb{0}\}

如果是xA=0\pmb{x} A =\pmb{0}，得到的就是左零空间，数学表示如下

{x∈Rm ∣ xA=0}\{\pmb{x} \in \mathbb{R}^m\ |\ \pmb{x} A = \pmb{0}\}

有一个重要的结论就是行空间与零空间相互垂直，列空间与左零空间相互垂直。
证明如下，取行空间向量b\pmb{b}，则满足xbA=b\pmb{x}_b A=\pmb{b}，取零空间内向量x\pmb{x}，则有Ax=0A \pmb{x}=0，于是

bx=xbAx=0\pmb{b} \pmb{x} = \pmb{x}_b A \pmb{x} =0

同理可以证明列向量与左零空间相互垂直。
另一个重要的结论是，行空间与零空间可以张成整个Rn\mathbb{R}^n空间，列空间与左零空间可以张成整个Rm\mathbb{R}^m空间
直观感觉上来说，令rr为矩阵AA的秩，那么列空间和行空间的维数就是rr，而零空间的维数是n−rn-r，左零空间的维数是m−rm-r。行空间与列空间相互垂直互不关联，刚好能张成维数为nn的空间。
由这两个结论可得，如果要求一个格的正交格（就是相互垂直的），那么只要求他的零空间（行看作基）或者左零空间（列看作基）就好。

Nguyen-Stern算法

给定h(modp)\pmb{h} \pmod p，首先找与h\pmb{h}垂直的向量u\pmb{u}，那么就有

u⋅h≡∑i=1nαi(u⋅xi)≡0(modp)\pmb{u} \cdot \pmb{h} \equiv \sum_{i=1}^n \alpha_i (\pmb{u} \cdot \pmb{x_i}) \equiv 0 \pmod p

令向量

pu=((u⋅x1),(u⋅x2),⋯ ,(u⋅xn))\pmb{p_u} = ((\pmb{u} \cdot \pmb{x_1}), (\pmb{u} \cdot \pmb{x_2}), \cdots, (\pmb{u} \cdot \pmb{x_n}))

那么问题就可以转化为

pu⋅α≡0(modp)\pmb{p_u} \cdot \pmb{\alpha} \equiv 0 \pmod p

也就是pu\pmb{p_u}和α\pmb{\alpha}在模pp的情况下相互垂直
然后如果u\pmb{u}是短向量的话，那么pu\pmb{p_u}也会是短向量（因为xi\pmb{x_i}的元素落在{0,1}\{0, 1\}中），如果pu\pmb{p_u}比所有与α\pmb{\alpha}垂直的非零向量都短的话，那么就只能是pu=0\pmb{p_u} = \pmb{0}
而如果pu=0\pmb{p_u} = \pmb{0}的话，就是u⋅xi=0\pmb{u} \cdot \pmb{x_i} = 0，令LxL_x是以x1,⋯ ,xn\pmb{x_1}, \cdots, \pmb{x_n}为基的格，就可以得到u∈Lx\pmb{u} \in L_x，即u\pmb{u}是LxL_x的正交格Lx⊥L_x^\bot中的向量
Lx⊥L_x^\bot的维度是m−nm-n：因为Lx⊥L_x^\bot的基的秩是r=nr=n（n≤mn \le m），然后我这里是看成行向量为基的空间（行空间），且LxL_x的基是nn行mm列的，所以根据前面的线性代数知识，与行空间垂直的零空间的维度就是m−r=m−nm-r = m-n
所以，如果我们可以找到m−nm-n个满足条件的向量u\pmb{u}的话，就相当于找到了LxL_x的正交格Lx⊥L_x^\bot，进而使用Lx⊥L_x^\bot找到LxL_x，最后由LxL_x恢复基x1,⋯ ,xn\pmb{x_1}, \cdots, \pmb{x_n}
于是，最后得到的攻击路线就是
1.用h\pmb{h}构造格基，LLL找到m−nm-n个短向量ui\pmb{u}_i
2.用ui\pmb{u}_i构造格Lx⊥L_x^\bot，用Lx⊥L_x^\bot找LxL_x的正交补Lxˉ\bar{L_x}（可以看作是和LxL_x同一个空间，但基不是xi\pmb{x}_i）
3.对Lxˉ\bar{L_x}使用BKZ恢复xi\pmb{x}_i

step1

首先先根据上面我们知道uh≡0(modp)\pmb{u} \pmb{h} \equiv 0 \pmod{p}，即∑i=1muihi≡0(modp)\sum_{i=1}^m u_i h_i \equiv 0 \pmod p，分离u1u_1则有

u1h1+∑i=2muihi≡0(modp)u_1h_1+\sum_{i=2}^m u_i h_i \equiv 0 \pmod p

两侧同乘h1−1h_1^{-1}，并转换成等式则

kp+∑i=2mui(−hih1−1)=u1kp + \sum_{i=2}^m u_i (-h_i h_1^{-1}) = u_1

于是我们构造格如下

B1=[M−h2h1−11−h3h1−11⋮⋱−hmh1−11]m×mB_1 = \begin{bmatrix} M & \\ -h_2 h_1^{-1} & 1 \\ -h_3 h_1^{-1} & & 1 & \\ \vdots & & & \ddots \\ -h_m h_1^{-1} & & & & 1 \end{bmatrix}_{m \times m}

线性关系如下

(k,u2,u3,⋯ ,um)⋅B1=(u1,u2,u3,⋯ ,um)(k,u_2,u_3,\cdots,u_m)\cdot B_1=(u_1,u_2,u_3,\cdots,u_m)

对格B1B_1进行LLL或BKZ操作即可得到m−nm-n个短向量ui\pmb{u}_i。

step2

首先根据上面分析，用L的前m-n就可以构造Lx⊥L_x^\bot
然后只需要求Lx⊥L_x^\bot的零空间就可以得到LxL_x的正交补Lxˉ\bar{L_x}
利用sagemath里的right_kernel函数即可得到。
值得注意的是，这里的Lxˉ\bar{L_x}和目标的LxL_x是同一个空间，只是格取的基不一样，如果讲两个格同时使用LLL会发现得到的新格是一样的，这也可以证明我们的结论。

step3

细看一下，x1,⋯ ,xn\pmb{x_1}, \cdots, \pmb{x_n}的元素在{0,1}\{0, 1\}中，这在01背包问题中也遇到过类似的问题，所以可以利用类似的解决方法，即把x1,⋯ ,xn\pmb{x_1}, \cdots, \pmb{x_n}转化为

2x1−1,2x2−1,⋯ ,2xn−12\pmb{x_1}-\pmb{1}, 2\pmb{x_2}-\pmb{1}, \cdots, 2\pmb{x_n}-\pmb{1}

就可以把元素转化到集合{−1,1}\{-1, 1\}中，构造格如下

B2=[−e2Lxˉ]n+1×mB_2 = \begin{bmatrix} -\pmb{e} \\ \hline 2 \bar{Lx} \end{bmatrix}_{n+1 \times m}

对于有些数据来说在这样操作完之后可能是得不到完整的xi\pmb{x}_i，误差来源在于这里构造格进行LLL或者BKZ之后，得到多组无效的xi\pmb{x}_i，但是我们实际上只能接受一组无效的，也就是第一行的向量。得不到完整的xi\pmb{x}_i也就会导致后面求解α\pmb{\alpha}时报错。根据目前的理解来看题目中大多构造模数pp的方式是

1
2
3
4
5
def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

但是这样的模数pp的前提条件是m=2nm=2n，如果mm取值不佳可能就会导致如上情况。
具体实现脚本如下

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
p=
h=
m=
n=
h1_=int(inverse_mod(h[0],p))
B1=block_matrix([
    [matrix(ZZ,1,1,[p]),zero_matrix(ZZ,1,m-1)],
    [matrix(ZZ,m-1,1,[-h[i]*h1_ for i in range(1,m)]),identity_matrix(ZZ,m-1)]
])
B1=B1.LLL()[:m-n]
Lxc=B1.right_kernel(algorithm='pari').matrix()
B2=block_matrix([
    [matrix(ZZ,[-1]*m)],
    [2*Lxc]
])
Lx=B2.BKZ()
print(Lx.nrows())
Lx=Lx[1:]
E = matrix(ZZ, [[1 for c in range(Lx.ncols())] for r in range(Lx.nrows())])
Lx = (Lx + E) / 2
Lx2 = []
e = vector(ZZ, [1] * m)
rsc = Lxc.row_space()
for lx in Lx:
    if lx in rsc:
        Lx2 += [lx]
        continue
    lx = e - lx
    if lx in rsc:
        Lx2 += [lx]
        continue
Lx = matrix(Zmod(p), Lx2)
vh = vector(Zmod(p), h)
va = Lx.solve_left(vh)
print(Lx)
print(va)

优化方向是：正常来说nn的值会特别大，用LLL或BKZ算法会导致运行时间很长，可以用flatter替代。 flatter