
1. 简介
rsa 是一种非对称密码算法,由三位数学家 Rivest、Shamir 和 Adleman 设计。其原理基于大数因式分解的复杂性。通常使用时,生成一对公私钥对,主要应用于以下两个场景。
- 加解密: 使用公钥加密,只有持有私钥的人可以解密。
- 签名和验签:使用私钥进行签名,公钥进行验签,用于一些数据签名,校验的场景。
2. 数学背景
2.1 欧拉函数
假设有正整数n,欧拉函数ϕ(n)的值等于小于n的正整数里有多少个与n互为质数。
欧拉函数有以下几个性质:
- ϕ(1)=1 因为 1 与任何数都保持了互质关系。
- 如果n为质数,ϕ(n)=ϕ(n−1)
- 如果n为质数的某一次方,即 n=pk:
ϕ(pk)=pk−pk−1=pk⋅(1−p1)
这是因为当 m<n 时,当且仅当 m 不为 p 的倍数,m才与 n 互质,而这样的数共有pk−1个(1⋅p,2⋅p,...,pk−1⋅p)。
例如:
对n=73求ϕ(n),需要枚举所有小于73的数中不为7的倍数的数,这样的数共有73−72=294个。
- 如果n可以分解成两个互质的整数乘积
n=p1⋅p2
则:
ϕ(n)=ϕ(p1⋅p2)=ϕ(p1)⋅ϕ(p2)
- 任意大于 1 的正整数,都可以写成一系列质数的乘积。
n=p1k1⋅p2k2...⋅prkr
根据第四条的结论,可以得到:
ϕ(n)=ϕ(p1k1)⋅ϕ(p2k3)...⋅ϕ(prkr)=n(1−p11)(1−p21)...(1−pr1)
也就是欧拉函数计算的通用公式。
2.2 欧拉定理
欧拉函数主要是为了推导出欧拉定理:
如果两个正整数 a 和 n互为质数,则n的欧拉函数ϕ(n)可以让下面的等式成立:
aϕ(n)modn=1
也就是a的 ϕ(n) 次方被n除的余数为 1。例如,3 和 7 互质,ϕ(7)=6,
所以 37−1=728可以被 7 整除 (728/7=104) 。
当 p 为质数时,ϕ(p)=p−1,所以此时可以得到:
ap−1modp=1 (p为质数)
这就是著名的费马小定理,是欧拉定理的特例。
欧拉定理是 RSA 的核心。
2.3 模反元素
如果两个整数 a 和 n 互质,则一定可以找到整数 b ,使得 a⋅b modn=1,此时称 b 为 a 的模反元素。
欧拉定理可以证明模反元素必定存在:
aϕ(n)modn=1⇒a⋅aϕ(n)−1modn=1
也即 aϕ(n)−1 就是 a 的模反元素。
3. 秘钥计算
- Step1:随机选取两个不相等的质数 p , q
如选取p=61,q=53。该步骤中选取的 p,q 越大越难破解。
- Step2:计算 p , q 的乘积设为n
上例可得:
n=p⋅q=61⋅53=3233
- Step3:计算 n 的欧拉函数 ϕ(n)
因为 p , q均为素数,所以
ϕ(n)=ϕ(p⋅q)=ϕ(p)ϕ(q)=(p−1)(q−1)⇒ϕ(3233)=60⋅52=3120
- Step4:随机选择一个整数 e,条件是1<e<ϕ(n),且 e 与 ϕ(n) 互质
如上例中,选择 e=17 ,实际应用常选择 65537。
- Step5:计算 e 对于 ϕ(n) 的模反元素 d
edmodϕ(n)=1⇒ed=kϕ(n)+1
此时ϕ(n)和e已知,只需要求得上述二元一次方程 k,d的一组解即可。
在以上例子中可以找到一组解 d=2753,k=15。
- Step6:将 (n,e) 封装成公钥,(n,d)封装成私钥。
rsa_pub=(3233,17)rsa_private=(3233,2753)
4. 可靠性分析
上面的密钥生成步骤,一共出现六个数字:
p q n ϕ(n) e d
其中,公钥用到了两个(n 和 e),其余四个数字都是不公开的。其中最关键的是d,因为 n 和 d 组成了私钥,一旦 d 泄漏,就等于私钥泄漏。
所以如果要破解 rsa,就要在已知 n 和 e 的情况下破解 d。
因为 e,d,对于 ϕ(n) 互为对方的模反元素,所以要想算出 d 必须算出ϕ(n),若要由 n 算出 ϕ(n) 需要将 n 分解成两个素数的乘积,也就是算n=p⋅q中的 p 和 q。而对于极大整数因式分解是极其困难的,所以 RSA 几乎不可能被破解。
5. 加解密过程
5.1 加密
设消息为 m, 公钥为 (e,n)
可以算出密文 c 为:
c=memodn
如上例中,假设 m=65:
c=6517mod3233=2970
5.2 解密
解密要用私钥:
m=cdmodn
假设收到的信息为 2970,解密过程可得:
m=29702753mod3233=65
注意: RSA 只能加密小于n的整数,如果要加密大于 n 的整数怎么办?主要有两种解决方法,种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如 DES),用这种算法的密钥加密信息,再用 RSA 公钥加密 DES 密钥。
6. 私钥解密的证明
要证明私钥解密过程是有效的,也就是证明:
cdmodn=m
根据加密规则:
c=memodn⇒c=me−k⋅n⇒cdmodn=(me−k⋅n)dmodn⇒cdmodn=medmodn
所以原式等价于证明:
medmodn=m
因为e,d 对于 ϕ(n) 互为模反,所以 edmodϕ(n)=1。
也即ed=t⋅ϕ(n)+1
medmodn=mt⋅ϕ(n)+1modn
接下来分两种情况:
(1) m, n 互质:
由欧拉定理可得:
mϕ(n)modn=1⇒mt⋅ϕ(n)+1modn=m⋅(mt⋅ϕ(n)modn)=m
由上面的式子推到出结论是因为一个取模的性质:乘积的模等于模的乘积。
(2) m, n 不互质:
此时,由于n=pq,所以要么m=kp,要么m=kq。
假设m=kp,此时 m 与 q 互为质数,由欧拉函数可得:
mϕ(q)≡1 (mod q)
(≡表示同余,上面的式子表示两边对 n 取余数相等) 这里用到同余的一个性质,对 n 同余的两个数乘以一个相同的数之后结果依然对 n 同余。将m=kp带入上式可得:
[(kp)q−1](p−1)⋅h≡1 (mod q)⇒[(kp)q−1](p−1)⋅h⋅kp≡kp (mod q)
也即
(kp)t⋅ϕ(n)+1≡kp (mod q)
以上关系转换成等式可以写成:
(kp)t⋅ϕ(n)+1=tq+kp⇒(kp)⋅(kp)t⋅ϕ(n)=tq+kp⇒p(k⋅kp)=p(ptq+k)
因为q,p互质,所以 t 必然被 p 整除,t=t′p。
(kp)t⋅ϕ(n)+1=t′pq+kp
将 kp 重新替换成 m,pq 替换成 n 就可以得到:
mt⋅ϕ(n)+1=t′n+m⇒mt⋅ϕ(n)+1modn=m
参考