8.3. 递归再探¶
8.3. Recursion Revisited
今天数值计算最常见的用途之一是加密领域。每次你查看银行账户、登录安全网站进行购买，或登录计算机时，你都在使用加密技术。一般来说，加密 涉及对你不希望其他人看到的信息进行加密和解密。在本节中，我们将探讨一些在日常加密编程中使用的函数。实际上，可能有更快速的方法来实现这些函数，但每个函数都有一个有趣的递归实现。
本节中的算法利用了 Python 的取模运算符（%）。记住，
早期的加密形式仅使用简单的模运算。例如，字符串 "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
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
如果两个数
- 如果
- 如果
- 如果
If two numbers,
- If
- If
- If
8.3.2. 模幂运算¶
8.3.2. Modular Exponentiation
假设我们想知道
对于第二个问题，根据上述第三个定理，答案很简单。
- 初始化结果为 1。
-
重复
- 将结果乘以
- 对结果应用模运算。
- 将结果乘以
这种方法使计算变得更简单，因为我们保持结果较小，而不是将其计算到完整精度。然而，我们可以使用递归方法做得更好。
记住，对于一个浮点数
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
注意，在上述方程中，无论是偶数还是奇数情况，都包括了一个因子 tmp 中。同时注意，由于我们在计算中应用了模 Listing lst_pow 中的解决方案保持了结果的大小较小，并且比纯粹的迭代方法使用了更少的乘法操作。
Suppose we wanted to know the last digit of
The answer to the second question is easy, given the third theorem from above.
- Initialize result to 1.
-
Repeat
-
Multiply result by
- 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.
Remember that for a floating point number
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 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
一个正整数
在模算术中，乘法逆元的概念最初可能看起来非常困惑。我们如何在上面的例子中选择了 5？5 是 3 模 7 唯一的乘法逆元吗？所有的数
让我们看一个示例，可能对第一个问题有所启示：我们如何选择 5 作为 3 模 7 的乘法逆元？查看以下 Python 会话：
>>> for i in range(1, 40):
... if (3 * i) % 7 == 1:
... print(i)
...
5
12
19
26
33
这个小实验告诉我们，对于
所有的数对
答案是，一个数
给定两个数
在递归算法设计方面，欧几里得算法非常直接。基本情况是 Listing lst_gcd1 中展示了。
def gcd(a, b):
if b == 0:
return a
elif a < b:
return gcd(b, a)
return gcd(a - b, b)
尽管欧几里得算法非常易于理解和编程，但它不是我们希望的那样高效，特别是当 Listing lst_gcd2 中展示了。
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
现在我们有了一个方法来确定两个数
我们已经将计算逆元的问题简化为寻找满足 Listing lst_gcd3 中展示了。
| Listing lst_gcd3 | |
|---|---|
1 2 3 4 5 6 | |
注意，当我们得到基本情况
注意第二行中的替代，[line:6] 行所做的！要检查这一点，请注意在算法的每一步返回值都满足方程 Figure 1 说明了递归函数的调用和返回值。
A multiplicative inverse of a positive integer
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
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
Do all pairs of numbers
The answer is that a number
Given two numbers
In terms of recursive algorithm design, Euclid’s algorithm is very straightforward. The base case is when 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 divided 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
We have reduced the problem of computing inverses to the problem of finding integers Listing lst_gcd3.
| Listing lst_gcd3 | |
|---|---|
1 2 3 4 5 6 | |
Notice that when we get the base case
Note the substitution made in the second line, [line:6] does! To check this, note that at each return step in the algorithm the return values satisfy the equation 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 的长整数类型本身就支持大数，这使得实现这个算法既有趣又容易。
为了生成这两个密钥，选择两个大素数
下一步是随机选择加密密钥
最后，解密密钥
将
为了加密消息，我们只需使用方程
很容易看出，当你记住
在将这些方程转化为 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 |
将所有十六进制数字合在一起，我们可以将这个大十六进制数字转换为十进制整数：
Python 可以很好地处理这个大数字。然而，真实使用 RSA 加密的程序有两个原因会将消息拆分成较小的块并加密每个块。第一个原因是性能。即使是相对较短的电子邮件消息，例如 1k 的文本，也会生成一个有 2000 到 3000 位数字的数字！如果我们将其提高到
第二个原因是消息分块的限制，即 bit_length 容易地找到。给定表示一个数字所需的位数，我们可以除以 8 来找到字节数。由于消息中的每个字符可以用一个字节表示，这种除法告诉我们每个块中可以放入的字节数。方便的是，这让我们可以简单地将消息分成
字符“h”、“e”和“l”的十六进制值分别是
| - | - | - | - |
|---|---|---|---|
注意，将消息分成块可能非常棘手，特别是当对一个块应用 RSA 转换时产生的数字少于七位数。在这种情况下，我们需要小心在将块拼接回去时添加前导零。你可以在上面的
现在让我们选择一个
让我们使用这些信息来加密消息的第一个块：
为了验证我们的工作，让我们解密
其余的消息块可以使用相同的过程进行加密，并作为加密消息一起发送。
最后，让我们看一下三个 Python 函数。
gen_keys创建一个公钥和一个私钥，给定encrypt接受一个消息、公钥和decrypt接受加密的消息、私钥和
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
The next step is to randomly choose the encryption key
Finally, the decryption key
The numbers
To encrypt a message we simply use the equation
It is easy to see that this works when you remember that
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:
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
The second reason for breaking the message into chunks is the restriction that 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
The characters “h,” “e,” and “l” have the hexadecimal values of
| - | - | - | - |
|---|---|---|---|
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
Now let’s choose a value for
Let’s use this information to encrypt the first chunk of our message:
To check our work, let’s decrypt
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, givenencrypttakes a message, the public key, anddecrypttakes the encrypted message, the private key, and
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日