结式、伴随矩阵、特征多项式和2023江苏省数据安全竞赛的hardrsa

思路比较新奇的一道题，马克一下。

本来是@V问的题目，后来由@春哥去问了全知全能的@maple，才有了点思路，于是在这马克一下。

附一下@maple原话：

WriteUp·

题目：https://www.nssctf.cn/problem/4461

审题，Part1是一个带pad的RSA加密$c \equiv m^{e_1} \pmod n$，Part2是一个承诺Commitment，在承诺中，

$$c_1 \equiv m^{d_2} + k_{ey}^8 + k_{ey}^4 + k_{ey}^2 \pmod n \\ c_2 \equiv f(k_{ey}) \pmod n$$

现知道$n, e_1, c, e_2, f, c_1, c_1$，求$m$。

Resultant·

首先看看结式Resultant，根据中文数学wiki里的介绍，Resultant是Sylvester Matrix的行列式，比如对多项式$f$和$g$，他们的Resultant记作$\text{res}(f, g)$，关于Resultant的知识这里先留坑，只需要知道它可以用作二元多项式方程组的消元，参考wiki

举个栗子：

# sage
R = PolynomialRing(ZZ, 'x, y')
x, y = R.gens()
f = R.random_element()	# 4*x^2 - x*y + 15*y^2 - x + 1
g = R.random_element()	# -x^2 - 5*x*y - 19*y^2 + 2
print(f.resultant(g, x))	# 5695*y^4 + 493*y^3 - 1016*y^2 - 39*y + 79
print(f.resultant(g, y))	# 5695*x^4 - 2788*x^3 + 6621*x^2 - 1862*x + 2401

代入题目中，现在知道

$$f_1 \equiv m^{d_2} + k^8 + k^4 + k^2 \pmod n \\ f_2 \equiv f(k) \pmod n$$

由于$m$和$d_2$未知，如果把$m^{d_2}$看成未知数，那么$f_1$和$f_2$就是关于$m^{d_2}$和$k$的一个二元多项式方程组（模$n$），计算他们的Resultant就可消去烦人的key

在这里如果直接使用像上面的f.resultant(g, x)的话会报TypeError: Singular error:，这里引用@maple的解释：

但问题不大，因为我们知道“Resultant是Sylvester Matrix的行列式”，所以只用求出$f_1$和$f_2$的Sylvester Matrix然后求行列式即可

R = PolynomialRing(Zmod(n), 'md, k')
md, k = R.gens()
f1 = md + k^8 + k^4 + k^2 - c1
f2 = sum([poly[i] * k^i for i in range(len(poly))]) - c2
res = f1.sylvester_matrix(f2, k).det()

到这里测一下res的类型会发现是multi_polynomial，但实际上它只有一个未知数，所以需要转成univariate_polynomial，另外后面我还需要求它的伴随矩阵，所以还需要转成monic，于是最后一句应该写成

res = f1.sylvester_matrix(f2, k).det().univariate_polynomial().monic()

到这里res即$\text{res}(f_1, f_2)$就是一个关于$m^{d_2}$的多项式，这个$d_2$还有点麻烦，所以需要先消去

PS：实际上是因为后面需要和c做GCD，而c是关于$m$的多项式，在GCD前需要统一c和res的未知数（估计把c转成关于$m^{d_2}$的多项式也行，留坑

Companion Matrix·

先看看不是多项式的情况，如果知道$m^{d_2} \pmod n$和$e_2$，那么直接计算$m \equiv (m^{d_2})^{e_2} \pmod n$即可，即普通的RSA解密，但问题是不可以直接对多项式做这样的操作

于是就需要用到伴随矩阵，根据wiki，只要多项式$p(x)$是monic的就可以转成以下的伴随矩阵$C(p)$，且矩阵$C(p)$的特征多项式即是$p(x)$

不妨先看看wiki中特征多项式的定义的第一句，$C(p)$的特征多项式是$p(x)$也即$p(x)$的解就是$C(p)$的特征值（代入题目的话，就是$C(r_{es})$的特征值中的其中一个是$m^{d_2}$）

接下来对矩阵$C(p)$进行特征分解，分解成$C(p) = V^{-1}DV$，

其中的$D$是对角线上放着$C(p)$所有特征值的对角矩阵

如果熟悉特征分解的话，就会知道他的一个作用是用于求矩阵幂的加速，即

$$C(p)^a = (V^{-1} D V)^a = V^{-1} D^a V$$

$D^a$对角矩阵次方的结果即对角线上是$\lambda_i^a$，把特征分解合回去，即得$C(p)^a$是特征值是$\lambda_i^a$的矩阵，其特征多项式是根为$\lambda_i^a$的矩阵

把上面这些代进题目中，只需要求$C(r_{es})^{e_2}$的特征多项式，即得到其中一个根为$m$的多项式

原理说了这么多，其实代码只需要一行

fres = (companion_matrix(res) ^ e2).charpoly()

PS：虽然特征分解出的不一定是对角矩阵，如果$p(x)$有重根的话就是Jordan Form，但Jordan Form由于不影响特征值所以好像也能做，待确认，先留个坑，可以先给个简单的栗子说明特征值没受影响

R = PolynomialRing(ZZ, 'x')
x = R.gen()
f = R((x-131)^2 * (x+45678)) 
c = companion_matrix(f.monic())
j = c.jordan_form()
print((j^3).eigenvalues())	# [-95306219005752, 2248091, 2248091]
print(131^3)	# 2248091

Greatest Common Divisor·

现在虽然有了根为$m$的多项式，但其实不能直接用这个多项式求根，因为模$n$多项式的求根是一个困难问题，所以需要找别的方法

先来看看多项式的一些性质，假设多项式$f$有一个根是$a$的话，它就可以被分解为

$$f(x) = (x - a) * f'(x)$$

当然在这里不能通过分解res求$m$，不然就解了模$n$多项式的求根难题了

前面说了，c也是一个关于$m$的多项式，也就是res和c可以被分解为

$$f_{res}(x) \equiv (x - m) * f'(x) \pmod n \\ f_{c}(x) \equiv (x - m) * f''(x) \pmod n$$

所以只需计算

$$\text{GCD}(f_{res}(x), f_{c}(x))$$

即可得到$(x - m)$然后即可恢复$m$

PS：在SageMath中直接对模$n$多项式用gcd的话会报NotImplementedError，所以还需要自己实现一遍，另在计算GCD是要用monic的多项式，不然结果好像会错

def polygcd(a, b):
  while b:
    a, b = b, a%b
  return a.monic()  # need monic ...

Padding·

虽说c是关于$m$的多项式，但因为Part1中的加密加了pad，所以这个多项式会有点复杂

先来分析一下pad，其实就是在msg后面不断重复len(msg) & 0xff直到字符长度为2048 // 8 - 1，而len(msg) & 0xff的变化只有256中，可枚举

令$m$为$x$（以构造根为$m$的多项式），把上面的padding粘上去，然后求$e_1$次幂做RSA加密，再减去$c$即可得到一个根为$m$的多项式，至于怎么粘，多调试一下就好了，假设ml是我枚举的len(msg)，那么$f_c$就是：

mx = x * 2^(2048 - 8*(ml+1)) + sum([(ml & 0xff) * 2^(8*i) for i in range(2048//8 - ml - 1)])
fc = mx^e1 - c

Exp·

最后就是枚举ml，然后计算g = polygcd(fc, fres)，如果g的degree为$1$的话把$m$提取出来检查是否为flag即可，也可以像我这样检查g是否为$1$，即$f_{res}$和$f_{c}$是否互素

参考代码：

import libnum

e1 = 233
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
c = 4236463649246394372490570028773321531426122440354351428997745409269923078428264643984899276198044684405861411922920531424639487584475747440112668094733950281377813868988540407013967573584191516922420060508458881142111648007775541541206593622564564631875373635260315932740995440619035591722675173125322220642392862827996987221780888705796026865917969313975598350208578877195524822778355327253625950282635041414028859491576352297298051077024341409125083650148374909480761558443601847884116325029903499801566422663448734010004472905405209374692154735955178855634936508017264189084568424915164265136679303107745093554391

e2 = 99181398864848350371016820825262886005052515653150198897546275436659368873943
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
poly = [11693140800527031176333218506340138430240732192854115958431704393516665671354696442539228569575338743555295185742126489158430815263152939757778849261704565332700814864041988371030487621611557506812653488873444536543143499111306076278080422306914610758456202844384883419669780999835836102076447921204517046598938140064244383099665415296806730515287813702062130475281955202867695799707516205462251852912274330831232375362037653669046715539164625549785400699583991291522758317569231805551847554593188947041531361947659444681456741424693383958548943092649257246992511287359572983628972516677506780721131000304618999959240, 8649833849514355009128561581797540267452805179286553003531347469534976088903045945255322948772127884435044654450320045837146400545547035413423698519877318250595578140049443137749594587635124784776640002144869420735353810166877391696732603701567388813523929688499591774843294322221335666734637085035509293762539158494372418206937167893545676403532672666734540153869114591107560124251452526082108870638702356111887843199439729119638581693415233654435010304861838471514755642714031294943492873471199466178392719343340089957082809543276507257853855309815913146064538017999492250838671852901021723088900839652630087246141, 10438652195883831412435505413668253747222376993835057512571018586886172468948369796145782100970559858131410652399919261454018181151110711244715955202406007064700539815605400586293839962095578425689125884220411946405356203770630361655071021743875660757465221991116870667245627142015074048387044977823496726850652712591020608153928488470683315016742274925734216097962308837642472645606961264797331661105479206824511239562468503777960135923781994521205671697654968415294210654160582131094288074290198995839634141037654146239631046959485219534841518635072303135929794463631818179287771643492272214514760725403082404954077, 6299797573437298253264628040275849948907328879976403409079992234253896659195171862234483958852183317706433020249500667696777456584466888790659866599735145200280792478137705987287433143791976037155630359309176772317673958151640355448435973240969550879845354695745860375206302178000370970096709147495071090575765018242388707621300316998885753178573503094652529005706228511805022756376570371219075764243214260191102332714962783026379460713478294288812651004299398765770489801066856526467071118037951998756053462219010773133084404686760087508480150118199064293552990969966284945601004840346771690026959557356854894243142, 5983820380221904115440358005660480412823344425839483679019674090060688612423646544886814493835896810583739677554610487986153726859924027361158809156736196645803178995096319914672180274662462472664438431485027075620562484665653780178408855146763748596173882017604170478152671447791422988271913561725716787175269110153429606771827175728957339646431861352878283239969487426243742285835160804730331718691578524218241320715981666141098574100230167376734068738383108974392515927882240711793555447542821660698352614753928088082506778754171275154966436158307349089886252792151153113074617130452582559608047038630881997177039, 8645965524213201512342533940160639034615963495013466945596780273953897799745861434427630308300521898525016597999525817531163934211570038600077012713829688089842641388807750705270930654414851381582193662566863633088157205775657627097344504719056435375579887356258011212827309329133255360061251120340523712584772477488197868145839887008419529501177350232970834479788126170916738231188284692568626261063508315725550701926154671018704631776622326225119240790109750932269682399309418540027656506064831086635915646225839228991353015865676434534451013307891476809505965003364463706502868834742525815830814492484165778659587, 8166140295702705700395932322789090244824428366114951893911644134774959163562810185361333621863609139128772766004899397707351421904667080061768039818505350911041979508989714659275009135159974367690971928143915291585444591471643654394998052988522554930699706249604920467869677602144648519540475773077094544621879816388166112425971849485960827238183936548150306573608653859245355573339051077997289111414512279487536882904628267661230723738630443448632824642827281459881525198877210749057510831197018233179399730814958129875964180438394548470264377690208812256581197996134290095012248199229098363134875105995583143456168, 7886150187486607733887128114395381216280632497989629748521639744973030901762862876238518693357844959238094796545062411041606956447558438012468158689781248611833577676585338278147089873855656470245899229225464314602079901728048645256171396517696354087510327916826422932730522688556064550363916637523771395744826680925934243060230500845916621676929436788265600433752247152028066595489876401981088262668869028915433063354318691392248675089923289405167438193023160255479805758334680481491101176946904940583407560870907209114968515837974428072735042388612237381596523708101955987248270337329833158967647159556534902013893]
c1, c2 = (9026467857515594907139807322545643350722792398333959966810869076838279879742354562376888810480050803270079309674260152449220680190968011586239815898932783620194546687257066163982003360839627375768650529178687560019057911732404297565185448089372452182330617296119274984700102752558018626083227105916899465707167123429214371669495986051607781832508462509001195586237627932854012820647829936908023798167666909963391041754465967388417732502397794744032988693994711566201865393143230144593516438201799281519569197057042946810458619730130134659584342739598850633062984339223231306255977280483664354044871774659593149033209, 5887596182170973664955287957462647377802905573127495764035296813527168813405478740764981971139443147816701320451276508908764320611456709375484716332728626903126128547418401252520849124559671921918551772662755206548324883488334170067283423978156495671895979491847768306791576421069205614999618915580196468910801165217204877300901375945537974466575619851388784172797986385425693707736028155214422059085724499916277733254676564775837649200298391496783417808690237433893136207762575843230800924871422368332950754364751040187058272878178869385694948947692002564148365094951441755961075673329949416511183562799400968841515)

R = PolynomialRing(Zmod(n), 'md, k')
md, k = R.gens()
f1 = md + k^8 + k^4 + k^2 - c1
f2 = sum([poly[i] * k^i for i in range(len(poly))]) - c2
#print(f1.resultant(f2))  # not implemented

# https://math.fandom.com/zh/wiki/%E7%BB%93%E5%BC%8F#%E4%BA%8C%E5%85%83%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%96%B9%E7%A8%8B%E7%BB%84
res = f1.sylvester_matrix(f2, k).det().univariate_polynomial().monic()
# https://en.wikipedia.org/wiki/Companion_matrix#Diagonalizability
fres = (companion_matrix(res) ^ e2).charpoly()

def polygcd(a, b):
  while b:
    a, b = b, a%b
  return a.monic()  # need monic ...

R = fres.parent()
x = R.gen()
for ml in range(10, 2048//8):
  mx = x * 2^(2048 - 8*(ml+1)) + sum([(ml & 0xff) * 2^(8*i) for i in range(2048//8 - ml - 1)])
  fc = mx^e1 - c
  g = polygcd(fc, fres)
  if g == 1:
    continue
  flag = -g[0] % n
  print(ml, flag)
  flag = libnum.n2s(int(flag))
  print(flag)

总结·

菜（：

PS：exp中部分代码参考了@maple的exp，其实很多地方好像都只有唯一的写法，不然会报各种奇怪的错误

PPS：这个Commitment好像有点不太“正宗”，正常的Commitment应该是承诺一个消息，以后打开时发送消息然后用承诺值判断这个是否之前承诺的消息，但这里好像体现不出来，而且Reveal还解密？等着大佬来指点