密码学专题 - 非对称加密算法 - RSA 算法
6.1 RSA 算法
第一个较完善的非对称加密算法 RSA，它既能用于加密也能用于数字签名。在已提出的非对称加密算法中，RSA 是最容易理解和实现的。这个算法也是最流行的。RSA 以它的三个发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。该算法已经经受住了多年深入的密码分析。虽然密码分析者既不能证明也不能否定 RSA 的安全性，但这恰恰说明该算法有一定的可信度。
RSA 的安全基于大数分解的难度。其公开密钥和私人密钥是一对大素数 (100 ~ 200 个十进制数或更大) 的函数。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。
为了产生两个密钥，选取两个大素数 和
。为了获得最大程度的安全性，两数的长度一样。计算乘积：
然后随机选取加密密钥 ，使
和
互素。最后用殴几里得扩展算法计算解密密钥
，以满足
则
注意 和
也互素。
和
是公开密钥，
是私人密钥。两个素数
和
不再需要，它们应该被舍弃，但绝不可泄露。
加密消息 时，首先将它分成比
小的数据分组 (采用二进制数，选取小于
的 2 的最大次幂)。也就是说，如果
和
为 100 位的素数，那么
将有 200 位，每个消息分组
应小于 200 位长 (如果你需要加密固定的消息分组，那么可以在它的左边填充一些 0 并确保该数比
小)。加密后的密文
，将由相同长度的分组
组成。加密公式简化为：
解密消息时，取每一个加密后的分组 并计算：
由于
全部 。
这个公式能恢复出明文，总结见下表。
消息用 加密就像用
解密一样容易。这里不引入数论来证明这样做为什么可行，现在的许多密码学教材中都包括了这些细节。
举一个简单的例子可能更清楚地说明这一点。如果 ，那么：
加密密钥 必须与
没有公因子。
随机选取 ，如 79，那么：
该数用扩展的殴几里得算法计算。公开 和
，将
保密，丢弃
和
。
为了加密消息
首先将其分成小的分组。在此例中，按 3 位数字一组就可以进行加密。这个消息将分成 6 个分组 ，进行加密：
第一个分组加密为：
对随后的分组进行同样的运算产生加密后的密文：
解密消息时需要用解密密钥 1019 进行相同的指数运算。因而：
消息的其余部分可用同样的方法恢复出来。
Reference
- RSA: A SIMPLE AND EASY-TO-READ IMPLEMENTATION (PYTHON RECIPE), http://code.activestate.com/recipes/578838-rsa-a-simple-and-easy-to-read-implementation/
项目源代码
项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。
Contributor
- Windstamp, https://github.com/windstamp
