2019年9月

脚本

使用Crypto库需要py2环境,更高版本用的是另外一个库(自行百度,懒):

pq可以尝试通过在线大整数分解网站求出
import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)
keypair.p = 440140550843727826962832356360132665339
keypair.q = 420226057252427765877741059207519510621
keypair.e = 65537

keypair.n = keypair.p * keypair.q  
Qn = long((keypair.p-1) * (keypair.q-1)) 

i = 1
while (True):
    x = (Qn * i ) + 1
    if (x % keypair.e == 0):
        keypair.d = x / keypair.e  # get d
        break
    i += 1

private = open('private.pem','w') 
private.write(keypair.exportKey()) 
private.close()

原理

  1. 由于N=p*q,分解出pq后极容易求得phi(N) = (p-1)*(q-1)
  2. 由于c = m^em = c^d,所以可以尝试从ed的关系下手,而e,d满足条件e*d ≡ 1(mod phi(N))e*d = 1 + k*phi(N)
  3. 由上面的关系式可以知道,只要从1到∞遍历k,代入到1 + k*phi(N),找到模上e后结果为0(整除)的那一项,即可得到正确的d!