参考：

原理：

已知：

$ c_1 \equiv m^{e_1}\pmod n,\qquad
c_2 \equiv m^{e_2}\pmod n, $

且存在整数 $ s_1,s_2 $ 使

$ e_1s_1+e_2s_2=1. $

证明：

$ \begin{aligned}
c_1^{,s_1}c_2^{,s_2}
&\equiv \bigl(m^{e_1}\bigr)^{s_1},\bigl(m^{e_2}\bigr)^{s_2}\pmod n \[2mm]
&\equiv m^{e_1s_1},m^{e_2s_2}\pmod n \[2mm]
&\equiv m^{,e_1s_1+e_2s_2}\pmod n \[2mm]
&\equiv m^{,1}\pmod n \[2mm]
&\equiv m \pmod n.
\end{aligned} $

因此

$ \boxed{,c_1^{,s_1}c_2^{,s_2}\equiv m \pmod n, }. $

共模攻击的基础在于有：两个公钥且互质（一般来说就是互质、因为是大素数）

所以这里引入一个函数：gcdext(e1, e2)是一个计算扩展最大公约数（Extended GCD）的函数

运行结果如上，这里常返回一个三元组 (d, x, y)，其中：

d：e1和 e2的最大公约数。

x, y：满足上述等式的整数系数（可能为负数）。

例题1：

n= 13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e1= 2333
c1= 12839285960223495540837529365339640783021439899108155136321855396508597591195084834231690640732914408618285996134049202996422114737474822115945692760871458165554118169402663520900701296114704740122786806542520699905862239914946533647899715822828542560800418499031431014437887839597676472165537391472198221714363610491291038442463223575122912669355380941374075599322428985304893846875110708290551186273543362765115647684956793570841630280930991407077401574158296542671529832884549202417721050055128956160795181219321381962644469613816746657814407025821523489911167830470453075666809891234756979759785607614579837734082
e2= 23333
c2= 3354756678232940495821979239801458007420410531822100812188898131516917749604851255269716527378343349516173106916414335163414268865824921119788877047553519631159949070051858008087712664995111487663781337726742683963116894637201549928831686056701870685405950856250977197910095810076403861881931015074416123490624856112462001350590171001296114611866177706693234039596982711256182797885834942186618425452535848339326240931859796433390218112045498069663580377366715346261942151557866185723732917427377138450852758541378023643134160677508933773941402646042004431292764888647202090679358894168736017515947373729257142729574

n= 13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e1= 2333
c1= 12839285960223495540837529365339640783021439899108155136321855396508597591195084834231690640732914408618285996134049202996422114737474822115945692760871458165554118169402663520900701296114704740122786806542520699905862239914946533647899715822828542560800418499031431014437887839597676472165537391472198221714363610491291038442463223575122912669355380941374075599322428985304893846875110708290551186273543362765115647684956793570841630280930991407077401574158296542671529832884549202417721050055128956160795181219321381962644469613816746657814407025821523489911167830470453075666809891234756979759785607614579837734082
e2= 23333
c2= 3354756678232940495821979239801458007420410531822100812188898131516917749604851255269716527378343349516173106916414335163414268865824921119788877047553519631159949070051858008087712664995111487663781337726742683963116894637201549928831686056701870685405950856250977197910095810076403861881931015074416123490624856112462001350590171001296114611866177706693234039596982711256182797885834942186618425452535848339326240931859796433390218112045498069663580377366715346261942151557866185723732917427377138450852758541378023643134160677508933773941402646042004431292764888647202090679358894168736017515947373729257142729574

import gmpy2
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s,s1,s2)
assert s==1 #!!!!注意

#错误算法
m = (c1**s1*c2**s2) % n
print("m=",m)

#正常算法
m=(pow(c1,s1,n)*pow(c2,s2,n))%n
print("m=",m)
act_m, torf = gmpy2.iroot(m, 3)
print("T or F=",torf)

from Cryptodome.Util.number import long_to_bytes as l2b
print(l2b(act_m))

//
1 -7781 778
act_m= 13040004482820198698847089094244152075790400869393100003271655421286266920976016007292478845
b'flag{6ed4c74e022cb18c8039e96de93aa9ce}'

这是一道最最基础的共模攻击。我先自己写了一个算法（错误算法，根据数学公式直接写的），但是没有做对，原因如下：

gcdext(e1,e2) 得到的 s,s1,s2 里至少有一个是负数

在 Python / gmpy2 里：

pow(c, s, n) 会把 s<0 解释为模逆（前提 gcd⁡(c,n)=1，整个过程都在整数环 Zn\mathbb{Z}_nZn 里进行，这是你 m1 的做法 → 正确。

c**s 当 s<0 时，不是“模逆幂”，而是实数幂：等价于 1/(c**|s|)。对巨大整数 c 和巨大指数 |s|，这会变成一个极小的浮点数，下溢成 ~0.0，随后

(c1**s1 * c2**s2) % n

是在浮点语义下的 %，得到你看到的 2.557...e-4315062 这种值 → 与模运算无关。

即：m2 错在错误的数学对象与数值域（浮点域 vs. 模 nnn 的整数域），不是“等价变形”的实现问题。

这是ai的回复，我的理解是py解释器会把负指数先算出来，gmpy2/pow函数会把负指数解释成逆元。

例题2

好我们接下来看另外一道例题：

from gmpy2 import *
from Crypto.Util.number import *
from secret import hint

hint=******
m = bytes_to_long(hint)
p = getPrime(256)
c = pow(m, 256, p)
print(p)

p, q = getPrime(256), getPrime(256)
n = p * q
e1, e2 = getPrime(32), getPrime(32)
c1, c2 = pow(c, e1, n), pow(c, e2, n)
print(n)
print(e1, c1)
print(e2, c2)

'''
(p=)107316975771284342108362954945096489708900302633734520943905283655283318535709
(n=)6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
(e1=)2303413961 (c1=)1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
(e2=)622163991 (c2=)1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
'''
#加粗的是用到的参数

from gmpy2 import *
from Crypto.Util.number import *
from secret import flag

flag = flag.strip(b"npuctf{").strip(b"}")
m = bytes_to_long(flag)

p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)

print(n)
print(c1)
print(c2)

'''
128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
'''

解题：

hint题解

s = gmpy2.gcdext(e1,e2)		#拓展欧几里得算法，s会有两个值，一个正一个负
cc1 = pow(c1,s[1],n)	#幂取模:(m1=（c1^s1）mod n)
cc2 = pow(c2,s[2],n)	#幂取模:(m2=（c2^s2）mod n)
c = (cc1*cc2)%n  
print(c)
#c=19384002358725759679198917686763310349050988223627625096050800369760484237557

e=256
m = sympy.nthroot_mod(c,e,p)
print("m=",m)
print(long_to_bytes(m))

解释一下nthroot_mod函数：

nthroots_mod(a, n, m) 求的是模 $ m $ 的 n 次方根集合：$ {,x \mid a \equiv x^n \pmod m,}. $

数学原理：

给定整数 $ a, n, m $，所谓“模 $ m $ 的 n 次方根”就是解方程：

$ x^n \equiv a \pmod m $

的整数解 $ x $。

例如：

模 $ 7 $ 下，解方程 $ x^2 \equiv 2 \pmod 7 $。
$ 3^2=9\equiv 2 $，$ 4^2=16\equiv 2 $。所以 $ 3,4 $ 是平方根。
nthroots_mod(2, 2, 7) 就会返回 $ {3,4} $。

运行结果如下：

m= 623314401187286670257694436875298172611109072944（这里只是出来一个）

b'm.bit_length() < 400'

flag题解

from gmpy2 import *
from Crypto.Util.number import *
from secret import flag

flag = flag.strip(b"npuctf{").strip(b"}")
m = bytes_to_long(flag)

p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)

print(n)
print(c1)
print(c2)

'''
128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
'''

这里引入数论的内容:

同余的基本性质：

$ n = p \cdot q $且$ a \equiv b \pmod{n} $，那么$ a \equiv b \pmod{p}, \quad a \equiv b \pmod{q}. $

证明：

若 $ n = p \cdot q $，且 $ p, q $ 都是 $ n $ 的因子。
如果

$ a \equiv b \pmod{n}, $

即 $ n \mid (a-b) $，
那么必然有

$ p \mid (a-b), \quad q \mid (a-b), $

即

$ a \equiv b \pmod{p}, \quad a \equiv b \pmod{q}. $

中国剩余定理的逆定理：

如果

$ a \equiv b \ (\text{mod} \ p) $ 且 $ a \equiv b \ (\text{mod} \ q) $

那么

$ （如果p、q互素）a \equiv b \ (\text{mod} \ p·q) $

$ （如果p、q不互素）a \equiv b \ (\text{mod} \ lcm(p·q)) $

费马小定理：

如果 p 是素数，且 a 是整数，且 a 不被 p 整除（即 a 与 p 互质），那么：

$ a^{p-1} \equiv 1 \ (\text{mod} \ p) $

在模 $ N $ 的同余方程

$ f(x) \equiv 0 \pmod N $

中，我们通常很难找到解，因为 $ N $ 很大（例如 RSA 的模数）。
如果 $ f(x) $ 是一个次数为 $ d $ 的整系数多项式，并且它在模 $ N $ 下有一个根 $ x_0 $，并且

$ |x_0| < N^{1/d}, $

那么可以在多项式时间内（LLL 算法）找到这个小根 $ x_0 $。

本题逻辑：

$ c_1 \equiv m^p \ \ (mod\ n) \ \ \ \ \ \ \ \ ,\ \ \ \ \ \ \ \ c_2 \equiv m^q \ \ (mod\ n)
$

$ n=p·q $

所以

$ c_1 \equiv m^p \ \ (mod\ p) \ \ \ \ \ \ \ \ ,\ \ \ \ \ \ \ \ c_2 \equiv m^q \ \ (mod\ q)
$

由费马小定理得

$ m^{p-1}\equiv1 \ \ (mod\ p) $

$ m^{q-1}\equiv1 \ \ (mod\ q) $

$ m^{p}\equiv m \ \ (mod\ p) $

$ m^{q}\equiv m \ \ (mod\ q) $

所以

$ c_1 \equiv m \ \ (mod\ p) $

$ c_2 \equiv m \ \ (mod\ q) $

所以

$ c_1 -m \equiv0 \ \ (mod\ p) $

$ c_2 -m \equiv0 \ \ (mod\ q) $

假设

$ f(x)=(c_1-x)·(c_2-x) $

构造的原因是因为要用到中国剩余定理的逆定理

有

$ f(m)=0\ (mod\ p) $

$ f(m)=0\ (mod\ q) $

由中国剩余定理逆定理可得

$ f(m)=0\ (mod\ n) $

在得出这样的式子之后就可以用LLL解m了：

n=128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1=96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2=9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
a=c1+c2
b=c1*c2
R.<x>=Zmod(n)[]
f = x^2-a*x+b
f.small_roots(X=2^400)


#m=4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855

py里面l2b即可：verrrrrrry_345yyyyyyy_rsaaaaaaa_righttttttt?

crypto1

来看这里遇到的crypto1：

from gmpy2 import *
from Crypto.Util.number import *

flag  = '****************************'
flag = {"asfajgfbiagbwe"}
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))

e1e2 = 3087
n = p*q
print()

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437

这里有两个加密过程、可以用共模攻击：

import gmpy2
from Cryptodome.Util.number import long_to_bytes as l2b

E=3087
flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437


for i in range(2,E):
    if E%i == 0:
        e1=i
        e2=E//e1
        print(e1,e2)
        s,s1,s2=gmpy2.gcdext(e1,e2)
        print("s=",s)
        m = (pow(flag1,s1,n)*pow(flag2,s2,n))%n
        m1 = gmpy2.iroot(m, s)[0]   //如果说e1和e2不互素，就用iroot，开方
        print(l2b(m1))

**iroot()**函数

gmpy2.iroot() 是 gmpy2 库中用于计算 整数的 s 次方根（即求整数的 s 次方根的最大整数解）的函数。这里m1 = gmpy2.iroot(m, s)[0]中的[0]是指读取iroot函数返回的第一个值。iroot返回两个值，第一个是开方值，一个是是否精确，以下是示例：

至此讲解完毕。8/30/25.

9/4调整排版。