抗量子密钥交换示例

本例将演示如何使用 NewHope 密钥交换协议。这是一种基于格的抗量子密钥交换算法，旨在提供至少 128 位后量子安全级别。其底层数学基于环上带误差学习（Ring-LWE）问题，并在对某个数取模的整数多项式环中运算。密钥交换的工作方式如下：

1. Alice 生成随机私钥和相应的公开消息（公钥），并将消息发送给 Bob。公开消息由 1024 个多项式系数（范围 [0...61443] 内的整数）和随机种子（32 字节）组成。
2. Bob 获取来自 Alice 的消息（多项式和种子），并据此计算 Alice 与 Bob 之间的共享密钥。Bob 还会在内部生成私钥，用它计算一条公开消息并发送给 Alice。该公开消息由 2 个多项式组成，每个多项式用 1024 个整数系数表示。
3. Alice 获取来自 Bob 的消息（这 2 个多项式），并使用自己的私钥据此计算 Alice 与 Bob 之间的共享密钥。计算出的共享密钥由 32 字节（256 位）组成，非常适合对称密钥加密。

为演示 NewHope 密钥交换算法，我们将使用 Python 官方 PyPI 仓库中的 PyNewHope 软件包（该软件包仅为教育用途而设计，未获生产环境使用认证）：

pip install pynewhope

演示抗量子密钥交换“NewHope”的代码很简单：

from pynewhope import newhope

# Step 1: Alice generates random keys and her public msg to Bob
alicePrivKey, aliceMsg = newhope.keygen()
print("Alice sends to Bob her public message:", aliceMsg)

# Step 2: Bob receives the msg from Alice and responds to Alice with a msg
bobSharedKey, bobMsg = newhope.sharedB(aliceMsg)
print("\nBob's sends to Alice his public message:", bobMsg)
print("\nBob's shared key:", bobSharedKey)

# Step 3: Alice receives the msg from Bob and generates her shared secret
aliceSharedKey = newhope.sharedA(bobMsg, alicePrivKey)
print("\nAlice's shared key:", aliceSharedKey)

if aliceSharedKey == bobSharedKey:
    print("\nSuccessful key exchange! Keys match.")
else:
    print("\nError! Keys do not match.")

运行上述代码示例：https://repl.it/@nakov/NewHope-key-exchange-in-Python。

Alice 生成私钥和公开消息，并将公开消息发送给 Bob；随后 Bob 根据 Alice 的消息计算自己的共享密钥副本，并为 Alice 生成一条公开消息；最后 Alice 根据自己的私钥和 Bob 的消息计算自己的共享密钥副本。

上述代码的输出如下（1024 个多项式系数以缩略形式给出）：

Alice sends to Bob her public message: ([12663, 7323, 8979, 7763, 11139, 5460, 7337, 12182, ..., 8214, 10808, 8987], b'*[\x98t\xae\xe9\xc5H\xfc\xc2\x9b$\xd6\xaa[8k\xc1\x8d\xad\x1d\x01\x87i\xed\x03\x06\xe1k2\xa7N')

Bob's sends to Alice his public message: ([2, 1, 1, 2, 0, 1, 1, 1, 1, 3, 3, 2, 1, 1, 3, 0, ..., 0, 0, 3], [7045, 4326, 6186, 8298, 12738, ..., 7730, 10577, 8046])

Bob's shared key: [228, 159, 146, 8, 56, 146, 50, 7, 59, 87, 113, 57, 151, 137, 240, 139, 215, 33, 71, 188, 108, 239, 231, 252, 230, 77, 181, 178, 176, 7, 219, 217]

Alice's shared key: [228, 159, 146, 8, 56, 146, 50, 7, 59, 87, 113, 57, 151, 137, 240, 139, 215, 33, 71, 188, 108, 239, 231, 252, 230, 77, 181, 178, 176, 7, 219, 217]

Successful key exchange! Keys match.

可以看出，Alice 和 Bob 计算出的共享密钥是相同的 32 字节序列，因此密钥交换算法工作正常。上面演示的 NewHope 密钥交换算法运行得相当快，并提供 128 位后量子安全性。