[NPUCTF2020]共 模 攻 击
上次做到了共模攻击的题，刚好来看看。
共模攻击
条件：当两个用户使用相同的模数 N、不同的私钥，且加密同一明文消息时即存在共模攻击。
原理：
设两个用户的公钥分别为e1和e2，且e1与e2互质
首先，由rsa的加密原理可知： c=m^e%n
如果是同一个n的话可以得到： c1=m^e1%n c2=m^e2%n ------------式1、2
当攻击者截获了c1和c2，其实就可以恢复出明文。
由拓展欧几里得算法：
有两个整数 a 与 b, 其必存在有整数 x 与 y 使得：ax + by = gcd(a,b)
得： s1·e1+s2·e2=gcd(e1,e2)=1--------------------式3
由此可得：
(c1s1·c2s2)%n=( (me1%n)s1·(me2%n)s2)%n
由 (a*b)%m = (a%m * b%m)%m 继续化简：
((me1)s1*(me2)s2)%n =(m(e1s1+e2^s2))%n
又因为式3我们已经知道s1·e1+s2·e2=1
所以(c1s1·c2s2)%n = m
分析
先看hint.py
from gmpy2 import *
from Crypto.Util.number import *
from secret import 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)
'''
107316975771284342108362954945096489708900302633734520943905283655283318535709
6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
2303413961 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
2622163991 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
'''
得到p n e1 c1 e2 c2
我们可以看到这个地方：c = pow(m, 256, p)
也就是说m^256 =c mod p
所以可以知道如果要求m，那么是存在两层加密：一层是m^256 =c mod p，另一层则是基础的共模攻击。
要求m，我们得先解决共模攻击求出c：
import gmpy2
import binascii
p = 107316975771284342108362954945096489708900302633734520943905283655283318535709
n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
e1 = 2303413961
c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
e2 = 2622163991
c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
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 = (m1*m2)%n
print(c)
#c=19384002358725759679198917686763310349050988223627625096050800369760484237557
解出c之后准备解出m：m^256 =c mod p
查阅资料，关于求m可以用一个函数：sympy.nthroots_mod(c,e,n)直接把m求出来。
其中这个nthroot_mod()用于求解
\[n i n d e x ≡ x ( m o d p ) n^{index}\equiv x\pmod p nindex≡x(modp) \]的同余式。
大佬分析是因为 256=2^8，所以我们可以知道这个 hint 反复使用 Cipolla 求二次剩余即可拿到（或者使用 sympy）
e=256
m = sympy.nthroot_mod(c,e,p)
print("m=",m)
print(long_to_bytes(m))
得到：
b'm.bit_length() < 400'
hint告诉了我们最后flag的字节长度。
再看看task.py
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
'''
然后我们来看 task，给出了n,以及：
\[c_{1,2} = pow(m,p,n),pow(m,q,n) \]我们知道：
\[c_1\equiv m\ (mod\ p),c_2 \equiv m\ (mod\ q) \]即：
\[c_1 = m+ip,c_2=m+jq \]那么，可以列出如下关系：
\[c_1c_2=m^2+(ip+jq)m+ijn\ (c_1+c_2)m=2m^2+(ip+jq)m \]那么我们可以得到：
\[ m^2-(c_1+c_2)m+c_1c_2\equiv 0\ mod\ n \]联系之前解出的 hint，得知
\[\arrowvert m \arrowvert <{1\over 2}n^{ {1\over 2} - \epsilon} \]则可使用 Coppersmith 求解。
c1，c2系数已知，则进行sage运算。
有大佬说用Sage来解这个方程。
查了一会儿，在线运行sage脚本：https://sagecell.sagemath.org/
建议先把c1+c2，以及c1*c2用pyton算出来…不然在线运行会慢。
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1 = 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2 = 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
a = c1 + c2
#a=106427507401691650533776606268030543324548306805584488340881108460215302001780649045082140067384306297497785054794169701530927082798998717147796265177082494273319180022953309137549878052025764276170773098393102683446915458123682447310617265418188192465923366892572673596378919944244343124060963227516817375783
b = c1*c2
#b=926651656671911333597022401968870409343942400492881255142377951759176631494915016941991504123810265329862246592861145719213675502795378053564904818765377025096483601036025012267103260702787555612216755188521913405305861451125814149409508425602231670292131422273268728629782633354498648021859614223672123489318899205627785426402597996319440198218774038390809403281952702730883306007226797632389267386912707857093556335846269954270572920361347019614365402744026533713442449916555425678184406380167614011131702418493073759816310890056281917310110034453007210415242707924141697749818907383248545179118594511927630223830
sage脚本：
a = 106427507401691650533776606268030543324548306805584488340881108460215302001780649045082140067384306297497785054794169701530927082798998717147796265177082494273319180022953309137549878052025764276170773098393102683446915458123682447310617265418188192465923366892572673596378919944244343124060963227516817375783
b = 926651656671911333597022401968870409343942400492881255142377951759176631494915016941991504123810265329862246592861145719213675502795378053564904818765377025096483601036025012267103260702787555612216755188521913405305861451125814149409508425602231670292131422273268728629782633354498648021859614223672123489318899205627785426402597996319440198218774038390809403281952702730883306007226797632389267386912707857093556335846269954270572920361347019614365402744026533713442449916555425678184406380167614011131702418493073759816310890056281917310110034453007210415242707924141697749818907383248545179118594511927630223830
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
R.<x>=Zmod(n)[]
f = x^2 - a*x +b
f.small_roots(X=2^400) #括号内的是根的边界，我们所求的根也就是m，这里hint已经给出了m.bit_length()<400
flag=4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855
flag = 4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855
print(long_to_bytes(flag))
结果：
b'verrrrrrry_345yyyyyyy_rsaaaaaaa_righttttttt?'
套上flag{verrrrrrry_345yyyyyyy_rsaaaaaaa_righttttttt?}
import gmpy2
import binascii
p = 107316975771284342108362954945096489708900302633734520943905283655283318535709
n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
e1 = 2303413961
c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
e2 = 2622163991
c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
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 = (m1*m2)%n
e = 256
m = nthroot_mod(c,e,p)
print(long_to_bytes(m))
"""
#这里是求c1+c2,c1*c2
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1 = 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2 = 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
a = c1 + c2
b = c1*c2
print(a,'.',b)
#这里是sage语言脚本
a = 106427507401691650533776606268030543324548306805584488340881108460215302001780649045082140067384306297497785054794169701530927082798998717147796265177082494273319180022953309137549878052025764276170773098393102683446915458123682447310617265418188192465923366892572673596378919944244343124060963227516817375783
b = 926651656671911333597022401968870409343942400492881255142377951759176631494915016941991504123810265329862246592861145719213675502795378053564904818765377025096483601036025012267103260702787555612216755188521913405305861451125814149409508425602231670292131422273268728629782633354498648021859614223672123489318899205627785426402597996319440198218774038390809403281952702730883306007226797632389267386912707857093556335846269954270572920361347019614365402744026533713442449916555425678184406380167614011131702418493073759816310890056281917310110034453007210415242707924141697749818907383248545179118594511927630223830
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
R.<m> = Zmod(n)[]
f = m^2 - sum*m + pro
flag = f.smallroots(2^400)[0] #括号内的是根的边界，我们所求的根也就是m，这里hint已经给出了m.bit_length()<400
"""
flag = 4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855
print(long_to_bytes(flag))