基于Barrett模乘的后量子密码算法Kyber在AVR平台上的实现方法
本发明涉及基于barrett模乘的后量子密码算法kyber在avr平台上的实现方法,属于信息安全。
背景技术:
1、量子计算技术的提出和发展对现有的公钥密码(pkc)系统安全性造成严重威胁。传统pkc方案所依赖的数学困难问题可以被量子计算机在多项式时间内破解。为应对潜在的量子攻击,美国国家标准与技术研究院(nist)发起了后量子密码算法(pqc)的标准化征集活动,以征集、评估和标准化可以抵抗量子计算攻击的新型密码系统。在nist公布入选的第一轮后量子候选方案中,kyber是其中唯一入选的密钥封装协议(kem)标准。kyber是一种达到ind-cca2安全的密钥封装机制,其安全性来源于模块误差学习问题(mlwe)。
2、kyber中的代数运算均是在多项式环进行的,即涉及的矩阵或向量中的每个元素都是该多项式环上的多项式,,模数。并且,因为在基域上只有原始的256阶本原单位根,最终采用的是不完整ntt变换,仅进行7层计算。相应地,经ntt处理后的多项式可表示为一个由128个一次多项式组成的向量,在ntt域上的多项式乘法即需要进行128个一次多项式相乘。
3、8位avr处理器因其高性能和低功耗的特性更加适用于资源受限的场景部署。但在8位avr处理器上的现有kyber实现方案需要消耗较大的内存空间,并且没有针对数论变换(number theoretic transform,ntt)或逆向数论变换(inverse ntt,intt)计算以及多项式乘法充分利用汇编指令集和32个8位寄存器,无法在提高执行速度的同时,实现资源优化利用。
技术实现思路
1、本发明所要解决的技术问题是:提供基于barrett模乘的后量子密码算法kyber在avr平台上的实现方法,对耗时的ntt、intt计算和多项式乘法计算通过barrett模乘重新实现,提高计算效率、减少内存占用。
2、本发明为解决上述技术问题采用以下技术方案:
3、基于barrett模乘的后量子密码算法kyber在avr平台上的实现方法,包括基于barrett模乘的数论变换计算、矩阵-向量乘法计算以及逆向数论变换计算的处理;
4、在后量子密码算法kyber中采用7层数论变换计算,根据8位avr平台特性采用2+2+2+1的层合并策略实现;即第一层和第二层进行一次2层数论变换合并计算,第三层和第四层进行一次2层数论变换合并计算,第五层和第六层进行一次2层数论变换合并计算,第七层独立进行数论变换计算,不参与层合并;
5、根据每层的步长距离规定加载进行当前2层合并计算的4个系数至寄存器,对这4个系数进行4次独立的蝴蝶变换后,再放回内存,对所有的系数重复数据加载-4次蝴蝶变换-放回内存的操作完成后,即为一次2层数论变换合并计算;
6、将7层数论变换计算结果进行矩阵-向量乘法计算,kyber中的矩阵-向量乘法计算在经7层数论变换得到的频域表示状态下进行;
7、将矩阵-向量乘法计算结果进行7层逆向数论变换计算,kyber中同样采用7层逆向数论变换计算,并根据8位avr平台特性采用2+2+2+1的层合并策略实现;
8、基于对所述数论变换、逆向数论变换以及矩阵-向量乘法计算的处理过程,完成后量子密码算法kyber在avr平台上的实现。
9、进一步地,将kyber中涉及的模乘运算均使用barrett模乘实现而非现有实现中的montgomery模乘或plantard模乘。在8位avr架构上仅支持8位乘法指令,在barrett模乘的近似变体实现中对类似的16位高位乘法仅需3次8位乘法即可完成,其中,,,极大提高运行速度。
10、进一步地,在kyber中进行ntt或intt计算时,均使用ct蝴蝶变换作为核心计算模块,即将一个系数进行乘法运算后与另一个系数进行加减得到结果。具体计算公式为:和。其中,和为进行ct蝴蝶变换的两个系数,是旋转因子,属于模乘模块;
11、对应用barrett模乘近似变体完成计算,具体计算公式为:。又因为ntt和intt使用的旋转因子已知,可以直接计算每个旋转因子对应的中间因子并和旋转因子存储在同个数组中。
12、进一步地,在kyber中进行ntt或intt计算时,利用avr上32个8位寄存器,其中r0-r1作为乘法指令结果寄存器、r26-r31作为指针寄存器可从传入地址读取数据。并使用x寄存器(r26-r27)放置旋转因子数组的地址,y寄存器(r28-r29)和z寄存器(r30-r31)放置多项式系数数组的地址。即从x寄存器读取和对应的,从y寄存器和z寄存器分别读取和。
13、进一步地,在kyber中进行ntt或intt计算中,因为kyber上使用的是不完整ntt,即对输入的高阶多项式进行7层ntt/intt计算,根据8位avr平台特性采用了2+2+2+1的层合并策略实现,以减少计算过程中需要的数据加载和存储指令。具体为:分别从y寄存器和z寄存器加载2个系数,每个系数表示为16位,在avr上需要2个8位寄存器进行存储。并将蝴蝶变换中不参与模乘模块的两个系数存储在r4-r7,将参与模乘模块的两个系数存储在r16-r19,旋转因子和中间因子存储在r20-r23。对加载的这4个系数进行4次独立ct蝴蝶变换,然后将这些系数放回内存;不断重复“数据加载-4次ct蝴蝶变换-放回内存”的操作,直到处理完所有系数,这即为一次2层ntt合并计算。
14、进一步地,kyber中的矩阵-向量乘法在ntt域内进行,其底层运算可表示为在ntt域内的多项式乘法,包括128个一次多项式相乘,即;一个一次多项式相乘共需要进行5次模乘包括一次模乘以常数和其余四次模乘以变量,其中的模乘以变量需要额外计算barrett模乘所需的中间因子如,故采用和间隔计算的方案设计了新乘法顺序,其中和,在符合寄存器限制的前提下实现数据复用,这里面的每个模乘同样使用barrett模乘实现。
15、进一步地,在kyber中进行矩阵-向量乘法计算时,维度为的矩阵每一行都需要重复地乘以秘密向量,即重复使用该向量共计次,应用一个独立的多项式向量缓存预计算的和,可以避免基乘中重复计算中间因子。使用和表示该多项式向量,其中每个包括256个系数,每个包括个。
16、本发明采用以上技术方案与现有技术相比,具有以下技术效果:
17、1、本发明充分利用了avr架构提供的32个通用寄存器,使用的barrett模乘而非参考实现的montgomery模乘,该模乘更适合处理器字长小于算法字长且缺乏高位乘法指令的平台。
18、2、本发明考虑到在模乘以两个变量的基乘中每次需要额外计算中间因子,重新设计一种适用于barrett模乘的基乘顺序,将重复使用的数据放置在固定寄存器中,尽可能减少乘法指令和数据移动指令。
19、3、与在8位avr微处理器上基于montgomery模乘的kyber实现相比,本发明提出的在8位avr微处理器上基于barrett模乘的kyber实现,在密钥生成、封装和解封装分别实现了46.3%、44.3%和47.9%的性能提升(在nist安全等级1下的测试结果)。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com