公钥密码的量子攻击研究现状与展望

近些年,随着量子计算的发展,以Shor算法为首的量子算法展现了对公钥密码体制的严重威胁。研究者们一方面研究量子算法对公钥密码的攻击实现,一方面着手后量子密码算法的过渡迁移。就此议题,首先介绍几类常用的公钥密码算法和相关量子攻击算法。其次,重点介绍Shor算法以及量子优化等算法攻击公钥密码算法的国内外研究现状,特别是对RSA和ECC的攻击实现以及当前存在的困难。最后,结合当前公钥密码量子攻击的研究进展以及后量子密码的发展,对产学研的未来发展规划作出了一些建议与展望。     

一种新的攻击RSA的量子算法

整数分解是数论中一个非常古老的难解性问题,而对于当今世界上最有名且广泛使用的RSA公钥密码体制,其安全性是基于整数分解的难解性的。迄今为止,最有希望破解RSA的方法就是Shor的量子算法。利用RSA不动点性质,基于量子Fourier变换和变量代换,提出了一种新的攻击RSA的量子算法。该算法不需要分解n,而是从RSA密文C中直接恢复其明文M。该算法与Shor算法相比,需要的量子位更少,且成功概率大于1/2。最后将新算法的资源消耗情况与Shor算法的进行了对比。     

量子Shor算法与RSA体制的安全性

一、量子Shor算法众所周知,RSA体制的安全性是建立在大数分解这一难题基础上的,严格说来,也只是涉及到两个大质数相乘所得到的合数。自RSA诞生伊始,人们对其安全性的理论论证就一直未停止过。由于RSA中指数运算保持了输入的乘积结构,这一点令人甚为担忧。近年来越来越多的研究人员对RSA的安全性产生了疑惑。特别是自1994年美国AT&T公司的研究人员Shor 发现了分解由两个大质因数相乘的合数的量子算法。它不仅给量子计算机研究注入了活力,引发了量子计算和量子计算机研究的热潮,同时也使得更多的理论密码学家认识到RSA安全性论证的紧…     

RSA攻击回顾

引言 Diffie 和Hellman于1976年第一次提出了公钥密码体制的观点。1977年，Shamir、Rivest和Adelman提出了第一个也是应用最广的公钥密码算法，即著名的RSA算法。经过20多年的密码分析和攻击，到目前为止，RSA仍然是安全的。由于这一突出贡献，Shamir、Rivest和Adelman获得了2002年的图灵奖。     

针对离散私钥比特泄漏的RSA格攻击方法

RSA算法是目前应用最广泛的公钥密码体制之一,而格攻击是针对RSA体制的一类重要攻击方法。为此,将RSA算法的部分私钥泄漏问题转化为多变元线性同余方程的求解问题,基于同余方程构造出特定的格,利用LLL格基约化算法进行约化,从而以一定的概率求得同余方程的小根。以上述多变元线性同余方程的小根求解技术为基础,提出一种针对离散私钥比特泄漏的RSA格攻击方法。在该方法下,如果RSA算法的公钥参数e=N~β≤N~(1/2),并且私钥d的未知部分N≤N~((1/2)-β),则能以高概率恢复出RSA算法的私钥d。通过NTL包对长度为1024 bit的大整数进行实验,结果验证了该攻击方法的有效性。     

量子计算与量子计算机展望

量子计算和量子计算机的研究是当代信息科学所面临的一个重大科学课题。阐述了量子计算、量子逻辑门的基本概念和Shor算法,指出了当前实现大规模量子计算所遇到的困难和可能的解决办法。     

RSA算法的攻击与防范

作为对典型的公钥密码算法,RSA算法在信息安全领域得到了广泛的应用,但是其安全性却一直是学者们议论的话题。本文首先介绍RSA公钥加密算法的工作原理,对RSA算法的缺陷以及对其所可能遭受的攻击进行分析,最后讨论了针对RSA算法攻击的防范措施。     

基于RSA密码体制的选择密文攻击的研究

本文对RSA加密算法作了简要介绍,并对RSA的选择密文攻击进行了详细的分析,最后总结了使用RSA算法应该注意的几个问题。     

针对RSA算法软件应用的故障攻击研究

原有的RSA故障攻击针对的都是运行在智能卡等硬件上的算法,为研究针对RSA软件实现方式的故障攻击,剖析中国剩余定理软件实现算法,提出针对OpenSSL密码库的RSA算法软件实现的故障攻击算法,给出一种只需要一次错误签名的改进攻击方案。通过仿真实验验证算法的可行性,并给出抵御此类攻击的有效措施。     

抗量子计算公钥密码需求分析与技术路线

本文对国外量子计算机研究进展情况进行了分析,并针对量子计算机对于信息安全的挑战,讨论了国内下一代公钥密码技术的需求、发展思路和技术路线。     

基于RSA公钥密码安全性的研究

RSA是目前最重要的公开密钥密码算法之一。文中介绍了该算法的实现、基本原理等,重点是对其攻击方法和安全性进行分析,相应给出了防止攻击的方法。通过对RSA密码特点以及目前的密码技术发展形势分析,RSA在将来相当一段时期内依旧是应用最广泛的密码算法之一。     

RSA 踪迹驱动指令Cache 计时攻击研究

指令Cache 攻击是基于获取算法执行路径的一种旁路攻击方式.首先,通过分析原有RSA 指令Cache 计时攻击存在可行性不高且能够获取的幂指数位不足等局限性,建立了新的基于监视整个指令Cache 而不只是监视特定指令Cache 的踪迹驱动计时攻击模型;然后,提出了一种改进的基于SWE 算法窗口大小特征的幂指数分析算法;最后,在实际环境下,利用处理器的同步多线程能力确保间谍进程与密码进程能够同步运行.针对OpenSSLv.0.9.8f 中的RSA算法执行指令Cache 计时攻击实验,实验结果表明:新的攻击模型在实际攻击中具有更好的可操作性;改进的幂指数分析算法能够进一步缩小密钥搜索空间,提高了踪迹驱动指令Cache 计时攻击的有效性.对于一个512 位的幂指数,新的分析算法能够比原有分析算法多恢复出大约50 个比特位.     

解决组合公钥共谋攻击和密钥碰撞的新方法

以解决组合公钥体制中共谋攻击和密钥碰撞问题为目的。首先,针对线性共谋攻击,提出了一种新的构造种子矩阵的方法,使得种子密钥和大于基点加法群的阶数,从而使密钥之间不能相互线性表示。其次在密钥的生产过程中,引入系数破坏了层不同和层互斥不同的关系,为解决选择共谋攻击提供了一种有效的方法,同时增强了抵御随机共谋攻击的能力。最后,在密钥产生的流程中,通过公钥对比来避免密钥碰撞,为解决密钥碰撞问题提出了一种新方法。     

应对反应攻击的级联中密度准循环奇偶校验码公钥方案

基于中密度准循环奇偶校验（QC-MDPC）码的McEliece公钥密码（PKC）方案具有较小的密钥量,利于存储,是一类在抵抗量子攻击上发展前景良好的公钥密码体制。然而目前存在一种反应攻击对其安全性产生了较大威胁。攻击者选取特殊的错误图样对大量消息进行加密以获得接收者反馈的译码失败情况,然后通过分析译码失败率与私钥结构的关系从而破解出私钥,该攻击被称为密钥恢复攻击。为应对此攻击,提出了一种将QC-MDPC码与喷泉码进行级联的公钥方案。该方案利用喷泉码的“无码率性”生成大量的加密包来取代反馈重发（ARQ）结构,使攻击者无法获取反馈信息。分析结果表明,所提出的方案能有效抗击密钥恢复攻击,同时还能保证在其他攻击下的安全性。     

RSA算法的安全参数研究

RSA算法是一个非对称密钥加密算法。文章系统地介绍了RSA公钥密码算法的基本原理及利用RSA算法进行数据加密的过程;对RSA公钥密码算法安全参数的选择进行分析,并探讨了安全参数的选择对RSA公钥密码算法的安全性影响及重要性。     

量子密码理论研究进展

21世纪信息空间的开发、利用和对抗无疑成为各国科技发展的战略高点。近年来,量子信息技术的快速发展拓宽了信息理论的研究内容,也给信息科学研究带来了新的机遇与挑战。介绍了量子计算理论对现代密码学的重要影响,建立了量子保密通信模型,给出了几类量子攻击模式。分析了量子密钥分配、量子消息加密和量子数字签名等理论和技术的研究新进展,对未来几类重点研究问题进行了总结和展望。     

Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment

Modern cryptography is based on various building blocks such as one way functions with or without trapdoors, pseudo-random functions, one way permutations with or without trapdoors, etc. In a quantum world some of the main candidates for these building blocks are broken. For instance, the security of the most popular public-key cryptosystem—RSA—is related to the difficulty of factoring large numbers, and is broken (in principle) by a quantum computer. We investigate some of the remaining candidates, and discuss the resulting “Post-Quantum Cryptography” (namely, the resulting “modern cryptography in a quantum environment”).