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

赤道企鹅

发布于 2022-08-01 13:47:40

7310

发布于 2022-08-01 13:47:40

文章被收录于专栏：赤道企鹅的博客

脚本

使用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()

原理

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-09-18，如有侵权请联系 cloudcommunity@tencent.com 删除

网站