Let's Encrypt 为什么押注 Merkle 树证书来对抗量子计算

import hashlib
import struct
import os

# ---- 构建一棵小型 Merkle 树（模拟一个证书批次） ----

def sha256_leaf(data: bytes) -> bytes:
    """叶子哈希：0x00 前缀 + data 的 SHA-256"""
    return hashlib.sha256(b'\x00' + data).digest()

def sha256_internal(left: bytes, right: bytes) -> bytes:
    """内部节点哈希：0x01 前缀 + left + right 的 SHA-256"""
    return hashlib.sha256(b'\x01' + left + right).digest()

def build_merkle_tree(leaves: list[bytes]) -> list[list[bytes]]:
    """
    构建 Merkle 树，返回每一层的节点列表。
    层 0 = 叶子哈希层，最后一层 = 根。
    """
    if not leaves:
        raise ValueError("至少需要一个叶子")
    # 填充到偶数个
    layer = list(leaves)
    if len(layer) % 2 == 1:
        layer.append(layer[-1])  # 复制最后一个叶子
    tree = [layer]
    while len(layer) > 1:
        next_layer = []
        for i in range(0, len(layer), 2):
            next_layer.append(sha256_internal(layer[i], layer[i + 1]))
        if len(next_layer) % 2 == 1 and len(next_layer) > 1:
            next_layer.append(next_layer[-1])
        tree.append(next_layer)
        layer = next_layer
    return tree

def get_merkle_path(tree: list[list[bytes]], leaf_index: int) -> list[tuple[bytes, bool]]:
    """
    返回从叶子到根的 Merkle 路径。
    每个元素是 (sibling_hash, is_right)，
    is_right=True 表示兄弟在右侧，当前节点在左侧。
    """
    path = []
    idx = leaf_index
    for layer in tree[:-1]:  # 不包括根层
        if idx % 2 == 0:
            sibling = layer[idx + 1]
            path.append((sibling, True))   # 当前是左，兄弟是右
        else:
            sibling = layer[idx - 1]
            path.append((sibling, False))  # 当前是右，兄弟是左
        idx //= 2
    return path

def verify_merkle_path(leaf_data: bytes, path: list[tuple[bytes, bool]], expected_root: bytes) -> bool:
    """沿 Merkle 路径从叶子哈希到根，比对期望根哈希"""
    current = sha256_leaf(leaf_data)
    for sibling, is_right in path:
        if is_right:
            current = sha256_internal(current, sibling)
        else:
            current = sha256_internal(sibling, current)
    return current == expected_root


# ---- 模拟一个证书批次 ----

# 5 张"证书条目"：域名 + 公钥指纹（简化）
cert_entries = [
    b"example.com|pubkey_hash_abc123",
    b"api.example.com|pubkey_hash_def456",
    b"shop.example.com|pubkey_hash_ghi789",
    b"blog.example.com|pubkey_hash_jkl012",
    b"mail.example.com|pubkey_hash_mno345",
]

leaf_hashes = [sha256_leaf(e) for e in cert_entries]
tree = build_merkle_tree(leaf_hashes)
root_hash = tree[-1][0]

# 模拟 CA 对根哈希的后量子签名（这里用 HMAC 代替，仅作演示）
ca_private_key = os.urandom(32)
batch_signature = hashlib.sha256(ca_private_key + root_hash).digest()
batch_header = {
    "root_hash": root_hash,
    "signature": batch_signature,
    "batch_time": "2026-06-03T10:00:00Z",
}

# ---- 验证第 3 张证书（leaf_index=2） ----

target_index = 2
target_entry = cert_entries[target_index]
merkle_path = get_merkle_path(tree, target_index)

# 步骤 1：沿路径计算根哈希
computed_root_valid = verify_merkle_path(target_entry, merkle_path, batch_header["root_hash"])

# 步骤 2：验证根哈希的签名（真实场景用 ML-DSA 公钥验证）
ca_public_key = ca_private_key  # 简化：HMAC 场景下"公钥"=私钥
expected_sig = hashlib.sha256(ca_public_key + batch_header["root_hash"]).digest()
sig_valid = batch_header["signature"] == expected_sig

print(f"证书条目: {target_entry}")
print(f"Merkle 路径长度: {len(merkle_path)} 层")
print(f"路径计算根哈希匹配: {computed_root_valid}")
print(f"根签名验证: {sig_valid}")
print(f"最终结论: 证书有效 ✓" if (computed_root_valid and sig_valid) else "证书无效 ✗")

# ---- 用错误数据验证，应该失败 ----

fake_entry = b"evil.example.com|pubkey_hash_fake"
fake_valid = verify_merkle_path(fake_entry, merkle_path, batch_header["root_hash"])
print(f"\n伪造证书验证: {fake_valid} (应为 False)")

证书条目: blog.example.com|pubkey_hash_ghi789
Merkle 路径长度: 3 层
路径计算根哈希匹配: True
根签名验证: True
最终结论: 证书有效 ✓

伪造证书验证: False (应为 False)

# 安装 oqs-openssl（以 Ubuntu 为例）
sudo apt update && sudo apt install -y cmake git ninja-build python3-pip
pip3 install oqs-sdk

# 克隆并编译 oqs-openssl
git clone https://github.com/open-quantum-safe/oqs-openssl.git
cd oqs-openssl
./configure --prefix=/opt/oqs-openssl
make -j$(nproc) && sudo make install

# 用 ML-KEM-768 + ML-DSA-65 生成后量子证书（传统 X.509 格式，仅测试）
export LD_LIBRARY_PATH=/opt/oqs-openssl/lib
/opt/oqs-openssl/bin/openssl req -x509 -newkey ml-dsa-65 \
  -keyout pq_key.pem -out pq_cert.pem -days 365 -nodes \
  -subj "/CN=test.pq.example.com"

# 启动后量子 TLS 测试服务器
/opt/oqs-openssl/bin/openssl s_server -cert pq_cert.pem -key pq_key.pem \
  -accept 4433 -groups ml-kem-768:x25519 &

# 客户端连接测试
/opt/oqs-openssl/bin/openssl s_client -connect localhost:4433 \
  -groups ml-kem-768:x25519 -CAfile pq_cert.pem

# 查看证书体积对比
echo "=== 后量子 ML-DSA-65 证书 ==="
wc -c pq_cert.pem
echo "=== 传统 ECDSA P-256 证书 ==="
openssl req -x509 -newkey ec -pkeyopt ec_paramgen_curve:P-256 \
  -keyout ec_key.pem -out ec_cert.pem -days 365 -nodes \
  -subj "/CN=test.ec.example.com" 2>/dev/null
wc -c ec_cert.pem