RISC-V指令集扩展加速后量子密码Kyber算法在嵌入式系统中的应用

1. 项目概述与背景

量子计算的迅猛发展，对当前广泛使用的公钥密码体系（如RSA、ECC）构成了现实且紧迫的威胁。这些经典算法所依赖的数学难题（如大整数分解、离散对数），在量子计算机的Shor算法面前将变得不堪一击。为了应对这一“后量子”时代的挑战，美国国家标准与技术研究院（NIST）主导了后量子密码学（PQC）标准化进程。经过多轮筛选，基于格（Lattice）难题的Crystals-Kyber算法脱颖而出，于2022年7月被选定为标准的密钥封装机制（KEM），并命名为ML-KEM。

Kyber算法的安全性建立在“带误差的学习”（Learning With Errors, LWE）问题的变体——模块化LWE（MLWE）问题之上。简单来说，它涉及在多项式环上进行一系列复杂的运算，包括多项式乘法、数论变换（NTT）、基于中心二项分布（CBD）的采样以及系数压缩。虽然其数学基础坚实，但带来的直接后果是计算开销巨大，尤其是在资源受限的嵌入式设备上，如物联网（IoT）节点、传感器和可穿戴设备。这些设备通常具有有限的处理器性能、内存容量和电池能量，直接运行Kyber软件实现可能导致密钥协商过程耗时过长、能耗过高，从而影响用户体验和系统可行性。

因此，如何在保持高安全等级的同时，让Kyber算法在低功耗、低复杂度的嵌入式系统中高效运行，成为了一个关键的研究与工程问题。硬件加速是解决这一矛盾的经典思路。而在开源、可扩展的RISC-V指令集架构上，通过定制指令集扩展（ISE）来实现细粒度、紧耦合的硬件加速，为这一问题提供了极具吸引力的解决方案。这不仅能利用专用硬件单元的高效性，还能通过共享处理器核心的寄存器文件、内存接口等资源，最大限度地控制面积和功耗的增长。

本文将深入探讨如何通过设计RISC-V指令集扩展，在低端32位Ibex处理器上全面加速Crystals-Kyber算法。我们将不仅分析对AES、SHA-2、Keccak（SHA-3）等对称原语的加速，还会提出一个名为Xkyber的全新扩展，专门用于加速Kyber特有的核心运算。我们的目标是在性能、能耗、代码大小和芯片面积这几个对嵌入式系统至关重要的指标上，取得最佳的平衡。

2. Crystals-Kyber算法核心原理与计算瓶颈

要理解硬件加速的设计点，首先需要拆解Kyber算法的核心步骤与计算负载。Kyber作为一个KEM，主要包含三个函数：密钥生成（KeyGen）、封装（Encapsulation, Enc）和解封装（Decapsulation, Dec）。其安全性源于一个公开的矩阵A和一个由秘密向量s和误差向量e生成的公开向量t，其中t = A * s + e。从公开的 (A, t) 恢复出秘密的 s，被证明是困难的（MLWE问题）。

2.1 核心运算分解

在实际计算中，上述线性代数运算被映射到多项式环R_q = Z_q[X] / (X^n + 1)上，其中q=3329,n=256。这带来了几个核心运算：

1. 多项式算术：尤其是多项式乘法，是Kyber中最耗时的操作。朴素算法的复杂度是O(n²)。Kyber使用数论变换（NTT）将其优化到O(n log n)。NTT可以理解为在有限域上的快速傅里叶变换（FFT），其核心是大量的“蝴蝶”运算，涉及系数的模乘、模加和模减。
2. CBD采样：用于生成秘密向量和误差向量。算法需要从均匀随机比特流中，通过计算两个η比特的和的差值，来采样一个服从中心二项分布的小系数。这是一个位操作密集的过程。
3. 系数压缩：为了减少密文大小，需要将12位的系数压缩到更少的位数（如d=10, 4, 3等）。这涉及乘法、移位和取整操作。
4. 对称原语：算法内部需要调用哈希函数（H, G, KDF）、可扩展输出函数（XOF）和伪随机函数（PRF）来生成随机性和进行密钥派生。Kyber标准定义了两种参数集：
   • Kyber-FIPS202：使用SHA-3（Keccak）家族的哈希和XOF。
   • Kyber-90s：使用SHA-2家族的哈希和AES-256-CTR作为PRF。

2.2 嵌入式系统面临的挑战

在像Ibex这样的32位、顺序、低功耗RISC-V核心上，上述运算会带来显著的开销：

• 性能瓶颈：大量的32位模乘、模约减操作，即使有硬件乘法器，其周期数也很可观。NTT中的蝴蝶运算循环是主要的性能热点。
• 内存访问：多项式系数、NTT旋转因子（twiddle factors）、预计算的T表（对于AES）等需要频繁访问内存，这对功耗和性能都不利。
• 代码体积：实现NTT、CBD采样、Barrett约减等算法的C代码体积较大，占用宝贵的指令存储器（Flash）空间。
• 能量效率：软件实现需要执行成千上万条指令，每条指令的取指、译码、执行都会消耗能量。

我们的硬件加速策略正是针对这些痛点：用专用指令替代复杂的软件循环和位操作，减少指令数和内存访问，从而在提升性能的同时，降低能耗和代码体积。

3. 对称原语的指令集扩展加速

Kyber的性能严重依赖于其内部使用的对称原语。我们首先评估了四种不同的Kyber参数化方案，并为其对称原语设计了相应的ISE加速。

3.1 四种参数化方案对比

我们不仅评估了标准的Kyber-FIPS202和Kyber-90s，还探索了两种新颖的方案，以研究算法级资源共享的潜力：

1. Kyber-FIPS202：使用SHA3-256、SHA3-512和SHAKE-256。通过RISC-V标量密码扩展中的Zbkb（位操作）扩展来加速Keccak排列中的ρ（循环移位）和χ（非线性层）步骤。
2. Kyber-90s：使用SHA-256、SHA-512和AES-256-CTR。通过Zkne（AES）和Zknh（SHA-2）扩展进行加速。aes32esmi指令能单周期完成AES一轮中的S盒查找、列混合和轮密钥加，避免了查表带来的内存访问和潜在的时间侧信道攻击。
3. Kyber-Ascon：使用NIST轻量级密码竞赛的获胜算法Ascon进行哈希和XOF。我们设计了Xascon扩展，专门加速Ascon排列中的线性扩散层，其原理与Zknh类似，通过专用指令高效计算Ascon的σ函数。
4. Kyber-Turbo：使用轮数减半（12轮）的TurboSHAKE替代标准的Keccak（24轮）。同样使用Zbkb扩展加速，旨在探索性能与安全裕度之间的权衡。

3.2 加速效果实测分析

我们在Ibex核心上集成这些ISE，并使用28nm工艺库进行综合与仿真。性能评估结果揭示了几个关键发现：

• 性能王者：Kyber-90s。无论是纯软件实现还是硬件加速后，Kyber-90s都是最快的方案。例如，在Kyber-512的封装操作中，纯软件的Kyber-90s比硬件加速后的Kyber-FIPS202还要快30%。这主要归功于AES算法本身极高的硬件友好性，以及Zkne扩展带来的巨大增益。
• 加速收益来源：对Kyber-90s的剖析显示，AES加速（Zkne）贡献了主要的性能提升（约23%），而SHA-2加速（Zknh）带来的额外增益相对较小（约7%）。这说明在Kyber中，PRF（AES-CTR）的调用频率或计算密度高于哈希函数。
• 新方案的潜力：Kyber-Ascon在纯软件下与Kyber-FIPS202性能相当，但在启用Xascon硬件加速后，其性能提升幅度（29%）是最大的，超过了其他方案。这表明Ascon算法本身从硬件加速中获益更多。Kyber-Turbo则凭借更少的轮数，性能显著优于Kyber-FIPS202。
• 内存占用考量：从构建完整密码系统的角度看（包含Kyber、认证加密和哈希），Kyber-Ascon方案的总内存占用最小（约13KB），因为它可以复用Ascon算法同时用于认证加密和Kyber内部的哈希/XOF。而Kyber-90s由于需要存储AES的T表和SHA-2的轮常数，内存占用最大（约17KB），但硬件加速后能减少14%的占用。

实操心得：算法选择与系统协同在选择Kyber的参数化方案时，不能只看Kyber本身的性能。必须从整个系统层面考虑。如果你的嵌入式设备已经因为其他原因（如安全存储、通信加密）需要实现AES和SHA-2，那么选择Kyber-90s并启用Zkne/Zknh扩展是最经济的选择，实现了硬件逻辑的复用。反之，如果设备对内存极其敏感，且需要轻量级认证加密，那么Kyber-Ascon方案提供了更优的整合度。硬件加速不仅提升了速度，还能通过消除查表需求来减少内存访问和代码体积，这是一举多得。

4. 专用Xkyber指令集扩展的设计与实现

尽管加速对称原语带来了显著收益，但Kyber特有的多项式运算、采样和压缩操作仍然是主要开销。为此，我们提出了Xkyber扩展，这是一组专门为Kyber算法定制的RISC-V指令。

4.1 设计哲学与指令集定义

Xkyber的设计严格遵循RISC-V的设计哲学：简单、模块化。所有指令都使用标准的R型或I型格式，最多两个源寄存器和一个目的寄存器，避免引入特殊的架构状态或复杂的寄存器文件。

我们充分利用了Kyber系数是12位整数这一特点。在32位处理器中，一个寄存器可以容纳两个系数。这启发了我们采用一种轻量级的单指令多数据（SIMD）方式。我们设计了6条新指令：

4.2 关键模块的硬件实现与资源共享

Xkyber扩展被紧密集成到Ibex核心的执行单元中，与原有的整数ALU、乘法器等部件最大限度地共享资源，这是控制面积开销的关键。

1. 模加/模减（kyberadd/kybersub）： 这两个指令的实现非常高效。加法/减法直接使用处理器原有的32位ALU完成。为了防止低16位系数向高16位进位（或借位），我们在ALU的输入输出端添加了简单的掩码逻辑。模运算（结果保持在0到q-1之间）通过一个条件加/减q的电路实现，该电路也被kybermul和kybercbd*指令共享。

2. 模乘与Barrett约减（kybermul）： 这是最复杂的指令。12位乘12位的结果最大是144位，远大于q。我们采用Barrett约减算法来高效计算模乘，而无需昂贵的除法器。算法需要预计算常数m = floor(2^k / q)，我们选择k=24，则m=5039。kybermul被分解为4个时钟周期执行，充分复用Ibex原有的3周期乘法器流水线：

• 周期1：在16位乘法器中计算a * b，结果存入临时寄存器temp0。
• 周期2：计算temp0 * m。这里我们设计了一个常数乘法器。因为m=5039 = 2^12 + 2^10 - 2^6 - 2^4 - 1，所以乘法可以通过一系列移位和加减法实现。我们复用ALU计算(x<<12)+(x<<10)，并新增3个小加法器计算-(x<<6)-(x<<4)-x，最后合并。结果右移k位后存入temp1。
• 周期3：在16位乘法器中计算temp1 * q，结果写回temp1。
• 周期4：在ALU中计算temp0 - temp1，然后通过共享的“条件减q”逻辑确保结果在[0, q-1)范围内。

3. 系数压缩（kybercompress）： 压缩公式为round((2^d / q) * x) mod 2^d。我们发现2^d / q与Barrett约减中的2^k / q形式相似。因此，我们巧妙地复用了kybermul的常数乘法器来计算整数部分，同时用通用乘法器计算小数部分，最后合并、移位、取整并模2^d。这避免了为压缩单独设计一套乘法逻辑。

4. CBD采样（kybercbd2/kybercbd3）： CBD采样需要将2η个随机比特分为两组求和，然后求差。我们为η=2和η=3分别设计了一条指令。硬件上使用并行的半加器（η=2）或全加器（η=3）来同时计算两个系数的A和B值，然后求差，并通过共享的“条件加q”电路将结果从[-η, η]映射到[0, q-1]的正确范围内。一条指令即可产生两个采样好的系数，并打包到一个32位寄存器中，极大地提升了采样效率。

4.3 面积开销与集成

通过上述精细的资源共享设计，Xkyber扩展在28nm工艺下仅增加了约4.3K等效门的面积，相当于基线Ibex处理器（无任何扩展）面积的13%。这是一个非常可观的代价，尤其是考虑到它带来的性能收益。扩展与Zkne、Zknh等单元并列，通过处理器解码逻辑统一调度。

注意事项：紧耦合加速的优势与局限与采用独立协处理器（Co-processor）或内存映射加速器的方式相比，这种紧耦合的ISE方式具有显著优势：1)零拷贝数据交换：操作数通过寄存器文件直接传递，避免了通过内存或总线进行昂贵的数据搬运；2)低延迟：指令在流水线中执行，与常规指令无异；3)简化编程模型：程序员使用标准的加载/存储指令和新的运算指令即可，无需管理额外的内存空间或DMA。其局限在于灵活性，这些指令是专门为Kyber（以及结构相似的Dilithium）定制的，难以用于其他类型的后量子算法。

5. 综合性能评估与权衡分析

我们将所有扩展（Zbkb/Zkne/Zknh/Xascon 和 Xkyber）集成到Ibex系统中，对Kyber的三个安全等级（512/768/1024）和四个参数化方案进行了全面的评估。

5.1 性能与能耗提升

实验数据清晰地展示了硬件加速的叠加效应：

• 对称原语加速：对于Kyber-90s，使用Zkne和Zknh扩展加速AES和SHA-2，能使Kyber-512的封装操作性能提升42%，能耗降低37%。
• Xkyber扩展加速：在已加速对称原语的基础上，进一步启用Xkyber扩展，可以将Kyber-512封装的性能再提升约5个百分点，总提升达到47%，能耗总降低达到41%。
• 热点消除：性能剖析显示，Xkyber对核心运算的加速效果极为显著。例如，多项式点乘加速了67%，CBD3采样加速了72%，系数压缩加速了78%。这些原本是软件实现中最耗时的循环，现在被单条或少数几条指令替代。

5.2 内存占用减少

Xkyber扩展不仅加速了计算，还减少了代码体积。因为许多用于模约减、条件判断的辅助函数和内联汇编循环不再需要。实测表明，Kyber-512（FIPS202参数）的核心算法代码大小从5,090字节减少到4,314字节，减少了15%。这对于Flash空间紧张的微控制器而言意义重大。

5.3 面积、性能与能效的权衡

我们引入“每单位面积性能增益”作为衡量ISE设计效率的指标：

• 最具性价比的加速：在Kyber-90s中，仅使用Zkne（AES加速）扩展，就能为Kyber-512封装带来27%的性能提升，而面积成本仅增加约4%。这是因为AES操作本身计算密集，且Zkne指令将其从多次内存访问和查表操作转化为单周期计算，收益极高。
• Xkyber的收益：Xkyber扩展以13%的面积成本，带来了与对称原语加速（Zkne+Zknh，成本15%）相近的额外性能提升。这表明，针对算法核心数学运算进行定制化加速，其效率与加速成熟的标准对称密码原语是相当的。
• 参数化方案选择指南：
  • 追求极致性能/能效：选择Kyber-90s，并启用Zkne和Xkyber扩展。这是综合表现最好的方案。
  • 追求最小内存占用：选择Kyber-Ascon，并启用Xascon扩展。特别适合需要整合轻量级认证加密和哈希的系统。
  • 平衡考虑：如果系统已支持SHA-3且不想引入AES，Kyber-Turbo是一个不错的折中，性能优于FIPS202，安全裕度经评估也可接受。

5.4 与现有工作的对比

我们的方案与文献中许多采用独立协处理器或复杂向量单元的方案有本质区别。那些方案虽然可能获得更高的绝对性能，但其面积开销往往是Ibex整个核心的数倍甚至数十倍（例如，达到106K等效门），完全不适合我们目标中的低复杂度嵌入式场景。我们的工作证明，通过精心设计的、紧耦合的标量指令集扩展，能够以微小的面积代价（~4-15%），在低功耗处理器上获得接近50%的整体性能提升和能耗降低，同时减少代码体积，这是一种更符合嵌入式系统约束的实用化路径。

6. 实现细节、问题排查与优化建议

在实际将ISE集成到处理器并移植Kyber软件栈的过程中，我们遇到并解决了一系列工程挑战。

6.1 工具链与软件生态适配

最大的挑战来自于工具链的支持。标准的RISC-V GCC工具链无法识别我们自定义的Xkyber和Xascon指令。

• 解决方案：我们需要修改GNU Binutils（汇编器和链接器）的源代码，添加对新指令编码（opcode）和汇编助记符的定义。这涉及修改opcodes/riscv-opc.c文件添加指令，以及gas/config/tc-riscv.c文件处理汇编语法。随后，需要重新编译整个工具链。
• 内联汇编的使用：在C代码中，我们通过__asm__ volatile内联汇编来调用这些新指令。为了确保编译器不会打乱我们的指令顺序或使用错误的寄存器，需要仔细编写约束条件。例如，对于kybermul指令：

  static inline uint16_t kyber_mul(uint16_t a, uint16_t b) { uint32_t result; __asm__ volatile (".word 0x0605850b" // 假设的kybermul编码 : "=r"(result) : "r"((uint32_t)a), "r"((uint32_t)b) ); return (uint16_t)result; }

  注意：这里的.word 0x...是手动编码的指令机器码，在实际开发中应使用定义好的宏或内建函数。

6.2 确保常数时间执行

密码学实现必须防止时间侧信道攻击。软件实现中的条件分支、基于数据的数组索引都可能导致执行时间差异，从而泄露秘密信息。

• 问题：原始的Kyber参考实现包含一些条件分支。我们的硬件指令实现必须是常数时间的。
• 解决方案：
  1. 硬件层面：所有Xkyber指令的数据通路设计为无论操作数值为何，其执行周期数都是固定的（例如kybermul固定4周期）。条件加/减q的操作使用无分支的位掩码和加法器实现。
  2. 软件层面：我们修改了Kyber代码，用位操作替代了所有与秘密数据相关的分支。同时，确保内存访问模式不依赖于秘密数据。Ibex处理器还提供了“数据无关时序”模式，我们启用了此功能以进一步消除微架构层面的时序差异。

6.3 性能剖析与瓶颈定位

为了精确找到热点，我们扩展了Ibex的性能计数器，并开发了一个剖析工具。

• 方法：该工具在RTL仿真时监控程序计数器（PC），能够以C函数为粒度，统计每个函数执行的时钟周期数、指令数、以及不同粒度的内存访问次数。
• 发现：在未加速前，NTT/INTT变换和CBD采样函数消耗了超过60%的运行时。这直接印证了设计kybermul、kyberadd、kybercbd*指令的正确性。剖析工具也帮助我们验证了加速后这些热点函数的周期数确实大幅下降。

6.4 综合与功耗评估流程

获得准确的面积和功耗数据需要严谨的流程：

1. 综合：使用Cadence Genus工具，在SS（慢速工艺角）、0.75V、125°C的保守条件下进行综合，以获得可靠的最大频率和面积报告。
2. 功耗分析：使用综合后的网表，在典型工艺角、0.9V、25°C条件下，通过Cadence Joules工具进行基于仿真活动因子的功耗分析。我们使用剖析工具确定的函数执行时间窗口，来计算该窗口内的平均功耗和总能耗。
3. 内存能耗建模：使用CACTI 7工具对16KB双端口SRAM进行建模，获取每比特读/写的能量成本。再结合性能计数器统计出的内存访问次数，计算出总的内存访问能耗，与核心能耗相加得到系统总能耗。

6.5 常见问题排查表

7. 总结与展望

通过这项探索，我们验证了在低功耗RISC-V嵌入式系统中，通过指令集扩展来硬件加速后量子密码算法Crystals-Kyber的可行性与高效性。我们的工作表明：

1. Kyber-90s是目前嵌入式场景下的优选方案，其性能优势在硬件加速后更为明显。而Kyber-Ascon在内存整合方面独具优势。
2. 细粒度、紧耦合的ISE设计是有效的。我们提出的Xkyber扩展，以仅13%的面积开销，换取了与加速对称原语相当的额外性能提升（~5-10%），并减少了15%的代码体积。
3. 系统级协同设计至关重要。选择Kyber参数化方案时，应综合考虑系统中已存在或需要的其他密码组件（如AES、SHA-2、Ascon），以实现算法和硬件逻辑的最大化复用，优化整体的面积、性能和内存开销。

未来工作可以沿着以下几个方向深入：

• 探索更多对称原语：例如，基于AES构建的哈希函数（如Haraka）或基于SPN结构的其他轻量级原语，它们可能从Zkne扩展中获益，从而创造出性能更高或更紧凑的Kyber变体。
• 扩展至数字签名：NIST标准化的后量子数字签名算法Dilithium与Kyber同属模格密码家族，共享多项式运算。Xkyber中的模加、模减、模乘指令可以复用。但需注意Dilithium系数位宽为23位，无法使用双系数SIMD，且其Barrett约减参数不同，需要调整硬件设计。另一种思路是研究基于KEM的身份认证协议，完全复用Kyber硬件，避免实现额外的签名算法。
• 更高层次的集成与优化：探索将Kyber的完整操作（如整个NTT）封装为更复杂的指令或微码序列的可能性。同时，研究编译器自动识别Kyber算法模式并生成优化代码（如自动使用Xkyber指令）的可能性。

这项工作为将后量子密码学实用化地部署到亿万物联网设备中提供了具体的技术路径和设计参考。随着RISC-V生态的日益繁荣和PQC标准的最终落地，这种软硬件协同设计的思路将发挥越来越重要的作用。