以moectf为例，解决rsa里e和phi不互素问题，ctf中rsa的ZeroDivisionError: invert() no inverse exists报错

作为一个非科班出身的选手，初学rsa总会遇到很多数学问题是当前没有见到过的，没深入密码学的ctfer，可能针对于题目给出的参数直接照搬网上脚本，有时候，我们就会遇到很多非标准的rsa题目(被出题人动过手脚)是不能直接用网上的脚本解决的，本文主要为解决笔者初学ctf中的rsa常常遇到的invert() no inverse exists报错。

[moectf 2023]bad_e

题目附件如下：

from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = 65537

print(p) # 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
print(q) # 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819

with open("flag.txt","r") as fs:
    flag = fs.read().strip()

m = bytes_to_long(flag.encode())
c = pow(m,e,p*q)
print(c) # 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

这道题目给出了rsa中的关键参数p,q,c,e,按照一般的脚本尝试，计算欧拉函数phi就会出现invert() no inverse exists报错(如下脚本的注释部分)，原因就出在e,phi不互素，没法进行求逆元的操作。在本题中用gcd函数求出e和（p-1）有因数,而e和(q-1)无因数，因此，借助式子：

e*d = 1 mod (q-1)
m = c ^ d mod q

在模（q-1）下，求解rsa明文，解决

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

p=6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
q=11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819
c=63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805
e = 65537
phi = (p-1)*(q-1)
# d = invert(e, phi)
# m = pow(c, d, n)
# print(long_to_bytes(m))
print(gcd(e,phi))
print(gcd(e,p-1))
print(gcd(e,q-1))
d = invert(e,(q-1))
m = pow(c,d,q)
print(long_to_bytes(m))

# 65537
# 65537
# 1
# b'moectf{N0w_Y0U_hAve_kN0w_h0w_rsA_w0rks!_f!lP0iYlJf!M3ru}'

[moectf 2023]Signin

from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
print('p=',p)
print('q=',q)
n=p*q
e=65537
c=pow(m,e,n)
print('c=',c)
#p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
#q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
#c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595

moectf老传统的题目了,套用即可

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

p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595
e=65537
phi = (p-1)*(q-1)
# d = invert(e, phi)
# m = pow(c, d, n)
# print(long_to_bytes(m))
print(gcd(e,phi))
print(gcd(e,p-1))
print(gcd(e,q-1))
d = invert(e,(p-1))
m = pow(c,d,p)
print(long_to_bytes(m))

# 65537
# 1
# 65537
# b'moectf{Oh~Now_Y0u_Kn0W_HoW_RsA_W0rkS!}'

moectf传送门：GitHub - XDSEC/MoeCTF_2023