出了三道Crypto水题

最近为Sloth的选拔赛出了三道Crypto“简单题”，应陈队长的要求，写了个WriteUp。

题目的源码和答案脚本都公开在Github仓库里。

vulfulKE·

这个灵感来源于NTRU-KE这篇论文（其实已经被发现可以中间人攻击了），魔改了一翻就是这个题了。

题目是一个KE（Key Exchange），按照代码的意思和最后给的hint，是这样的：

Step1（for A）：

$$r_a, s_a \leftarrow T(d, d) \\ e_a \equiv pr_a+s_a\ (mod\ q)$$

Step2（for B）：

$$r_b, s_b \leftarrow T(d, d) \\ e_b \equiv pr_b+s_b\ (mod\ q)$$

Step3和Step4的过程其实不用管，只要知道最后交换的Key是：

$$K_a = K_b = (s_as_b\ (mod\ q))\ (mod\ p) = s_as_b\ (mod\ p)$$

就好了，至于最后一个等号为什么成立，先来看一下T的定义：

意思是，$T(d_1, d_2)$返回的是有$d_1$项是+1，$d_2$项是-1的多项式（当然，$d_1+d_2<=N$）;那么$s_as_b$最大的系数不会大于$2d$，即$s_a$和$s_b$的+1项（模q）乘起来后只剩指数为$c$的项，即$s_a$和$s_b$的-1项（模q）乘起来后也只剩指数为$c$的项，举个栗子：

$$\begin{align} d &= 2, \ \ N = 5 \\ s_a &= x^4 + x^3 - x - 1 \\ s_b &= x^3 + x^2 - x - 1 \\ s_as_b &= 1 + 2x - 3x^3 - 3x^4 + 2x^6 + x^7\ (mod\ x^5-1) \ \ \\ &= 1 + 4x + x^2 - 3x^3 - 3x^4 \\ \end{align} \\$$

最大的系数是$2d=4$，在$x^1$项。题目给的$d$是$5$，$2d$即$10$，很显然是小于$q=2048$的。所以：

$$s_as_b\ (mod\ q) = s_as_b$$

然后题目给了$e_a$和$e_b$（模拟A、B通信时被窃听），如果把$e_a$和$e_b$乘起来的话：

$$\begin{align} e_ae_b &= (pr_a+s_a)(pr_b+s_b)\ (mod\ q) \\ &= p^2r_ar_b+ps_a+ps_b+s_as_b\ (mod\ q) \\ &= p^2r_ar_b+ps_a+ps_b+s_as_b \\ &= s_as_b\ (mod\ p) \\ &= K_a = K_B \end{align}$$

第三个等号为何成立上面已经解释过一遍了，知道了Key后后面就是一次普通的AES解密，脚本：

# sage
from Crypto.Hash import SHA3_256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# parameters
N = 509
p = 3
q = 2048
d = 5

R.<x> = ZZ['x']

# functions
def convolution(f,g):
    global N
    return (f * g) % (x^N-1)

def balancedmod(f,q):
    global N, R
    g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
    return R(g)

# from out
Ea = x^468 - 3*x^457 - x^418 + x^377 - x^281 - 3*x^276 - 3*x^270 + 3*x^244 + x^241 + 3*x^220 + 3*x^219 - x^185 - 3*x^149 - x^138 + x^110 + 3*x^58 + 3*x^47 - x^41 + x^40 - 3*x^35
Eb = x^499 - x^495 + 3*x^485 + 3*x^472 - x^454 + x^429 - x^421 - 3*x^389 - 3*x^383 + x^381 - 3*x^350 - x^324 + 3*x^302 - x^287 + 3*x^229 + 3*x^221 - 3*x^207 - 3*x^97 + x^52 + x^40
Cipher = b'\xb6\xe2\xa5\x07\xe7\xe8!!\xac\xb8\xb8\r\x06\xd4`\xf9=\x15f\xd2\x8f\x98\xfa\xfc\x0e\xd0_\xd5\xe6\xe3\x10t\x92\xfd\x01+c\x88ZNR!p\xeb\x8e\x84\x81\xf0N\xff\xa4\xc8B\x90\\\n\xbd%\x8d\x1f/\xb4\x85T'
Ea = R(Ea)
Eb = R(Eb)

# hack
K = balancedmod(balancedmod(convolution(Ea, Eb), q), p)

# Key
hobj = SHA3_256.new()
hobj.update(bytes(str(K).encode('utf-8')))
Key = hobj.digest()

# decrypt
aes = AES.new(Key, AES.MODE_ECB)
flag = aes.decrypt(Cipher)
print(unpad(flag, 32))

不过因为是选拔赛，为了防止把人都劝退坑了~~（但后来其实也并没防到）~~，所以留了个非预期解：

观察一下e的构成：

$$\begin{align} e &= pr+s\ (mod\ q) \\ &= pr+s \end{align}$$

那么把e中的系数是±p的项和系数是±1的项分离出来后，即可恢复r和s（无脚本.）。

扩展（多项式乘法，卷积）·

记：

$$a(x) = a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_1x+a_0 \\ b(x) = b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0\\$$

那么$a(x)*b(x) = c(x)\ (mod\ x^n-1)$可以写成：

$$(a_0, a_1, ..., a_{n-1}) \begin{pmatrix} b_0 & b_1 & b_2 & \cdots & b_{n-1} \\ b_{n-1} & b_0 & b_1 & \cdots & b_{n-2} \\ b_{n-2} & b_{n-1} & b_0 & \cdots & b_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b_1 & b_2 & b_3 & \cdots & b_0 \\ \end{pmatrix} \\ = (c_0, c_1, ..., c_{n-1})\ \ (mod\ x^n-1)$$

可以观察到$a$乘上$b$的每一列的下标和模n是一样的。根据这个就可以很容易的构造出上面的”栗子“了。

babyKnap·

简单的背包密码（KnapSack），用背包密码的解法可以解，这个在下一题再讲（Github给的预期解）。

这里讲一下较简单的解法，题目是对flag的每个byte用相同的公钥各进行一次背包加密，加密如下：

$$S = \sum_{i=1}^{n}x_iM_i$$

$x_i$是那个byte的一位，$M_i$是公钥；公钥是知道的，一个byte只有$2^8=256$种情况，完全可以列个表把256种可能的S都存起来，然后拿密文查表即可恢复出flag（人话：爆破）。

M = [9530281573991126869, 16968150138575267893, 17766734670940897570, 10961868430066885229, 14541311909632720933, 17085188397343521115, 16372215539280934197, 14139407420367658549]
Ss = [68192288746140620775, 66361385116492407511, 48874292229883824012, 82331696166508279324, 90749688108864364371, 47479773098223860639, 74377472569583430174, 45696753239583050692, 49276196719148886396, 65959480627227345127, 62068968778863984889, 90068141835266987916, 63415604139516544945, 76208376199231643438, 90068141835266987916, 80500792536860066060, 74377472569583430174, 90068141835266987916, 82331696166508279324, 63415604139516544945, 62068968778863984889, 66361385116492407511, 68192288746140620775, 62068968778863984889, 63415604139516544945, 65959480627227345127, 82733600655773341708, 51820073206859686578, 65765450517198073815, 91462660966926951289]
N = len(M)

def enc1(a):
  x = '{:08b}'.format(a)
  x = [int(a) for a in list(x)]
  S = sum([x[i]*M[i] for i in range(N)])
  return S

bpS = []

for i in range(2**8):
  bpS.append(enc1(i))

res = ''
for S in Ss:
  res += chr(bpS.index(S))
print(res)

strongerKnap·

魔改了一下普通的背包加密，把原来的明文只有0和1（二进制）改成明文可以是小整数的（为了最后凑出来的格维度不会太大），和上一题不同，这里只做了一次加密，爆破是不可能的（即和爆破flag是等同的），但是可以用普通背包（二进制）的格解法来解的；难度略大于前两题（因为没有非预期解~~，应该~~）。

$$S = \sum_{i=1}^{n}x_iM_i \\ \sum_{i=1}^{n}x_iM_i - S = 0$$

用格解背包和各种方程的方法在上上上篇文章里已经提过了（建议看一下，安利），大概是可以构造这样一个东西：

$$(x_1, x_2, ..., x_n， -1) \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & M_1 \\ 0 & 1 & 0 & \cdots & 0 & M_2 \\ 0 & 0 & 1 & \cdots & 0 & M_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & M_n \\ 1 & 1 & 1 & \cdots & 1 & S \\ \end{pmatrix}_{(n+1)*(n+1)} \\ = (x_1-1, x_2-1, ..., x_n-1, 0)\\$$

记为$v*L=w$；先来求一下L的行列式（可以搜一下箭形/爪形的行列式解法）：

$$\begin{align} det(L) &= \begin{vmatrix} 1 & 0 & \cdots & 0 & M_1 \\ 0 & 1 & \cdots & 0 & M_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & M_n \\ 1 & 1 & \cdots & 1 & S \\ \end{vmatrix} = \begin{vmatrix} 1 & 0 & \cdots & 0 & M_1 \\ 0 & 1 & \cdots & 0 & M_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & M_n \\ 0 & 0 & \cdots & 0 & S-\sum_{i=1}^{n}M_i \\ \end{vmatrix} \\ &= S-\sum_{i=1}^{n}M_i = \sum_{i=1}^{n}x_iM_i - \sum_{i=1}^{n}M_i = \sum_{i=1}^{n}(x_i-1)M_i \end{align}$$

接着求（x四位十位数、n=20、M有1024bits）：

$$\|w\| \le \sqrt{n}*max(x_i-1) < \sqrt{n}*O(10^4) \\ \sigma(L) \approx \sqrt{n}*(\sum_{i=1}^{n}(x_i-1)M_i)^{1/(n+1)}=\sqrt{n}*O(10^{4/21}*2^{1024/21})$$

然后可以估算一下（具体值不好算，所以都是按规模来算的）：

$$10000 = 10^4 << 10^{4/21}*2^{1024/21} \approx 740068926129646$$

所以有：

$$\|w\| < \sigma(L)$$

即w有大概率是L中的最短向量，于是用LLL求出来L的最短向量就有大概率是w（这题就是），于是求出$x_i-1$即求出$x_i$，拼接一下恢复flag：

# sage
import libnum

M = [120294571677898903240356152530487900741280701903373310345664434531211977763153804007281367752216605848960771169521503642368299661918603284481616432510271592697939555031118390135818862120042020489132292886891304720752890636063977645910076571564306845917868721730284669936796293742405809304943848135655414392811, 129700172801436249990591241970079237595724409885942082029764751594750448122109720946440896043552212011373294236481721010708519180759376629667496680095668230592581876675890030318671384784476378111069216304265728859311561790201316980640417692709193146527911688184199547568510451810733102730266782757489826433253, 159435722877331641976354184328068656574066348217923673970411843567774833279349405915976056408154044302638225291184459000867268892567293562302192688442455762220218530452508512828390835779765011909648706615685385737786272185521217981360965521205148822608135595294169844942461546899141297400583513684962472092203, 115522054877336891552477735064038273124803846649701610587728061565916679303091116679228627287740195261921836119529033907275653832496948572551980945637103823629121124778416287302613255048379685646978252121771489405329324492281525048249297334467579793967518393566843843837432343220094880669009230454321885761529, 157946711211247950845415156354332555286481540650438711849354913769243740257367403205620958969866025255080058601363092891095863576770395163925706995965885715354617049744918993535515666298299300028827094956500268999781213149192859231875203023358911276765521847467528488785080976073016593567446027509779676997852, 140167985794605064855878146350480005748429733921686478434156333875199301094517088019596063564893422127086728617198393522897528599092983961609914436682653384343789127057610345747442309099842732654916861915550287840789330879055960877484889773667027108797802998463597815583699313187289062857453335220475850173649, 178296027423032926816853059328577406817122464033859553638661502429007240175594890823028730587123683410058257189558915795457888248745375404406981738640854423005712359679342534460889228936253723803552090353913412612516106804772872516183467698379324556995316808997798745210800290842043534027286031051964907324974, 121359207850683003517776013158505963634357829971511462863059960191512520079532777669417824657554243868290792651444574834106377317932258291830814517369768335537277651455261577193982285862539380563502830471071697950073090825690475034196589355897630092911734848744719062991990774126112179781784179630016429027178, 139732632048677850532372840322435115648421153587746304566151263858370395817513221382185610167571176721969183611101306060296562643804618209145437759035682963215402731410793640166003037085844412285656423311124128591859775293209525633704873668877031000746815483195809193379676434770968114110007454178039778753840, 177559257847095490274721234383101485509787406752336247385154807107465997813548489067284617197250980991917086190184325753736254997008747967523858623793984169171707265266701219863737395698653171875580083899072330927433785734205984887717069556296103184659708684046718166732646229977652795873299560829239763267287, 172357113946430612347302816713219422750937125928692687380947887254795558660784471516398196089985181402090642884781663714638371580362443175086368858012409343492048796867871276419707781904689756392703194766976738675888202016056707560354772587246125702042961447749362294071358852866178396428017536608453216620810, 95429399150492955414827702225169021905876176474434544437386377157379104632033531408403804632608479256686136202864266307794976278351363440386769619605820214396489627096432911422798315333899660401245389523016126435292295582680359606958100565081470442987653786440893423663410873746176881625871294157204946823953, 101949026933874774967050164077933618569804916796969487883537219937390224683154413972217100129173332674319080821019435671450062718518782193128492591693468939454825358745485383615499548707142037287100409481783048066029610174814148119808498130683674977066186834629597074110576157521420383677575323868880921357440, 158782190961588405189973145435707356384260472854894118536488482238698924571926908227894781120247396038143945578945413527440386514188985853506109002441443768257442338029299991841872761968671693206527199659450851391947712435556331311395096978129544255376357607442858592913719651863724395031787706363054085791474, 129155134338008562334033962787692652255896020600857731796626350181081709365046919953744630514400151772510555762587049906068524060954631763458880497099465436802595367689448713838280619900850377569931892695443987416596216663696095539514283793377507092881016274239068893768930999084329842545749386748550597455433, 148126499638629657838799168751690409474162809069188478853940812160354410617374908876537174768905856908356690976916998207880146602459316191962525384701595132638560776854433958762603448027448354372362408434718921977739885291470661466055981292982469241690881336923943065657248130317925500254046659168579263264805, 125863180289399354989672683393240804594426286942677844331973668361670048724754507583955430197919979969233926592034526315199620544528837570211598580125365588037459301507362932527000508781386936715527155213977051700569471286276879880240779027503450274870097899686246170622342742193453632601857731430329402200244, 138865975893051206264080483287993038817112579256527148002962294138227281026870951300683340569238371255056736068750873492129134843662725889267615077928423960481714478366971605667824377584934369366982048226603116003369251168739810208953684971024303176036443814516913540939506879172517468218763067726145785148352, 94065109763202487550806814470187330074507446811158359345679347740474821483252001173710197702309223201259401070695683668920866196800478671078168614949353650382317237707730223196092619477515575478715271086658119515754782505708131392237662500644996246016997257585595160383688492308707912010739558889880875561897, 144796387461212451257536305970216938765594956661059136009081877341345671457423015212369351045958995036782800715408256564887724912251939416015971194296917843428383512005126250915989663052434490960833418985349436582058642154145822109132545560614761341393984576141201750917359697136199588046032121848372077847718]
S = 12608351631387095568258553162541536931226118375817868009401236888991702843601313178949793108380206161734852041687214909846541496641542576065023537032702149056613936557270989302095924330517230621858668537233623546745028963467384699109033066380427081740284750250945430151990861540158747530117801195241749301973664403
N = len(M)

flag = ''
D = [1 for i in range(N+1)]
D[N] = 2^(256*N)
D = diagonal_matrix(ZZ, D)

Mt = identity_matrix(N+1)
for i in range(N):
    Mt[-1, i] = 1
    Mt[i, -1] = M[i]
Mt[N, N] = S
#Mt *= D
L = Mt.LLL()
b = vector(ZZ, L[0])

v1 = vector(ZZ, [1 for i in range(N+1)])
if b[-1]==0:
    if b[0]<0:
        x = list(v1-b)[:-1]
    else:
        x = list(b+v1)[:-1]
    flag = ''.join(['{:04d}'.format(a) for a in x])
    flag = libnum.n2s(int(flag))
    print(flag)
else:
    print('Opps')

其中有一点要注意的是LLL求出来的最短向量有可能要乘个-1，长度相等、方向相反。

-·

结果一题都没人做，浪费题目啊 -