简述rsa算法基本思想（RSA基本思路如下）

1.公钥与私钥的生成：，我来为大家科普一下关于简述rsa算法基本思想?以下内容希望对你有帮助!

简述rsa算法基本思想

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

,