后量子密码算法的侧信道攻击与防御综述

为了解决量子计算对公钥密码安全的威胁,后量子密码成为密码领域的前沿焦点研究问题.后量子密码通过数学理论保证了算法的安全性,但在具体实现和应用中易受侧信道攻击,这严重威胁到后量子密码的安全性.基于美国NIST第2轮候选算法和中国CACR公钥密码竞赛第2轮的候选算法,针对基于格、基于编码、基于哈希、基于多变量等多种后量子密...     

CRYSTAL-KYBER硬件设计优化空间探索

公钥密码学对全球数字信息系统的安全起着至关重要的作用。然而,随着量子计算机研究的发展和Shor算法等的出现,公钥密码学的安全性受到了潜在的极大的威胁。因此,能够抵抗量子计算机攻击的密码算法开始受到密码学界的关注,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)发起了后量子密码(Post-quantum cryptography,PQC)算法标准全球征集竞赛。在参选的算法中,基于格的算法在安全性、公钥私钥尺寸和运算速度中达到了较好的权衡,因此是最有潜力的后量子加密算法体制。而CRYSTALS-KYBER作为基于格的密钥封装算法(Key encapsulation mechanism,KEM),通过了该全球征集竞赛的三轮遴选。对于后量子密码算法,算法的硬件实现效率是一个重要评价指标。因此,本文使用高层次综合工具(High-level synthesis,HLS),针对CRYSTALS-KYBER的三个主模块(密钥生成,密钥封装和密钥解封装),在不同参数集下探索了硬件设计的实现和优化空间。作为一种快速便捷的电路设计方法,HLS可以用来对不同算法的硬件实现进行高效和便捷的探索。本文利用该工具,对CRYSTALS-KYBER的软件代码进行了分析,并尝试不同的组合策略来优化HLS硬件实现结果,并最终获得了最优化的电路结构。同时,本文编写了tcl-perl协同脚本,以自动化地搜索最优优化策略,获得最优电路结构。实验结果表明,适度优化循环和时序约束可以大大提高HLS综合得到的KYBER电路性能。与已有的软件实现相比,本文具有明显的性能优势。与HLS实现工作相比,本文对Kyber-512的优化使得封装算法的性能提高了75%,解封装算法的性能提高了55.1%。与基准数据相比,密钥生成算法的性能提高了44.2%。对于CRYSTALS-KYBER的另外两个参数集(Kyber-768和Kyber-1024),本文也获得了类似的优化效果。     

面向格密码的能耗分析攻击技术

量子计算的飞速发展对传统密码的安全性带来巨大挑战,Peter Shor提出的量子计算模型下分解整数和计算离散对数的多项式时间算法对基于传统数论难题的密码系统构成了威胁.美国国家标准与技术研究院(NIST)于2016年开始征集后量子公钥密码算法标准,其中,大多基于格、基于哈希、基于编码、基于多变量这四种密码体制,而基于格的密码体制在其公钥尺寸、计算效率和安全性方面具有更好的平衡性,所占比例最大.然而,格密码的实现在实际环境中易遭受能耗分析攻击(Power Analysis Attacks).能耗分析攻击是利用密码设备运行过程中产生的功耗、电磁等信息,攻击者建立这些旁路信息与密码算法中间值之间的联系从而恢复密钥等敏感信息.自从能耗分析攻击出现以来,该类攻击手段严重威胁了密码系统的安全.随着量子计算的发展,后量子密码的安全性日益成为密码研究的热点,特别地,近期NIST公布了最新轮的后量子密码算法,作为占据比例最多的格密码,其侧信道安全性也受到了学术界的广泛关注.本文针对格密码的能耗分析攻击技术从攻击模型、攻击目标、攻击条件开展研究,分析了面向格密码的攻击原理、格密码的各个算子的侧信道安全性,...     

基于编码的后量子公钥密码研究进展

基于编码的公钥密码由于能抵抗量子攻击和美国NIST后量子公钥密码算法的征集而受到越来越多的关注。本文主要围绕最近的基于编码的NIST抗量子攻击公钥密码征集算法,梳理基于编码的公钥方案具有的特点,即三种加密方式,三种重要的参与码类,三种安全性基于的困难问题,为对这方面有兴趣的科研人员提供一篇综述性论文。     

基于格陷门的高效密钥封装算法

量子计算机的深入研究已经威胁到基于离散对数和大整数分解问题的传统公钥密码,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)于2017年开始了后量子密码算法征集,希望从全球提交的算法中评选出可以代替传统公钥密码的后量子公钥密码标准。在征集的后量子密码算法中,基于格的密码算法占比最多,基于格的密码算法具有抵抗量子算法攻击、困难问题存在“最坏情形”到“平均情形”的安全归约、计算简单等优势,是后量子密码算法中最具应用前景的密码算法。目前为止,提交的基于格的密钥封装算法均需要去随机化、误差采样等操作。去随机化即将底层概率性加密算法,通过引入随机喻言机模型(Random Oracle Model,ROM),将加密算法转化为确定性算法,以实现量子随机喻言机模型下的安全归约。误差采样指模空间上的离散高斯采样,在基于格的公钥加密中,通常需要特殊的算法设计,以满足加密算法性能与安全性需求。去随机化和误差采样操作既降低了算法运行效率,又增加了遭受侧信道攻击的风险。本文基于格的单向陷门函数,设计并实现了高效密钥封装算法,算法避免了去随机化和误差采样等操作,从算法设计层面提升了方案的效率。首先,本文提出了针对密钥封装算法设计场景的格上单向陷门优化技术,显著减小了格陷门的长度;其次,基于优化的格上陷门单向函数,构造了高效的量子随机喻言机模型(Quantum Random Oracle Model,QROM)下选择密文攻击不可区分安全(Indistinguishabilityagainst Chosen Ciphertext,IND-CCA)的密钥封装方案;最后,对密钥封装方案进行了攻击分析和实用参数设置分析,并对方案进行了软件实现和性能分析。     

迈向量子安全：后量子密码迁移研究与思考

量子科技的飞速发展使得大规模量子计算机的实现只是时间问题,一些量子算法的提出(如Shor、Grover、Simon)使得对现代密码体制(公钥密码和对称密码)实施量子计算攻击成为可能,从而严重威胁经典密码的安全。为提升密码系统抵抗量子计算攻击的能力,以格密码为代表的后量子密码(PQC)算法得到广泛关注和研究。从经典密码算法到PQC的迁移是密码系统实现量子安全的有效路径。首先,该文调研了NIST,ETSI及其他组织和学者提出的PQC迁移路线,总结起来,就是以NIST为代表的替换方案、以ETSI为代表的二次加密方案以及其他混合加密方案三种迁移路线;其次,针对PQC迁移过程,从迁移目标、迁移准备、迁移实施三个环节介绍了迁移策略;此外,为了促进PQC迁移的顺利高效实施,提出了需要考虑的迁移评估要素,包括资源投入、时间成本、业务风险、维护成本、用户体验、商业影响六个方面;最后,提出PQC迁移下一步研究方向。总之,文中工作将为PQC迁移的方案设计和高效实施提供有益参考。     

从演化密码到量子人工智能密码综述

如何采用人工智能设计出高强度密码和使密码设计自动化是人们长期追求的目标.中国学者将密码学与演化计算结合,借鉴生物进化的思想独立提出演化密码的概念和用演化计算设计密码的方法,得到可变渐强的密码,减少攻击所需搜索空间的量级.国内外研究表明:演化密码已经在对称密码、非对称密码领域、侧信道攻击以及后量子密码等领域均取得了实际成果：可在1min内设计出一百多个好S盒(8×8),其中一些密码学指标达到最佳值;对于典型的后量子密码NTRU密码体制,演化密码攻击有望降低密钥搜索空间2～3个数量级;部分ECC安全曲线产生基域范围超过NIST现已公布的曲线;并在NIST现已公布的曲线范围内又发现了新的曲线.演化密码已具备人工智能密码的一些特征,进一步结合量子人工智能,不仅取得了目前国际上量子计算破译RSA最好实验指标,超过了最新IBM Q系统,如果运行Shor算法的理论最大值,也超过了洛克希德马丁公司采用量子退火破译RSA的最大规模;提出了量子计算机设计密码的原创性理论成果,完成了国际上首次D-Wave 2000Q真实量子计算机密码设计,有望快速产生一系列亚优解,达到一次一密码算法的作用,增强密码系统安全性.     

RAKA:一种新的基于Ring-LWE的认证密钥协商协议

后量子时代,基于格理论的公钥密码被认为是最有前途的抵抗量子计算机攻击的公钥密码体制.然而,相对于格上公钥加密体制和数字签名方案的快速发展,基于格上困难问题的密钥协商协议成果却较少.因此,现阶段如何构建格上安全的密钥协商协议是密码学领域具有挑战性的问题之一.针对上述问题,基于环上带错误学习问题困难假设,采用调和技术构造了一种新的认证密钥协商协议RAKA(authenticated key agreement protocol based on reconciliation technique),该方案采用格上陷门函数技术提供了单向认证功能,并且在Ring-LWE假设下证明是安全的.与现有的基于LWE的密钥协商协议相比,该方案的共享会话密钥减小为2nlogq,效率更高;同时,由于该方案的安全性是基于格上困难问题,因此可以抵抗量子攻击.     

基于BRLWE的物联网后量子加密技术研究

随着量子计算机的发展,现有的公钥加密体系无法保障物联网通信的安全性。后量子加密算法所基于的数学难题目前还不能被量子计算机攻破,因此具备良好的抗量子安全性,尤其是基于格的公钥密码体制,有望成为下一代公钥加密体系的主流。然而,后量子加密算法存在计算量大、存储空间大等问题,如果将其直接应用于物联网终端的轻量级设备中,会降低物联网环境的通信效率。为了更好地保护物联网通信安全,保障物联网通信效率,提出了Sym-BRLWE(symmetrical binary RLWE)后量子加密算法。该算法在基于二进制环上容错学习(BRLWE,binary ring-learning with errors)问题的加密算法的基础上,改进了离散均匀分布上的随机数选取方式和多项式乘法的计算方式,从而满足物联网通信的效率要求,增加了加密安全性防护性措施以保证算法在取得高效率的同时具有高安全性,更加适应于物联网轻量设备。安全性分析表明,Sym-BRLWE加密算法具有高安全性,从理论上能够抵抗格攻击、时序攻击、简单能量分析和差分能量分析;仿真实验结果表明,Sym-BRLWE加密算法具有通信效率高的优势,加密解密效率高且密钥尺寸小,在模拟8 bit微型设备的二进制运算环境下,选择140 bit的抗量子安全级别参数时,相较于其他已有的基于BRLWE的加密算法,同等加密条件下Sym-BRLWE加密算法能够在加密总时间上减少30%~40%。     

AKCN-MLWE算法AVX2高效实现

随着量子计算机的快速发展,经典密码系统面临巨大的威胁.Shor算法可以在量子计算机上多项式时间内分解大整数和求解离散对数,而这两类问题分别对应经典公钥密码系统中的RSA和椭圆曲线密码(ECC)所依赖的困难问题,因此可以抵御量子计算攻击的后量子密码近年来受到广泛的研究.格密码是后量子密码中最为高效且拓展性强的一类密码算法,在未来会逐步替代传统公钥密码算法(RSA、ECC等).256位高级向量扩展(AVX2)指令集是英特尔64位处理器中普遍支持的一类单指令多数据(SIMD)指令集,可用于并行计算.但是,由于格密码结构复杂,在支持AVX2指令集的英特尔64位处理器上难以对格密码方案进行高适配的深度优化.AKCN MLWE算法是我国自主设计的基于模格上容错学习(MLWE)问题的格密码密钥封装(KEM)方案,是中国密码学会举办的公钥密码算法竞赛第二轮的获奖算法.本文基于256位高级向量扩展(AVX2)指令集设计了针对AKCN MLWE算法的高效实现方案,包括以下几个关键优化点:针对多项式乘法,本文结合最优的数论变换(NTT)算法,将NTT的最后一层转换为线性多项式并使用Karatsuba算法进行加速计算,大幅提升计算效率的同时减少了预计算表的空间占用;针对取模运算,本文结合了Barrett约减算法和蒙哥马利约减算法的优势,同时采用延迟约减技术降低取模次数;本文针对所有多项式运算均实现了高度并行化,设计了针对多项式压缩与解压缩的并行算法,进一步提升了实现效率.本文设计的AKCN-MLWE算法AVX2高效实现方案在八核Intel Core i99880H处理器上仅需不到0.04 ms即可完成一次完整的KEM(包括密钥生成、密钥封装和密钥解封装),相比于参考实现提升8.84倍,其中密钥生成提升7.07倍,密钥封装提升7.90倍,密钥解封装算法提升11.78倍.本文提出的AKCN MLWE算法AVX2实现方案在相近经典安全强度下性能优于美国国家标准技术研究所(NIST)后量子密码标准化进程第二轮中众多格密码方案(Kyber、NewHope和Saber等).同时,本文设计的部分优化方案可用于提升Kyber、NewHope等格密码方案的性能.     

Post-quantum cryptography for automotive systems

Automotive systems have become powerful computing platforms with an increasing demand for secure communication. The hyperconnectivity of the Vehicle-to-Everything (V2X) environment drastically increases the attack surface and the need for crypto-agility. In addition, the long lifecycle of automotive products demands that not only current but also future attacks are considered. Thus, empowering automotive devices with efficient, robust, and long-term security solutions is challenging. The foreseeable breakthrough of quantum computers and their threat to traditional cryptography requires that automotive devices are able to efficiently implement quantum secure cryptographic mechanisms, also known as Post-Quantum Cryptography (PQC). One of the most promising PQC approaches is lattice-based cryptography. Among the seven finalists of the NIST third round post-quantum standardization process, five algorithms (three KEM/encryption and two signature algorithms) belong to the category of lattice-based cryptography. While lattice-based cryptography has been previously integrated in general-purpose microcontrollers, their impact on automotive environments has been neglected. To this end, this work presents two contributions. As a first contribution, we provide a performance exploration of four lattice-based KEM/encryption algorithms implemented on the automotive microcontroller AURIX. The exploration includes the three finalists CRYSTALS-KYBER, NTRU, and Saber, together with ThreeBears. Despite ThreeBears was not selected as a PQC finalist, NIST recommended further investigations in this direction due to interesting security and performance characteristics of the algorithm. Our analysis has shown that all of these algorithms can be implemented on the AURIX microcontroller while achieving a competitive performance. As a second contribution, we explore the improvement of the security level of ThreeBears by extending its error correction capability.     

Aigis密钥封装算法多平台高效实现与优化

量子计算技术快速发展带来的新挑战使得后量子密码(post-quantum cryptography, PQC)成为当前密码学界研究热点.基于格的密码方案因其安全高效的特性,已经成为后量子公钥密码的主流之一.Aigis密钥封装算法(Aigis-enc)是我国学者自主设计的基于模格上非对称错误学习(A-MLWE)问题的后量子密码算法,是中国密码学会举办的全国密码算法设计竞赛公钥密码算法一等奖获奖算法之一.为了应对量子攻击,维护国家网络空间的长远安全,为未来国家后量子密码算法标准的制定和实际部署贡献力量,对我国自行研发的优秀后量子密码算法进行优化具有重要意义.工作重点关注Aigis-enc算法在不同平台的实现优化,包含高性能平台的快速并行实现与嵌入式低功耗平台的紧凑实现.具体而言,运用单指令多数据流(single instruction multiple data, SIMD)指令,充分优化了Aigis-enc现有AVX2实现,并提供了其首个ARM Cortex-M4平台的轻量级紧凑实现.实现包含4个关键优化点:降低Montgomery约减与Barrett约减汇编指令数目,提升了约减效率;使用裁剪层数的数论变换并优化指令流水调度,加速多项式乘法运算并减少了预计算表存储需求;提供了多项式序列化与反序列化的并行汇编指令实现,加快了编码解码与加解密过程;结合on-the-fly计算与空间复用优化算法存储空间.实验结果表明：提出的优化技术在8核Intel Core i7处理器上可将Aigis-enc算法原始AVX2实现提升25%,且大幅减少了其在ARM Cortex-M4平台的预计算表存储、代码尺寸与运行堆栈占用,对算法的实际应用有重要现实意义.     

基于编码的抗量子广义签密方案

随着量子计算机的发展以及网络环境的日益复杂,传统的公钥密码为目前的通信环境所提供的安全保障面临着越来越大的威胁,抗量子密码能够有效抵抗量子计算机攻击而受到广泛关注.抗量子密码中的编码密码具有加解密简单、易于操作的特点而成为后量子时代优良的密码方案候选者之一.通过对编码密码进行研究,利用LEDAkem密钥封装机制中对信息进行加密的方法与CFS签名方案相结合,提出了一种基于QC-LDPC码的广义签密方案.新方案可以实现在签名、加密以及签密方案三者之间的自适应转换,由于采用的是LEDAkem的加密方法以及QC-LDPC码,新方案在密钥量方面具有一定优势.通过安全性分析证明新方案满足IND-CPA安全以及EUF-CMA安全,并进一步给出方案转换为IND-CCA2安全的方法,新方案能够适应越发复杂的网络通信,为后量子时代的网络环境提供可靠的安全保障.     

应用于后量子密码的高速高效SHA-3硬件单元设计

随着量子计算技术的高速发展,传统的公钥密码体制正在遭受破译的威胁,将现有加密技术过渡到具有量子安全的后量子密码方案上是现阶段密码学界的研究热点。在现有的后量子密码(Post-Quantum Cryptography,PQC)方案中,基于格问题的密码方案由于其安全性,易实施性和使用灵活的众多优点,成为了最具潜力的PQC方案。SHA-3作为格密码方案中用于生成伪随机序列以及对关键信息散列的核心算子之一,其实现性能对整体后量子密码方案性能具有重要影响。考虑到今后PQC在多种设备场景下部署的巨大需求,SHA-3的硬件实现面临着高性能与有限资源开销相互制约的瓶颈挑战。对此,本文提出了一种高效高速的SHA-3硬件结构,这种结构可以应用于所有的SHA-3家族函数中。首先,本设计将64 bit轮常数简化为7 bit,既减少了轮常数所需的存储空间,也降低了运算复杂度。其次,提出了一种新型的流水线结构,这种新型结构相比于通常的流水线结构对关键路径分割得更加均匀。最后,将新型流水线结构与展开的优化方法结合,使系统的吞吐量大幅提高。本设计基于XilinxVirtex-6现场可编程逻辑阵列(FPGA)完成了原型实现,结果显示,所设计的SHA-3硬件单元最高工作频率可达459 MHz,效率达到14.71 Mbps/Slice。相比于现有的相关设计,最大工作频率提高了10.9%,效率提升了28.2%。     

基于证书的抗泄露的安全加密方案

近期实践表明密码系统容易受到各种攻击而泄漏密钥等相关秘密信息, 泄漏的秘密信息破坏了以前的已证明安全的方案, 因此设计抗泄漏的密码学方案是当前密码研究领域的一个热点研究方向。设计一个基于证书的加密方案, 总的设计思想是使用一个基于证书的哈希证明系统, 这个证明系统包含一个密钥封装算法, 用这个密钥封装算法结合一个提取器去加密一个对称加密所用的密钥, 那么得到的加密方案就是可以抵抗熵泄漏并且是安全的。对方案的安全性分析和抗泄漏性能分析, 表明本方案在抵抗一定量的密钥泄漏和熵泄漏时可以保持安全性。