RSA总结

rsa的基本原理

公钥(n,e) 私钥（n,d)

其中，n是两个质数p,q的积，e是随机整数满足1<e<m且e与m互质，d满足（e*d)%m = 1.

代码

已知p,q,n,e

def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
# y maybe < 0, so convert it
if y < 0:
return fn + y
return y


def extendedGCD(a, b):
# a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
# a*x1 + b*y1 = a
x1 = 1
y1 = 0
# a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
# ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
# xi = x(i-2) - q*x(i-1)
x = x1 - q * x2
x1 = x2
x2 = x
# yi = y(i-2) - q*y(i-1)
y = y1 - q * y2
y1 = y2
y2 = y
return (x1, y1, a)

fn = (p - 1) * (q - 1)

d = computeD(fn, e)
m = pow(c,d,n)
print m

dp泄露

for i in range(1, e):
if (dp*e-1) % i == 0:
p = (dp*e-1)//i + 1
if n % p == 0:
q = n // p
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(libnum.n2s(m))
exit()