RSA加密原理大公开，简单理解其基本概念与运作机制
最编程
2024-02-12 14:01:53
...
#coding=utf-8
#__author__ = 'ralph'
import random
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)
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 keyGeneration(p,q,e):
#generate public key and private key
n = p * q
fn = (p-1) * (q-1)
d = computeD(fn, e)
return (d,n)
p_v = int(raw_input('请输入p的值(10进制)\n'))
q_v = int(raw_input('请输入q的值(10进制)\n'))
e_v = int(raw_input('请输入e的值(10进制)\n'))
c_v = int(raw_input('请输入密文c的值(10进制)\n'))
(d,n) = keyGeneration(p_v,q_v,e_v) #生成 d和n
m = pow(c_v,d,n)
print ("得到的明文m是: "+str(m))