之前建博客的时候说会把一些非WP的内容搬到论坛，然后后来很多东西都和某道题目的WP混在一起写了，所以论坛这边就不知不觉咕了大半年（逃
所以仔细想想，有些内容即使混着WP还是可以搬过来的，顺便蹭一下SEO，所以
原文链接：https://tover.xyz/p/resultant-companion-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还解密？等着大佬来指点