论文部分内容阅读
量子计算技术的发展对基于大整数因子分解、离散对数等问题具有交换代数结构的密码体制(如RSA、ECC和EIGamal密码)构成威胁,因为量子Shor算法能够在多项式计算复杂度内求解离散对数问题和大整数因子分解问题.为此,具有抗量子计算性质的公钥密码受到了广泛关注.目前提出的具有抗量子计算攻击潜力的公钥密码体制,主要有基于格中困难问题的公钥密码体制,基于Hash函数的公钥密码体制,基于纠错编码中困难问题的公钥密码体制以及多变量二次多项式(简称MQ)公钥密码体制等类型.由于矩阵运算效率高并且矩阵运算具有非交换属性.将格密码,纠错码密码以及MQ密码为研究对象,主要研究其中的基于矩阵的公钥密码体制,是一个备受关注课题.为了减少公私钥的大小,更有效的执行Diffie-Hellman类型的公钥密码体制,Kahrobaei等人基于自同构群扩展,于2013年将一般矩阵群环作为平台并且于2014年将有限域上的矩阵群作为平台分别提出了一个全新的HKKS密钥交换协议.针对基于有限域上矩阵群的HKKS密钥交换协议,我们进行了密码分析,提出了 4种攻击方法,分别是:结构攻击方法,线性化方程组攻击方法,超定多变量方程组攻击方法和离散对数方法攻击并且分别给出了对应的算法描述和有效性分析.通过分析可知:(1)结构攻击算法是确定性算法,能够在计算复杂度O(n2ω)内获得共享密钥,其中n是矩阵H的阶数,ω≈2.3755.(2)线性化方程组攻击和超定多变量方程组攻击都利用 Halmiton-Caylay 定理将 HKKS 协议中私钥矩阵对(Ha,(HM)a)和(H-a,(HM)a)进行线性表示,采用线性方程组求解和XL算法求出一个相应的等价私钥矩阵进而计算共享密钥,这两种攻击方法的计算复杂度分别是O(nω+1)和O(n2ω).(3)当矩阵H(或者是矩阵HM)的特征多项式可约时,离散对数方法利用伴侣矩阵的性质分析P-HKKS问题进而求出该协议的私钥(a或者b),该分析方法的计算复杂度是O(n4).同时,本文将结构攻击方法,线性化方程组攻击方法,超定多变量方程组攻击方法应用到一般矩阵群环上的HKKS协议,这三种攻击方法也分别能够在多项式计算复杂度内得到共享密钥.与ACNS 2014会议上提出的线性代数攻击方法相比,结构攻击方法是确定性算法并且线性化方程组攻击的计算复杂度最低.计算能力有限的设备(如移动手机,智能卡等)中需要特殊的处理器,为了避免大整数的算术操作,Raulynaitis等人提出的一个基于分解问题的非对称密码协议.针对该协议,我们进行密码分析.首先提出了一个计算复杂度为O(n2ω)的代数攻击方法,攻击成功的概率趋近于1.然后对攻击方法进行算法算法描述和有效性分析,实验结果表明我们攻击方法的正确性.最后我们提出了一个修正方案,同时对修正方案也进行了安全性分析.为了抗量子算法攻击,基于非交换代数结构出现在现今的密码学阶段.一批基于非交换群上困难问题的密码体制被提出,如基于多项式对称分解问题的公钥密码体制,基于不变交换族问题的公钥密码体制.针对这类密码体制,我们对其进行密码分析,提出了多种多项式计算复杂度的代数攻击方法.分析结果表明,这些方案能够以最低的计算复杂度O(nω+1)被攻破,并通过攻击方法的算法描述和实验验证我们密码分析的有效性.