几类快速公钥密码设计和的分析

《几类快速公钥密码设计和的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要传统的公钥密码算法速度比较慢，这制约了公钥密码的广泛应用。国内外密码学界都在加强快速密码算法的研制与开发，以便使公钥密码能够应用到更广泛的环境中。在快速公钥密码这一研究领域，本文取得了如下成果：(1)找到了一类新的易解背包问题，并用此问题构造了一个背包型加密算法。该算法是第一个基于背包问题的概率加密方案。证明了该算法能够抵抗低密度攻击和联立丢番图逼近攻击等。而且该算法的加解密计算复杂度是二次的。(2)找到了RSA公钥密码算法的一类弱密钥，指出如果RSA数的两个素因子的比值能够被一个小分数有效逼近的话，则RSA数是容易分解的。(3)使用中国剩余定理构造了一个快速公钥加密算法，证明了攻

2、击者重构陷门信息等价于求解两个数论困难问题，即整数分解和联立丢番图逼近问题。(4)对RSA问题进行了推广，提出了广义RSA问题，给出了广义RSA问题与RSA问题之间的联系。并用此问题构造了一个具有双重陷门解密机制的公钥密码算法GRSA．证明了GRSA是单向的当且仅当广义RSA计算问题是困难的，GRSA是选择明文攻击下语义安全的当且仅当广义RsA判定问题是困难的。(5)构造了一个安全性基于两个数学困难问题的公钥密码算法，该算法的安全陛同时基于整数分解和联立丢番图逼近困难问题，而且陔密码算法的加解密计算复杂度是二次的。(6)使用矩阵环上的一个特殊的组合问题构造了一个公钥加密算法，其安全性与

3、整数分解问题有关，但并不直接依赖于整数分解问题，而是依赖于一类特殊的矩阵组合问题。(7)从辫群上求根问题的困难性出发构造了一个数字签名方案，证明了攻击者能够成功地伪造一个签名当且仅当他能够求解辫群上的求根问题。而且从该数字签名方案出发构造了一个基于身份的数字签名方案。(8)对公钥密码算法Naccache-Stern进行了安全性分析，指出该算法的解密可以看作一个群分解问题，并说明了该攻击算法攻击成功的概率依赖于把一个随机的自然数转化成一个光滑数的概率。(9)对2000年ACISP会议上的一个快速公钥密码算法进行了安全性分析，给出了该算法的安全性与联立丢番图逼近问题以及格上的最小向量问题之

4、间的关系。关键词：快速公钥密码陷门背包整数分解辫群联立丢番图逼近格规约AbstractThetraditionalpublic—keycipherssufferfromadrawbackthattheirspeedisrelativelylow，whichhampersthefurtherapplicationsofpublickeycryptographyandalsomotivatesthecryptographiccommunitytodesignfastpublic—keycryptosystems，Intheareaoffastpublic—keycryptography，t

5、heauthorobtainsthefollowingmainresults．(1)Anewkindofeasyknapsack—typeproblemsisfound．Aknapsack—typepublic—keyencryptionschemeisconstructedbasedOiltheproblem．Thisisthefirstprob-abilisticknapsack—typeencryptionscheme，Itisshownthatthecryptosystemissecureagainstlow-densityattacksandthesimultaneousDi

6、ophantineapproxima-tionattacks．Furthermore，thecomputationalcomplexitiesoftheencryptionandthedecryptionalgorithmsofthecryptosystemarequadratic．(2)AweakkeyoftheRSAcryptosystemisfound．ItturnsoutthatthemodulusoftheRSAcryptosystemiseasytofactoriftheratioofthetwoprimefactorsofthemoduluscanbewellapprox

7、imatedbyasmallfraction．(3)Afastpublic-keyencryptionschemeisdevelopedbyusingtheChineseremaindertheorem．Itispointedoutthattheattackermustsolvetwonumber-theoreticin—tractableproblems，namelytheintegerfactorizationandsimultaneous