信安实验
RSA入门
- 简介
- 前置知识
- 模运算
- 余数计算
- 等价类中所有成员得到行为等价
- 乘法逆元(模逆元)
- Python实现模逆元
- 模运算
- 欧拉函数
- 秘钥生成
- 加解密函数
- 加密过程
- 解密过程
简介
-
来源
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,可记作:
a ≡ r mod m
其中m为模数,r为余数
余数计算
总可以找到一个a∈Z,使得
a = q · m + r , 其中0 ≤ r < m
由于a - r = q · m(m除a-r),上面的表达式可以写作:
a ≡ r mod m(r∈{0,1,2,…,m-1})
如a=88,m=12,则88 = 12 ·7 + 4
因此88 ≡ 4 mod 12
等价类中所有成员得到行为等价
对于一个给定模数m,选择等价类中任何一个元素来计算,结果都是一样的
直接计算
3⁸ = 6561 ≡ 2 mod 7
替代计算(简化)
将3⁸ 替换为3⁴ ·3⁴ = 81 ·81
因为81 = 11 · 7 +4
则3⁸ = 81 · 81 ≡ 4 · 4 =16 mod 7
最后得到16 ≡ 2 mod 7
乘法逆元(模逆元)
模逆元也称为模倒数。
一整数 𝑎 对同余 𝑛 之模逆元是指满足以下公式的整数 𝑏:
也可以写成以下的式子:
整数 𝑎 对模数 𝑛 之模逆元存在的充分必要条件是 𝑎 和 𝑛 互素,若此模逆元存在,在模数 𝑛 下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。
Python实现模逆元
可以使用Python第三方包Crypto的 inverse() 函数求模逆元。
from Crypto.Util.number import inverse
print(inverse(3, 7)) # 3 是要求逆元的数,7是模数#5
可以使用Python第三方包gmpy2的 invert() 函数求模逆元。
from gmpy2 import invert
print(invert(3, 7)) # 3 是要求逆元的数,7是模数#5
可以在SageMath中直接用 inverse_mod() 函数求模逆元。
inverse_mod(3, 7) # 3 是要求逆元的数,7是模数
模运算
加法
3 + 4 ≡ 0 (𝑚𝑜𝑑 7)
5 + 5 ≡ 3 (𝑚𝑜𝑑 7)
1 + 5 ≡ 6 (𝑚𝑜𝑑 7)
减法
5 − 2 ≡ 3 (𝑚𝑜𝑑 7)
3 − 5 ≡ 3 − 5 + 7 ≡ 3 + 2 (𝑚𝑜𝑑 7)
乘法
3 × 4 ≡ 5 (𝑚𝑜𝑑 7)
2 × 2 ≡ 4 (𝑚𝑜𝑑 7)
模运算没有除法(此处结合乘法逆元)
欧拉函数
Zm内与m互素的整数的个数可以表示为φ(n)
示例:
假设 m 等于 6 时,现在对应的集合为 {0, 1, 2, 3, 4, 5}
GCD(0, 6) = 6
GCD(1, 6) = 1------互素
GCD(2, 6) = 2
GCD(3, 6) = 3
GCD(4, 6) = 2
GCD(5, 6) = 1------互素
由于该集合中,有两个与 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
更多推荐
信安实验
发布评论