RSA加密算法¶
一、简介¶
- RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制
- 在公开密钥密码体制中，加密密钥（即公开密钥）
PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥 \(PK\) 决定的，但却不能根据PK计算出 SK - 正是基于这种理论， \(1978\) 年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为 \(500\) 位长，一般推荐使用 \(1024\) 位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的
DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要 - RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一
二、原理¶
2.1 加密过程¶
| 步骤 | 说明 | 描述 |
|---|---|---|
| 1 | 选择一对不相等且足够大的质数 | p,q |
| 2 | 计算 \(p,q\) 的乘积 | \(n=p\times q\) |
| 3 | 计算 \(n\) 的欧拉函数 | \(\varphi(n)=(p-1)\times(q-1)\) |
| 4 | 选一个与 \(\varphi(n)\) 互质的整数 \(e\) | \(1<e<\varphi(n)\) |
| 5 | 计算出 \(e\) 对于 \(\varphi(n)\) 的模反元素（或者称其为逆元） \(d\) | \(de \ mod \ \varphi(n)=1\) |
| 6 | 公钥 | \(KU=(e,n)\) |
| 7 | 私钥 | \(KR=(d,n)\) |
设明文为 \(M\) ，密文为 \(C\) 的话 - 加密操作： \(M^e \ mod \ n = C\) - 解密操作： \(C^d \ mod \ n = M\)
2.2 计算n的欧拉函数¶
- 欧拉函数 是小于 \(n\) 的正整数中与 \(n\) 互质的数的数目
- 互质 是指公约数只有 \(1\) 的两个整数
- 质数 是指在大于 \(1\) 的自然数中，除了 \(1\) 和它本身以外不再有其他因数的自然数
从上面的条件中，我们不难发现，对于一个质数 \(n\) 而言，它的欧拉函数就是 \(n-1\)
- 如果 \(n\) 可以分解为 \(2\) 个互质 \(p、q\) 的整数之积，那么 \(n\) 的欧拉函数就等于这两个因子的欧拉函数之积，也就是 \(\varphi(n)=\varphi(p)\times \varphi(q) = (p-1)\times (q-1)\)
2.3 逆元计算¶
对于逆元的计算，我们使用的是扩展欧几里得算法，对于数 \(a\) ，因为我们是想找到一个 \(x\) 使得 \(a\times x\) 在模 \(n\) 的意义下得到 \(1\) ，那这个式子其实可以转化为：
\[
a\times x + n \times y = 1 \ (mod \ n)
\]
其中我们需要求的就是 \(x\) ，因为 \(y\) 等于多少我们不在意，因为 \(y\) 随便取一个非负整数都可以
那么这个式子一下子我们就能联想到贝祖定理，但是贝祖定理还有一个前提条件： 那就是 \(a\) 和 \(n\) 需要 互质
详细的过程可以查看：https://acmer.blog.csdn.net/article/details/122280910的 拓展欧几里得 部分
2.4 高次幂的计算¶
关于高次幂我们可以将其幂指数变为二进制，然后再逐步计算位为 \(1\) 的数的值，然后再加起来，其实就是一个 快速幂 的实现过程
2.5 举例¶
三、优缺点¶
3.1 优点：¶
- RSA算法是国际标准算法，属于主流算法之一，相对来说也会更为普及，如果需要了解这方面的具体理论，RSA算法是必须要学习的一个算法。因为它在应用的过程之中会更为广泛，也不容易受到其他问题的限制
- RSA算法的兼容性比较广，能够适用于各种不同的系统之中，比起如今的一些新算法，RSA算法的兼容性令其在真正使用的过程之中更加方便，不会出现各种各样不同的限制
- RSA算法不像其他新算法一样复杂，它的构成相对来说更为简单，因为其难点在于对大数的质数分解
3.2 缺点¶
- RSA算法的加密长度为2048位，因此对于服务端的消耗是比较大的，所以计算的速度也会比较慢，效率相对较低
- RSA算法比起其他的算法而言，它的安全性并不算非常的高，容易被攻击，所以它的防御能力并不高
- RSA算法在运行的过程之中，内容使用比较多，这也是其效率低下、消耗高的原因之一
四、题外话大质数判定¶
由于现在的计算能力，不能对大数做一个准确质数的判定，所以当前只有一些素性检测的方法
4.1 随机算法¶
- 费尔马素性测试法
Miller-Rabin素性测试法Solovay–Strassen素性测试法
4.2 确定型启发式算法¶
- AKS素性测试法
- Baillie–PSW素性测试法
- 试除法
- 卢卡斯素性测试法
- 卢卡斯-莱默素性测试法
五、RSA签名¶
5.1 签名¶
- 利用一个安全的
hash函数 \(h\) 产生信息摘要 \(h(m)\) - 计算签名 \(S = sign_k(m) = h(m)^d\ mod \ n\)
5.2 验证¶
- 接收者使用相同的 \(hash\) 函数 \(h\) 计算消息摘要 \(h(m)\)
- 接收者验证 \(h(m) \ mod \ n = s^e \ mod \ n\) 是否成立，如果成立，那么签名就有效，否则签名无效
这里验证其实也就是用到的逆元的知识
5.3 举例¶
最后更新:
2022-09-18 12:08:00