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 | 计算公钥E | 1 < E < φ(N) | E的取值必须是整数 E 和 φ(N) 必须是互质数 |
5 | 计算私钥D | E * D % φ(N) = 1 | |
6 | 加密 | C = M E mod N | C:密文 M:明文 |
7 | 解密 | M =C D mod N | C:密文 M:明文 |
公钥=(E , N)
私钥=(D, N)
对外,我们只暴露公钥。
找出质数P、Q
我们这里为了测试方便随机选取两个数值小的数字
1 | P = 5 |
计算公共模数N
1 | N = P * Q = 5 * 11 = 55 |
欧拉函数
1 | φ(N) = (P-1)(Q-1) = 4 * 10 = 40 |
计算公钥E
1 | 1 < E < φ(N) |
E的取值必须是整数, E
和 φ(N)
必须是互质数
所以E的取值范围为:
5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37
为了测试方便,我们取一个相对小一点的数来测试
1 | E = 7 |
计算私钥D
1 | E * D % φ(N) = 1 |
正向加解密
公钥加密
我们这里为了测试方便,同样取一个比较小的数字进行加密测试
1 | M = 4 |
根据我们的公式我们来计算下加密结果C
C = M E mod N
1 | C = 16384 % 55 |
我们将数字4加密后的结果是49,接下来我们尝试使用私钥对其进行解密,看能不能得到加密前的数字4
私钥解密
同样根据我们的解密公式,来尝试计算出原始明文M。
M =C D mod N
1 | M = 749048330965186233494494102694560000000 % 55 |
反向加解密
私钥加密
我们这里为了测试方便,同样取一个比较小的数字进行加密测试
1 | M = 5 |
根据我们的公式我们来计算下加密结果C
C = M d mod N
1 | C = 11920928955078125 % 55 |
我们将数字5加密后的结果是15,接下来我们尝试使用公钥对其进行解密,看能不能得到加密前的数字5
公钥解密
同样根据我们的解密公式,来尝试计算出原始明文M。
M =C e mod N
1 | M = 170859375 % 55 |
经过以上示例,我们双向加解密已经成功。