1. 项目概述为什么我们需要一个“瘦身”的NTT如果你最近在关注后量子密码PQC的硬件实现尤其是围绕NIST标准化的ML-KEM也就是之前的CRYSTALS-Kyber方案那么“数论变换”NTT这个词一定不会陌生。简单来说NTT是格基密码中进行多项式乘法的核心加速器其地位堪比深度学习里的矩阵乘法。没有高效的NTTML-KEM的密钥封装和解封装速度将大打折扣在物联网终端、边缘设备这类对功耗和面积极其敏感的场景里这几乎是不可接受的。传统的硬件优化思路无论是学术论文还是工程实践大多把火力集中在两个“显眼包”上模乘单元和模约减单元。这很好理解因为它们确实是计算最密集、最耗资源的部分。于是我们看到了各种精巧的DSP映射算法、基于常数的快速约减技巧目标都是把那几个纳秒的延迟和几百个LUT的资源再压榨一点。然而在反复折腾这些计算单元之后大家发现了一个尴尬的事实整个NTT加速器的性能瓶颈有时候并不在计算本身而在“喂数据”这个环节。这就是地址生成器——一个负责告诉内存“下一个该读/写哪个系数”的调度中心。在资源受限的FPGA上一个低效的地址生成器可能意味着巨大的查找表LUT开销、复杂的控制逻辑以及由此带来的高功耗。它就像城市交通中的红绿灯控制系统计算单元是性能强悍的跑车但如果调度系统混乱拥堵跑车也只能干等着。我们这次要聊的设计正是从这个被忽视的“交通调度”入手提出了一套极其轻量化的地址生成方案并围绕它构建了一个完整的、无需DSP和BRAM的NTT/INTT逆变换硬件架构。最终在Virtex-7上只用147个Slices和557个LUT就实现了完整功能动态功耗低至15mW相比之前的一些设计面积减少了近90%。这不仅仅是数字游戏它意味着我们能把一个完整的后量子密码协处理器塞进那些原本被认为不可能的小型FPGA甚至未来ASIC中。2. 核心思路拆解从“算得快”到“拿得准、花得少”这个项目的核心设计哲学可以概括为在保证必要吞吐量的前提下极致追求面积和功耗的优化尤其针对地址生成和数据通路这两个传统高开销模块进行重构。这背后是对应用场景的深刻理解对于大量电池供电、计算能力有限的物联网节点它们不需要追求极致的单次运算速度比如达到几百MHz而是更需要一个“够用且省电”的硬件引擎确保在完成安全通信的同时不影响设备整体的续航和成本。2.1 为什么地址生成器成了关键在经典的Cooley-Tukey或Gentleman-Sande蝶形算法中数据访问模式是“位反转”的。对于256点的NTTML-KEM的参数这意味着在7个阶段stage、每个阶段128步step的计算中每一对参与蝶形运算的系数地址以及用到的旋转因子twiddle factor地址都不是顺序递增的。传统的实现方法有两种预计算查表法事先把所有阶段的地址对和旋转因子地址算好存在ROM或BRAM里。这种方法简单直接但需要存储7 stages * 128 steps * (地址宽度)的数据对于小FPGA来说这块存储开销不小而且访问ROM本身也有功耗。实时计算法通过组合逻辑实时计算地址。这通常涉及位宽操作、条件判断和乘法/除法逻辑路径可能较长影响时序并且消耗的LUT资源也可能很可观。本项目提出的方法属于第二种但做了极度简化。它洞察到NTT地址生成的内在规律地址本质上是阶段索引stage和步进索引step的特定比特位拼接和反转。因此设计了一个基于10位计数器低7位表示step高3位表示stage的轻量级电路辅以简单的XOR异或逻辑来在INTT时实现比特反转再通过多路选择器Mux输出最终的三个地址操作数A、B和旋转因子。整个模块没有任何复杂的运算单元几乎就是计数器、线网和Mux的组合从而将资源占用压到最低。注意这里有一个非常关键的取舍。这种简化地址生成器通常与“多周期蝶形运算”架构搭配。也就是说一个蝶形运算可能需要4个时钟周期来完成。对于追求单周期吞吐的高性能设计这种简单的地址生成器可能无法满足每个周期都输出新地址的需求。但对于目标在“面积-功耗-性能”平衡点的设计用稍长的延迟换取巨大的面积和功耗节省是完全合理的。2.2 统一的蝶形运算单元少即是多另一个设计重点是统一的蝶形运算单元。NTT和其逆运算INTT的数学公式很相似NTT (Cooley-Tukey):a_out (a_in b_in * w) mod q,b_out (a_in - b_in * w) mod qINTT (Gentleman-Sande):a_out (a_in b_in) * w mod q,b_out (a_in - b_in) * w mod q可以看到核心操作都是模加、模减和模乘只是顺序不同。很多设计会为NTT和INTT分别实现两套硬件或者用一套硬件但需要复杂的控制逻辑进行重配置。本项目采用了一种更巧妙的方法硬件完全共享通过调度Schedule区分模式。具体来说设计一个支持模加、模减、模乘的算术逻辑单元ALU然后通过一个精确定义的4周期时序来组织这些操作。在NTT模式下周期1取数周期2做乘法周期3做加减法并写回第一个结果周期4写回第二个结果。在INTT模式下周期1取数并做加减法周期2做乘法周期3取数并做加法写回周期4写回乘法结果。这样同一套硬件电路仅仅通过控制信号切换操作顺序就服务了两种运算模式彻底避免了硬件冗余。2.3 告别DSP和BRAM极致的LUT化设计为了达到极致的轻量化和可移植性本设计坚定地摒弃了FPGA上的专用硬件资源DSP数字信号处理器和BRAM块存储器。为什么不用DSPDSP是FPGA上做乘法的利器但对于模乘后紧接着模约减的操作DSP的固定流水线有时并不高效且会占用固定的、有限的芯片资源。本设计采用基于LUT的乘法器虽然频率可能更低但资源使用更灵活且不依赖于特定FPGA型号的DSP数量可移植性更强。为什么不用BRAMBRAM是大的块存储适合存放大数据。但NTT中我们只需要存储256个系数12-bit和128个旋转因子总容量很小。使用BRAM会造成存储资源的浪费一个BRAM单元可能只用了一小部分且BRAM的功耗通常高于分布式RAM用LUT搭建的小存储器。本设计采用分布式LUT-RAM来存储所有数据它将存储单元打散分布在FPGA的逻辑单元中既能满足容量需求又便于布局布线靠近计算单元减少连线延迟和功耗。这种“全LUT”的设计理念使得整个NTT核心就像一个纯粹由逻辑资源构成的“软核”可以轻松适配从高端到低端的各种FPGA平台甚至为后续的ASIC流片铺平了道路。3. 架构细节与实现要点3.1 轻量级地址生成器的实现剖析地址生成器是整个设计的“智慧枢纽”。它的输入很简单一个启动信号Start一个模式信号NTT/INTT。输出是三个9位地址Addr_A, Addr_B, Addr_TW。核心机制10位全局计数器这是状态机的心脏。counter[9:7]的3位表示当前阶段0-6counter[6:0]的7位表示当前阶段内的步进0-127。计数器在每个时钟周期递增遍历所有7*128896个状态。模式自适应在INTT模式下需要对阶段索引进行比特反转。这里没有使用一个完整的反转电路而是巧妙地利用了XOR运算。当模式为INTT时将counter[9:7]与7二进制111进行异或再减1即可等效实现所需的比特反转效果。这比通用的桶形移位器或查找表节省了大量资源。地址拼接逻辑根据当前阶段i和步进j按照特定规则拼接出地址。阶段0地址规则最简单A和B地址仅是步进索引j与一个固定位的拼接旋转因子地址固定。阶段1-6地址是j的高(7-i)位、一个固定位、j的低(6-i)位的拼接。旋转因子地址则由j的高两位和一个左移值决定。 所有这些规则都通过硬连线的位选择和拼接操作完成无需任何算术运算。优势资源极简主要就是一个计数器、几个XOR门和多路选择器。论文中报告该模块仅贡献约2mW的动态功耗占整个NTT模块功耗的25%远低于同类设计11-23mW。无存储开销完全省去了存储地址表的ROM/BRAM。确定性延迟地址生成是组合逻辑与计数器同步时序简单可控。3.2 统一蝶形运算单元的四周期舞步蝶形单元是执行计算的“肌肉”。它内部包含模加、模减、模乘和模约减子模块。关键创新在于其**四周期流水线非真正流水线而是分步执行**的调度策略以及如何用同一套硬件支持两种运算。硬件组成基于LUT的模乘器采用经过优化的设计参考了Bertels等人的工作仅用49个LUT实现模乘和约减避免了DSP。模加/模减器在模数q3329下加法器和减法器后都需要跟一个条件减法或加法来实现模运算这部分逻辑也做了合并优化。数据通路与寄存器用于暂存中间结果如乘法结果、加减法结果。四周期调度详解结合数据RAM的双端口读写 假设我们有一个双端口RAMPort A和Port B可以同时读两个数。周期1 (读操作数):NTT模式从Addr_A和Addr_B读取操作数a_in和b_in锁存到寄存器。INTT模式从Addr_A和Addr_B读取操作数a_in和b_in立即执行(a_in - b_in) mod q结果暂存。周期2 (读旋转因子并乘):NTT模式将RAM的Port A地址切换到旋转因子地址 Addr_TW读取因子w。同时将上周期锁存的b_in与w进行模乘结果暂存。INTT模式将RAM的Port A地址切换到 Addr_TW读取因子w。将上周期暂存的(a_in - b_in)结果与w进行模乘结果暂存。周期3 (计算并写回第一个结果):NTT模式再次从Addr_A读取a_in或直接使用寄存器中的值取决于架构。将其与周期2的乘法结果进行模加得到a_out写回Addr_A。同时计算(a_in - b_in*w) mod q得到b_out但不立即写回。INTT模式再次从Addr_A读取a_in。将其与b_in进行模加注意b_in可能需从寄存器中取出再与w进行模乘这里需要仔细核对根据公式INTT应是(a_in b_in) * w mod q。实际上在优化的硬件流程中为了共享乘法器通常先做加减法再做乘法。所以周期1做了减法并暂存周期2将其与w乘。周期3则需要做加法(a_in b_in)但这个结果不需要再乘w因为a_out的公式是(a_in b_in) * w而b_out是(a_in - b_in) * w。因此更合理的调度可能是周期1读出a_in,b_in并同时计算sum a_in b_in和diff a_in - b_in将diff暂存周期2将diff与w相乘得到b_out暂存周期3将sum与w相乘得到a_out并写回Addr_A周期4将b_out写回Addr_B。论文中的描述可能是一种等效的优化变体核心思想是通过固定的周期步骤复用算术单元完成所有计算。周期4 (写回第二个结果):NTT模式将周期3计算好的b_out写回Addr_B。INTT模式将周期2计算好的b_out即diff * w写回Addr_B。这种调度确保了在每个时钟周期RAM端口和算术单元都没有闲置最大化利用了硬件资源同时避免了为NTT和INTT设计两套数据通路。3.3 存储方案分布式LUT-RAM的优势使用分布式RAMDistributed RAM 由LUT构成而非BRAM是本设计低功耗的关键之一。容量匹配存储256个12位系数和128个旋转因子总容量为(256128)*12 4608 bits。这完全在LUT-RAM的能力范围内一个6输入LUT可配置为64位RAM。功耗优势BRAM是大型的静态存储阵列即使只访问一位整个模块也会有一部分电路活动功耗相对固定且较高。而LUT-RAM是分散的只有被访问的特定LUT才会消耗动态功耗更精细的功耗控制。布局灵活LUT-RAM可以布局在蝶形单元和地址生成器附近减少长距离走线这不仅降低了布线延迟有助于时序收敛也减少了线网切换带来的功耗。避免碎片化在小型存储应用中使用BRAM会导致其大部分容量被浪费而多个小BRAM又会造成布局资源碎片化。LUT-RAM则不存在这个问题。3.4 模约减的优化K-RED算法的轻量实现模约减是模乘运算中最耗时的部分之一。对于ML-KEM的模数q3329接近2^12可以采用高效的专用约减算法。本设计借鉴了K-RED算法的一种变体。其核心思想是对于一个小于q^2的乘法结果t我们可以利用q的特殊形式3329 2^12 - 2^8 1实际上3329是素数但可以找到接近2的幂次的表示以便简化运算例如利用3329 13*256 1等性质但更常见的是使用Barrett或Montgomery约减的优化版本。这里提到的Bertels等人的设计通过将乘法结果拆分高位和低位利用预计算的常数通过几次加法、减法和移位操作在很少的LUT资源内完成约减且避免了使用DSP。实操心得在FPGA上实现模约减时不要一上来就调用IP核或使用通用的Barrett约减。对于像3329这样的固定小模数花时间分析其二进制表示设计一个定制化的、多步的加/减/移位操作序列往往能节省大量逻辑资源。虽然最大工作频率可能会受限于这个较长的组合逻辑路径但对于追求面积和功耗的设计这是值得的。我们的目标是在100MHz下稳定工作而不是追求400MHz。4. 硬件实现与资源评估4.1 目标平台与工具链FPGA平台Xilinx Virtex-7。选择该平台进行评估具有代表性其丰富的逻辑资源可以验证设计的可综合性同时其性能指标也便于与同类研究进行对比。设计工具Xilinx Vivado。用于综合Synthesis、实现Implementation、时序分析Timing Analysis和功耗估算Power Estimation。评估指标资源占用Slices, LUTs, FFs, DSPs, BRAMs。性能最大工作频率Fmax完成一次256点NTT所需的时钟周期数执行时间。功耗静态功耗Static Power和动态功耗Dynamic Power。效率指标吞吐率Throughput以及更重要的A2TArea² × Time指标。A2T越小说明在单位面积平方和时间的乘积上效率越高越适合面积严格受限的场景。4.2 综合与实现结果根据论文数据在Virtex-7上实现后的关键数据如下资源类型使用量说明Slices147主要消耗在地址生成器、蝶形单元控制逻辑和分布式RAM。LUTs557用于实现组合逻辑、分布式RAM和模乘约减单元。FFs59用于构建计数器、状态机和数据流水线寄存器。DSPs0刻意避免使用提升可移植性。BRAMs0刻意避免使用采用分布式LUT-RAM。最大频率~100 MHz受限于多周期蝶形单元和LUT-based乘法器的关键路径。NTT延迟3584 cycles256点7级每级128个蝶形每个蝶形4周期 71284 3584周期。执行时间35.84 µs3584 cycles / 100 MHz。动态功耗15 mW核心模块功耗非常低。A2T7.745 × 10^5(147^2) * 35.84e-6。这是一个核心效率指标。4.3 与同类工作的对比分析为了体现本设计的优势论文与近年来的多个NTT硬件实现进行了对比。我们选取几个有代表性的设计设计平台SlicesLUTsDSP/BRAM频率(MHz)时间(µs)A2T (×10^5)特点本设计Virtex-71475570/010035.847.75极致轻量低功耗Kieu-Do-Nguyen [19]Artix-72215410/44171.11115.2高频高性能但用BRAMBisheh-Niasar [27]Artix-71093603/22278.17535.0使用DSP和BRAMYaman [33]Artix-7218700是/是115未明确较高高性能配置Bertels [36]Virtex-7未明确~950是/是200未明确未明确优化蝶形单元对比解读面积优势明显本设计在Slices和LUTs的使用上是最低的之一并且彻底放弃了DSP和BRAM。虽然[27]的Slices更少109但它使用了3个DSP和2个BRAM这些是更宝贵的专用资源且在不同FPGA上可用性不同。从“总硬件成本”综合来看本设计是最低的。A2T指标领先A2T是面积效率的体现。本设计的A2T值7.75e5远低于其他设计如[19]的115.2e5[27]的535.0e5表明在“面积平方×时间”这个衡量面积受限系统效率的指标上本设计具有显著优势。性能与功耗的权衡本设计的最大频率100MHz和执行时间35.84µs并非最快。[19]的设计能在1.11µs内完成快了30多倍。但这是用更高的频率417MHz、更深的流水线和BRAM资源换来的。本设计的动态功耗仅15mW远低于其他报告了功耗的设计通常在40-60mW。这完美体现了设计目标为对功耗和面积敏感但对绝对延迟不那么苛刻的应用场景提供最优解。可移植性由于不依赖DSP和BRAM本设计可以几乎不加修改地部署在Xilinx、IntelAltera甚至低成本的Lattice等FPGA上也可以更直接地转换为ASIC网表适用性更广。5. 设计中的挑战与解决方案5.1 时序收敛挑战采用全LUT设计特别是基于LUT的乘法器和多周期路径可能会面临时序挑战。关键路径很可能出现在模乘-约减的组合逻辑中。解决方案精细的流水线划分虽然整体是4周期蝶形但在模乘器内部可以进一步插入寄存器流水线。本设计可能采用了Bertels方案该方案本身可能就包含了几级内部流水。逻辑重构与优化使用Vivado的综合属性如MAX_FANOUT控制信号扇出对关键路径进行逻辑复制replication或寄存器平衡retiming。约束驱动布局布线通过物理约束Pblock将关键模块如蝶形单元、地址生成器、相邻的分布式RAM布局在相邻区域减少连线延迟。接受适中的频率明确设计目标不是极限频率而是面积功耗比。将时钟频率目标设定在100MHz为组合逻辑留出足够的时间余量Slack从而更容易时序收敛并能使用更低的电压进一步降低功耗。5.2 功能验证与正确性保障在如此高度优化的设计中确保功能正确性至关重要尤其是地址生成和四周期调度逻辑。解决方案分层测试平台单元测试单独验证地址生成器输入所有可能的计数器和模式检查输出地址序列是否符合NTT/INTT的位反转访问模式。可以用Python或C编写参考模型进行对比。模块级测试验证蝶形单元分别输入NTT和INTT模式的测试向量检查输出。系统级集成测试将整个NTT模块集成用随机或固定的多项式系数作为输入在FPGA上运行将结果与软件实现的NTT如PQClean库中的Kyber实现进行逐点比对。形式化验证辅助对于地址生成器这类控制逻辑可以使用形式化验证工具来证明其状态机在所有可能输入下都不会进入非法状态或产生错误地址。利用FPGA的在线调试通过Vivado的ILA集成逻辑分析仪抓取实际运行时的地址、数据和控制信号波形与仿真波形对比这是排查硬件时序问题的终极手段。5.3 资源利用与布局拥塞将所有存储用分布式LUT-RAM实现并且逻辑资源使用率很低147个Slices这本身有利于布局布线。但需要防止工具将逻辑分散到整个芯片增加布线延迟。解决方案区域约束在Vivado中可以创建一个包含大约200-300个Slices的Pblock区域将整个NTT模块约束在其中。这能迫使工具将相关逻辑紧密布局。手动布局提示对于地址生成器和蝶形单元可以将其相对位置固定确保它们之间的关键路径最短。优化RAM配置分布式RAM的配置方式单端口、双端口、简单双端口会影响其映射到的LUT类型和数量。需要根据读写模式选择最节省资源的配置。6. 应用场景与未来扩展6.1 目标应用场景这个轻量级NTT IP核是为以下场景量身定做的物联网终端设备例如智能传感器、可穿戴设备。这些设备电池容量小计算资源有限可能使用Spartan-7甚至更小的FPGA或ASIC需要一种“刚好够用”的PQC加速器。边缘安全网关在边缘侧进行大量的加密解密操作但网关可能有多项任务并行需要将密码运算的资源占用和功耗降到最低。嵌入式系统安全协处理器作为主处理器如ARM Cortex-M系列的一个硬件加速外设通过APB或AXI总线连接专门处理ML-KEM中的多项式运算。6.2 集成到完整的ML-KEM方案单独的NTT加速器需要集成到完整的ML-KEM数据通路中才能发挥作用。一个典型的集成方案包括顶层控制器负责协调密钥生成、封装、解封装的整个流程调用NTT/INTT模块。采样器用于生成噪声多项式可能需要一个SHA-3或SHAKE硬件模块。多项式/矩阵存储器需要更大的存储空间例如BRAM来存放公钥、私钥、密文和中间矩阵。本设计的NTT核自带分布式RAM只能存放一个多项式外部需要提供数据加载/卸载的接口。点乘与加法NTT变换后多项式乘法变为点乘系数逐点相乘。这需要额外的乘法累加单元。本设计的蝶形单元可以复用吗理论上点乘更简单可以设计一个更简单的模乘累加单元或者由软件完成。接口提供简单的内存映射接口或流式接口方便与主处理器或DMA交互。6.3 未来优化方向可配置性与参数化当前设计针对ML-KEM-768n256, q3329写死。可以将其参数化支持不同的多项式长度n和模数q以适配其他格基密码算法如Dilithium签名方案。抗侧信道攻击加固作为密码硬件必须考虑安全性。简单的功耗分析SPA或时序攻击可能通过观测地址序列或运算时间差来泄露信息。未来可以加入随机延迟、操作盲化blinding或隐藏hiding技术。更精细的功耗门控目前的设计已经很低功耗但可以进一步引入时钟门控Clock Gating甚至电源门控Power Gating在NTT模块空闲时关闭其大部分电路的时钟或电源将静态功耗也降到最低。ASIC流片验证本设计不依赖FPGA专用单元非常适合进行ASIC实现。在ASIC上可以更精确地评估其面积、功耗和性能并可能通过定制标准单元库获得更好的能效比。探索更高阶的优化例如研究Radix-4或Radix-8的蝶形算法虽然单次蝶形更复杂但能减少总的蝶形运算级数可能在高频率下带来更好的整体性能但会牺牲面积。这需要根据新的应用需求做权衡。这个设计向我们展示了一个清晰的思路在后量子密码硬件化的道路上当通用高性能架构遇到瓶颈时针对特定场景进行深度定制化、挖掘每一个模块的优化潜力尤其是那些被忽视的“非计算”部分往往能带来意想不到的收获。它可能不是跑得最快的那个但绝对是能在最严苛的角落面积、功耗里站稳脚跟的可靠选择。
后量子密码硬件优化：轻量级NTT地址生成器与全LUT架构设计
发布时间：2026/5/27 19:28:08
1. 项目概述为什么我们需要一个“瘦身”的NTT如果你最近在关注后量子密码PQC的硬件实现尤其是围绕NIST标准化的ML-KEM也就是之前的CRYSTALS-Kyber方案那么“数论变换”NTT这个词一定不会陌生。简单来说NTT是格基密码中进行多项式乘法的核心加速器其地位堪比深度学习里的矩阵乘法。没有高效的NTTML-KEM的密钥封装和解封装速度将大打折扣在物联网终端、边缘设备这类对功耗和面积极其敏感的场景里这几乎是不可接受的。传统的硬件优化思路无论是学术论文还是工程实践大多把火力集中在两个“显眼包”上模乘单元和模约减单元。这很好理解因为它们确实是计算最密集、最耗资源的部分。于是我们看到了各种精巧的DSP映射算法、基于常数的快速约减技巧目标都是把那几个纳秒的延迟和几百个LUT的资源再压榨一点。然而在反复折腾这些计算单元之后大家发现了一个尴尬的事实整个NTT加速器的性能瓶颈有时候并不在计算本身而在“喂数据”这个环节。这就是地址生成器——一个负责告诉内存“下一个该读/写哪个系数”的调度中心。在资源受限的FPGA上一个低效的地址生成器可能意味着巨大的查找表LUT开销、复杂的控制逻辑以及由此带来的高功耗。它就像城市交通中的红绿灯控制系统计算单元是性能强悍的跑车但如果调度系统混乱拥堵跑车也只能干等着。我们这次要聊的设计正是从这个被忽视的“交通调度”入手提出了一套极其轻量化的地址生成方案并围绕它构建了一个完整的、无需DSP和BRAM的NTT/INTT逆变换硬件架构。最终在Virtex-7上只用147个Slices和557个LUT就实现了完整功能动态功耗低至15mW相比之前的一些设计面积减少了近90%。这不仅仅是数字游戏它意味着我们能把一个完整的后量子密码协处理器塞进那些原本被认为不可能的小型FPGA甚至未来ASIC中。2. 核心思路拆解从“算得快”到“拿得准、花得少”这个项目的核心设计哲学可以概括为在保证必要吞吐量的前提下极致追求面积和功耗的优化尤其针对地址生成和数据通路这两个传统高开销模块进行重构。这背后是对应用场景的深刻理解对于大量电池供电、计算能力有限的物联网节点它们不需要追求极致的单次运算速度比如达到几百MHz而是更需要一个“够用且省电”的硬件引擎确保在完成安全通信的同时不影响设备整体的续航和成本。2.1 为什么地址生成器成了关键在经典的Cooley-Tukey或Gentleman-Sande蝶形算法中数据访问模式是“位反转”的。对于256点的NTTML-KEM的参数这意味着在7个阶段stage、每个阶段128步step的计算中每一对参与蝶形运算的系数地址以及用到的旋转因子twiddle factor地址都不是顺序递增的。传统的实现方法有两种预计算查表法事先把所有阶段的地址对和旋转因子地址算好存在ROM或BRAM里。这种方法简单直接但需要存储7 stages * 128 steps * (地址宽度)的数据对于小FPGA来说这块存储开销不小而且访问ROM本身也有功耗。实时计算法通过组合逻辑实时计算地址。这通常涉及位宽操作、条件判断和乘法/除法逻辑路径可能较长影响时序并且消耗的LUT资源也可能很可观。本项目提出的方法属于第二种但做了极度简化。它洞察到NTT地址生成的内在规律地址本质上是阶段索引stage和步进索引step的特定比特位拼接和反转。因此设计了一个基于10位计数器低7位表示step高3位表示stage的轻量级电路辅以简单的XOR异或逻辑来在INTT时实现比特反转再通过多路选择器Mux输出最终的三个地址操作数A、B和旋转因子。整个模块没有任何复杂的运算单元几乎就是计数器、线网和Mux的组合从而将资源占用压到最低。注意这里有一个非常关键的取舍。这种简化地址生成器通常与“多周期蝶形运算”架构搭配。也就是说一个蝶形运算可能需要4个时钟周期来完成。对于追求单周期吞吐的高性能设计这种简单的地址生成器可能无法满足每个周期都输出新地址的需求。但对于目标在“面积-功耗-性能”平衡点的设计用稍长的延迟换取巨大的面积和功耗节省是完全合理的。2.2 统一的蝶形运算单元少即是多另一个设计重点是统一的蝶形运算单元。NTT和其逆运算INTT的数学公式很相似NTT (Cooley-Tukey):a_out (a_in b_in * w) mod q,b_out (a_in - b_in * w) mod qINTT (Gentleman-Sande):a_out (a_in b_in) * w mod q,b_out (a_in - b_in) * w mod q可以看到核心操作都是模加、模减和模乘只是顺序不同。很多设计会为NTT和INTT分别实现两套硬件或者用一套硬件但需要复杂的控制逻辑进行重配置。本项目采用了一种更巧妙的方法硬件完全共享通过调度Schedule区分模式。具体来说设计一个支持模加、模减、模乘的算术逻辑单元ALU然后通过一个精确定义的4周期时序来组织这些操作。在NTT模式下周期1取数周期2做乘法周期3做加减法并写回第一个结果周期4写回第二个结果。在INTT模式下周期1取数并做加减法周期2做乘法周期3取数并做加法写回周期4写回乘法结果。这样同一套硬件电路仅仅通过控制信号切换操作顺序就服务了两种运算模式彻底避免了硬件冗余。2.3 告别DSP和BRAM极致的LUT化设计为了达到极致的轻量化和可移植性本设计坚定地摒弃了FPGA上的专用硬件资源DSP数字信号处理器和BRAM块存储器。为什么不用DSPDSP是FPGA上做乘法的利器但对于模乘后紧接着模约减的操作DSP的固定流水线有时并不高效且会占用固定的、有限的芯片资源。本设计采用基于LUT的乘法器虽然频率可能更低但资源使用更灵活且不依赖于特定FPGA型号的DSP数量可移植性更强。为什么不用BRAMBRAM是大的块存储适合存放大数据。但NTT中我们只需要存储256个系数12-bit和128个旋转因子总容量很小。使用BRAM会造成存储资源的浪费一个BRAM单元可能只用了一小部分且BRAM的功耗通常高于分布式RAM用LUT搭建的小存储器。本设计采用分布式LUT-RAM来存储所有数据它将存储单元打散分布在FPGA的逻辑单元中既能满足容量需求又便于布局布线靠近计算单元减少连线延迟和功耗。这种“全LUT”的设计理念使得整个NTT核心就像一个纯粹由逻辑资源构成的“软核”可以轻松适配从高端到低端的各种FPGA平台甚至为后续的ASIC流片铺平了道路。3. 架构细节与实现要点3.1 轻量级地址生成器的实现剖析地址生成器是整个设计的“智慧枢纽”。它的输入很简单一个启动信号Start一个模式信号NTT/INTT。输出是三个9位地址Addr_A, Addr_B, Addr_TW。核心机制10位全局计数器这是状态机的心脏。counter[9:7]的3位表示当前阶段0-6counter[6:0]的7位表示当前阶段内的步进0-127。计数器在每个时钟周期递增遍历所有7*128896个状态。模式自适应在INTT模式下需要对阶段索引进行比特反转。这里没有使用一个完整的反转电路而是巧妙地利用了XOR运算。当模式为INTT时将counter[9:7]与7二进制111进行异或再减1即可等效实现所需的比特反转效果。这比通用的桶形移位器或查找表节省了大量资源。地址拼接逻辑根据当前阶段i和步进j按照特定规则拼接出地址。阶段0地址规则最简单A和B地址仅是步进索引j与一个固定位的拼接旋转因子地址固定。阶段1-6地址是j的高(7-i)位、一个固定位、j的低(6-i)位的拼接。旋转因子地址则由j的高两位和一个左移值决定。 所有这些规则都通过硬连线的位选择和拼接操作完成无需任何算术运算。优势资源极简主要就是一个计数器、几个XOR门和多路选择器。论文中报告该模块仅贡献约2mW的动态功耗占整个NTT模块功耗的25%远低于同类设计11-23mW。无存储开销完全省去了存储地址表的ROM/BRAM。确定性延迟地址生成是组合逻辑与计数器同步时序简单可控。3.2 统一蝶形运算单元的四周期舞步蝶形单元是执行计算的“肌肉”。它内部包含模加、模减、模乘和模约减子模块。关键创新在于其**四周期流水线非真正流水线而是分步执行**的调度策略以及如何用同一套硬件支持两种运算。硬件组成基于LUT的模乘器采用经过优化的设计参考了Bertels等人的工作仅用49个LUT实现模乘和约减避免了DSP。模加/模减器在模数q3329下加法器和减法器后都需要跟一个条件减法或加法来实现模运算这部分逻辑也做了合并优化。数据通路与寄存器用于暂存中间结果如乘法结果、加减法结果。四周期调度详解结合数据RAM的双端口读写 假设我们有一个双端口RAMPort A和Port B可以同时读两个数。周期1 (读操作数):NTT模式从Addr_A和Addr_B读取操作数a_in和b_in锁存到寄存器。INTT模式从Addr_A和Addr_B读取操作数a_in和b_in立即执行(a_in - b_in) mod q结果暂存。周期2 (读旋转因子并乘):NTT模式将RAM的Port A地址切换到旋转因子地址 Addr_TW读取因子w。同时将上周期锁存的b_in与w进行模乘结果暂存。INTT模式将RAM的Port A地址切换到 Addr_TW读取因子w。将上周期暂存的(a_in - b_in)结果与w进行模乘结果暂存。周期3 (计算并写回第一个结果):NTT模式再次从Addr_A读取a_in或直接使用寄存器中的值取决于架构。将其与周期2的乘法结果进行模加得到a_out写回Addr_A。同时计算(a_in - b_in*w) mod q得到b_out但不立即写回。INTT模式再次从Addr_A读取a_in。将其与b_in进行模加注意b_in可能需从寄存器中取出再与w进行模乘这里需要仔细核对根据公式INTT应是(a_in b_in) * w mod q。实际上在优化的硬件流程中为了共享乘法器通常先做加减法再做乘法。所以周期1做了减法并暂存周期2将其与w乘。周期3则需要做加法(a_in b_in)但这个结果不需要再乘w因为a_out的公式是(a_in b_in) * w而b_out是(a_in - b_in) * w。因此更合理的调度可能是周期1读出a_in,b_in并同时计算sum a_in b_in和diff a_in - b_in将diff暂存周期2将diff与w相乘得到b_out暂存周期3将sum与w相乘得到a_out并写回Addr_A周期4将b_out写回Addr_B。论文中的描述可能是一种等效的优化变体核心思想是通过固定的周期步骤复用算术单元完成所有计算。周期4 (写回第二个结果):NTT模式将周期3计算好的b_out写回Addr_B。INTT模式将周期2计算好的b_out即diff * w写回Addr_B。这种调度确保了在每个时钟周期RAM端口和算术单元都没有闲置最大化利用了硬件资源同时避免了为NTT和INTT设计两套数据通路。3.3 存储方案分布式LUT-RAM的优势使用分布式RAMDistributed RAM 由LUT构成而非BRAM是本设计低功耗的关键之一。容量匹配存储256个12位系数和128个旋转因子总容量为(256128)*12 4608 bits。这完全在LUT-RAM的能力范围内一个6输入LUT可配置为64位RAM。功耗优势BRAM是大型的静态存储阵列即使只访问一位整个模块也会有一部分电路活动功耗相对固定且较高。而LUT-RAM是分散的只有被访问的特定LUT才会消耗动态功耗更精细的功耗控制。布局灵活LUT-RAM可以布局在蝶形单元和地址生成器附近减少长距离走线这不仅降低了布线延迟有助于时序收敛也减少了线网切换带来的功耗。避免碎片化在小型存储应用中使用BRAM会导致其大部分容量被浪费而多个小BRAM又会造成布局资源碎片化。LUT-RAM则不存在这个问题。3.4 模约减的优化K-RED算法的轻量实现模约减是模乘运算中最耗时的部分之一。对于ML-KEM的模数q3329接近2^12可以采用高效的专用约减算法。本设计借鉴了K-RED算法的一种变体。其核心思想是对于一个小于q^2的乘法结果t我们可以利用q的特殊形式3329 2^12 - 2^8 1实际上3329是素数但可以找到接近2的幂次的表示以便简化运算例如利用3329 13*256 1等性质但更常见的是使用Barrett或Montgomery约减的优化版本。这里提到的Bertels等人的设计通过将乘法结果拆分高位和低位利用预计算的常数通过几次加法、减法和移位操作在很少的LUT资源内完成约减且避免了使用DSP。实操心得在FPGA上实现模约减时不要一上来就调用IP核或使用通用的Barrett约减。对于像3329这样的固定小模数花时间分析其二进制表示设计一个定制化的、多步的加/减/移位操作序列往往能节省大量逻辑资源。虽然最大工作频率可能会受限于这个较长的组合逻辑路径但对于追求面积和功耗的设计这是值得的。我们的目标是在100MHz下稳定工作而不是追求400MHz。4. 硬件实现与资源评估4.1 目标平台与工具链FPGA平台Xilinx Virtex-7。选择该平台进行评估具有代表性其丰富的逻辑资源可以验证设计的可综合性同时其性能指标也便于与同类研究进行对比。设计工具Xilinx Vivado。用于综合Synthesis、实现Implementation、时序分析Timing Analysis和功耗估算Power Estimation。评估指标资源占用Slices, LUTs, FFs, DSPs, BRAMs。性能最大工作频率Fmax完成一次256点NTT所需的时钟周期数执行时间。功耗静态功耗Static Power和动态功耗Dynamic Power。效率指标吞吐率Throughput以及更重要的A2TArea² × Time指标。A2T越小说明在单位面积平方和时间的乘积上效率越高越适合面积严格受限的场景。4.2 综合与实现结果根据论文数据在Virtex-7上实现后的关键数据如下资源类型使用量说明Slices147主要消耗在地址生成器、蝶形单元控制逻辑和分布式RAM。LUTs557用于实现组合逻辑、分布式RAM和模乘约减单元。FFs59用于构建计数器、状态机和数据流水线寄存器。DSPs0刻意避免使用提升可移植性。BRAMs0刻意避免使用采用分布式LUT-RAM。最大频率~100 MHz受限于多周期蝶形单元和LUT-based乘法器的关键路径。NTT延迟3584 cycles256点7级每级128个蝶形每个蝶形4周期 71284 3584周期。执行时间35.84 µs3584 cycles / 100 MHz。动态功耗15 mW核心模块功耗非常低。A2T7.745 × 10^5(147^2) * 35.84e-6。这是一个核心效率指标。4.3 与同类工作的对比分析为了体现本设计的优势论文与近年来的多个NTT硬件实现进行了对比。我们选取几个有代表性的设计设计平台SlicesLUTsDSP/BRAM频率(MHz)时间(µs)A2T (×10^5)特点本设计Virtex-71475570/010035.847.75极致轻量低功耗Kieu-Do-Nguyen [19]Artix-72215410/44171.11115.2高频高性能但用BRAMBisheh-Niasar [27]Artix-71093603/22278.17535.0使用DSP和BRAMYaman [33]Artix-7218700是/是115未明确较高高性能配置Bertels [36]Virtex-7未明确~950是/是200未明确未明确优化蝶形单元对比解读面积优势明显本设计在Slices和LUTs的使用上是最低的之一并且彻底放弃了DSP和BRAM。虽然[27]的Slices更少109但它使用了3个DSP和2个BRAM这些是更宝贵的专用资源且在不同FPGA上可用性不同。从“总硬件成本”综合来看本设计是最低的。A2T指标领先A2T是面积效率的体现。本设计的A2T值7.75e5远低于其他设计如[19]的115.2e5[27]的535.0e5表明在“面积平方×时间”这个衡量面积受限系统效率的指标上本设计具有显著优势。性能与功耗的权衡本设计的最大频率100MHz和执行时间35.84µs并非最快。[19]的设计能在1.11µs内完成快了30多倍。但这是用更高的频率417MHz、更深的流水线和BRAM资源换来的。本设计的动态功耗仅15mW远低于其他报告了功耗的设计通常在40-60mW。这完美体现了设计目标为对功耗和面积敏感但对绝对延迟不那么苛刻的应用场景提供最优解。可移植性由于不依赖DSP和BRAM本设计可以几乎不加修改地部署在Xilinx、IntelAltera甚至低成本的Lattice等FPGA上也可以更直接地转换为ASIC网表适用性更广。5. 设计中的挑战与解决方案5.1 时序收敛挑战采用全LUT设计特别是基于LUT的乘法器和多周期路径可能会面临时序挑战。关键路径很可能出现在模乘-约减的组合逻辑中。解决方案精细的流水线划分虽然整体是4周期蝶形但在模乘器内部可以进一步插入寄存器流水线。本设计可能采用了Bertels方案该方案本身可能就包含了几级内部流水。逻辑重构与优化使用Vivado的综合属性如MAX_FANOUT控制信号扇出对关键路径进行逻辑复制replication或寄存器平衡retiming。约束驱动布局布线通过物理约束Pblock将关键模块如蝶形单元、地址生成器、相邻的分布式RAM布局在相邻区域减少连线延迟。接受适中的频率明确设计目标不是极限频率而是面积功耗比。将时钟频率目标设定在100MHz为组合逻辑留出足够的时间余量Slack从而更容易时序收敛并能使用更低的电压进一步降低功耗。5.2 功能验证与正确性保障在如此高度优化的设计中确保功能正确性至关重要尤其是地址生成和四周期调度逻辑。解决方案分层测试平台单元测试单独验证地址生成器输入所有可能的计数器和模式检查输出地址序列是否符合NTT/INTT的位反转访问模式。可以用Python或C编写参考模型进行对比。模块级测试验证蝶形单元分别输入NTT和INTT模式的测试向量检查输出。系统级集成测试将整个NTT模块集成用随机或固定的多项式系数作为输入在FPGA上运行将结果与软件实现的NTT如PQClean库中的Kyber实现进行逐点比对。形式化验证辅助对于地址生成器这类控制逻辑可以使用形式化验证工具来证明其状态机在所有可能输入下都不会进入非法状态或产生错误地址。利用FPGA的在线调试通过Vivado的ILA集成逻辑分析仪抓取实际运行时的地址、数据和控制信号波形与仿真波形对比这是排查硬件时序问题的终极手段。5.3 资源利用与布局拥塞将所有存储用分布式LUT-RAM实现并且逻辑资源使用率很低147个Slices这本身有利于布局布线。但需要防止工具将逻辑分散到整个芯片增加布线延迟。解决方案区域约束在Vivado中可以创建一个包含大约200-300个Slices的Pblock区域将整个NTT模块约束在其中。这能迫使工具将相关逻辑紧密布局。手动布局提示对于地址生成器和蝶形单元可以将其相对位置固定确保它们之间的关键路径最短。优化RAM配置分布式RAM的配置方式单端口、双端口、简单双端口会影响其映射到的LUT类型和数量。需要根据读写模式选择最节省资源的配置。6. 应用场景与未来扩展6.1 目标应用场景这个轻量级NTT IP核是为以下场景量身定做的物联网终端设备例如智能传感器、可穿戴设备。这些设备电池容量小计算资源有限可能使用Spartan-7甚至更小的FPGA或ASIC需要一种“刚好够用”的PQC加速器。边缘安全网关在边缘侧进行大量的加密解密操作但网关可能有多项任务并行需要将密码运算的资源占用和功耗降到最低。嵌入式系统安全协处理器作为主处理器如ARM Cortex-M系列的一个硬件加速外设通过APB或AXI总线连接专门处理ML-KEM中的多项式运算。6.2 集成到完整的ML-KEM方案单独的NTT加速器需要集成到完整的ML-KEM数据通路中才能发挥作用。一个典型的集成方案包括顶层控制器负责协调密钥生成、封装、解封装的整个流程调用NTT/INTT模块。采样器用于生成噪声多项式可能需要一个SHA-3或SHAKE硬件模块。多项式/矩阵存储器需要更大的存储空间例如BRAM来存放公钥、私钥、密文和中间矩阵。本设计的NTT核自带分布式RAM只能存放一个多项式外部需要提供数据加载/卸载的接口。点乘与加法NTT变换后多项式乘法变为点乘系数逐点相乘。这需要额外的乘法累加单元。本设计的蝶形单元可以复用吗理论上点乘更简单可以设计一个更简单的模乘累加单元或者由软件完成。接口提供简单的内存映射接口或流式接口方便与主处理器或DMA交互。6.3 未来优化方向可配置性与参数化当前设计针对ML-KEM-768n256, q3329写死。可以将其参数化支持不同的多项式长度n和模数q以适配其他格基密码算法如Dilithium签名方案。抗侧信道攻击加固作为密码硬件必须考虑安全性。简单的功耗分析SPA或时序攻击可能通过观测地址序列或运算时间差来泄露信息。未来可以加入随机延迟、操作盲化blinding或隐藏hiding技术。更精细的功耗门控目前的设计已经很低功耗但可以进一步引入时钟门控Clock Gating甚至电源门控Power Gating在NTT模块空闲时关闭其大部分电路的时钟或电源将静态功耗也降到最低。ASIC流片验证本设计不依赖FPGA专用单元非常适合进行ASIC实现。在ASIC上可以更精确地评估其面积、功耗和性能并可能通过定制标准单元库获得更好的能效比。探索更高阶的优化例如研究Radix-4或Radix-8的蝶形算法虽然单次蝶形更复杂但能减少总的蝶形运算级数可能在高频率下带来更好的整体性能但会牺牲面积。这需要根据新的应用需求做权衡。这个设计向我们展示了一个清晰的思路在后量子密码硬件化的道路上当通用高性能架构遇到瓶颈时针对特定场景进行深度定制化、挖掘每一个模块的优化潜力尤其是那些被忽视的“非计算”部分往往能带来意想不到的收获。它可能不是跑得最快的那个但绝对是能在最严苛的角落面积、功耗里站稳脚跟的可靠选择。
