复用RSA/ECC硬件加速后量子密码：克罗内克替代实战指南

1. 项目概述与核心价值

如果你正在为嵌入式设备或移动平台的后量子密码（PQC）迁移寻找一条既经济又高效的路径，那么“复用现有硬件”绝对是一个绕不开的关键词。在格基密码（Lattice-based Cryptography）成为NIST PQC标准有力候选的今天，其核心运算——多项式乘法——的计算开销成为了性能瓶颈。传统思路是设计专用的PQC硬件加速器或依赖新的CPU指令集，但这意味着高昂的研发成本和漫长的部署周期。

一个更务实的策略是：榨干现有RSA/ECC密码协处理器的每一分潜力。这些硬件模块早已广泛部署在从智能卡到手机SoC的无数设备中，专为大整数模乘优化。我们的目标，就是通过巧妙的数学变换，将格基密码中的多项式乘法“翻译”成这些协处理器擅长的大整数运算，从而实现近乎“零新增硬件成本”的性能飞跃。这不仅仅是技术上的优化，更是一种极具商业和工程价值的平滑过渡方案。

本文将以我在三星Exynos2100 SSP（Smart Secure Platform）平台上的实际工程实践为基础，深入剖析如何利用RSA/ECC协处理器加速NIST PQC第三轮候选算法（如CRYSTALS-Kyber和Saber）中的多项式乘法。我会带你从最底层的数学原理（克罗内克替代）出发，一路拆解到具体的代码实现、性能调优和踩坑经验。无论你是嵌入式安全工程师、密码学库开发者，还是对PQC硬件加速感兴趣的研究者，这篇文章都将提供一份从理论到落地的完整参考。

2. 核心原理：从多项式到整数的桥梁

2.1 为什么是多项式乘法？

在基于LWE（Learning With Errors）或MLWE（Module-LWE）的PQC算法（如Kyber, Saber）中，核心操作是在多项式环 R_q = Z_q[x]/(x^n + 1) 上的运算，其中 n 通常是256，q 是一个模数。密钥生成、封装和解封过程中，充斥着形如c = A * s + e的运算，这里的 A、s、e 都是多项式或多项式矩阵/向量。一次多项式乘法的复杂度是 O(n²)，在资源受限的嵌入式环境中，纯软件实现的开销是难以承受的。

2.2 克罗内克替代（Kronecker Substitution, KS）的精髓

KS的核心思想惊人的简洁：通过选取一个足够大的基数 B，将一个多项式“编码”成一个巨大的整数。

假设有两个多项式：f(x) = 12x + 34g(x) = 56x + 78

它们的乘积是h(x) = 672x² + 2840x + 2652。

现在，我们选取 B = 10⁴。进行如下变换（称为“Clumping”或求值）：φ(f) = f(B) = 12 * 10⁴ + 34 = 120034φ(g) = g(B) = 56 * 10⁴ + 78 = 560078

神奇的事情发生了：多项式乘法被映射为了整数乘法！φ(f) * φ(g) = 120034 * 560078 = 67228402652

这个结果67228402652正是h(B) = h(10⁴)。我们只需要将这个整数按基数 B=10⁴ 进行“解码”（称为“Lifting”），就能恢复出多项式的系数：67228402652-> 提取出672,2840,2652->h(x) = 672x² + 2840x + 2652。

关键细节：基数 B 的选择B 必须大于任何可能出现的中间系数绝对值的两倍。在上例中，系数最大可能值约为 12*56=672，其两倍为1344，而 B=10⁴=10000 > 1344，保证了在整数域运算时不会发生系数间的“进位污染”，使得从整数结果中能唯一、正确地提取出每个系数。在实际的PQC算法中，B 通常选择为 2 的幂次（如 2^13, 2^32），以便于计算机通过移位操作高效实现“编码”和“解码”。

2.3 当整数太大时：KS的变体与多项式分割

现实很骨感。以Saber算法为例，其多项式次数 n=256，系数位数约为13比特。简单应用KS，编码后的整数长度将达到 256 * 13 = 3328 比特。而市面上常见的RSA协处理器通常最大支持2048或4096位模乘。3328比特虽然能放入4096位协处理器，但运算效率并非最优，且对于更大参数或更小协处理器就不适用了。

因此，我们需要在应用KS之前，先将大多项式“分割”成更小的片段。这引出了两大技术路线：

1. 分割与乘法（Division and Multiplication, DM）思路直接：利用Schönhage的恒等式h(x) = x * h₀(x²) + h₁(x²)，将一个 n 次多项式乘法，转化为两个 n/2 次多项式乘法。这本质上是一种分治策略。结合Karatsuba或Toom-Cook算法，可以进一步减少乘法次数。例如，Karatsuba能将2个 n/2 次多项式乘法所需的4次乘法，减少到3次，代价是增加一些加/减法。

2. 克罗内克+（Kronecker+）这是KS2思想的推广。KS2利用正负点求值来降低整数规模。对于f(x) = f₀(x²) + x * f₁(x²)，我们不仅计算f(B)，还计算f(-B)。通过解一个线性方程组，可以从f(B)和f(-B)中恢复出f₀(B²)和f₁(B²)。这样，我们需要处理的整数规模就从B^n降到了B^(n/2)。Kronecker+将这种思想推广到了 t 路分割，通过在一系列复数单位根处求值，实现更大幅度的规模缩减。

实操心得：DM与Kronecker+的选择两者的核心权衡在于“预计算/后处理开销”与“核心乘法次数”。

• DM（结合Karatsuba）：思路直观，预计算（多项式重排）和后处理（系数重组）相对简单，主要开销在多次的协处理器调用（乘法）上。在协处理器调用开销（如数据传输、启动延迟）不高的场景下表现良好。
• Kronecker+：通过更精巧的数学变换，能用更少的乘法次数（理论上最优）完成计算。但代价是预计算（在不同复数根处求值）和后处理（解插值）更为复杂，涉及大量的模加、模减和移位操作。如果你的硬件平台除了模乘单元，还有强大的大整数加法和桶式移位器（Barrel Shifter）硬件支持，那么Kronecker+的潜力巨大。否则，这些复杂的辅助操作在软件中实现可能会抵消掉乘法次数减少带来的收益。我在Exynos2100 SSP上的实测也印证了这一点。

3. 硬件适配与工程实现要点

3.1 理解你的RSA/ECC协处理器

不是所有叫“协处理器”的硬件都提供同样的能力。在动手前，必须像侦探一样摸清家底：

1. 支持的最大整数位宽：这是硬约束。是2048位？4096位？还是可配置？这直接决定了你能否以及如何分割多项式。
2. 支持的核心操作：
   • 模乘（Modular Multiplication）：几乎所有协处理器都必备。这是我们的主力武器。
   • 模加/模减（Modular Add/Sub）：很多协处理器也会提供，能显著加速Kronecker+等算法的辅助步骤。
   • 桶式移位（Barrel Shifter）：较少见，但对处理KS中涉及的大量2的幂次乘除（即移位）至关重要。
3. 运算模式：最常见的是蒙哥马利模乘（Montgomery Multiplication）。你需要理解其原理：Mont(A, B) = A * B * R⁻¹ mod N。这意味着输入输出数字都处于“蒙哥马利域”。在使用KS时，你必须管理好域转换：
   • 在调用模乘前，将整数a转换到蒙哥马利域：a' = a * R² mod N。
   • 进行模乘：c' = Mont(a', b)。
   • 得到结果后，可能需要转换回普通域：c = Mont(c', 1)。

   踩坑记录：蒙哥马利常数 R协处理器定义的蒙哥马利常数 R 通常是 2^m（m 为模数位宽对齐值）。在KS中，我们选择的基数 B 也常是 2^l。如果l能整除m，那么B^k的幂次运算在蒙哥马利域中可能简化为数组下标的循环移位，能带来巨大的性能提升。在选型时，这是一个值得仔细考量的优化点。

3.2 Exynos2100 SSP平台实战剖析

我使用的Exynos2100 SSP是一个典型的商业移动SoC安全子系统。其RSA/ECC协处理器特性如下：

• 最大支持4096位模乘（蒙哥马利算法）。
• 提供最多512位的模加/模减硬件（但主要用于ECC，对大整数操作帮助有限，因数据搬移和控制开销大）。
• 没有专用的桶式移位器硬件。

基于此硬件特性，我排除了严重依赖移位操作的Shift&Add算法，也因小系数乘法无优势而排除了KSV。主攻方向定为DM和Kronecker+。

实现步骤分解：

以DM结合Karatsuba（2路分割）为例，一次多项式乘法的硬件加速流程如下：

1. 多项式分割与重排（Pre-processing）：

   • 输入两个256次多项式f(x),g(x)。
   • 应用Schönhage变换：f(x) = f₀(x²) + x * f₁(x²)， 将f,g各自拆分成两个128次多项式f₀, f₁和g₀, g₁。这一步主要是内存操作，无复杂计算。

2. 克罗内克编码（Evaluation / SNORT）：

   • 为每个128次多项式选择基数B = 2^32。
   • 计算F0 = f₀(B),F1 = f₁(B),G0 = g₀(B),G1 = g₁(B)。由于B是2的幂，此步骤在内存中就是简单地将系数按32位对齐放置，几乎没有计算成本。

3. 核心模乘运算（Pointwise Multiplication）：

   • 这是调用硬件协处理器的核心环节。需要计算三个大整数乘法（Karatsuba）：
     • M0 = Mont(F0, G0)
     • M1 = Mont(F1, G1)
     • M2 = Mont(F0+F1, G0+G1)（注意：F0+F1等加法需在调用模乘前完成，可能需软件实现或调用硬件加法）
   • 每次调用前，需确保操作数已转换到蒙哥马利域。

4. 组合与解码（Post-processing / SNEEZE）：

   • 利用Karatsuba公式组合结果：(F0+F1)(G0+G1) - M0 - M1得到中间项。
   • 将M0,M1, 中间项这三个大整数，根据它们代表的B^2,B,1的权重，进行加权和组合，得到最终的大整数H。
   • 系数提取与符号处理：这是最易出错的一步。从H中按基数B=2^32提取出512个系数（两个256次多项式乘积的最高次数为511）。由于多项式系数可正可负，而整数H的每一位都是非负的，需要一套“借位”算法来恢复系数的正确符号。例如，如果提取出的一个“块”的值大于B/2，则说明它实际代表一个负数，需要向高位“借位”。
   • 模约减（针对Kyber）：对于Saber，由于模数是2的幂，提取后直接截断即可。对于Kyber，需要对每个系数进行模q=3329的约减。

3.3 性能数据与深度分析

在Exynos2100 SSP上，我实测了多种方法。下表展示了核心多项式乘法（单次）的时钟周期数对比：

关键发现：

1. 硬件模乘并非全部：即使在最理想的Karatsuba方案中，纯粹的模乘操作也只占不到70%的时间。数据搬运、域转换、系数提取等“外围”操作开销巨大。这提醒我们，优化不能只盯着乘法器。
2. Karatsuba (2-way) 胜出：在仅有模乘硬件的平台上，Karatsuba在减少乘法次数和保持较低预/后处理开销之间取得了最佳平衡。4路分割虽然每次乘法规模更小，但乘法次数变为9次，总时间反而增加。
3. Kronecker+的潜力与瓶颈：它的模乘占比最低，理论最优。但在Exynos2100上，其复杂的移位和加法在软件中实现，成为了主要瓶颈。这强烈暗示：如果协处理器集成桶式移位器和宽位加法器，Kronecker+的性能很可能反超。

4. 在完整PQC算法中的集成与优化

4.1 算法适配性分析

不是所有NIST PQC算法都同样适合这套“借壳生蛋”的方案。

• Saber (Winner)：天然契合。Saber使用纯粹的多项式乘法，不涉及数论变换（NTT）。我们可以直接将矩阵-向量乘法中的每一个多项式乘法替换为KS加速版本。实测表明，在Exynos2100上，将Saber的参考实现（使用Toom-Cook 4软件实现）替换为KS+Karatsuba硬件加速后，整体性能提升接近3倍。

• CRYSTALS-Kyber (Challenging)：面临挑战。Kyber为了极致性能，其官方提交算法（NTTD版本）将公钥矩阵A直接采样并存储在NTT域中。这意味着，在加解密过程中，我们拿到手的多项式已经是NTT域表示。要使用KS，就必须先做逆NTT将其变回普通多项式域，用KS算完乘法后，再做NTT变回去。这两次域转换的软件开销，足以抵消甚至超过KS硬件加速带来的收益。我们的测试显示，对Kyber NTTD版本使用KS加速，整体性能反而下降。

  变通方案：Kyber还有一个更基础的算法描述（NTTM版本），其中矩阵A是在普通域生成的。虽然整体效率不如NTTD版本，但在这个版本上应用KS可以获得正向加速。这给了我们一个启示：如果未来有基于Kyber的协议或标准允许使用非NTT域表示的密钥，那么KS加速将大有可为。

• 其他算法：

  • NTRU：基于多项式环，未强制使用NTT，是KS加速的潜在优秀候选。
  • Dilithium（签名）：情况与Kyber类似，严重依赖NTT域优化，直接应用KS收益有限。
  • Falcon, Rainbow, Classic McEliece：其数学基础（浮点运算、多变量方程、纠错码）与整数多项式乘法相去甚远，难以直接利用RSA/ECC协处理器。

4.2 系统级集成注意事项

1. 侧信道攻击防护：硬件协处理器通常是防侧信道的重点区域。当你将PQC运算映射到其上时，必须确保整个计算流程（包括软件预处理部分）不会引入新的时序、功耗或电磁旁路漏洞。例如，系数提取和符号处理算法必须是常数时间的。
2. 内存管理：KS过程中会产生数倍于原多项式的中间大整数。在内存紧张的嵌入式环境中（如智能卡），需要精心设计缓冲区复用策略，避免动态内存分配。
3. 与原有密码栈的共存：协处理器可能原本用于RSA签名、ECDH密钥交换等。需要设计良好的调度机制，避免PQC运算和传统密码运算的资源冲突。
4. 编译器优化与手工汇编：我们的测试使用-O0编译选项以保护防侧信道代码，但这牺牲了性能。在安全允许的前提下，对性能关键路径（如大整数加法和移位）编写精心优化的汇编代码，能带来显著提升。我们的汇编优化版本比C版本（-O0）快数倍。

5. 不同硬件配置下的策略选择与模拟

你的硬件配置决定了最优策略。我通过模拟不同硬件组合，得到了以下决策指南：

模拟数据启示：在一个假设拥有“模乘+加法+移位”全功能硬件的平台上，Kronecker+ (2-way) 模拟运行Saber，其性能预计可达纯软件Toom-Cook 4实现的4倍以上。这清晰地展示了专用硬件单元对算法选择的决定性影响。

6. 总结与展望

利用RSA/ECC协处理器加速后量子密码，是一条被证实可行的“旧瓶装新酒”之路。它最大的价值在于利用现有、成熟的硬件基础设施，以极低的边际成本为PQC迁移提供可观的性能加速，特别适合对成本敏感、换代周期长的嵌入式与物联网设备。

从我的实践经验来看，成功的关键在于深度协同：

1. 算法与硬件的协同：理解Saber比Kyber更友好，理解Karatsuba与Kronecker+对不同硬件资源的依赖。
2. 数学与工程的协同：将优雅的克罗内克替代数学，转化为对蒙哥马利域、内存布局、常数时间操作等工程细节的精确把控。
3. 软件与硬件的协同：精心设计数据通路，减少硬件调用开销，用汇编优化关键软件路径。

这项工作远未结束。未来的探索方向包括：

• 针对更多样的协处理器架构（如不同位宽、是否支持连续乘加等）进行更精细的算法调优。
• 探索将KS技术应用于更多类型的PQC算法，如基于NTRU的方案。
• 研究如何将此类加速引擎无缝集成到TLS、物联网协议栈等实际安全协议中，形成完整的后量子安全解决方案。

最后一点个人体会：在嵌入式密码工程中，绝对的性能数字固然重要，但可部署性、成本效益和安全性往往是更关键的决策因素。这套基于现有硬件的加速方案，正是在这些约束下找到的一个精巧的平衡点。它可能不是终极性能的答案，但绝对是当前从实验室走向大规模应用过程中，最务实、最有力的工具之一。