8.3. 递归再探¶
8.3. Recursion Revisited
今天数值计算最常见的用途之一是加密领域。每次你查看银行账户、登录安全网站进行购买，或登录计算机时，你都在使用加密技术。一般来说，加密 涉及对你不希望其他人看到的信息进行加密和解密。在本节中，我们将探讨一些在日常加密编程中使用的函数。实际上，可能有更快速的方法来实现这些函数，但每个函数都有一个有趣的递归实现。
本节中的算法利用了 Python 的取模运算符（%）。记住，\(a \% b\) 是 \(a\) 除以 \(b\) 后的余数，例如 \(10 \% 7 = 3\)。当我们计算任何数学表达式模 10 的结果时，唯一可能的结果是 0 到 9。
早期的加密形式仅使用简单的模运算。例如，字符串 "uryybjbeyq"。你能猜出加密的消息是什么吗？Listing lst_enc 显示了生成该消息的函数。查看代码，看看你能否找出答案。
def encrypt(m):
s = "abcdefghijklmnopqrstuvwxyz"
n = ""
for i in m:
j = (s.find(i) + 13) % 26
n = n + s[j]
return n
encrypt 函数演示了一种被称为 Caesar Cipher 的加密形式。它也被称为 ROT13，这更具描述性。encrypt 函数简单地将消息中的每个字母在字母表中的位置加上 13。如果位置超出了字母表的末尾，它会回绕。这个回绕函数可以通过取模运算符轻松实现。此外，由于字母表中有 26 个字母，这个函数是对称的。对称性允许我们使用这个函数加密和解密相同的消息。如果你将字符串 "uryybjbeyg" 传递给 encrypt 函数，它将返回 "helloworld"。
除了 13 的旋转之外，还可以使用其他旋转量；然而，它们在加密和解密方面并不对称。非对称性要求我们编写一个单独的解密算法，该算法会减去旋转的量。在这种情况下，我们可以将 encrypt 和 decrypt 函数泛化，使其接受旋转量作为参数。在加密术语中，旋转参数称为 key，它表示旋转的位置数。给定消息和密钥，加密和解密算法可以完成它们的工作。Listing lst_dec_key 显示了一个接受旋转量作为参数的解密算法。作为练习，你应该能够修改 Listing lst_enc 以接受指定密钥的参数。
def decrypt(m, k):
s = "abcdefghijklmnopqrstuvwxyz"
n = ""
for i in m:
j = (s.find(i) + 26 - k) % 26
n = n + s[j]
return n
即使你将数字 k 隐藏在除了接收消息的人之外的所有人中，这种简单的加密形式仍然不能长时间阻止任何人窃取你的秘密。在本节的剩余部分，我们将介绍一种更安全的加密形式，即 RSA 公钥加密 算法。
One of the most common uses of numerical computing today is in the field of cryptography. Each time you check your bank account, sign on to a secure website to purchase something, or sign on to your computer, you are using cryptography. In a general sense, cryptography is concerned with encrypting and decrypting information that you do not want other people to see. In this section we will look at some functions that are used in everyday cryptographic programming. In practice there may be faster ways to implement these functions, but each of them has an interesting recursive implementation.
The algorithms in this section make use of Python’s modulo operator (%). Remember that \(a \% b\)` is what is left over after \(a\) is divided by \(b\), for example \(10 \% 7 = 3\). When we compute the result of any mathematical expression modulo 10, the only possible results are 0–9.
One of the earliest forms of cryptography used only simple modular arithmetic. Take the string "uryybjbeyq", for example. Can you guess what message is encrypted? Listing lst_enc shows you the function that produced the message. Look at the listing and see if you can figure it out.
def encrypt(m):
s = "abcdefghijklmnopqrstuvwxyz"
n = ""
for i in m:
j = (s.find(i) + 13) % 26
n = n + s[j]
return n
The encrypt function illustrates a form of encryption known as the Caesar Cipher. It also goes by the name ROT13, which is a bit more descriptive. encrypt simply takes each letter in the message and adds 13 to its ordinal position in the alphabet. If the position goes past the end of the alphabet, it wraps around. This wraparound function is easily accomplished using the modulo operator. In addition, since there are 26 letters in the alphabet, this function is symmetric. The symmetry allows us to use the function to encrypt and decrypt the same message. If you pass the string "uryybjbeyg" to the encrypt function, it returns "helloworld".
Rotations by amounts other than 13 are possible; however, they are not symmetric with respect to encrypting and decrypting. Asymmetry would require us to write a separate decryption algorithm that subtracts the amount to rotate. In that case, we could generalize both the encrypt and decrypt functions to take the amount of rotation as a parameter. In cryptographic terms, the rotation parameter is called the key and would be the number of positions to rotate. Given the message and the key, the encryption and decryption algorithms can do their jobs. Listing lst_dec_key shows the decryption algorithm that takes the amount of rotation as a parameter. As an exercise you should be able to modify Listing lst_enc to accept a parameter that specifies a key.
def decrypt(m, k):
s = "abcdefghijklmnopqrstuvwxyz"
n = ""
for i in m:
j = (s.find(i) + 26 - k) % 26
n = n + s[j]
return n
Even if you keep the number k from everyone except the person you are sending the message to, this simple form of encryption is not going to stop anyone from stealing your secrets for very long. In the remainder of this section, we will build up to a much more secure form of encryption, the RSA public key encryption algorithm.
8.3.1. 模运算定理¶
8.3.1. Modular Arithmetic Theorems
如果两个数 \(a\) 和 \(b\) 除以 \(n\) 时余数相同，我们说 \(a\) 和 \(b\) 是“模 \(n\) 同余的”。简写为 \(a \equiv b \pmod{n}\)。本节中的算法利用了三个重要的定理：
- 如果 \(a \equiv b \pmod{n}\)，则对任意 \(c\)，有 \(a + c \equiv b + c \pmod{n}\)。
- 如果 \(a \equiv b \pmod{n}\)，则对任意 \(c\)，有 \(ac \equiv bc \pmod{n}\)。
- 如果 \(a \equiv b \pmod{n}\)，则对任意正整数 \(p\)，有 \(a^p \equiv b^p \pmod{n}\)。
If two numbers, \(a\) and \(b\), give the same remainder when divided by \(n\), we say that \(a\) and \(b\) are “congruent modulo \(n\).” In shorthand we write \(a \equiv~b~\pmod{n}\). The algorithms in this section make use of three important theorems:
- If \(a \equiv b \pmod{n}\) then \(\forall c, a + c \equiv b + c \pmod{n}\).
- If \(a \equiv b \pmod{n}\) then \(\forall c, ac \equiv bc \pmod{n}\).
- If \(a \equiv b \pmod{n}\) then \(\forall p, p > 0, a^p \equiv b^p \pmod{n}\).
8.3.2. 模幂运算¶
8.3.2. Modular Exponentiation
假设我们想知道 \(3^{1,254,906}\) 的最后一位数字。这不仅是一个大计算问题，而且使用 Python 的任意精度整数，结果有 598,743 位数字！我们只想知道最右边数字的值。这里有两个问题。首先，如何高效地计算 \(x^n\)？其次，如何在不计算出所有 598,743 位数字后再查看最后一位的情况下计算 \(x^n \pmod{p}\)？
对于第二个问题，根据上述第三个定理，答案很简单。
- 初始化结果为 1。
-
重复 \(n\) 次：
- 将结果乘以 \(x\)。
- 对结果应用模运算。
这种方法使计算变得更简单，因为我们保持结果较小，而不是将其计算到完整精度。然而，我们可以使用递归方法做得更好。
\(x^n = \begin{cases} (x \cdot x)^{ n/2 } & \text{如果} \space n \space \text{是偶数} \\ (x \cdot x^{n-1}) = x \cdot (x \cdot x)^{\lfloor n/2 \rfloor} & \text{如果} \space n \space \text{是奇数} \end{cases}\)
记住，对于一个浮点数 \(n\)，地板操作 \(\lfloor n \rfloor\) 结果是小于 \(n\) 的最大整数。Python 的整数除法运算符返回除法结果的地板值，因此在代码中我们不需要做任何特别的处理来实现我们想要的结果。上面的方程给出了计算 \(x^n\) 的一个非常好的递归定义。我们现在只需要一个基本情况。回忆一下，对于任何数字 \(x\)，\(x^0 = 1\)。由于我们在每次递归调用中减少了指数的大小，因此检查条件 \(n = 0\) 是一个好的基本情况。
def modexp(x, n, p):
if n == 0:
return 1
t = (x * x) % p
tmp = modexp(t, n // 2, p)
if n % 2 != 0:
tmp = (tmp * x) % p
return tmp
注意，在上述方程中，无论是偶数还是奇数情况，都包括了一个因子 \((x \cdot x)^{\lfloor n/2 \rfloor}\)，因此我们无条件地计算它并将其存储在变量 tmp 中。同时注意，由于我们在计算中应用了模 \(p\)，因此在每一步计算时仍然应用了模运算。Listing lst_pow 中的解决方案保持了结果的大小较小，并且比纯粹的迭代方法使用了更少的乘法操作。
Suppose we wanted to know the last digit of \(3^{1,254,906}\). Not only is that a large computation problem, but using Python’s arbitrary-precision integers the number has 598,743 digits! All we want to know is the value of the rightmost digit. There are really two problems here. First, how do we compute \(x^n\) efficiently? Second, how can we compute \(x^n \pmod{p}\) without first calculating all 598,743 digits and then looking at the last one?
The answer to the second question is easy, given the third theorem from above.
- Initialize result to 1.
-
Repeat \(n\) times:
-
Multiply result by \(x\).
- Apply modulo operation to result.
The above approach makes the computation simpler because we are keeping the result smaller rather than following it out to its full precision. However, we can do even better using a recursive approach.
\(x^n = \begin{cases} (x \cdot x)^{ n/2 } & \text{if} \space n \space \text{is even} \\ (x \cdot x^{n-1}) = x \cdot (x \cdot x)^{\lfloor n/2 \rfloor} & \text{if} \space n \space \text{is odd} \end{cases} \label{eqn:pow}\)
Remember that for a floating point number \(n\) the floor operation, \(\lfloor n \rfloor\), results in the largest integer smaller than \(n\). Python’s integer division operator returns the floor of the result of the division, so we do not need to do anything special in our code to achieve the results we want. The above equation gives us a very nice recursive definition for computing \(x^n\). All we need now is a base case. Recall that for any number \(x\), \(x^0 = 1\). Since we are reducing the size of our exponent in each recursive call, checking for the condition \(n = 0\) is a good base case.
def modexp(x, n, p):
if n == 0:
return 1
t = (x * x) % p
tmp = modexp(t, n // 2, p)
if n % 2 != 0:
tmp = (tmp * x) % p
return tmp
Notice that in the above equation both the even and odd cases include a factor of \((x \cdot x)^{\lfloor n/2 \rfloor}\), so we compute that unconditionally and store it in the variable tmp. Also note that since we are computing modulo p we still apply the modulo operator at each step of the calculation. The solution in Listing lst_pow keeps the result size small and uses many fewer multiplications than a purely iterative approach.
8.3.3. 最大公约数与乘法逆元¶
8.3.3. The Greatest Common Divisor and Multiplicative Inverses
一个正整数 \(x\) 的 乘法逆元 模 \(m\) 是任何使得 \(ax \equiv 1 \pmod{m}\) 的数 \(a\)。例如，设 \(x = 3\)，\(m = 7\)，和 \(a = 5\)；因为 \(3 \times 5 = 15\) 且 \(15 \% 7 = 1\)，所以 5 是 3 模 7 的乘法逆元。
在模算术中，乘法逆元的概念最初可能看起来非常困惑。我们如何在上面的例子中选择了 5？5 是 3 模 7 唯一的乘法逆元吗？所有的数 \(a\) 对于任何给定的 \(m\) 都有乘法逆元吗？
让我们看一个示例，可能对第一个问题有所启示：我们如何选择 5 作为 3 模 7 的乘法逆元？查看以下 Python 会话：
>>> for i in range(1, 40):
... if (3 * i) % 7 == 1:
... print(i)
...
5
12
19
26
33
这个小实验告诉我们，对于 \(x=3\) 和 \(m=7\)，有很多乘法逆元（模 7），即 \(5, 12, 19, 26, 33\)，等等。你注意到这个序列有什么有趣的地方吗？序列中的每个数字比 7 的倍数小 2。
所有的数对 \(x\) 和 \(m\) 都有乘法逆元吗？让我们看另一个示例。考虑 \(x=4\) 和 \(m=8\)。将 4 和 8 插入到之前的循环中不会有输出。如果我们去掉条件并打印出 \((4 \cdot i)\ \% 8\) 的结果，我们得到序列 \((0, 4, 0, 4, 0, 4 \dots)\)。在这里，余数在 0 和 4 之间交替变化。显然，结果永远不会是 1。我们如何事先知道这一点？
答案是，一个数 \(x\) 对于模 \(m\) 存在乘法逆元，当且仅当 \(m\) 和 \(x\) 是互质的。两个数互质的条件是 \(gcd(m,x) = 1\)。回忆一下，最大公约数（GCD）是能同时整除这两个数的最大整数。下一个问题是我们如何计算两个数的最大公约数？
给定两个数 \(a\) 和 \(b\)，我们可以通过重复从 \(a\) 中减去 \(b\) 直到 \(a < b\) 来找到 GCD。当 \(a < b\) 时，我们交换 \(a\) 和 \(b\)。在某个时候 \(a - b\) 变为 0，因此我们再交换一次 \(a\) 和 \(b\)。此时我们有 \(gcd(a, 0) = a\)。这个算法在 2000 多年前首次被描述，被称为欧几里得算法。
在递归算法设计方面，欧几里得算法非常直接。基本情况是 \(b = 0\)。递归调用有两种可能性：当 \(a < b\) 时，我们交换 \(a\) 和 \(b\) 并进行递归调用。否则，我们可以进行递归调用，将 \(a - b\) 作为 \(a\) 传递。欧几里得算法在 Listing lst_gcd1 中展示了。
def gcd(a, b):
if b == 0:
return a
elif a < b:
return gcd(b, a)
return gcd(a - b, b)
尽管欧几里得算法非常易于理解和编程，但它不是我们希望的那样高效，特别是当 \(a >> b\) 时。再次，模算术来拯救我们。注意最后一次减法的结果（当 \(a - b < b\) 时）实际上与 \(a\) 除以 \(b\) 的余数相同。考虑到这一点，我们可以去掉所有减法，并在一个递归调用中结合 \(a\) 和 \(b\) 的交换。修订后的算法在 Listing lst_gcd2 中展示了。
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
现在我们有了一个方法来确定两个数 \(x\) 和 \(m\) 是否会有乘法逆元，我们的下一个任务是编写一个高效的算法来计算逆元。假设对于任意一对数 \(x\) 和 \(y\)，我们可以计算出 \(gcd(x, y)\) 以及一对整数 \(a\) 和 \(b\)，使得 \(d = gcd(x, y) = ax + by\)。例如，\(1 = gcd(3, 7) = -2 \times 3 + 1 \times 7\)，所以这里 \(a = -2\) 和 \(b = 1\) 是 \(a\) 和 \(b\) 的可能值。我们不再考虑任意的数 \(x\) 和 \(y\)，而是使用我们之前的例子中的 \(m\) 和 \(x\)。现在我们有 \(1 = gcd(m, x) = am + bx\)。根据本节开头的讨论，我们知道 \(bx = 1 \mod{m}\)，因此 \(b\) 是 \(x\) 模 \(m\) 的乘法逆元。
我们已经将计算逆元的问题简化为寻找满足 \(d = gcd(x, y) = ax + by\) 的整数 \(a\) 和 \(b\)。由于我们从 GCD 算法开始这个问题，我们也可以通过扩展这个算法来完成它。我们将两个数 \(x \geq y\) 作为输入，返回一个元组 \((d, a, b)\)，其中 \(d = gcd(x, y)\) 且 \(d = ax + by\)。欧几里得算法的扩展在 Listing lst_gcd3 中展示了。
| Listing lst_gcd3 | |
|---|---|
1 2 3 4 5 6 | |
注意，当我们得到基本情况 \(y = 0\) 时，我们返回 \(d = x\) 就像原始的欧几里得算法一样。然而，我们还返回两个额外的值 \(a = 1\) 和 \(b = 0\)。这三个值一起满足方程 \(d = ax + by\)。如果 \(y > 0\)，则我们递归计算值 \((d, a, b)\)，使得 \(d = gcd(y, x \mod{y})\) 且 \(d = ay + b(x \mod{y})\)。与原始算法一样，\(d = gcd(x, y)\)。但其他两个值 \(a\) 和 \(b\) 呢？我们知道 \(a\) 和 \(b\) 必须是整数，所以我们将它们称为 \(A\) 和 \(B\)。进一步地，我们知道 \(d = Ax + By\)。为了找出 \(A\) 和 \(B\) 应该是什么，我们将方程重新排列如下：
\(\begin{aligned} d = & ay + b(x \mod{y}) \\ = & ay + b(x - \lfloor x / y \rfloor y) \\ = & bx + (a - \lfloor x / y \rfloor b)y\end{aligned}\)
注意第二行中的替代，\(x \mod{y} = x - \lfloor x / y \rfloor y\)。这是合法的，因为这就是我们通常计算 \(x / y\) 的余数（\(x \mod{y}\)）的方法。查看重新排列的方程，我们可以看到 \(A = b\) 和 \(B = a - \lfloor x / y \rfloor b\)。注意这正是 [line:6] 行所做的！要检查这一点，请注意在算法的每一步返回值都满足方程 \(d = ax + by\)。要理解我们的扩展 GCD 算法如何工作，让我们从一个示例开始：设 \(x = 25\) 和 \(y = 9\)。Figure 1 说明了递归函数的调用和返回值。
A multiplicative inverse of a positive integer \(x\) modulo \(m\) is any number \(a\) such that \(ax \equiv 1 \pmod{m}\). For example, let \(x = 3\), \(m = 7\), and \(a = 5\); \(3 \times 5 = 15\) and \(15\ \%\ 7 = 1\), so 5 is a multiplicative inverse of 3 modulo 7.
The idea of multiplicative inverses in the world of modulo arithmetic may seem very confusing at first. How did we select 5 in the previous example? Is 5 the only multiplicative inverse of 3 modulo 7? Do all numbers \(a\) have a multiplicative inverse for any given \(m\)?
Let’s look at an example that may shed some light on the first question: how did we select 5 as the multiplicative inverse of 3 modulo 7? Look at the following Python session:
>>> for i in range(1, 40):
... if (3 * i) % 7 == 1:
... print i
...
5
12
19
26
33
This little experiment tells us that there are many multiplicative inverses (modulo 7) for \(x=3\) and \(m = 7\), namely \(5, 12, 19, 26, 33\), and so on. Do you notice anything interesting about the sequence? Each number in the sequence is two less than a multiple of seven.
Do all pairs of numbers \(x\) and \(m\) have a multiplicative inverse? Let’s look at another example. Consider \(x=4\) and \(m=8\). Plugging 4 and 8 into the loop in the previous example gives us no output. If we take out the conditional and print out the results of \((4 \cdot i)\ \%\ 8\), we get the sequence \((0, 4, 0, 4, 0, 4\dots)\). Here we have a case where the remainder alternates between 0 and 4 repeatedly. Clearly the result is never going to be 1. How can we know that ahead of time?
The answer is that a number \(x\) has a multiplicative inverse, modulo \(m\), if and only if \(m\) and \(x\) are relatively prime. Two numbers are relatively prime if \(gcd(m,x) = 1\). Recall that the greatest common divisor (GCD) is the largest integer that divides both numbers. The next question is how can we compute the greatest common divisor for a pair of numbers?
Given two numbers \(a\) and \(b\) we can find the GCD by repeatedly subtracting \(b\) from \(a\) until \(a < b\). When \(a < b\), we switch roles for \(a\) and \(b\). At some point \(a - b\) becomes 0, so we swap \(a\) and \(b\) one more time. At that point we have $gcd(a, 0) = a`. This algorithm was first described more than 2,000 years ago and is called Euclid’s algorithm.
In terms of recursive algorithm design, Euclid’s algorithm is very straightforward. The base case is when \(b = 0\). There are two possibilities for a recursive call: when \(a < b\), we swap \(a\) and \(b\) and make a recursive call. Otherwise, we can make a recursive call passing \(a - b\) in place of \(a\). Euclid’s algorithm is shown in Listing lst_gcd1.
def gcd(a, b):
if b == 0:
return a
elif a < b:
return gcd(b, a)
return gcd(a - b, b)
Although Euclid’s algorithm is quite easy to understand and program, it is not as efficient as we would like, particularly if \(a >> b\). Once again, modular arithmetic comes to our rescue. Notice that the result of the last subtraction (when \(a - b < b\)) is really the same as the remainder of $adivided by $b$. With that in mind, we can cut out all of the subtractions and combine the swap of $a$ and $b$ in one recursive call. A revised algorithm is shown inListing lst_gcd2`.
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
Now that we have a way to know whether two numbers \(x\) and \(m\) will have a multiplicative inverse, our next task is to write an efficient algorithm to compute the inverse. Suppose that for any pair of numbers \(x\) and \(y\) we could compute both \(gcd(x,y)\) and a pair of integers \(a\) and \(b\) such that \(d = gcd(x, y) = ax + by\). For example, \(1 = gcd(3, 7) = -2 \times 3 + 1 \times 7\), so here \(a = -2\) and \(b = 1\) are possible values for \(a\) and \(b\). Rather than any numbers \(x\) and \(y\), let’s use \(m\) and \(x\) from our previous examples. Now we have \(1 = gcd(m, x) = am + bx\). From the discussion at the beginning of this section we know that \(bx = 1 \mod{m}\), so \(b\) is a multiplicative inverse of \(x\) modulo \(m\).
We have reduced the problem of computing inverses to the problem of finding integers \(a\) and \(b\) that satisfy the equation \(d = gcd(x, y) = ax + by\). Since we started this problem with the GCD algorithm, we can finish it with an extension of this algorithm as well. We will take two numbers \(x >= y\) and return a tuple \((d, a, b)\) such that \(d = gcd(x, y)\) and \(d = ax + by\). The extension to Euclid’s algorithm is shown in Listing lst_gcd3.
| Listing lst_gcd3 | |
|---|---|
1 2 3 4 5 6 | |
Notice that when we get the base case \(y = 0\), we return \(d = x\) just like the original Euclid’s algorithm. However, we return two additional values \(a =1\) and \(b = 0\). Together these three values satisfy the equation \(d = ax + by\). If \(y > 0\), then we recursively compute values \((d, a, b)\) such that \(d = gcd(y, x \mod{y})\) and \(d = ay + b(x \mod{y})\). As with the original algorithm, \(d = gcd(x, y)\). But what about the other two values, \(a\) and \(b\)? We know that \(a\) and \(b\) must be integers, so let’s call them \(A\) and \(B\). Further, we know that \(d = Ax + By\). To figure out what \(A\) and \(B\) should be, let’s rearrange the equation as follows:
\(\begin{aligned} d = & ay + b(x \mod{y}) \\ = & ay + b(x - \lfloor x / y \rfloor y) \\ = & bx + (a - \lfloor x / y \rfloor b)y\end{aligned}\)
Note the substitution made in the second line, \(x \mod{y} = x - \lfloor x / y \rfloor\). This is legal because this is how we would normally calculate the remainder of x / y (\(x \mod{y}\)). Looking at the rearranged equation, we can see that \(A = b\) and \(B = a - \lfloor x / y \rfloor b\). Notice that this is exactly what line [line:6] does! To check this, note that at each return step in the algorithm the return values satisfy the equation \(d = ax + by\). To understand how our extended GCD algorithm works, let’s start with an example: let \(x = 25\) and \(y = 9\). Figure 1 illustrates the call and return values for the recursive function.
8.3.4. RSA算法¶
8.3.4. RSA Algorithm
现在我们有了编写 RSA 加密算法所需的所有工具。RSA 算法可能是所有公钥加密算法中最容易理解的一种。公钥密码学由 Whitfield Diffie 和 Martin Hellman 以及 Ralph Merkle 独立发明。公钥密码学的主要贡献是提出了密钥成对的概念：一个加密密钥用于将明文消息转换为密文，另一个解密密钥用于将密文转换回明文。这些密钥只能单向工作，因此用私钥加密的消息只能用公钥解密，反之亦然。
RSA 的安全性来源于大数因式分解的困难。公钥和私钥是从一对大（100-200 位数字）素数中推导出来的。由于 Python 的长整数类型本身就支持大数，这使得实现这个算法既有趣又容易。
为了生成这两个密钥，选择两个大素数 \(p\) 和 \(q\)。然后计算它们的乘积：
\(n = p \times q\)
下一步是随机选择加密密钥 \(e\)，使得 \(e\) 和 \((p - 1) \times (q - 1)\) 互质，即
\(gcd(e, (p - 1) \times (q - 1)) = 1\)
最后，解密密钥 \(d\) 是 \(e\) 模 \((p - 1) \times (q - 1)\) 的乘法逆元。为此我们可以使用扩展的欧几里得算法。
将 \(e\) 和 \(n\) 组合起来就是公钥。数字 \(d\) 是私钥。一旦我们计算出 \(n, e\) 和 \(d\)，原始的素数 \(p\) 和 \(q\) 就不再需要。然而，它们不应被公开。
为了加密消息，我们只需使用方程 \(c = m^e \pmod{n}\)。为了解密消息，我们使用 \(m = c^d \pmod{n}\)。
很容易看出，当你记住 \(d\) 是 \(e \pmod{n}\) 的乘法逆元时，这些公式是有效的。
\(\begin{aligned} c^d & = (m^e)^d \pmod{n} \\ & = m^{ed} \pmod{n} \\ & = m^1 \pmod{n} \\ & = m \pmod{n} \end{aligned}\)
在将这些方程转化为 Python 代码之前，我们需要讨论几个其他细节。首先，我们如何将像“hello world”这样的文本消息转换为数字？最简单的方法是直接使用每个字符的 ASCII 值并将所有数字连接在一起。然而，由于 ASCII 值的十进制表示的位数不一致，我们将使用十六进制数字，在十六进制中，我们可以可靠地知道两个十六进制数字表示一个字节或字符。
| h | e | l | l | o | w | o | r | l | d | |
|---|---|---|---|---|---|---|---|---|---|---|
| 104 | 101 | 108 | 108 | 111 | 32 | 119 | 111 | 114 | 108 | 100 |
| 68 | 65 | 6c | 6c | 6f | 20 | 77 | 6f | 72 | 6c | 64 |
将所有十六进制数字合在一起，我们可以将这个大十六进制数字转换为十进制整数：
\(m = 126207244316550804821666916\)
Python 可以很好地处理这个大数字。然而，真实使用 RSA 加密的程序有两个原因会将消息拆分成较小的块并加密每个块。第一个原因是性能。即使是相对较短的电子邮件消息，例如 1k 的文本，也会生成一个有 2000 到 3000 位数字的数字！如果我们将其提高到 \(d\) 的 10 位幂，我们谈论的将是一个非常长的数字。
第二个原因是消息分块的限制，即 \(m \le n\)。我们必须确保消息在模 \(n\) 下有唯一的表示。对于二进制数据，选择小于 \(n\) 的最大二的幂。例如，假设我们选择 \(p\) 和 \(q\) 为 5563 和 8191。那么 \(n = 5563 \times 8191 = 45,566,533\)。为了保持块的整数值小于 \(n\)，我们将把我们的单词分成少于表示 \(n\) 所需字节数的块。在 Python 中，这可以通过整数方法 bit_length 容易地找到。给定表示一个数字所需的位数，我们可以除以 8 来找到字节数。由于消息中的每个字符可以用一个字节表示，这种除法告诉我们每个块中可以放入的字节数。方便的是，这让我们可以简单地将消息分成 \(n\) 个字符的块，并将每个块的十六进制表示转换为一个整数。对于这个示例，我们可以使用 26 位表示 \(45,566,533\)。使用整数除法并除以 8 告诉我们应该将消息分成三字符的块。
字符“h”、“e”和“l”的十六进制值分别是 \(68\)、\(65\) 和 \(6c\)。将这些值连接在一起得到 \(68656c\)，转换为十进制值为 \(6841708\)。
| - | - | - | - |
|---|---|---|---|
| \(m_1 = 6841708\) | \(m_2 = 7106336\) | \(m_3 = 7827314\) | \(m_4 = 27748\) |
注意，将消息分成块可能非常棘手，特别是当对一个块应用 RSA 转换时产生的数字少于七位数。在这种情况下，我们需要小心在将块拼接回去时添加前导零。你可以在上面的 \(m_1\) 和 \(m_4\) 中看到这可能发生的情况。
现在让我们选择一个 \(e\) 的值。我们可以随机选择值并使用 GCD 算法测试它们与 \((p - 1) \times (q - 1) = 45552780\) 的互质性。记住，我们在寻找一个与 45,552,780 互质的 \(e\)。在这个示例中，1471 是一个合适的选择。
\(\begin{aligned}d & = ext\_gcd(45552780, 1471) \\ & = -11705609 \\ & = 45552780 - 11705609 \\ & = 33847171\end{aligned}\)
让我们使用这些信息来加密消息的第一个块：
\(c = 6841708^{1471} \pmod{45566533} = 16310024\)
为了验证我们的工作，让我们解密 \(c\) 以确保恢复原始值：
\(m = 16310024^{33847171} \pmod{45566533} = 6841708\)
其余的消息块可以使用相同的过程进行加密，并作为加密消息一起发送。
最后，让我们看一下三个 Python 函数。
gen_keys创建一个公钥和一个私钥，给定 \(p\) 和 \(q\)。encrypt接受一个消息、公钥和 \(n\)，并返回消息的加密版本。decrypt接受加密的消息、私钥和 \(n\)，并返回原始消息。
def gen_keys(p, q):
n = p * q
m = (p - 1) * (q - 1)
e = int(random.random() * n)
while gcd(m, e) != 1:
e = int(random.random() * n)
d, a, b = ext_gcd(m, e)
if b < 0:
d = m + b
else:
d = b
return (e, d, n)
def encrypt(msg, e, n):
chunk_size = n.bit_length() // 8
all_chunks = str_to_chunks(msg, chunk_size)
return [
modexp(msg_chunk, e, n)
for msg_chunk in all_chunks
]
def decrypt(cipher_chunks, d, n):
chunk_size = n.bit_length() // 8
plain_chunks = [
modexp(cipher_chunk, d, n)
for cipher_chunk in cipher_chunks
]
return chunks_to_str(plain_chunks, chunk_size)
下面是一个会话，使用这些函数创建公钥和私钥，进行加密和解密，如上例所示。
>>> msg = "Python"
>>> e, d, n = gen_keys(5563, 8191)
>>> print(e, d, n)
2646697 33043453 45566533
>>> c = encrypt(msg, e, n)
>>> print(c)
[22810070, 18852325, 34390906, 22805081]
>>> m = decrypt(c, d, n)
>>> print(m)
Python
>>>
最后要查看的是两个辅助函数，这些函数将字符串分成块并将块合并回字符串（Listing lst_chunk）。这些函数利用 Python 的 bytearray 对象，这使我们能够将任何字符串存储为字节序列。这使得将字符串转换为十六进制数字序列非常方便，也允许我们将十六进制数字序列转换回字符串。
def str_to_chunks(msg, chunk_size):
msg_bytes = bytes(msg, "utf-8")
hex_str = "".join([f"{b:02x}" for b in msg_bytes])
num_chunks = len(hex_str) // chunk_size
chunk_list = []
for i in range(
0, num_chunks * chunk_size + 1, chunk_size
):
chunk_list.append(hex_str[i : i + chunk_size])
chunk_list = [
eval("0x" + x) for x in chunk_list if x
]
return chunk_list
def chunks_to_str(chunk_list, chunk_size):
hex_list = []
for chunk in chunk_list:
hex_str = hex(chunk)[2:]
clen = len(hex_str)
hex_list.append(
"0" * ((chunk_size - clen) % 2) + hex_str
)
hstring = "".join(hex_list)
msg_array = bytearray.fromhex(hstring)
return msg_array.decode("utf-8")
在 Listing lst_chunk 中，我们看到将字符串转换为块列表的过程。一个重要的注意事项是，我们必须确保我们的十六进制数字对应的字符长度正好为两位。这意味着有时我们可能需要添加一个前导零。我们可以通过使用字符串格式化表达式 f"{b:02x}" 来轻松实现。这种表达式创建了一个正好两位的字符串，如果需要的话，前面会有一个前导零。创建了一个包含整个消息的长十六进制字符串后，我们可以将这个长字符串分成 num_chunks 个十六进制数字块。这就是在 for 循环（从第 6 行开始）中发生的事情。最后，我们可以使用 eval 函数和列表推导式将每个十六进制数字转换为整数。
将解密后的块转换回字符串就像创建一个长的十六进制字符串并将其转换为 bytearray 一样简单。bytearray 有一个内置的 decode 函数，将 bytearray 转换为字符串。这个过程唯一棘手的部分是，在转换过程中，块所表示的数字可能会比原始数字小得多。如果是这种情况，我们可能需要添加前导零，以确保在将所有块拼接回一起时，所有块的长度都是相同的。额外的零是通过使用字符串重复运算符在表达式 "0" * ((chunk_size) - clen) % 2) 中添加到任何块中的，其中 chunk_size 代表字符串中应有的数字位数，clen 代表实际数字位数。
Now we have all the tools we need to write the RSA encryption algorithm. The RSA algorithm is perhaps the easiest to understand of all the public key encryption algorithms. Public key cryptography was invented by Whitfield Diffie and Martin Hellman and independently by Ralph Merkle. The major contribution of public key cryptography was the idea that keys could come in pairs: an encryption key to convert the plaintext message to ciphertext, and a decryption key to convert the ciphertext back to plaintext. The keys only work one way so that a message encrypted with the private key can only be decrypted with the public key, and vice versa.
RSA gets its security from the difficulty of factoring large numbers. The public and private keys are derived from a pair of large (100–200 digit) prime numbers. Since long integers are native to Python, this is a fun and easy algorithm to implement.
To generate the two keys, choose two large prime numbers \(p\) and \(q\). Then compute the product
\(n = p \times q\)
The next step is to randomly choose the encryption key \(e\) such that \(e\) and \((p - 1) \times (q - 1)\) are relatively prime; that is
\(gcd(e, (p - 1) \times (q-1)) = 1\)
Finally, the decryption key \(d\) is simply the multiplicative inverse of \(e\) modulo \((p - 1) \times (q - 1)\). For this we can use our extended version of Euclid’s algorithm.
The numbers \(e\) and \(n\) taken together are the public key. The number \(d\) is the private key. Once we have computed \(n, e\), and \(d\), the original primes \(p\) and \(q\) are no longer needed. However, they should not be revealed.
To encrypt a message we simply use the equation \(c = m^e \pmod{n}\). To decrypt the message we use \(m = c^d \pmod{n}\).
It is easy to see that this works when you remember that \(d\) is the multiplicative inverse of \(e \pmod{n}\).
\(\begin{aligned} c^d & = (m^e)^d \pmod{n} \\ & = m^{ed} \pmod{n} \\ & = m^1 \pmod{n} \\ & = m \pmod{n} \end{aligned}\)
Before we turn all these equations into Python code, we need to talk about a couple of other details. First, how do we take a text message like "hello world" and turn it into a number? The easiest way is to simply use the ASCII values associated with each character and concatenate all the numbers together. However, since the decimal versions of the numbers of the ASCII values vary in the number of digits needed to represent them, we will use the hexadecimal numbers where we know very reliably that two hexadecimal digits represent a single byte or character.
| h | e | l | l | o | w | o | r | l | d | |
|---|---|---|---|---|---|---|---|---|---|---|
| 104 | 101 | 108 | 108 | 111 | 32 | 119 | 111 | 114 | 108 | 100 |
| 68 | 65 | 6c | 6c | 6f | 20 | 77 | 6f | 72 | 6c | 64 |
Putting all the hexadecimal digits together we could convert that large hex number into a decimal integer:
\(m = 126207244316550804821666916\)
Python can handle this large number just fine. However, there are two reasons that real programs using RSA encryption break the message up into smaller chunks and encrypt each chunk. The first reason is performance. Even a relatively short email message, say 1k of text, will generate a number with 2,000 to 3,000 digits! If we raise that to a power of \(d\) which has 10 digits, we are talking about a very long number indeed.
The second reason for breaking the message into chunks is the restriction that \(m \le n\). We must be sure that the message has a unique representation modulo \(n\). With binary data, choose the largest power of two that is less than \(n\). For example, let’s choose \(p\) and \(q\) to be 5563 and 8191. So \(n = 5563 \times 8191 = 45,566,533\). To keep the integer value of our chunks less than \(m\), we will divide up our word into chunks that use less than the number of bytes needed to represent \(n\). This is easy to find in Python using the integer method bit_length. Given the number of bits needed to represent a number, we can divide by eight to find the number of bytes. Since each character in the message can be represented by a single byte, this division tells us the number of bytes we can put in each chunk. Conveniently, this lets us simply break the message up into chunks of \(n\) characters and convert the hexadecimal representation of each chunk into an integer. For this example we can represent \(45,566,533\) using 26 bits. Using integer division and dividing by eight tells us that we should break our message into chunks of three characters.
The characters “h,” “e,” and “l” have the hexadecimal values of \(68\), \(65\), and \(6c\), respectively. Concatenating those together gives us \(68656c\) and converting that to a decimal gives us \(6841708\).
| - | - | - | - |
|---|---|---|---|
| \(m_1 = 6841708\) | \(m_2 = 7106336\) | \(m_3 = 7827314\) | \(m_4 = 27748\) |
Note that breaking the message into chunks can be very tricky, in particular when the result of applying the RSA transformation to a chunk produces a number that is less than seven digits long. In this case we need to be careful to add a leading zero to the result when we glue our chunks back together again. You can see how this might happen in \(m_1\) and \(m_4\) above.
Now let’s choose a value for \(e\). We can select values randomly and use the GCD algorithm to test them against \((p - 1) \times (q - 1) = 45552780\). Remember that we are looking for an \(e\) that is relatively prime to 45,552,780. The number 1,471 will work nicely for this example.
\(\begin{aligned}d & = ext\_gcd(45552780, 1471) \\ & = -11705609 \\ & = 45552780-11705609 \\ & = 33847171\end{aligned}\)
Let’s use this information to encrypt the first chunk of our message:
\(c = 6841708^{1471} \pmod{45566533} = 16310024\)
To check our work, let’s decrypt \(c\) to make sure we recover the original value:
\(m = 16310024^{33847171} \pmod{45566533} = 6841708\)
The remaining chunks of the message can be encrypted using the same procedure and sent all together as the encrypted message.
Finally, let’s look at three Python functions.
gen_keyscreates a public and private key, given \(p\) and \(q\).encrypttakes a message, the public key, and \(n\) and returns an encrypted version of the message.decrypttakes the encrypted message, the private key, and \(n\) and returns the original message.
def gen_keys(p, q):
n = p * q
m = (p - 1) * (q - 1)
e = int(random.random() * n)
while gcd(m, e) != 1:
e = int(random.random() * n)
d, a, b = ext_gcd(m, e)
if b < 0:
d = m + b
else:
d = b
return (e, d, n)
def encrypt(msg, e, n):
chunk_size = n.bit_length() // 8
all_chunks = str_to_chunks(msg, chunk_size)
return [
modexp(msg_chunk, e, n)
for msg_chunk in all_chunks
]
def decrypt(cipher_chunks, d, n):
chunk_size = n.bit_length() // 8
plain_chunks = [
modexp(cipher_chunk, d, n)
for cipher_chunk in cipher_chunks
]
return chunks_to_str(plain_chunks, chunk_size)
Here is a session that uses these functions to create public and private keys, encrypt, and decrypt as we did in the example above.
>>> msg = "Python"
>>> e, d, n = gen_keys(5563, 8191)
>>> print(e, d, n)
2646697 33043453 45566533
>>> c = encrypt(msg, e, n)
>>> print(c)
[22810070, 18852325, 34390906, 22805081]
>>> m = decrypt(c, d, n)
>>> print(m)
Python
>>>
The last thing to look at is the two helper functions that break our string into chunks and merge chunks into a string (Listing lst_chunk). These functions make use of Python bytearray objects, which allow us to store any string as a sequence of bytes. This makes it very convenient for us to convert a string to a sequence of hexadecimal digits and allows us to convert a sequence of hexadecimal digits back to a string.
def str_to_chunks(msg, chunk_size):
msg_bytes = bytes(msg, "utf-8")
hex_str = "".join([f"{b:02x}" for b in msg_bytes])
num_chunks = len(hex_str) // chunk_size
chunk_list = []
for i in range(
0, num_chunks * chunk_size + 1, chunk_size
):
chunk_list.append(hex_str[i : i + chunk_size])
chunk_list = [
eval("0x" + x) for x in chunk_list if x
]
return chunk_list
def chunks_to_str(chunk_list, chunk_size):
hex_list = []
for chunk in chunk_list:
hex_str = hex(chunk)[2:]
clen = len(hex_str)
hex_list.append(
"0" * ((chunk_size - clen) % 2) + hex_str
)
hstring = "".join(hex_list)
msg_array = bytearray.fromhex(hstring)
return msg_array.decode("utf-8")
In Listing lst_chunk we see the procedure for turning a string into a list of chunks. One important thing to note is that we must always make sure that our hexadecimal number corresponds to a character that is exactly two digits long. This means that sometimes we may need to add a leading zero. We can do this easily by using the string formatting expression f"{b:02x}". This expression creates a string that is exactly two characters long, with a leading zero at the beginning if necessary. Once we have created a single long hexadecimal string out of the entire message, we can then break up that long string into num_chunks chunks of hexadecimal numbers. This is what is happening in the for loop (starting on line 6). Finally, we can transform each hexadecimal number into an integer using the eval function and the list comprehension.
Transforming the decrypted chunks back to a string is as easy as creating a single long hex string and turning that hexadecimal string into a bytearray. The bytearray has a built-in decode function to turn the bytearray into a string. The only tricky part of this procedure is that after the transformation process the number represented by the chunk may end up significantly smaller than the original. If this is the case we may need to add a leading zero to make sure that all of the chunks are the same length when we concatenate them back together again. The extra zeros are prepended to any chunk by using the string repetition operator in the expression "0" * ((chunk_size) - clen) % 2) where chunk_size represents the number of digits that should be present in the string and clen represents the actual number.
创建日期: 2024年9月9日