Python 从p, q, e参数恢复RSA私钥中的d
脚本
使用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!
是? awsl
企鹅TQL!!!!!!
Orz
有一说一企鹅真的太强了
这个评论框快把我闪瞎了 (
Orz