您当前的位置:首页 > 计算机 > 加密解密

RSA 基本思路如下

时间:02-24来源:作者:点击数:

1.公钥与私钥的生成:

  • (1) 随机挑选两个大质数 p 和 q,构造n = p*q;
  • (2)计算欧拉函数φ(n) = (p-1) * (q-1);
  • (3)随机挑选e,使得gcd(e, φ(n)) = 1,即 e 与 φ(n) 互素,gcd指的是求最大公约数;
  • (4)计算d,使得 e*d ≡ 1 (mod φ(n)),即d 是e 的乘法逆元。

2.加密过程:

  • (1)待加密信息(明文)为 m,m < n;(因为要做模运算,若m大于n,则后面的运算不会成立,因此当信息比n要大时,应该分块加密);
  • (2))密文 c 的生成是 $$ c = m^e mod (n) $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

为什么能解密?

要用到欧拉定理(其实是费马小定理的推广)

a^φ(n) ≡ 1 (mod n),

再推广:a^(φ(n)k) ≡ 1 (mod n),

得到 a^(φ(n)k+1) ≡ a (mod n)

注意到 ed ≡ 1 mod φ(N),即:ed = 1 + k*φ(N)。

因此,$$ M^(de) mod N = M^1 + kφ(N) mod N = M $$

4.代码如下

实例

#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))

当输入p值:18443,q值:49891,e值19,

密文c值:

70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148
得到的结果就会显示

得到的明文m是: 88455713

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门