相关代数密码分析CryptanalysisofMORcryptosystembasedonfinit

CryptanalysisofMORcryptosystembasedonfiniteassociativealgebra姓名：吴万青导师：张焕国教授目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结研究背景什么是量子计算机?量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。主要的量子算法有：Grover搜索算法Shor算法隐藏子群问题算法(HSP)量子计算的并行性使得它优于经典的算法。量子算法的出现不仅威胁到现有的公钥密码，且丰富了密码学的理论研究。研究背景为什么研究抗量子计算公钥密码?Grover搜索算法对公钥密码的威胁：它的复杂性是亚指数的，即O(N1/2)；对于密码的破译而言,Grover搜索算法的作用相当于把密码的密钥长度减少一半.这已对现有的密码体制构成相当大的威胁,抵御方法是增加密钥长度至少一倍；具有通用性,既可攻击对称密码又可攻击公钥密码.研究背景为什么研究抗量子计算公钥密码?Shor算法对基于交换群公钥密码存在威胁Heauregard指出在N=2k位量子计算机上可以有效地求解k比特位大整数分解问题。例：2048位量子计算机破译1024位RSA密码[2]。Proos指出在N=5k+8k1/2+5logk量子位的量子计算机上可有效地求解k比特椭圆曲线离散对数问题。例：1448位量子计算机破译256位椭圆曲线密码[1]。[1]ProosJ,ZalkaC.Shor’sdiscretelogarithmquantumalgorithmforellipticcurves.QuantumInformationandComputation,2003(3):317-344.[2]DarrelHankerson,AlfrendMenezes,ScottVanstone,GuidetoEllipticCurveCryptography,Springer,2004.研究背景Shor算法扩展到隐藏子群问题(HSP)如果H是非交换群G的正规子群，那么弱傅里叶实验能够成功实现[1]。话句话，存在有效的量子算法寻找任意群的正规子群。凡是可归结到Abelian隐藏子群问题(AHSP)上的公钥密码都不能抵抗量子计算的攻击。[1]ChildsAM,DamWV.QuantumAlgorithmsForAlgebraicProblems.Rev.mod.phys,2010,82(1):1-52.为什么研究抗量子计算公钥密码?但是，对一般非交换群没有有效的算法解决隐藏子群问题。即，基于非交换群的公钥密码被认为是抗量子的。研究背景基于非交换群公钥密码的研究现状自1999年，隐藏子群问题提出以后，出现了许多基于非交换群的公钥密码体制。作者密码群Ko-Lee(CRYPTO2000)辫群Paeng(CRYPTO2001)内自同构群Lempken(JournalofCryptology2009)非交换群Magliveras(CommunicationsinAlgebra2012)非交换群研究背景基于非交换群公钥密码的研究现状本文攻击MOR方案正是在此背景下提出的。它可以看做是ElGamal方案在自同构群上的模拟。下面对已有的攻击MOR方案进行小结。目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结MOR方案介绍设{si}是非交换群G的生成集，Aut(G)是G的自同构群。给定任意的群元素g=s1…sn，则f(g)=f(s1)…f(sn)，f∈Aut(G)。MOR加密算法输入：f，fx，m；输出：c第一步：任意选数y计算fxy；第二步：分别计算fxy(m)，fy，并发送c=(fxy(m)，fy)给接收方。MOR解密算法输入：c输出：m第一步：计算(fy)-x；第二步：计算m=(fy)-xfxy(m)。MOR方案最初建立在内自同构群上，随后被作者推广到自同构群上。该方案被视作ElGama的模拟。稳定子群与隐藏子群问题稳定子群：设任意群G作用在集合S上，对任意的x∈S，集合{g∈G|gx=x}是G的一个子群，成为稳定子群Hx。性质：对于群G在集合S上的作用，稳定子群构成群G的正规子群。结论：寻找群G的稳定子群是一个隐藏子群问题。量子算法：Childs在文中指出存在有效的量子算法求解含有正规子群的隐藏子群问题[1]。[1]ChildsAM,DamWV.QuantumAlgorithmsForAlgebraicProblems.Rev.mod.phys,2010,82(1):1-52.目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结量子算法的提出[1]刘绍学.环与代数.科学出版社,1983.•问题的提出：–在数学理论中，任意的群G都可以诱导出一个结合代数F[G][1]。在初始的MOR方案中，群G可以嵌入到一个结合代数中。若f∈Aut(G)且满足线性关系，那么f∈Aut(F[G])。–提出基于结合代数的MOR的公钥算法。•问题解决的思路：–设L是有限结合代数。求出Aut(L)的维数。分别计算dimIm(f)和dimKer(f)，组合得到dimAut(L)=dimIm(f)+dimKer(f).–利用求解离散对数的量子算法恢复MOR公钥的私钥。量子算法的提出目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结算法的分析•dimIm(f)的计算：–在文中，证明了Im(f)=Stabcomp(H,I)(g+B2(H,I))，其中g∈Z2(H,I)。–利用量子算法求出dimIm(f)。•dimKer(f)的计算：–在文中，证明了Ker(f)≌Z1(H,I)。–利用计数定理求出dimKer(f)。正确性证明•密钥恢复：–将结果组合得到dimAut(L)=dimIm(f)+dimKer(f)。–利用量子算法恢复出密钥。算法的分析•算法的主体需要两次稳定子群的计算和一次离散对数的计算。•设结合代数L=H+I的维数是n，其中n=dH+dI。不失一般性，令素数p2k，在算法3中所以，稳定子群计算的时间复杂性是O(kn2)。另外，计算离散对数的时间复杂性是O(n2)。算法的复杂性分析•于是攻击基于结合代数的MOR方案的时间复杂性是O(n2)。目录研究背景MOR公钥方案介绍量子算法的提出算法的分析总结总结•在本文中，我们将MOR公钥密码推广到结合代数上。•如果映射f∈Aut(L)，MOR方案的私钥是不安全的。•本文提出了一个多项式时间的量子算法攻击基于结合代数的MOR公钥密码方案。•为了设计安全的公钥密码方案，不能使用线性变换。致谢感谢各位老师给予指导！