OpenSSL 中 RSA 加密探索
当通过公共媒介（如互联网）发送您的信用卡号时，如果该号码未先加密，您的财务信誉可能会受到损害。当您在线购买新 CD 或书籍时，无法得知谁可能在监听您的连接。RSA 加密方法经常被用来隐藏您在互联网上潜在窃贼的信用卡号，因为它使用公钥来隐藏您的信息，并使用私钥来揭示它。本文消除了 RSA 加密的神秘感，并解释了 OpenSSL 库中 RSA 的实际实现是如何工作的。您只需要关注 openssl/crypto/bn 和 openssl/crypto/rsa 子目录中的文件。请随意下载并查看代码，以便在继续之前对其有所了解。
理解非对称加密的最佳方法是想象一个有两种钥匙的盒子：一种钥匙锁住它，另一种钥匙打开它。任何拥有锁定钥匙（又称公钥）副本的人都可以将秘密放入盒子中。因为只有您拥有解锁钥匙（又称私钥），所以没有人可以揭示别人锁在盒子里的秘密。这与对称密钥加密不同，在对称密钥加密中，相同的密钥用于锁定和解锁。
这是一个使用相同密钥加密的示例。首先，我们选择一个数字并称之为密钥。我们想要加密一个信用卡号，所以我们从密钥中减去信用卡号的每个数字。例如，取数字 1424 3135 2435 1556 并选择数字 12。我们可以像这样加密它
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 -1 -4 -2 -4 -3 -1 -3 -5 -2 -4 -3 -5 -1 -5 -5 -6 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 11 8 10 8 9 11 9 7 10 8 9 7 11 7 7 6
底部的数字列表将是加密后的信用卡号。要解密信用卡号，我们只需要再次从密钥中减去每个数字
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 11 8 10 8 9 11 9 7 10 8 9 7 11 7 7 6 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 1 4 2 4 3 1 3 5 2 4 3 5 1 5 5 6
现代加密算法，如 AES 和 Triple DES，比这种技术复杂得多——更不用说更安全了——但这个例子显示了相同的密钥是如何用于加密和解密的。在双方可以使用这个系统之前，他们都需要知道密钥 12。象征这种算法的代数方程式是
C = K - M
M = K - C
其中 M 是要加密的数字，K 是密钥（在上面的例子中是 12），C 是加密后的密文数字。如果双方可以在开始通信之前就密钥达成一致，那么对称加密就足够了。然而，这种预先安排并非总是可行的。
假设您第一次登录书店，并决定用信用卡购买东西。您如何知道使用哪个密钥？您或在线书店必须选择密钥 (K)，但它不能通过互联网发送，因为窥探者可能会看到它。这就是 RSA 发挥作用的地方。加密和解密的方程式只比减法技术稍微复杂一点
C = ME mod N
M = CD mod N
如果您不习惯看到 mod，这意味着取数字除以 N 的余数。在第一个方程式中，我们将 M 提高到 E 次方，并将结果除以 N，然后将余数存储在 C 中。
同样，M 是要加密的数字，C 是密文数字。有两个密钥：E 用于加密，而 D 用于解密。理解 N 的最佳方式是将其视为隐藏秘密的盒子。例如，假设我们希望加密数字 6。我们选择加密密钥 E=3，解密密钥 D=17 和盒子 N=25。您想将消息 M=6 发送给书店，所以加密过程如下
C = 63 mod 25 = 16
当您登录在线书店时，卖家会向您发送密钥 E=3 和盒子 N=25，以便您可以加密您的信用卡号。但是，如果不知道 D=17，则无法解密
M = 1617 mod 25 = 6
因为没有人知道 D=17，所以除了书店之外，任何人都无法解密消息。因此，您可以联系互联网上的任何人，并感到安全，您的敏感信息不会被盗。
这项技术非常简单，以至于 32 位数字的编码和解码可以在一行 C 代码中实现。真正的复杂性在于当您提出诸如“我如何生成 RSA 密钥对？”或“为了安全起见，数字需要多大？”之类的问题时。这些问题的答案使 RSA 实现复杂了一百倍。本文的其余部分说明了 OpenSSL 库中如何解决这些障碍。您可以从 www.openssl.org 下载最新版本。点击标记为 Source 的选项卡下载最新版本（在撰写本文时为 0.9.7b）。
生成数字 N、E 和 D 需要生成素数和互质数。要生成 N，您需要找到两个大素数并将它们相乘。我们可以将 N 定义为一个数学方程式
N = P * Q
其中 P 和 Q 都是随机素数。加密密钥 E 和解密密钥 D 都必须与 (P-1)*(Q-1) 互质。这意味着它们必须满足方程式
(E * D) mod (P-1)*(Q-1) = 1
如果两个数字是互质数，这意味着它们的素数分解没有共同之处。例如，9 和 40 彼此互质，因为它们没有公因数
9 = 3 * 3
40 = 2 * 2 * 2 * 5
为 RSA 密钥生成随机素数只不过是一个猜测和检查的过程。文件 openssl/bn/bn_prime.* 实现了快速筛法测试方法来选择素数。快速筛法方法会问“这个数字是素数吗？”，但只收到以下答案
否
可能
OpenSSL 生成随机数，然后多次运行测试素数函数，以排除任何误报。如果测试失败，则丢弃随机数，然后重新开始该过程。不能保证生成的数字真的是素数，但数学大师已经证明，通过使用此测试，可以以 99.9% 的概率证明一个数字是素数。
加密密钥 E 通常被选择为一个常数素数用于协议（例如 SSL）。因此，只需要通过互联网发送数字 N。常见的选择是数字 3 或 65537。找到解密密钥 D 稍微困难一些，因为您需要找到模逆元。这涉及使用欧几里得算法计算最大公约数，详见 Knuth 的书（见资源）。如果您查看文件 openssl/crypto/rsa/rsa_gen.c，您可以了解它在 OpenSSL 中是如何工作的。
安全的 RSA 实现需要相当大的数字。大多数安全协议标准建议使用 1,024 位数字的密钥大小，而 Pentium III 或 PowerPC 等 32 位处理器无法原生处理这些数字。为了绕过这个障碍，OpenSSL 实现了一种名为 BIGNUM 的新数据类型。BIGNUM 数据结构在文件 openssl/crypto/bn/bn.h 中实现，并在列表 1 中定义。
通用计算机只能处理 1,024 位数字，前提是将它们存储为较小的 32 位数字数组。BIGNUM 结构中的变量 d 存储指向动态分配数组的指针。数组的长度存储在 dmax 中，以便处理 BIGNUM 变量的例程可以避免缓冲区溢出错误。
BIGNUM 的基本算术运算就像小学数学课一样简单，但增加了一些变化。让我们看一下两个数字的简单加法
1 1 <== carry
1 4 7
+ 2 6 3
-------
4 1 0
人类通过一次添加一位数字（从右到左）将多位数字的加法分解为更小的部分。计算机可以以相同的方式添加大数。如果我们把每个数字分成一个单独的数组元素，我们可以像这样实现基本加法
#define BASE 10
void add(int *a, int *b, int *c, int top) {
int i, carry;
for (i=carry=0; i < top; i++) {
c[i] = a[i] + b[i] + carry;
if (c[i] >= BASE) {
carry = 1;
c[i] -= BASE;
} else {
carry = 0;
}
}
}
变量 top 表示要添加的位数。通过使用这种技术来分解数字，如果需要，我们可以定义一个数千位大小的数字。将 BASE 定义为十进制效率不高，那么为什么不使用十六进制甚至四十亿进制呢？答案是我们可以使用我们喜欢的任何进制，直到 32 位整数的最大值
void add(unsigned int *a, unsigned int *b,
unsigned int *c, int top) {
int i, carry;
for (i=carry=0; i < top; i++) {
c[i] = a[i] + b[i] + carry;
/* is there an overflow? */
if ((c[i] < a[i]) || (c[i] < b[i])) {
carry = 1; /* yes overflow, so carry */
} else {
carry = 0; /* no overflow, no carry */
}
}
}
因为 32 位整数可以存储的最大数字是 232-1，任何更大的数字都会环绕并出现溢出错误。我们可以利用这个“错误”，因为它具有与减去基数相同的效果。这就是 OpenSSL 用于实现 BIGNUM 结构算术运算的原理。
如果您查看 openssl/crypto/bn/bn_add.c 和 openssl/crypto/bn/bn_asm.c，您可以找到超优化的加法和减法函数。这些函数使用花哨的指针技术来引用 BIGNUM 变量中的数组元素，但原理是相同的。它们跟踪的其他一些细节包括
负数，减法运算所必需的
top 变量的不同值
缓冲区溢出错误
微处理器独立性
解决这些问题的所有错误检查和次要优化可能会使 BN_add() 和 BN_sub() 最初看起来令人生畏，但它们只是对旧的、经过验证的方法进行花哨的 C 代码包装。
乘法也很好地推广到 BIGNUM 数据结构。当使用 32 位无符号整数来表示单个数字时，我们可以使用经典的小学算法。例如
2 4 3
* 4 1 5
-------
1 2 1 5 <== 243 * 5
2 4 3 <== 243 * 1
9 7 2 <== 243 * 4
-----------
1 0 0 8 4 5
如果我们允许总共有 232 位数字而不是通常的十位数字，我们可以根据前面讨论的加法函数来实现乘法。
void mul(unsigned int *a, unsigned int *b,
unsigned int *c, int top) {
unsigned long long prod; /* 64-bit num in GNU C */
unsigned int i,j, hi32, lo32, carry;
unsigned int acc[top]; /* array of size top */
/* initialize c[] to all zeros */
for (j=0; j < top; j++) {
/* initialize acc[] to all zeros */
for (i=carry=0; i < top; i++) {
prod = a[i] * b[j];
lo32 = prod & 0x00000000FFFFFFFFULL;
hi32 = prod & 0xFFFFFFFFr0000000ULL;
acc[i] = lo32+carry;
carry = hi32;
}
add(acc,c+i,c+i,top);
}
}
请注意，当乘以两个 32 位数字时，我们需要 64 位。为了正确处理 64 位数量，我们需要将其拆分为两个 32 位数量。数字 a 乘以 b 中的一位数字，结果添加到总数中。为了优化乘法，OpenSSL 使用了一种称为 Karatsuba 递归算法的技巧。它通过使用分而治之的方法将时间复杂度从 O(n2) 降低到 O(n1.5)。
除法是一种类似于乘法的野兽，但需要更多思考。虽然将加法转换为减法只需要更改符号，但除法必须考虑余数或模数。尽管 OpenSSL 在 openssl/crypto/bn/bn_div.c 中实现了除法，但在 RSA 中并不直接需要它，因为 RSA 使用蒙哥马利乘法代替（稍后会详细介绍）。
OpenSSL 基于乘法-模算法实现求幂。直接将 1,024 位数字提高到 1,024 位数字的幂次方需要大约 10300 GB 的内存。那么，计算机如何计算 RSA 运算 ME mod N 呢？诀窍在于在乘法中分配模运算。例如
436 mod 13 =
(432 mod 13) * (44 mod 13)
通过分配模运算，无需存储超过 1,024 个额外的位在中间运算中。
求幂的另一个微妙之处使其可以在短时间内计算出结果。让我们看一下 openssl/crypto/bn/bn_exp.c
for (i=1; i<bits; i++)
{
if (!BN_sqr(v,v,ctx)) goto err;
if (BN_is_bit_set(p,i))
{
if (!BN_mul(rr,rr,v,ctx)) goto err;
}
}
此函数计算 vp，然后将结果存储在 rr 中。因为数字以二进制表示，所以可以将求幂表示为 2 的幂的乘积。看看这个分解
432 = 416 * 416 <==
416 = 48 * 48
48 = 44 * 44
44 = 42 * 42 <==
436 = 432 * 44
如果我们检查上面 BN_exp() 的摘录，我们看到 v 在每一步都被平方。然后，如果在 p 中设置了一位，则将其乘以总数。数字 36 在二进制中是 00100010，因此求幂只不过是一个移位-测试-乘法运算。
为了对 BIGNUM 变量进行求幂，每个步骤都需要乘法运算和模运算。与其经历基本算法，不如将乘法和模运算组合成一个称为模乘法（又称蒙哥马利乘法）的步骤。OpenSSL 使用这种方法来加速 BIGNUM 变量的模幂运算。文件 openssl/crypto/bn/bn_mont.c 有一个实现，需要一些时间才能完全理解。如果您有进一步的兴趣，请查看这篇论文。
将文本字符串转换为 BIGNUM 变量并返回是实现 RSA_public_encrypt() 和 RSA_private_decrypt() 函数所需的最后一步。两者都在 openssl/crypto/rsa/rsa_lib.c 中定义。如果您有兴趣了解如何在您自己的程序中包含 RSA，请查看 openssl/crypto/rsa/rsa_test.c。此示例说明了如何使用 OpenSSL RSA 包完成您可能需要的任何操作。
这绝不是对 RSA 工作原理的全面解释，也并非旨在如此。希望它解释了一些更晦涩的细节。RSA 的安全性基于分解大数的难度，对于今天的 1,024 位数字来说，这几乎是不可能的。然而，随着技术的发展，这种情况可能会在明天发生改变。RSA 实验室的 RSA 分解挑战赛有关于分解的最新公开信息（见资源）。
OpenSSL 库用于多个开源软件包。您可能熟悉的一些著名的软件包包括 Samba、Apache-SSL 和 OpenSSH。如果您有兴趣了解更多关于如何实现加密算法或其安全性的信息，下面列出了一些资源。
Kernighan & Ritchie，《C 程序设计语言》
Knuth，《计算机程序设计艺术，第 2 卷》
Schneier，《应用密码学》
Menezes, Alfred J., Van Oorschot, Paul C. 和 Vanstone, Scott A.，《应用密码学手册》
James Tandon 目前在 Computer Motion 担任顾问，并且喜欢狗胜过猫。他的主页是 www.antinomian.net。
