• RSA算法的概念与原理
  • 发布于 2个月前
  • 99 热度
    0 评论
  • LoveC
  • 1 粉丝 38 篇博客
  •   
一、什么是 RSA 算法
1977 年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。
(1)甲方选择某一种加密规则,对信息进行加密;

(2)乙方使用同一种规则,对信息进行解密。


二、互质关系
如果两个正整数,除了 1 以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15 和 32 没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

三、欧拉函数
任意给定正整数 n,请问在小于等于 n 的正整数之中,有多少个与 n 构成互质关系?(比如,在 1 到 8 之中,有多少个数与 8 构成互质关系?)
计算这个值的方法就叫做欧拉函数,以 φ(n) 表示。在 1 到 8 之中,与 8 形成互质关系的是 1、3、5、7,所以 φ(n) = 4。

四、欧拉定理
欧拉函数的用处,在于欧拉定理。” 欧拉定理” 指的是:
如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
a^φ(n) ≡ 1 (mod n)
也就是说,a 的 φ(n) 次方被 n 除的余数为 1。或者说,a 的 φ(n) 次方减去 1,可以被 n 整除。

比如,3 和 7 互质,而 7 的欧拉函数 φ(7) 等于 6,所以 3 的 6 次方(729)减去 1,可以被 7 整除(728/7=104)。

五、最大公约数
最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b 的最大公约数记为(a,b),同样的,a,b,c 的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。与最大公约数相对应的概念是最小公倍数,a,b 的最小公倍数记为 [a,b]。

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即(a,b)×[a,b]=a×b。所以,求两个数的最小公倍数,就可以先求出它们的最大公约数,然后用上述公式求出它们的最小公倍数。
4   |108    96
3   |27     24
     9      8
最大公约数是4*3 = 12
最小公倍数是4*3*9*8 = 864 或 108*96/12 = 864
六、模反元素
如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 ab-1 被 n 整除,或者说 ab 被 n 除的余数是 1。
ab ≡ 1 (mod n)
这时,b就叫做a的"模反元素"。比如,3 和 11 互质,那么 3 的模反元素就是 4,因为 (3 × 4)-1 可以被 11 整除。显然,模反元素不止一个, 4 加减 11 的整数倍都是 3 的模反元素 {…,-18,-7,4,15,26,…},即如果 b 是 a 的模反元素,则 b+kn 都是 a 的模反元素。

七、密钥生成的步骤
1.随机选择两个不相等的质数。p=61,q=53。(实际应用中,这两个质数越大,就越难破解。)
2.计算 p 和 q 的乘积 n。
n = 61×53 = 3233
n 的长度就是密钥长度。3233 写成二进制是 110010100001,一共有 12 位,所以这个密钥就是 12 位。实际应用中,RSA 密钥一般是 1024 位,重要场合则为 2048 位。

3.计算 n 的欧拉函数 φ(n),并求出最小公倍数。
λ(n) = lcm((p-1),(q-1)) = 780
4.随机选择一个整数 e,条件是 1 <e < λ(n),且 e 与 λ(n) 互质。
随机选择17。(实际应用中,常常选择65537。)
5.计算 e 对于 λ(n) 的模反元素 d。所谓 “模反元素” 就是指有一个整数 d,可以使得 ed 被 λ(n) 除的余数为 1。
ed ≡ 1 (mod λ(n)) = 17 * d % λ(n) = 1
d = 413 或者更大倍数的数值
6.公钥为为 (n = 3233, e = 17)。明文消息为 m,密文信息为 c,加密公式为
c = m^17 mod 3233
7.私钥为 (n = 3233, d = 413)。明文消息为 m,密文信息为 c,解密公式为
m = c^413 mod 3233
八、使用密钥进行加密解密
例如,为了加密 m = 65,我们计算
c = 64^17 mod 3233 = 2790
为了解密 c = 2790,我们计算
m = 2790^413 mod 3233 = 65


用户评论