Python 从p, q, e参数恢复RSA私钥中的d

脚本

使用Crypto库需要py2环境，更高版本用的是另外一个库（自行百度，懒）：

pq可以尝试通过在线大整数分解网站求出

代码语言：javascript复制

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^e，m = 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！

网站 百度 遍历 脚本 原理

0 人点赞