加密算法分为对称加密算法和非对称加密算法, 其中非对称加密算法作为计算机通信安全的基石, 在保证数据安全方面起着重要的作用. 而相对于对称加密算法的易理解性, 非对称加密算法存在一定的难度. 下面通过对 RSA 算法的剖析, 让我们更好的理解非对称加密算法的原理.
一, 对称加密算法和非对称加密算法
1, 对称加密算法
对称加密算法: 加密和解密都使用同样规则 (密钥) 的算法.
(1),A 选择某一种规则对信息进行加密;
(2),B 使用同一规则 (逆规则) 对信息进行解密;
2, 非对称加密算法
非对称加密算法: 加密和解密可以使用不同的规则, 只要这两种规则之间存在某种对应关系即可.
(1),B 根据算法生成两把密钥(公钥和私钥), 其中私钥是保密的, 公钥是公开的, 供要与 B 通信的其它人使用;
(2),A 从 B 处获取公钥, 并用它来加密;
(3),B 得到 A 加密后的信息, 用私钥进行解密, 完成通信;
二, RSA 算法的数学基础
1, 互质关系
互质又称为互素, 如果两个或两个以上的整数的最大公约数是 1, 则称它们为互质. 比如 7 和 10, 他们最大的公约数是 1, 所以他们互质. 8 和 10 最大的公约数是 2, 所以他们不是互质. 并不是只有两个质数才能形成互质.
根据互质关系, 可以得出以下结论(后面欧拉函数会用到):
两个不同的质数一定互质. 例如, 2 与 7,13 与 19.
一个质数, 另一个不为它的倍数, 这两个数互质. 例如, 3 与 10,5 与 26.
1 和任何一个自然数都互质. 如 1 和 9908.
2 的幂和任何一个奇数都互质. 如 32 和 75,256 与 315.
相邻两个自然数互质. 如 15 与 16.
相邻两个奇数互质. 如 49 与 51.
2, 欧拉函数
欧拉函数指的是对正整数 n, 求小于或等于 n 的正整数中与 n 互质的数的数目, 记作φ(n). 比如 1 至 10 中, 与 10 形成互质关系的有 1,3,7,9, 所以φ(10)=4.
欧拉函数通用公式为(除 n=1 外,φ(1)=1):
\[ φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})......(1-\frac{1}{p_r}) \\ n={p_1}^{k_1}*{p_2}^{k_2}......{p_r}^{k_r}, 其中 p_1,p_2......p_r 为质数 \]
比如φ(20)=8 计算过程如下:
\[ φ(20)=φ(2^2\times5)=20(1-\frac{1}{2})(1-\frac{1}{5})=8 \]
欧拉函数证明如下:
当 n=1 时,φ(1) = 1
因为 1 与任何数都构成互质关系, 则 φ(1) = 1 .
当 n 是质数,φ(n) =n-1
因为质数与小于它的每一个数, 都构成互质关系, 则φ(n) =n-1. 如φ(5)=5-1=4.
当 n 是质数的某个次方, 公式如下, 其中 p 为质数, k 为大于 1 的整数
\[ φ(p^k) =p^k(1-\frac{1}{p}) \]
因为质数的某个次方与除与质数的倍数外都形成互质关系, 而质数的倍数 1 * p,2 * p,3 * p,......,p^(k-1) * p, 即有 p^(k-1)个, 则
\[ φ(p^k) =p^k-p^{k-1}=p^k(1-\frac{1}{p}), 如φ(5^3)=5^3(1-\frac{1}{5})=100. \]
当 n 可以分解成两个互质的整数之积,
\[ φ({p_1}\times{p_2})= φ(p_1)φ(p_2) \]
该定理用到中国剩余定理即可证明, 具体过程可参考其它文档. 如φ(15)=φ(3 * 5)=φ(3) φ(5) =2 * 4 =8.
根据以上推论, 因为任意一个大于 1 的正整数, 都可以写成一系列质数的积, 可以推导出当 n 为大于 1 的整数时:
\[ n={p_1}^{k_1}{p_2}^{k_2}...{p_r}^{k_r} \]
\[ φ(n)=φ({p_1}^{k_1}{p_2}^{k_2}...{p_r}^{k_r}) \]
\[ φ(n)=φ({p_1}^{k_1})φ({p_2}^{k_2})...φ({p_r}^{k_r}) \]
\[ φ(n)={p_1}^{k_1}(1-\frac{1}{p_1}){p_2}^{k_2}(1-\frac{1}{p_2})...{p_r}^{k_r}(1-\frac{1}{p_r}) \]
\[ φ(n)={p_1}^{k_1}{p_2}^{k_2}...{p_r}^{k_r}(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_r}) \]
\[ φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) \]
以上即为欧拉函数的通用计算公式.
3, 欧拉定理
欧拉定理也称费马 - 欧拉定理, 指的是: 如果两个正整数 a 和 n 互质, 则 n 的欧拉函数 φ(n) 可以让下面的等式成立.
\[ a^{φ(n)}=1(mod\ n) \]
即 a 的φ(n)次方被 n 除的余数为 1, 或者说 a 的φ(n)次方减 1, 能被 n 整除. 如 7 和 5 互质
\[ 7^{φ(5)}-1=7^4-1=2401-1=2400, 可以被 5 整除 \]
4, 模反元素
如果两个正整数 a 和 n 互质, 那么一定可以找到整数 b, 使得 ab-1 被 n 整除, 或者说 ab 被 n 除的余数是 1. 这时, b 就叫做 a 的模反元素. 证明如下:
\[ a^{φ(n)}=a\times a^{φ(n-1)} = 1(mod\ n), 其中 a^{φ(n-1)}就是 a 的模反元素 \]
三, RSA 算法过程
1, 生成密钥对(公钥和私钥)
随机找两个质数 a 和 b(a 和 b 越大越安全), 并计算他们的乘积 n
比如 a = 5 ,b = 11. 计算他们的乘积 n = 5 * 11 = 55 , 转化为二进为 110111, 该加密算法即为 6 位. 本例子中是为了计算方便, 所以取的数比较小, 实际算法是 1024 位 或 2048 位, 位数越长, 算法越难被破解.
计算 n 的欧拉函数 m = φ(n)
根据公式 m = φ(55) = φ(5)φ(11) = (5-1)(11-1) = 40
随机选择一个整数 e, 条件是 1<e<m, 且 e 与 m 互质
我们随机选择 e=17
计算 e 对于φ(n)(即 m)的模反元素 d
即找一个整数 d, 使得 (e * d ) % m = 1. 等价于 e * d - 1 = y * m ( y 为整数) 找到 d , 实质就是对下面二元一次方程求解. e * x - m * y = 1 . 其中 e = 17,m = 40,17x - 40y = 1 这个方程可以用 "扩展欧几里得算法" 求解. 具体求解过程略, 算出一组整数解(x,y )= (33,14), 即 d=33. 到此密钥对生成完毕. 不同的 e 生成不同的 d, 因此可以生成多个密钥对.
本例中公钥为 (n,e) = (55 , 17), 私钥为(n,d) = (55 ,33) , 仅(n,e) =(55 , 17) 是公开的, 其余数字均不公开. 可以想像如果只有 n 和 e, 如何推导出 d, 目前只能靠暴力破解, 位数越长, 暴力破解的时间越长.
2, 加密生成密文
对明文 z 采用公钥 (n,e) 进行加密, 其中明文必须转换为数字, 且必须比 n 小. 加密的公式如下:
\[ z^e=c(mod\ n) \]
其中 z 为明文, n 和 e 为公钥, c 为加密后的密文, 所以 c 可以转换为:
\[ c=z^e \% n \]
假如明文为 15, 公钥(n,e) = (55 , 17), 则加密后的密文 c 为:
\[ c=15^{17}\U=5 \]
3, 解密生成明文
对密文 c 采用公钥 (n,d) 进行解密, 解密的公示如下:
\[ c^d=z(mod\ n) \]
其中 c 为密文, n 和 d 为私钥, z 为解密后的明文, 所以 z 可以转换为:
\[ z=c^d\%n \]
根据上述条件, 密文 c 为 5, 私钥(n,d) = (55 ,33) , 则解密后的明文 z 为:
\[ z=5^{33}\U=15 \]
四, RSA 算法有效性证明
1, 有效性问题
根据上述 RSA 算法示例, 要验证 RSA 算法的有效性, 即验证根据加密公式:
\[ z^e=c(mod\ n) \]
可以推导出, 解密公式是有效的:
\[ c^d=z(mod\ n) \]
2, 证明过程
根据加密规则, 可以推导出:
\[ c= z^e - kn \]
将上述式子代入解密公式, 即求证以下式子成立:
- \[ (z^e-kn)^d = z(mod\ n) \]
- \[ z^{
- ed
- } = z(mod\ n) \]
当 z 与 n 互质时
根据欧拉定理
\[ z^{φ(n)} = 1(mod\ n) \]
则可以推出
\[ z\times {(z^{φ(n)})}^p=z(mod\ n) \]
\[ z^{1+pφ(n)}=z(mod\ n) \]
由于
\[ ed = 1(mod\ φ(n)) \]
\[ ed = 1+pφ(n) \]
所以可以推导出
\[ z^{ed} = z(mod\ n) \]
当 z 与 n 不为互质时
因为 n=a*b, 其中 a 和 b 都为质数. 因为 z 和 n 不为互质, 则 z 和 n 必定有一个公约数, 由于 n 为两个质数 a 和 b 的乘积, 则 z 一定为 a 或 b 的倍数, 记作 ka 或者 kb.
假定 z=ka(a=kb 同理). 由于 b 为质数, 如果 k 为 b 的倍数, 即 k=hb, 则 z=hab, 其中 h 为正整数, 则推导出 z 大于 n, 但是根据条件被加密的明文必须小于 n, 所以可以推导出 k 不是 b 的倍数, 由于 b 为质数, 所以可以推断出 k 和 b 互质, 同理, 推导出 ka 与 b 互质, 即 z 与 b 互质.
根据欧拉定理, 可知下列式子成立:
\[ z^{φ(b)}≡1(mod\ b) \]
可推导出:
\[ z^{φ(b)}=(ka)^{φ(b)}=(ka)^{b-1}≡1(mod\ b) \]
对于一个数求余结果为 1, 那么它的 n 次方, 求余也为 1. 根据这个定理, 可推导出:
\[ {[(ka)^{b-1}]}^{h(a-1)}≡1(mod\ b) \]
\[ {[(ka)^{b-1}]}^{h(a-1)}\times ka≡ka(mod\ b) \]
\[ {(ka)}^{ed}≡ka(mod\ b) \]
\[ {(ka)}^{ed}=ka+ob \]
由于两名等式成立, 且 a 与 b 互质, 可以推导出 o 一定为 a 的倍数, 即 0=ja, 可推导出:
\[ {(ka)}^{ed}=ka+ob=ka+jab \]
因为 z=ka,n=ab, 所以可以退出:
\[ z^{ed}≡z(mon\ n) \]
五, RSA 算法的安全性
RSA 算法的安全性, 是基于目前的条件下, 在空间和时间上, 无法对它进行有效破解.
根据上述推导, RSA 算法用到 a,b,n,m,e,d 六个数字. 其中公钥 (n,e) 是公开的, 其余的 4 个数字是保密的. 其中密钥 d 是算法的核心.
e*d ≡ 1 (mod m). 其中 e 是公开的, 那就需要知道 m, 才能算出 d.
根据公式φ(n)=(a-1)(b-1)=m, 要计算出 m, 必须知道 a 和 b.
n=ab. 只有将 n 因数分解, 才能算出 a 和 b.
目前对于大数的因数分解, 除了暴力破解, 没有更好的途径. 以现有的计算资源和能力, 目前能被破解的最长 RSA 密钥就是 768 位, 所以只要保证 RSA 密钥是 1024 位及以上, 即可保证算法的安全性.
六, 总结
1,RSA 算法流程
2,RSA 算法安全性
目前对于大数的因数分解, 除了暴力破解, 没有更好的途径. 以现有的计算资源和能力, 目前能被破解的最长 RSA 密钥就是 768 位, 所以只要保证 RSA 密钥是 1024 位及以上, 即可保证算法的安全性.
3,RSA 算法应用
在 RSA 算法中, 公钥(n,e) 只能加密小于 n 的整数. 对于大于 n 的整数, 可以采用两种方法. 一是把长信息分割成若干段短消息, 每段分别加密; 另一种是先选择一种对称性加密算法加密信息, 再用 RSA 公钥加密对称性加密算法的密钥.
另外, 由于 RSA 算法性能问题, 通常加解密都比较慢, 所以通常和对称性加密算法一起配合使用.
来源: https://www.cnblogs.com/xtiger/p/10972373.html