是否存在利用Poly1305并行特性的知名实现方案？

mbedTLS的Poly1305实现走的是最小可移植路线，优先适配资源受限的嵌入式设备，没做并行、增量更新相关的优化是非常正常的设计取舍，这两个特性在很多面向高性能场景的密码实现里都有成熟应用。

已落地并行优化的知名实现 #

目前主流面向服务器、桌面端的高性能密码库基本都实现了Poly1305的并行计算，最常见的包括：

• OpenSSL 内置的Poly1305实现
• BoringSSL 内置的Poly1305实现
• Linux内核Crypto子系统中的Poly1305实现
• 亚马逊s2n-tls库中的Poly1305实现

并行计算的核心实现思路 #

Poly1305的数学结构天生支持并行，和串行实现的核心差异在于多项式求值的拆分逻辑：

• 标准串行Poly1305的计算本质是在模2^130 - 5的有限域上，对拆分后的16字节消息块a_i计算多项式值：a_1*r^n + a_2*r^(n-1) + ... + a_n*r + s，其中r、s是从认证密钥拆出的两个参数，串行实现必须一块算完再算下一块。
• 并行实现会先根据所用SIMD指令的位宽确定并行粒度：x86平台用AVX2指令集时通常一次处理8个块，ARM平台用NEON指令集时通常一次处理4个块。计算开始前先预计算好对应偏移的r的幂次（r^1到r^N，N为并行块数），之后就可以用SIMD寄存器同时完成N个块的乘加操作，最后把组内的计算结果按对应幂次加权合并，不需要块之间串行等待。
• 如果是Poly1305-AES的组合模式，还可以把AES生成块掩码的操作和Poly1305的块计算做指令级并行，进一步掩盖AES运算的延迟。

增量更新特性的实现思路 #

相比并行优化，增量更新的落地场景更窄，主要用在大文件校验、增量数据同步这类场景，实现逻辑非常直接：

• 计算时预先缓存好两个值：每个消息块对应的中间多项式状态、当前已处理长度对应的r的幂次表。当已知消息某个位置的块发生小幅修改时，不需要从头计算整条消息的MAC，只需要重新计算修改块的贡献值，乘上对应偏移的r幂次后，和原有最终结果做模2^130 -5的加减修正即可，重计算的成本和修改块的数量正相关，和消息总长度无关。
• 通用TLS场景下的消息都是一次性流式传输，不存在收到消息后再修改局部内容重算MAC的需求，所以绝大多数TLS库都不会实现这个特性。

补充说明：官方文档提到的可并行、可增量特性，是Poly1305多项式求值结构自带的原生性质，不是需要特殊补丁实现的额外功能，不同库只是根据自己的目标场景选择是否落地这些优化而已。

内容的提问来源于stack exchange，提问作者arkountos