ChaCha20-Poly1305 算法原理：从流密码到 AEAD 的完整构造

概述

ChaCha20-Poly1305 是一套完整的 AEAD（Authenticated Encryption with Associated Data，认证加密与关联数据） 算法，由 Daniel J. Bernstein 设计的 ChaCha20 流密码（2008 年）和 Poly1305 消息认证码（2005 年）组合而成。它在 RFC 8439（2018 年 6 月发布，取代 RFC 7539）中被正式标准化，已成为 TLS 1.3、SSH、IPsec、WireGuard 等核心安全协议的默认密码套件。

ChaCha20-Poly1305 的设计哲学简洁而深刻：用 ChaCha20 加密明文，用 ChaCha20 自身产生 Poly1305 所需的一次性认证密钥，再用 Poly1305 对\"密文 + 关联数据\"计算认证标签。这种自举设计使得整个 AEAD 仅依赖一个 256 位密钥，同时保持了极高的实现效率。

设计哲学：ARX 密码范式

ChaCha20 属于 ARX（Addition-Rotation-XOR，加法-旋转-异或） 类密码。这一范式与 AES 的 S 盒替换网络结构截然不同，其核心运算只有三种：

• 恒定时间执行：所有运算在硬件层面天然恒定时间，天然抵抗时序侧信道攻击
• 无 S 盒查表：避免了 AES 等 SPN 结构中 S 盒的缓存侧信道问题（如 Cache-Collision 攻击）
• 软件高效性：在没有 AES-NI 指令集的平台上（ARM 移动设备等），通常比 AES-GCM 快 3 倍

ChaCha20 流密码

2.1 ChaCha20 状态矩阵

ChaCha20 的输入是一个 512 位（64 字节）的状态矩阵，由 16 个 32 位字组成：

+————+————+————+————+
| 0  | 1  | 2  | 3  |  ← 常量 (constants)
+————+————+————+————+
| 4  | 5  | 6  | 7  |  ← 密钥 (key)
+————+————+————+————+
| 8  | 9  | 10 | 11 |  ← 密钥 (key)
+————+————+————+————+
| 12 | 13 | 14 | 15 |  ← 计数器 +  nonce
+————+————+————+————+

• 字 0-3：常量 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574（ASCII \"expand 32-byte k\"）
• 字 4-11：256 位密钥（小端序）
• 字 12：32 位块计数器
• 字 13-15：96 位 nonce（小端序）

2.2 四分之一轮函数（Quarter Round）

ChaCha20 的基本操作单元是四分之一轮函数 QR(a, b, c, d)，作用于状态矩阵中的四个字：

def quarter_round(a, b, c, d):
    a = (a + b) & 0xFFFFFFFF; d ^= a; d = roll(d, 16)
    c = (c + d) & 0xFFFFFFFF; b ^= c; b = roll(b, 12)
    a = (a + b) & 0xFFFFFFFF; d ^= a; d = roll(d,  8)
    c = (c + d) & 0xFFFFFFFF; b ^= c; b = roll(b,  7)
    return a, b, c, d

关键性质：四分之一轮是可逆的。 每个操作都是可逆的（加法逆为减法，异或逆为自身，旋转逆为反方向旋转），这保证了加密和解密使用同一套逻辑。

测试向量验证（RFC 8439 §2.1.1）：

2.3 二十轮变换：列轮与对角轮交替

ChaCha20 执行 20 轮（10 次迭代），每次迭代由两个半轮组成：

列轮（Column Round）：对 4 列分别执行四分之一轮

QR(0, 4, 8, 12)
QR(1, 5, 9, 13)
QR(2, 6, 10, 14)
QR(3, 7, 11, 15)

对角轮（Diagonal Round）：对 4 条对角线分别执行四分之一轮

QR(0, 5, 10, 15)
QR(1, 6, 11, 12)
QR(2, 7, 8, 13)
QR(3, 4, 9, 14)

这种\"列轮→对角轮\"交替的结构确保每个字在每轮中都能与其他所有字产生交互。经过 20 轮后，输入的每个比特都会影响输出的每个比特——完全扩散（Full Diffusion）。

2.4 块函数与密钥流生成

ChaCha20 的块函数将 512 位输入状态变换为 512 位输出的过程：

chacha20_block(key, counter, nonce):
    state = constants ∥ key ∥ counter ∥ nonce
    initial_state = state  （保存副本）
    for i = 1 to 10:
        state = column_round(state)
        state = diagonal_round(state)
    state = state + initial_state   （模 2^32 加法）
    return serialize_little_endian(state)

最后将变换后的状态与初始状态相加（模 2^32），这一步骤确保输出不仅依赖变换过程，还与原始输入保持关联。

2.5 加密过程

ChaCha20 加密即为明文与密钥流的异或：

chacha20_encrypt(key, counter, nonce, plaintext):
    keystream_blocks = []
    for j in range(ceil(len(plaintext) / 64)):
        block_counter = counter + j
        ks = chacha20_block(key, block_counter, nonce)
        keystream_blocks.append(ks)
    keystream = concat(keystream_blocks)[:len(plaintext)]
    return plaintext XOR keystream

解密采用相同的操作（异或的自反性）。

Poly1305 消息认证码

3.1 数学基础：素数域运算

Poly1305 的核心数学结构是素数域 p = 2^130 - 5 上的多项式运算。这个素数被精心选择：

• 接近 2^130：使得域内运算可通过 130 位整数实现
• p = 2^130 - 5：低位为 -5 mod 2^130，允许使用高效的约减算法

3.2 一次性密钥 (r, s)

Poly1305 使用一个 256 位的一次性密钥，分为两部分：

• r（128 位）：多项式基底的\"乘数\"，必须经过钳位（clamp）处理
• s（128 位）：加法密钥

def clamp(r):
    r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
    # 位 2,3,6,7,... 清零 → r[3]&=15, r[7]&=15, r[11]&=15, r[15]&=15
    # 位 0,1,4,5,... → r[4]&=252, r[8]&=252, r[12]&=252
    return r

钳位的目的是使 r * accumulator 的结果不超过 288 位，从而可以用两个 128 位字高效模拟 288 位乘法。

3.3 Poly1305 认证算法

poly1305_mac(message, key):
    r = little_endian_bytes_to_num(key[0:15])
    clamp(r)
    s = little_endian_bytes_to_num(key[16:31])
    accumulator = 0
    p = (1 << 130) - 5
    
    for each 16-byte block of message:
        n = little_endian_bytes_to_num(block ∥ 0x01)
        accumulator = ((accumulator + n) * r) % p
    
    accumulator = (accumulator + s) % 2^128
    return num_to_16_le_bytes(accumulator)

关键设计：每个消息块末尾追加的 0x01 字节确保不同的消息长度不会产生相同的认证标签（\"域分离\"）。

AEAD 构造：ChaCha20-Poly1305 的组合范式

4.1 算法流程

AEAD 构造遵循\"先加密后认证\"（Encrypt-then-MAC）范式：

AEAD_CHACHA20_POLY1305_encrypt(key, nonce, plaintext, aad):
    # 步骤 1: 生成 Poly1305 一次性密钥
    otk = poly1305_key_gen(key, nonce)
    
    # 步骤 2: ChaCha20 加密
    ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)
    
    # 步骤 3: Poly1305 认证
    mac_data = aad ∥ pad16(aad) ∥ ciphertext ∥ pad16(ciphertext) ∥ 
               len_64le(aad) ∥ len_64le(ciphertext)
    tag = poly1305_mac(mac_data, otk)
    
    return (ciphertext, tag)

4.2 Poly1305 密钥派生

poly1305_key_gen(key, nonce):
    # 用 ChaCha20 块函数在 counter=0 处生成密钥
    block = chacha20_block(key, 0, nonce)
    # 取前 32 字节作为 Poly1305 一次性密钥
    return block[0:31]

这种自举设计极具美感：加密和认证共用同一个 256 位密钥，无需额外输入。

4.3 认证数据内容

Poly1305 对以下完整数据计算标签：

[AAD] [pad16(AAD)] [Ciphertext] [pad16(Ciphertext)] [len(AAD)] [len(Ciphertext)]

• pad16(X)：填充 0-15 个零字节，使 X 的长度达到 16 的整数倍
• len(X)：X 的字节数，编码为 64 位小端序整数

4.4 解密与验证

AEAD_CHACHA20_POLY1305_decrypt(key, nonce, ciphertext, tag, aad):
    otk = poly1305_key_gen(key, nonce)
    mac_data = aad ∥ pad16(aad) ∥ ciphertext ∥ pad16(ciphertext) ∥ 
               len_64le(aad) ∥ len_64le(ciphertext)
    computed_tag = poly1305_mac(mac_data, otk)
    if computed_tag != tag:  raise AuthenticationError
    plaintext = chacha20_encrypt(key, 1, nonce, ciphertext)
    return plaintext

重要：Poly1305 验证必须在解密之前完成。如果认证失败，绝对不能返回解密后的明文，否则会泄露明文信息。

XChaCha20-Poly1305：扩展 Nonce 变体

XChaCha20-Poly1305 将 nonce 从 96 位扩展到 192 位，使得随机选择 nonce 时碰撞概率降至 2^-96。

其核心创新是 HChaCha20——ChaCha20 的变体，用于子密钥派生：

HChaCha20(key, nonce[0:15]):
    # 使用 128 位 nonce（而非 96 位）
    state = constants ∥ key ∥ nonce[0:15]
    # 执行 20 轮
    # 取结果的四个特定字输出
    return state[0:3] ∥ state[12:15]  # 128 位子密钥

XChaCha20 的完整流程：

• subkey = HChaCha20(key, nonce[0:15])
• inner_nonce = nonce[16:23] + zero_pad（8 字节 nonce 前缀扩展为 12 字节 ChaCha20 nonce）
• 使用 subkey 和 inner_nonce 执行标准 ChaCha20-Poly1305

性能分析

5.1 与 AES-GCM 的对比

来自 Adam Langley 的性能测试（RFC 8439 Appendix B）：

• 无 AES-NI 的 ARM 平台：ChaCha20-Poly1305 快 3 倍以上
• 有 AES-NI 的 x86 平台：AES-GCM 快约 1.8 倍（硬件加速）

5.2 性能优势来源

• 并行性：ChaCha20 的 20 轮变换可高度并行化（现代 CPU 的乱序执行）
• 无复杂乘法：ARX 结构仅有整数加法和移位，比 AES 的有限域乘法简单
• 大块大小：64 字节块（AES 仅 16 字节），减少块计数器溢出风险
• 恒定时间：无需担心时序泄漏，实现更简单且安全

安全分析

6.1 安全模型

ChaCha20-Poly1305 在以下安全模型下被证明安全：

• IND-CCA2：适应性选择密文攻击下的不可区分性
• SUF-CMA：强存在不可伪造性（对 MAC 部分）
• Nonce-misuse resistance：无——重复 nonce 会完全破坏安全性

6.2 Nonce 重用攻击

当同一密钥下使用重复 nonce 时：

• ChaCha20 部分：相同的密钥流会泄露两个明文的异或值：C1 ⊕ C2 = P1 ⊕ P2
• Poly1305 部分：攻击者可以恢复完整的 Poly1305 密钥，从而伪造任意消息

6.3 认证标签截断

RFC 8439 建议：

• 标签不应被截断（必须完整 128 位传输）
• 如果必须截断，最低不得少于 64 位
• 使用恒定时间比较（不能用 memcmp）

6.4 多用户安全性

在大量用户共享同一密钥的场景中（如 CDN），ChaCha20-Poly1305 的多用户安全界已被证明是紧的——在大约 2^64 条消息后，成功伪造的概率才开始显著增加。

应用场景

7.1 TLS 1.3

ChaCha20-Poly1305 是 TLS 1.3 中两个不可或缺的密码套件之一：

TLS_CHACHA20_POLY1305_SHA256  (0x13,0x03)

传输层安全协议用它来加密应用层数据（HTTP/HTTPS 流量）。

7.2 SSH

OpenSSH 以 chacha20-poly1305@openssh.com 实现了该算法，作为 AES-GCM 的替代方案。SSH 使用的是原始 ChaCha20 变体（64 位计数器 + 64 位 nonce），与 RFC 8439 的 96 位 nonce 不兼容。

7.3 WireGuard

WireGuard VPN 协议唯一支持的加密模式就是 ChaCha20-Poly1305，反映其对简洁性和一致性能的追求。

7.4 IPsec

• RFC 7634：ESP 协议中的 ChaCha20-Poly1305
• RFC 7905：IKEv2 中的 ChaCha20-Poly1305
• RFC 8103：S/MIME 中的使用

标准与实现

8.1 RFC 规范

8.2 主流实现

8.3 Python 使用示例

from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
import os

key = ChaCha20Poly1305.generate_key()
nonce = os.urandom(12)  # 96-bit nonce
aad = b"metadata"

chacha = ChaCha20Poly1305(key)
ciphertext = chacha.encrypt(nonce, b"Hello, world!", aad)
plaintext = chacha.decrypt(nonce, ciphertext, aad)

总结

ChaCha20-Poly1305 代表了密码学工程中\"正确组合简单组件\"的哲学典范：

• ChaCha20 提供高效的流密码加密——ARX 设计使它在所有平台上都能恒定时间执行
• Poly1305 提供数学上优雅的一次性认证——在素数域 2^130-5 上实现高效认证
• 自举密钥派生 减少了密钥管理负担——一个 256 位密钥同时加密和认证
• AEAD 构造 消除了 Encrypt-then-MAC 组合中的实现陷阱——RFC 8439 提供了明确的实现指南

参考来源

• RFC 8439: ChaCha20 and Poly1305 for IETF Protocols
• RFC 7539: ChaCha20 and Poly1305 for IETF Protocols (被 RFC 8439 取代)
• D. J. Bernstein, \"ChaCha, a variant of Salsa20\", 2008
• D. J. Bernstein, \"The Poly1305-AES Message-Authentication Code\", 2005
• Signal Specification: The Double Ratchet Algorithm
• G. Procter, \"A Security Analysis of the Composition of ChaCha20 and Poly1305\", IACR 2014/613

相关实践

• SM4-GCM 国密认证加密模式原理
• 认证加密与关联数据（AEAD）概念概述
• TLS 1.3 协议架构深度解析