算法精粹：经典计算机科学问题的Python实现
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

一次性密码本（one-time pad）是一种加密数据的方法，它将无意义的随机的假数据（dummy data）混入数据中，这样在无法同时拿到加密结果和假数据的情况下就不能重建原始数据。这实质上是给加密程序配上了密钥对。其中一个密钥是加密结果，另一个密钥则是随机的假数据。单个密钥是没有用的，只有两个密钥的组合才能解密出原始数据。只要运行无误，一次性密码本就是一种无法破解的加密方案。图1-6演示了这一过程。

图1-6 一次性密码本会产生两个密钥，它们可以分开存放，后续可再组合起来以重建原始数据

以下示例将用一次性密码本方案加密一个srt。Python 3的str类型有一种用法可被视为UTF-8字节序列（UTF-8是一种Unicode字符编码）。通过encode()方法可将str转换为UTF-8字节序列（以bytes类型表示）。同理，用bytes类型的decode()方法可将UTF-8字节序列转换回str。

一次性密码本的加密操作中用到的假数据必须符合3条标准，这样最终的结果才不会被破解。假数据必须与原始数据长度相同、真正随机、完全保密。第1条标准和第3条标准是常识。如果假数据因为太短而出现重复，就有可能被觉察到规律。如果其一个密钥不完全保密（可能在其他地方被重复使用或部分泄露），那么攻击者就能获得一条线索。第2条标准给自己出了一道难题：能否生成真正随机的数据？大多数计算机的答案都是否定的。

本例将会用到secrets模块的伪随机数据来生成函数token_ bytes()（自Python 3.6开始包含在于标准库中）。这里的数据并非是真正随机的，因为secrets包在幕后采用的仍然是伪随机数生成器，但它已足够接近目标了。下面就来生成一个用作假数据的随机密钥，具体代码如代码清单1-15所示。

代码清单1-15 unbreakable_encryption.py

from secrets import token_bytes
from typing import Tuple

def random_key(length: int) -> int:
# generate length random bytes
    tb: bytes = token_bytes(length)
# convert those bytes into a bit string and return it
return int.from_bytes(tb, "big")

以上函数将创建一个长度为length字节的int，其中填充的数据是随机生成的。int. from_bytes()方法用于将bytes转换为int。如何将多字节数据转换为单个整数呢？答案就在1.2节。在1.2节中已经介绍过int类型可为任意大小，而且还展示了int能被当作通用的位串来使用。本节以同样的方式使用int。例如，from_bytes()方法的参数是7字节（7字节×8位/字节= 56位），该方法会将这个参数转换为56位的整数。为什么这种方式很有用呢？因为与对序列中的多字节进行操作相比，对单个int（读作“长位串”）进行位操作将更加简单高效。下面将会用到XOR位运算。

如何将假数据与待加密的原始数据进行合并呢？这里将用XOR操作来完成。XOR是一种逻辑位操作（二进制位级别的操作），当其中一个操作数为真时返回true，而如果两个操作数都为真或都不为真则返回false。可能大家都已猜到了，XOR代表“异或”。

Python中的XOR操作符是“^”。在二进制位的上下文中，0^1和1^0将返回1，而0^0和1^1则会返回0。如果用XOR合并两个数的二进制位，那么把结果数与其中某个操作数重新合并即可生成另一个操作数，这是一个很有用的特性。

A ^ B = C
C ^ B = A
C ^ A = B

上述重要发现构成了一次性密码本加密方案的基础。为了生成结果数据，只要简单地将原始str以字节形式表示的int与一个随机生成且位长相同的int（由random_key()生成）进行异或操作即可。返回的密钥对就是假数据和加密结果。具体代码如代码清单1-16所示。

代码清单1-16 unbreakable_encryption.py（续）

def encrypt(original: str) -> Tuple[int, int]:
    original_bytes: bytes = original.encode()
    dummy: int = random_key(len(original_bytes))
    original_key: int = int.from_bytes(original_bytes, "big")
    encrypted: int = original_key ^ dummy# XOR
return dummy, encrypted

注意 int.from_bytes()要传入两个参数。第一个参数是需要转换为int的bytes。第二个参数是这些字节的字节序（endianness）"big"。字节序是指存储数据所用的字节顺序。首先读到的是最高有效字节（most significant byte），还是最低有效字节（least significant byte）？在本示例中，只要加密和解密时采用相同的顺序就无所谓，因为实际只会在单个二进制位级别操作数据。如果是在编码过程的两端不全由自己掌控的其他场合，字节序可能是至关重要的因素，所以请务必小心！

解密过程只是将encrypt()生成的密钥对重新合并而已。只要在两个密钥的每个二进制位之间再次执行一次XOR运算，就可完成解密任务了。最终的输出结果必须转换回str。首先，用int.to_bytes()将int转换为bytes。该方法需要给定int要转换的字节数。只要把总位长除以8（每字节的位数），就能获得该字节数。最后，用bytes类型的decode()方法即可返回一个str。具体代码如代码清单1-17所示。

代码清单1-17 unbreakable_encryption.py（续）

def decrypt(key1: int, key2: int) -> str:
    decrypted: int = key1 ^ key2# XOR
    temp: bytes = decrypted.to_bytes((decrypted.bit_length()+ 7) // 8, "big")
return temp.decode()

在用整除操作（//）除以8之前，必须给解密数据的长度加上7，以确保能“向上舍入”，避免出现边界差一（off-by-one）错误。如果上述一次性密码本的加密过程确实有效，那么应该就能毫无问题地加密和解密Unicode字符串了。具体代码如代码清单1-18所示。

代码清单1-18 unbreakable_encryption.py（续）

if __name__ == "__main__":
    key1, key2 = encrypt("One Time Pad!")
    result: str = decrypt(key1, key2)
    print(result)

如果控制台输出了“One Time Pad!”，就万事大吉了。

上一章目录下一章