该题给了很多p,q的约束条件
assert p > 0
assert q > 0
assert p != q
assert p.bit_length() == 512
assert q.bit_length() == 512
assert isPrime(p)
assert isPrime(q)
assert p % e != 1
assert q % e != 1
主要是限制你e与欧拉函数不互素的情况
key = RSA.construct([n,e,d,p,q])
这里只需要让construct([n,e,d,p,q])
报错
报错条件有下面这些
好像这5个条件都实现不了,那么只能通过参数错误才能实现报错了。
那么就只能从逆元d出手,通过师傅们给的提示:给出个素数p,让d是p的倍数,使得d与n的公因数不等于1
那么我们就需要通过d,p,e求出q
我们令d=m*p
,先求出满足条件的m值
\(
d=m*p\\
d=m+m*(p-1)\\
e*d=e*m+e*m*(p-1)\\
因为e*d\equiv 1\pmod \phi\\
就有e*m+e*m*(p-1)\equiv 1\pmod{p-1}\\
e*m\equiv 1\pmod {p-1}\\
所以m=inverse(e,p-1)\\
\)
\(
e*d=e*m*p\equiv 1\pmod \phi
e*m*p=1+k*(p-1)*(q-1)
k*(q-1)=\frac{e*m*p-1}{p-1}
这里可以爆破k的值,k\in [1,e+1]
q=\frac{e*m*p-1}{(p-1)*k}+1
\)
求q:
while True:
e=65537
p=getPrime(512)
m=inverse(e,p-1)
temp=(e*m*p-1)//(p-1)
for k in range(1,e+1):
if temp %k ==0:
q=temp//k+1
if isPrime(q) and q.bit_length()==512:
print('p =',p)
print('q =',q)
sys.exit(0)
#p = 8421653256813693467327420543663576095525957858499069795905275775105913628777973154663037299646187656120434361709768773180360369189504761968356610803846019
#q = 8268931175064080437894709841703693765995327463048305152043396908528782858938453271740660539203864353919527661268006747865039212242353910906779185878512409
标签:pmod,assert,2023CISCN,badkey,报错,isPrime,512,equiv
From: https://www.cnblogs.com/--Lookback--/p/17444533.html