软件学报

作者：梁志闯，赵旭阳，方博越，赵运磊

单位：梁志闯，复旦大学 计算机科学技术学院, 上海 20043311,赵旭阳，复旦大学 计算机科学技术学院, 上海 20043302,方博越，复旦大学 计算机科学技术学院, 上海 20043303,赵运磊，复旦大学 计算机科学技术学院, 上海 200433;密码科学技术国家重点实验室, 北京 10003604

关键词：格密码;后量子密码;数论研究单元(NTRU);素阶数域;密钥封装方案;数论变换;模约减;软件实现

基金：国家自然科学基金(61877011); 国家重点研发计划(2022YFB2701600); 上海市科学技术发展基金(21DZ2200500); 山东省重点研发计划(2017CXG0701, 2018CXGC0701)

基于格(特别是NTRU格)设计后量子密钥封装方案是格密码领域的主流方向之一. 现有多数格密码方案基于分圆环构造, 但分圆环饱含丰富的代数结构导致这些方案容易遭受相关攻击. 一个可选的且更安全的代数结构是大Galois群、素数阶、基于素理想的数域(简称为素阶数域). NTRU-Prime是一个基于素阶数域的备受青睐的NTRU密钥封装方案, 且早已经在国际标准OpenSSH中默认应用. 旨在设计出比NTRU-Prime性能更优的素阶数域上NTRU密钥封装方案. 首先, 梳理分圆环的安全隐患, 特别是针对2次幂分圆环的系列攻击, 同时展示出素阶数域在抵御这些攻击方面的安全优势. 接着, 基于素阶数域提出NTRU密钥封装方案CNTR-Prime, 并给出详细的相关分析和参数集. 然后, 提出一种伪梅森数不完整NTT, 它能有效计算CNTR-Prime中关于素阶数域的多项式乘法. 此外, 还提出一种改进的伪梅森数约减算法, 并将它应用在伪梅森数不完整NTT中. 它在软件实现方面比Barrett约减快2.6%, 在硬件实现方面比Montgomery约减和Barrett约减快2–6倍. 最后, 提供CNTR-Prime的C语言实现, 并与其他同类方案进行全面对比. 结果表明, 与SNTRU-Prime相比, CNTR-Prime在安全强度、带宽和实现效率上有优势, 其中CNTR-Prime-761的经典和量子安全强度都比SNTRU-Prime-761的高19 bit, 密文尺寸降低8.3%, 密钥生成算法、密钥封装算法和解封装算法分别快25.3倍、10.8倍和2.0倍. 实际上, CNTR-Prime-653的经典和量子安全强度已可与SNTRU-Prime-761相媲美, 且CNTR-Prime-653的带宽降低13.8%, 密钥生成算法、密钥封装算法和解封装算法分别快33.9倍、12.6倍和2.3倍. 所提工作可为后续同类型的格密码方案的设计、分析和优化实现提供重要参考.

来源：2025年第2期

《软件学报》期刊编辑部

查看软件学报杂志2025年第2期