简介
来源
RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特(Ron Rivest)、阿迪 · 萨莫尔(Adi Shamir)和伦纳德 · 阿德曼(Leonard Adleman)一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
安全性
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今,只有短的 RSA 密钥才可能被强力方式解破。到2017 年为止,还没有任何可靠的攻击RSA 算法的方式。
前置知识
模运算
假设a,r,m∈Z(Z为整数集),并且m>0。如果m除a-r,可记作:
1 | a ≡ r mod m |
其中m为模数,r为余数
余数计算
总可以找到一个a∈Z,使得
1 | a = q · m + r , 其中0 ≤ r < m |
由于a - r = q · m(m除a-r),上面的表达式可以写作:
1 | a ≡ r mod m(r∈{0,1,2,…,m-1}) |
1 | 如a=88,m=12,则 |
等价类中所有成员得到行为等价
对于一个给定模数m,选择等价类中任何一个元素来计算,结果都是一样的
直接计算
1 | 3⁸ = 6561 ≡ 2 mod 7 |
替代计算(简化)
1 | 将3⁸ 替换为3⁴ ·3⁴ = 81 ·81 |
乘法逆元(模逆元)
模逆元也称为模倒数。
一整数 𝑎 对同余 𝑛 之模逆元是指满足以下公式的整数 𝑏:
也可以写成以下的式子:
整数 𝑎 对模数 𝑛 之模逆元存在的充分必要条件是 𝑎 和 𝑛 互素,若此模逆元存在,在模数 𝑛 下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。
Python实现模逆元
可以使用Python第三方包Crypto的 inverse() 函数求模逆元。
1 | from Crypto.Util.number import inverse |
可以使用Python第三方包gmpy2的 invert() 函数求模逆元。
1 | from gmpy2 import invert |
可以在SageMath中直接用 inverse_mod() 函数求模逆元。
1 | inverse_mod(3, 7) # 3 是要求逆元的数,7是模数 |
模运算
加法
1 | 3 + 4 ≡ 0 (𝑚𝑜𝑑 7) |
减法
1 | 5 − 2 ≡ 3 (𝑚𝑜𝑑 7) |
乘法
1 | 3 × 4 ≡ 5 (𝑚𝑜𝑑 7) |
模运算没有除法(此处结合乘法逆元)
欧拉函数
Zm内与m互素的整数的个数可以表示为φ(n)
示例:
假设 m 等于 6 时,现在对应的集合为 {0, 1, 2, 3, 4, 5}
1 | GCD(0, 6) = 6 |
由于该集合中,有两个与 6 互素的数字,即 1 和 5
所以欧拉函数的值为 2,即 φ(6) = 2。
φ(n)=(p-1)(q-1) //pq为不相等的质数
秘钥生成
1、选择两个不相等的质数p和q
2、计算q与p的乘积n
3、计算n的欧拉函数φ(n)
4、选择一个整数e,(1<e<φ(n)),且e与φ(n)互质
5、计算e对于φ(n)的模反元素d,公式表示为ed≡1(modφ(n))
6、(n,e)打包为公钥,(n,d)打包为秘钥
加解密函数
加密过程
1、首先取一个明文m,假设为4
2、选择不相等的质数。假设q=3,p=11
3、计算n=pq=33
4、计算φ(n)=(p-1)(q-1)=(3-1)(11-1)=20
5、选择一个整数e,假设e=3
6、计算d ≡ e⁻¹ ≡ 7 mod 20,即d = 7
7、计算mᵉ ≡ c mod n,即 64 ≡ 31 mod 33,得到c = 33
此时得到密文c = 31,公钥对(33,3),私钥对(33,7)
解密过程
1、假设只知道n=33,c=31,e=3
2、首先分解n,n=11·3
3、计算欧拉函数φ(n)=(11-1)·(3-1)=20
4、计算模反元素d,根据ed≡1(modφ(n))
,d=(20+1)/3=7
5、解密cᵈ ≡ m mod n
,即31⁷ ≡ m mod 33,计算得到 m = 4