rsa非对称加密数学计算原理剖析

这里不在叙述rsa从古到今的由来了,我们直奔主题剖析其原理,只需知道rsa就是这个加解密算法的创始人缩写就可以了。

在此之前我们回顾下那些被遗忘的数学名词。

质数(素数)

质数又称素数指整数在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数

比1大但不是素数的数称为合数。1和0既非素数也非合数。

素数在数论中有着很重要的作用。

因数

因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数,我们就说b是a的因数。

公因数

公因数,亦称“公约数”。它是一个能同时整除若干整数的整数 [1] 。如果一个整数同时是几个整数的因数,称这个整数为它们的“公因数”;公因数中最大的称为最大公因数。

互质数

互质数为数学中的一种概念,即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数,叫做互质数。

注:两个数为互质数,不代表两个数都是质数;同为质数的两个不同数必然是互质数。

如:4, 5,两个数只有一个公因数1,所以这两个数是互质数,但是很明显4不是质数

如:3, 7, 两个数只有一个公因数1,所以这两个数是互质数,且两个数明显都是质数

欧拉函数

就是对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) 。

mod

mod函数是一个求余函数,在编程中也叫取模,就是计算最后的余数。在编程中取模的计算表达式通常为%

如:15%12=3

rsa加解密流程

步骤说明描述备注
1找出质数P 、Q
2计算公共模数N = P * Q
3欧拉函数φ(N) = (P-1)(Q-1)
4计算公钥E1 < E < φ(N)E的取值必须是整数
E 和 φ(N) 必须是互质数
5计算私钥DE * D % φ(N) = 1
6加密C = M E mod NC:密文 M:明文
7解密M =C D mod NC:密文 M:明文

公钥=(E , N)
私钥=(D, N)

对外,我们只暴露公钥。

找出质数P、Q

我们这里为了测试方便随机选取两个数值小的数字

1
2
P = 5
Q = 11

计算公共模数N

1
N = P * Q = 5 * 11 = 55

欧拉函数

1
φ(N) = (P-1)(Q-1) = 4 * 10 = 40

计算公钥E

1
2
1 < E < φ(N)
1 < E < 40

E的取值必须是整数, Eφ(N) 必须是互质数

所以E的取值范围为:

5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37

为了测试方便,我们取一个相对小一点的数来测试

1
E = 7

计算私钥D

1
2
3
4
5
E * D % φ(N) = 1
// 即
7 * D % 40 = 1
// 得出
D = 23

正向加解密

公钥加密

我们这里为了测试方便,同样取一个比较小的数字进行加密测试

1
M = 4

根据我们的公式我们来计算下加密结果C

C = M E mod N

1
2
C =  16384 % 55
C = 49

我们将数字4加密后的结果是49,接下来我们尝试使用私钥对其进行解密,看能不能得到加密前的数字4

私钥解密

同样根据我们的解密公式,来尝试计算出原始明文M。

M =C D mod N

1
2
3
M = 749048330965186233494494102694560000000 % 55
// 得出
M = 4

反向加解密

私钥加密

我们这里为了测试方便,同样取一个比较小的数字进行加密测试

1
M = 5

根据我们的公式我们来计算下加密结果C

C = M d mod N

1
2
C =  11920928955078125‬ % 55
C = 15

我们将数字5加密后的结果是15,接下来我们尝试使用公钥对其进行解密,看能不能得到加密前的数字5

公钥解密

同样根据我们的解密公式,来尝试计算出原始明文M。

M =C e mod N

1
2
3
M = 170859375‬ % 55
// 得出
M = 5

经过以上示例,我们双向加解密已经成功。