RSA中e与φ(n)不互素

在ctf.show中刷到一道题目，给出了两组e,p,q,c，但其中gcd(e,φ(n))!=1，网上查了一下

https://blog.csdn.net/chenzzhenguo/article/details/94339659

https://www.anquanke.com/post/id/164575#h2-2

题目

e1 = 14606334023791426
p1 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
p2 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919

解题

其中p1=p2，gcd(e1, φ(n1)) = gcd(e1, φ(n2)) = 14

$$gcd(e,\varphi(n))=b \\ ed\equiv 1\pmod {\varphi(n)} \\ e = a * b \\ abd\equiv 1\pmod {\varphi(n)} \\ m^{ab}\equiv c \pmod n \\ c^{bd}\equiv m^{abbd}\equiv m^b\pmod n$$

可以得到b=14，而此时，a与φ(n)正好互素

可以通过逆元求到bd bd=gmpy2.invert(e, φ(n))

通过pow(c,bd,n)

可以得到两组值：

$$res1 \equiv m^{14}\pmod {n1} \\ res2 \equiv m^{14}\pmod {n2}$$

接着进一步推导

$$res1 \equiv m^{14}\pmod {p1} \\ res1 \equiv m^{14}\pmod {q1} \\ res2 \equiv m^{14}\pmod {q2}$$

这里就是可以使用中国剩余定理了

可以解出一个特解m的值

当模n1，n2无法解出时，考虑换成模q1*q2

$$res \equiv m^{14}\pmod {q1*q2}\\ 原理如下\\ res1 = k1 * q1 + m^{14}\\ res2 = k2 * q2 + m^{14}\\ res1 * res2 = k1k2q1q2 + (k1q1 + k2q2 + m^{14})m^{14} \\ 两边同时模q1*q2即为上式$$

此时，该题目就被化简为一个新的RSA

密文为刚刚求出的特解m

公钥e=14

模数分解为q1，q2

而此时就可按照之前的思路进行求解

$$c\equiv m^e\pmod {q1q2} \\ e = 2 * 7 \\ 2 * 7 * d \equiv 1 \pmod {q1q2} \\ m^2\equiv c^{d*2}\pmod {q1q2}$$

先求得7的逆元，然后对m开方即可

完整脚本

from libnum import *
import gmpy2

e1 = 14606334023791426
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248
e2 = 13813369129257838
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
p = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
n1 = p * q1
n2 = p * q2
f1 = (p - 1) * (q1 - 1)
f2 = (p - 1) * (q2 - 1)
tmp = 14

e1 = e1 // tmp
e2 = e2 // tmp
bd1 = invmod(e1, f1)
bd2 = invmod(e2, f2)

m1 = pow(c1, bd1, n1)
m2 = pow(c2, bd2, n2)
m3 = m1 % p
m2 = m2 % q2
m1 = m1 % q1

m = solve_crt([m1, m2, m3], [q1, q2, p]) 
print(m)
n = q1 * q2
f = (q1 - 1) * (q2 - 1)
m = m % n
d2 = invmod(7, f)
m = pow(m, d2, n)
print(n2s(gmpy2.iroot(m, 2)[0]))