基于Cortex-M4的CNTR/CTRU密钥封装高效实现

量子计算技术的迅猛发展对现有的公钥密码体制造成了极大的威胁,为了抵抗量子计算的攻击,后量子密码成为当前密码学界的研究热点.目前,物联网的安全问题备受关注,ARM Cortex-M4作为低功耗嵌入式处理器,被广泛应用于物联网设备中,在其上部署后量子密码算法将为物联网设备的安全提供更加可靠的保障.CNTR和CTRU是我国学者提出的NTRU格基密钥封装方案,相比于基于LWE技术路线的格基密钥封装方案在安全性和其他性能上具有综合优势,并在我国密标委得到立项.本文工作首次在ARM Cortex-M4平台上高效紧凑地实现了CNTR和CTRU方案,充分利用单指令多数据(Single Instruction Multiple Data,SIMD)指令,调整运算结构和指令安排,优化核心的多项式运算,从而在算法实现速度和堆栈空间上进行全面优化升级.本文主要工作如下:本文首次在ARM Cortex-M4上实现耗时模块多项式中心二项分布采样,采样速度提升32.49%;使用混合基数论变换(Number Theoretic Transform,NTT)加速非NTT友好多项式乘法运算,充分利用浮点单元(Floating-Point Unit,FPU)寄存器,在NTT实现中采用层融合技术,最大化减少加载和存储等耗时指令使用,使得正向NTT和逆向NTT的速度分别提升84.24%、81.15%;通过NTT过程系数范围分析进行延迟约减,进而减少约减次数,并使用改进的Barrett约减和Montgomery约减技术实现降低约减汇编指令条数;使用循环展开技术实现多项式求逆,优化多项式求逆这一耗时过程,速度优化率为68.85%;针对解密过程中的非NTT友好素数模数多项式环乘法,采用多模数NTT和中国剩余定理(Chinese Remainder Theorem,CRT)结合的方法进行加速,完成解密过程96.26%的速度提升;使用空间复用的方法优化堆栈空间,CNTR和CTRU的堆栈空间分别减少了29.86%、28.17%.实验结果表明:提出的优化技术大幅提升了算法实现效率,与C参考实现相比,CNTR和CTRU的整体速度优化率分别为85.54%、85.56%.与其他格基密钥封装方案最新ARM Cortex-M4实现相比,本文的优化实现在速度、空间和安全性上具有综合性的优势.

NTRU格上高效紧凑密钥封装方案

基于NTRU格设计后量子密钥封装方案是格密码领域主流方向之一.为降低密文尺寸,现有方案会引入额外的困难性假设和使用纠错码来辅助压缩密文,但这会导致方案的假设过强和实现更复杂.为克服这些障碍,提出了一个仅基于NTRU单向困难性假设、不使用纠错码也能压缩密文的高效紧凑的密钥封装方案LTRU.给出一套性能均衡的LTRU参数集:具有128 b量子安全强度、与之匹配且可忽略的错误率、较小的公钥尺寸和密文尺寸.LTRU基于NTT友好环构造,给出一种高效的混合基数论变换算法来计算该环上多项式运算还给出了LTRU的C实现和AVX2实现.与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%;在AVX2实现的密钥生成和解封装算法上分别快了10.9倍和1.7倍.

NTRU格基密钥封装方案GPU高性能实现

随着量子计算技术的发展,传统加密算法受到的威胁日益严重.为应对量子计算时代的挑战,各国正积极加强后量子密码算法的实现和迁移部署工作.由于NTRU密码方案具有结构简洁、计算效率高、尺寸较小、无专利风险等优点,因此NTRU格基密钥封装算法对于后量子时代的密码技术储备和应用具有重要意义.同时,图形处理器(Graphics Processing Unit,GPU)以其强大的并行计算能力、高吞吐量、低能耗等特性,已成为当前高并发密码工程实现的重要平台.本文给出后量子密码算法CTRU/CNTR的首个GPU高性能实现方案.对GPU主要资源占用进行分析,我们综合考虑并行计算、内存访问、数据布局和算法优化等多个方面,采用一系列计算和内存优化技术,旨在并行加速计算、优化访存、合理占用GPU资源以及减少I/O时延,从而提高本方案的计算能力和性能.本文的主要贡献在于以下几个方面:首先,针对模约减操作,使用NVIDIA并行指令集实现,有效减少所需指令条数;其次,针对耗时的多项式乘法模块,采用混合基NTT,并采用层融合、循环展开和延迟约减等方法,加快计算速度;此外,针对内存重复访问和冲突访问等问题,通过合并访存、核函数融合等优化技术,实现内存的高效访问;最后,为实现高并行的算法,设计恰当的线程块大小和数量,采用内存池机制,实现多任务的快速访存和高效处理.基于NVIDIA RTX4090平台,本方案CTRU768实现中密钥生成、封装和解封装的吞吐量分别为每秒1170.9万次、926.7万次和315.4万次.与参考实现相比,密钥生成、封装和解封装的吞吐量分别提高了336倍、174倍和128倍.本方案CNTR768实现中密钥生成、封装和解封装的吞吐量分别为每秒1117.3万次、971.8万次和322.2万次.与参考实现相比,密钥生成、封装和解封装的吞吐量分别提高了329倍、175倍和134倍;与开源Kyber实现相比,密钥生成、密钥封装和密钥解封装的吞吐量分别提升10.84~11.36倍、9.49~9.95倍和5.11~5.22倍.高性能的密钥封装实现在大规模任务处理场景下具有较大的应用潜力,对保障后量子时代的信息和数据安全具有重要意义.

抗泄露的(分层)身份基密钥封装机制

在真实应用环境中,冷启动、边信道等物理攻击方式的出现,使得敌手能够获得参与者内部私有状态的泄露信息,从而导致传统可证明安全的密码机制在有泄露的环境下已无法继续保持其原有的安全性,因此更多的密码学研究者开始致力于抗泄露密码机制的研究.混合加密技术同时具备了对称加密和非对称加密的优势,由于身份基密钥封装机制(Identity-Based Key-Encapsulation Mechanism,IB-KEM)是身份基混合加密机制的重要组成部分,近年来得到了广泛关注.为满足真实环境的抗泄露性需求,抗泄露IB-KEM被提出;然而现有的构造在计算、传输和存储等方面均存在不足.针对上述不足,本文提出了选择密文攻击(Chosen-Ciphertext Attacks,CCA)安全的抗泄露IB-KEM的通用构造,并基于底层IB-KEM的选择明文攻击(Chosen-Plaintext Attacks,CPA)安全性对通用构造的CCA安全性进行了形式化证明.此外,为展示本文通用构造的实用性及普遍性,分别设计了 IB-KEM和分层身份的身份基密钥封装机制(Hierarchical Identity-Based Key-Encapsulation Mechanism,HIB-KEM)的具体实例,并在选择身份的安全模型下,基于判定的双线性Diffie-Hellman假设和双线性Diffie-H ellman指数假设对本文实例的CPA安全性分别进行了证明.最后,为了实现抵抗连续泄露攻击的目标,本文研究了各实例的密钥更新算法.相较于已有CCA安全的抗泄露IB-KEM,本文构造在计算、传输和存储等方面具有一定的优势.

标准模型下安全的基于证书密钥封装方案

混合加密是将公钥加密与对称加密结合的一种加密技术.将密钥封装机制引入到基于证书加密方案中,提出了基于证书密钥封装机制的形式化定义及安全模型,构造了一个基于证书密钥封装方案.基于判定双线性Diffie-Hellman困难问题假定,在标准模型下证明提出的方案是自适应选择密文安全的.

带标签的基于证书密钥封装机制

基于证书加密方案通常将消息空间限制于某个特殊的群并且不适合大块消息加密.为了解决这一问题,将带标签的密钥封装机制引入到基于证书系统中,提出了带标签的基于证书密钥封装机制的形式化定义及安全模型.在此基础上构造了一个带标签的基于证书密钥封装方案,并证明了该方案在随机预言模型下是自适应选择密文不可区分的.

无证书体制下的多接收者签密密钥封装机制

无证书签密密钥封装机制(CLSC-KEM)与数据封装机制共同构成无证书混合签密方案。该文提出一个新的概念:无证书体制下的多接收者签密密钥封装机制(mCLSC-KEM)。给出了mCLSC-KEM的定义以及安全模型,并构造了一个具体的方案。该方案比一般性构造(对每个接收者分别运行CLSC-KEM)高效很多,其密钥封装仅需计算1个双线性对,且对应的数据封装仅需运行1次对称加密,而一般性构造需计算n个双线性对和n次数据封装(设n个接收者)。在随机预言模型下,基于Gap双线性Diffie-Hellman问题,该文的方案是可证明安全的。

基于身份的高效签密密钥封装方案

KEM-DEM结构的混合密码体制是获得IND-CCA安全最实际有效的方法,传统的KEM由公钥加密方案实现,仅提供DEM使用的会话密钥的保密性安全.2005年Alexander等人将签密的概念与KEM-DEM结构的混合密码体制相结合,提出了Signcryption KEM-DEM结构的混合签密.其中Signcryption KEM是利用发送者私钥和接收者公钥共同生成会话密钥及其密钥封装.该方法可以使密钥封装同时具有保密安全性和不可伪造安全性.在基于身份密码体制上扩展了签密密钥封装的定义,结合Sakai-Kasahara私钥提取结构以及椭圆曲线上相关的困难问题给出了一个基于身份的签密密钥封装的实例方案,并在随机预言机模型下对该实例方案的安全性进行了证明.该方案具有ID-IND-CCA保密性安全和ID-UF-CMA不可伪造性安全.提出的实例方案在会话密钥封装阶段不需要进行对计算以及映射到点的Hash函数计算.通过有效的对优化计算和点压缩技术,本实例方案在具有高安全性的同时也具有执行性能上的优势.

一种匿名的多接收者密钥封装机制

匿名性能够保障用户的个人隐私不受非授权方侵害.针对接收者隐私保护的需求,基于双线性对提出了一个新的基于身份的匿名多接收者密钥封装机制.利用一次匿名密钥协商技术和Hash函数生成临时密钥,从而实现接收者的匿名.在随机预言机模型下,证明了其在选择密文攻击和身份攻击下满足封装密钥的机密性和匿名性,具有较高的效率且密文较短.

标准模型下高效安全的基于证书密钥封装机制

基于证书密码体制有机结合了传统公钥密码体制和基于身份密码体制,不仅克服了基于身份密码体制固有的密钥托管和密钥分发问题,而且简化了传统公钥基础设施中复杂的公钥证书管理,是一种颇受关注的新型公钥密码体制.基于证书密钥封装机制,将密钥封装机制与基于证书密码体制相结合,具备基于证书密码体制的优良特性.基于双线性对,提出了一个高效的并且可证明安全的基于证书密钥封装机制方案.在标准模型下基于判定性截断q-ABDHE问题和判定性1-BDHI问题的困难性,该方案被证明满足适应性选择密文攻击下的不可区分安全性,即满足选择密文安全性.与已有的标准模型下安全的基于证书密钥封装机制方案相比,该方案具有更高的计算效率和更低的通信带宽要求.

一种基于身份和密钥封装机制的加密方案

提出一个基于身份和密钥封装机制的加密方案,采用对称加密技术实现信息的高效加密解密,利用基于身份的密码算法传递对称密钥。该方案扩展了标准模型下可证明安全的选择密文攻击的加密方案,其安全性规约为判定性Diffie-Hellman假设。分析结果表明,该方案对抵抗自适应选择密文攻击是不可区分的。

CCA安全的抗连续泄露的广播密钥封装机制

传统公钥基础设施中的证书复杂管理和身份基密码体制中的密钥托管等问题在基于证书的密码体制下得到了很好的解决,因此无证书密码体制近年来得到了广泛关注.此外,在现实应用中,攻击者基于冷启动、边信道等各种各样的泄露攻击获得密码机制内部敏感状态(如秘密钥等)的泄露信息,导致在传统理想模型下被证明安全的密码机制不再具有相应的安全性.此外,由于广播通信模式具有较高的消息通信效率,多个具有广播通信功能的密码原语相继被提出.针对基于证书密钥封装机制对泄露容忍性和广播通信等性能的需求,提出抗泄露的基于证书的广播密钥封装机制的实例化构造,并基于判定的Diffie-Hellman困难性假设对其选择密文攻击下的安全性进行了证明.此外,为进一步增强该构造的实用性,研究了广播密钥封装机制的连续泄露容忍性,通过定期更新用户密钥的方式实现了对连续泄露攻击的抵抗目标.与现有工作的分析对比表明,该构造在保证安全性可证明的基础上,不仅实现了抵抗泄露攻击和广播通信的功能,而且拥有较高的计算效率.

标准模型下基于身份的签密密钥封装

针对随机预言模型下的签密密钥封装机制依赖现实世界无法实现的随机预言假设的问题,提出在标准模型下可证明安全的基于身份签密密钥封装机制(IBSC-KEM)。新提出的IBSC-KEM方案基于一种受到广泛研究的身份加密机制,在标准模型下被规约为求解q-ABDHE问题和判定性q-ABDHE问题,具有机密性和不可伪造性。新方案主要计算开销为5次群G上的指数运算、3次群GT上的指数运算和3次双线性对运算,与类似的签密方案比较,计算开销较低。此外,新方案还具有公开可验证性,适用于构建安全的端到端传输。

标准模型下格上的密钥封装机制

密钥封装机制(key encapsulation mechanism,KEM)使得会话双方能够安全地共享一个随机的会话密钥,改善了使用公钥加密明文时空间受限的问题,是大规模网络中密钥分发和密钥管理问题的有效解决方案之一。提出一种标准模型下安全高效的格上的密钥封装机制,将陷门函数与带误差学习问题(learning with errors,LWE)算法相结合,并引入参与者的身份信息,保证密钥封装机制的机密性和可认证性,可抵抗现有已知量子算法攻击。采用密文压缩技术,对封装后的密文元素进行压缩,分析结果表明,能够有效提高传输效率。在标准模型下,该机制安全性归约至判定性LWE的难解性,并包含严格的安全性证明。其安全性为可证明的选择密文安全,适用于多种类型基于格的密钥交换协议方案。

标准模型下基于身份的多接收者签密密钥封装

签密密钥封装机制能同时实现封装密钥的机密性和认证性。以Wa-IBE加密方案和PS-IBS签名机制为基础,提出一种标准模型下的身份基签密密钥封装机制(IBSC-KEM)和多接收者签密密钥封装机制(mIBSC-KEM)。新方案中的签名算法直接采用了PS-IBS签名,密钥封装算法采用了变形的WaIBE加密方案。因此,新方案的不可伪造性和机密性在标准模型下分别被规约为破解PS-IBS签名与WaIBE加密,具有可证明安全性。新方案可用于构建标准模型下安全的一对一和多对一认证与密钥交换方案。

支持多密文批量审计的解密外包SM9-HIBE密钥封装机制

SM9-HIBE密钥封装机制的解密操作需要2次双线性配对运算,在设备算力受限且需对大规模信息资源进行高频解密时,配对运算的高额计算开销会束缚系统的有效部署。为此,基于SM9-HIBE提出了一种支持解密外包和多密文批量审计的新型密钥封装机制OASM9-HIBE,并利用Fujisaki-Okamoto转换技术在随机谕言模型下证明了OASM9-HIBE具备RCCA安全性。OASM9-HIBE将计算繁重的双线性配对运算全部安全外包至算力强大的云端,第k层用户只需执行一次简单的指数运算即可完成最终解密,有效提升了原SM9-HIBE的解密效率,OASM9-HIBE同时运用密钥盲化技术实现了多份转换密文的高效批量审计功能,从而拓展了SM9系列算法的应用领域。

内部攻击者安全模式下的签密密钥封装

基于Signcryption KEM-DEM混合签密结构,提出一个内部攻击者安全模式下签密密钥封装的形式化定义,引入一个随机标签与验证算法来保证签密密钥封装在内部攻击者模式下的安全性。在形式化定义的基础上,对该定义在可证明安全概念下的保密性和数据完整性的安全进行讨论,给出相应的攻击游戏的安全模型。

基于签密的密码工作流密钥封装机制

密码工作流(cryptographic workflow)是多用户环境下一种特殊的密码系统工作模式,在这种工作模式下,加密消息需要依据某种策略进行,因此只有履行这一策略的实体才能进行消息解密.为保证在密码工作流模式下密钥封装能够同时实现密钥免托管性和密钥封装传递的不可伪造性,基于签密的思想定义了一个新的密码工作流模式下的密钥封装机制.首先定义了密码工作流模式下基于签密的密钥封装一般模型,并给出了相应的安全模型;其次,结合秘密共享方案、基于身份加密方案和签密方案,提出一个新的结构方案,并在标准模型(standard model)下利用序列游戏证明方法对该结构方案的安全性进行了详细证明.证明结果表明,该密钥封装结构方案能够达到密码工作流模式下要求的接收者安全和外部安全.

具有多接收者的抗泄露匿名密钥封装机制

基于证书的密码体制在继承传统公钥基础设施和身份基密码体制优势的同时,避免了证书管理和密钥托管等不足.为了向基于证书的密钥封装机制提供匿名性和抗泄露攻击的能力,本文提出具有多接收者的抗泄露匿名密钥封装机制的形式化定义及抵抗泄露攻击的安全模型,并给出具体的实例化构造;同时基于判定的Diffie-Hellman假设的困难性,对上述实例泄露容忍的选择明文攻击安全性进行了证明.与现有相关构造相比,本文方案不仅具有匿名性、泄露容忍性和多接收者等更优的性能,而且当为多个用户生成封装密钥时具有更优的计算效率.

基于模格的密钥封装方案的比较分析与优化

到目前为止,不使用复杂纠错码的基于模LWE LWR问题设计的高效密钥封装方案主要有2类:1)如Kyber,Aigis和Saber直接基于(对称或非对称)模LWE LWR问题设计;2)如AKCN-MLWE和AKCN-MLWR基于密钥共识机制结合模LWE LWR问题设计.一般来说,在满足一定安全性和实现效率的基础上,实际应用中构造的密钥封装方案会通过压缩一些通信比特来达到节省通信带宽的目的.据作者所知,现存文献的关注点一般集中在详细分析对应某具体参数条件下密码体制的安全性,还没有文献系统地分析上述2类构造方式的异同以及采用相同(或不同)压缩函数情况下不同参数选择与错误率的关系.从理论上系统地比较了直接基于LWE LWR构造的密钥封装方案和基于密钥共识机制结合模LWE LWR问题设计的密钥封装方案的异同,并从理论分析和实际测试2方面证明了当采用相同的压缩函数和相同的参数设置时,AKCN-MLWE采用的构造方式要优于Kyber采用的构造方式,而Saber采用的构造方式本质上与AKCN-MLWR是相同的.针对Kyber-1024这一组参数对应的安全强度,还详细分析了3种封装512 b密钥长度的方法.根据理论分析和大量的实验测试,给出了AKCN-MLWE和AKCN-MLWR的新的优化建议和参数推荐,也给出了对于Aigis和Kyber的优化方案(对应的命名为AKCN-Aigis和AKCN-Kyber)和新的参数推荐.