基于NPC和ECDLP的陷门背包公钥密码体制设计与分析

作     者：罗坤杰 

作者单位：贵州大学 

学位级别：硕士

导师姓名：罗文俊

授予年度：2009年

学科分类：11[军事学] 1105[军事学-军队指挥学] 0839[工学-网络空间安全] 08[工学] 110505[军事学-密码学] 110503[军事学-军事通信学] 

主      题：背包公钥密码 陷门背包 NPC ECDLP 安全分析 

摘      要：基于背包问题的公钥密码算法是密码学历史上最早被设计出来的几个公钥密码算法之一。由于背包密码的快速加解密优势和背包问题是NP完全问题,很长一段时间内背包算法受到普遍的关注。自从Merkle和Hellman提出第一个背包算法以来,密码学界提出了很多背包型加密算法。然而,这些背包算法易于遭受低密度子集和攻击、GCD攻击、联立丢番图逼近攻击以及正交格攻击等。 根据公钥密码体制所依赖的困难问题,大多数公钥密码体制可以分为两大类:一类是建立在数论问题基础之上,另一类则以背包问题为基础。这两种类型的公钥密码体制各有利弊。基于数论难题的公钥密码系统保密性较强,但加、解密速度比较慢;基于背包问题的公钥密码系统的加、解密速度较快,但随着各种攻击的出现,其安全性似乎越来越得不到保障。基于此,为了兼顾加、解密算法的速度和安全性,本文对基于背包问题的现有公钥密码算法和GF(p)上椭圆曲线密码体制进行了深入的研究,本文所做的主要工作与创新处如下: 1.对背包型公钥密码体制的研究状况进行了系统的研究,总结出了背包型公钥体制存在的问题。 2.认真学习椭圆曲线密码体制的相关知识;研究了椭圆曲线上的基本算法及椭圆曲线的基本密码学性质、有限域的确定、安全椭圆曲线的选取算法以及明文映射到椭圆曲线上的算法等。 3.提出三种基于NP完全问题的背包公钥密码体制方案。三种方案的安全性是基于背包的难解性以及分解两个大素数的积的难解性。方案1是一个加密/解密都很快的系统,缺点是公钥的尺寸依赖于所需要的安全水平;由于方案1密钥量较大,所以我们提出了方案2,该方案仅仅改变私钥且采用一列超递增向量代替可逆矩阵,减少了密钥尺寸;最后,在对前面两种方案进行优化的基础上提出了方案3,该方案中的矩阵ε利用了方案1中的线性性来仔细隐蔽了超递增向量从而提高了该方案的安全性。 4.提出一个基于椭圆曲线对数问题的背包公钥密码体制。通过选择适当的参数,就能控制在ECC中元素的数量与它们的比特大小,这对掩饰脆弱的背包起到很好的效果。利用现有的对椭圆曲线密码体制的攻击算法分析了对所提出的密码体制方案的可行性和安全性。