RSA算法原理

原创
10/18 00:56
阅读数 0

一、什么是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
  1. 随机选择一个整数e,条件是1 < e < λ(n),且e与λ(n) 互质。
随机选择17。(实际应用中,常常选择65537。)
  1. 计算e对于λ(n)的模反元素d。所谓"模反元素"就是指有一个整数d,可以使得ed被λ(n)除的余数为1。
ed ≡ 1 (mod λ(n)) = 17 * d % λ(n) = 1
d = 413 或者更大倍数的数值
  1. 公钥为为(n = 3233, e = 17)。明文消息为m,密文信息为c,加密公式为
c = m^17 mod 3233

私钥为(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

参考文档:

RSA算法原理(一)(阮一峰)

RSA算法原理(二)(阮一峰)

RSA算法简易解析

Wiki 欧拉函数

Wiki 欧拉定理

Wiki RSA算法

Baike LCM函数

Baike 最小公倍数

Baike 最大公约数

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部