6.1 密码学专题 - 非对称加密算法 - RSA 算法

密码学专题 - 非对称加密算法 - RSA 算法

6.1 RSA 算法

第一个较完善的非对称加密算法 RSA，它既能用于加密也能用于数字签名。在已提出的非对称加密算法中，RSA 是最容易理解和实现的。这个算法也是最流行的。RSA 以它的三个发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。该算法已经经受住了多年深入的密码分析。虽然密码分析者既不能证明也不能否定 RSA 的安全性，但这恰恰说明该算法有一定的可信度。

RSA 的安全基于大数分解的难度。其公开密钥和私人密钥是一对大素数 (100 ~ 200 个十进制数或更大) 的函数。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。

为了产生两个密钥，选取两个大素数 p 和 q。为了获得最大程度的安全性，两数的长度一样。计算乘积：
n = pq

然后随机选取加密密钥 e，使 e 和 (p-1)(q-1) 互素。最后用殴几里得扩展算法计算解密密钥 d，以满足
ed \equiv 1 \ mod \ (p-1)(q-1)

则

d = e^{-1} \ mod \ (p-1)(q-1)

注意 d 和 n 也互素。e 和 n 是公开密钥，d 是私人密钥。两个素数 p 和 q 不再需要，它们应该被舍弃，但绝不可泄露。

加密消息 m 时，首先将它分成比 n 小的数据分组 (采用二进制数，选取小于 n 的 2 的最大次幂)。也就是说，如果 p 和 q 为 100 位的素数，那么 n 将有 200 位，每个消息分组 m_i 应小于 200 位长 (如果你需要加密固定的消息分组，那么可以在它的左边填充一些 0 并确保该数比 n 小)。加密后的密文 c，将由相同长度的分组 c_i 组成。加密公式简化为：
c_i = m_i^e \ (mod \ n)

解密消息时，取每一个加密后的分组 c_i 并计算：
m_i = c_i^d \ (mod \ n)

由于
c_i^d = (m_i^e)^d = m_i^{ed} = m_i^{k(p-1)(q-1)+1} = m_i \times m_i^{k(p-1)(q-1)} = m_i \times 1 = m_i

全部 (mod \ n)。

这个公式能恢复出明文，总结见下表。

RSA 解密.jpg

消息用 d 加密就像用 e 解密一样容易。这里不引入数论来证明这样做为什么可行，现在的许多密码学教材中都包括了这些细节。

举一个简单的例子可能更清楚地说明这一点。如果 p=47,q=71，那么：
n=pq=3337

加密密钥 e 必须与 (p-1)(q-1)=46 \times 70=3220 没有公因子。

随机选取 e，如 79，那么：
d = 79^{-1} \ mod \ 3220 = 1019

该数用扩展的殴几里得算法计算。公开 e 和 n，将 d 保密，丢弃 p 和 q。

为了加密消息
m = 688232687966683

首先将其分成小的分组。在此例中，按 3 位数字一组就可以进行加密。这个消息将分成 6 个分组 m，进行加密：
m_1 = 688

m_2 = 232

m_3 = 687

m_4 = 966

m_5 = 668

m_6 = 003

第一个分组加密为：
688^{79} \ mod \ 3337 = 1570 = c_1

对随后的分组进行同样的运算产生加密后的密文：
c = 1570 \ 2756 \ 2091 \ 2276 \ 2423 \ 158

解密消息时需要用解密密钥 1019 进行相同的指数运算。因而：
1570^{1019} \ (mod \ 3337) = 688 = m_1

消息的其余部分可用同样的方法恢复出来。

Reference

项目源代码

项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。

Contributor

  1. Windstamp, https://github.com/windstamp
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容