密码学——n,d,e求p q

发布于 2021-01-09  57 次阅读


原文:https://www.di-mgt.com.au/rsa_factorize_n.html
代码

# coding=utf-8
import random
import libnum

d = 5
e = 88447120342035329077203801890175181441227843548712394915405983098804986074228491993716303861346713336901472423214577098721961679062412555594462454080858396158886857405021364693424253936899868042331165487633709535319154171592544118785565876198853503758641178366299573880796663815089204345025378660387680199869
n = 0x009d70ebf2737cb43a7e0ef17b6ce467ab9a116efedbecf1ead94c83e5a082811009100708d690c43c3297b787426b926568a109894f1c48257fc826321177058418e595d16aed5b358d61069150cea832cc7f2df884548f92801606dd3357c39a7ddc868ca8fa7d64d6b64a7395a3247c069112698a365a77761db6b97a2a03a5

k = e * d - 1

r = k
t = 0
while True:
    r = r / 2
    t += 1
    if r % 2 == 1:
        break

success = False

for i in range(1, 101):
    g = random.randint(0, n)
    y = pow(g, r, n)
    if y == 1 or y == n - 1:
        continue

    for j in range(1, t):
        x = pow(y, 2, n)
        if x == 1:
            success = True
            break
        elif x == n - 1:
            continue
        else:
            y = x

    if success:
        break
    else:
        continue

if success:
    p = libnum.gcd(y - 1, n)
    q = n / p
    print 'P: ' + '%s' % p
    print 'Q: ' + '%s' % q
else:
    print 'Cannot compute P and Q'

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。