基于自组装算法破译rsa公钥密码系统

《基于自组装算法破译rsa公钥密码系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第３９卷第２期华中科技大学学报（自然科学版）Ｖｏｌ．３９Ｎｏ．２２０１１年２月Ｊ．ＨｕａｚｈｏｎｇＵｎｉｖ．ｏｆＳｃｉ．＆Ｔｅｃｈ．（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｆｅｂ．２０１１基于自组装算法破译ＲＳＡ公钥密码系统程珍１２３许进周康（１浙江工业大学计算机科学与技术学院，浙江杭州３１００２３；２北京大学信息科学技术学院，北京１００８７１；３武汉工业学院数理科学系，湖北武汉４３００２３）摘要研究了如何利用自组装技术对公钥密码系统ＲＳＡ进行密码分析，提出了破译ＲＳＡ公钥密码系统的自组装算法．创建３个子系统，包括非确定性指派子系统

2、、乘法子系统和比较子系统，在此基础上建立自组装模型，提出自组装非确定性算法将整数分解为２个素因子的乘积，该方法用常量种类的Ｔｉｌｅ类型在多项式时间内能成功分解整数，且通过其并行计算的特点破译ＲＳＡ密码系统．关键词自组装算法；自组装模型；分解整数；破译；公钥密码系统中图分类号ＴＰ３０１文献标志码Ａ文章编号１６７１－４５１２（２０１１）０２－００１５－０４ＤｅｃｏｄｉｎｇＲＳＡｐｕｂｌｉｃ－ｋｅｙｃｒｙｐｔｏｓｙｓｔｅｍｂｙａｌｇｏｒｉｔｈｍｉｃｓｅｌｆ－ａｓｓｅｍｂｌｙ１２３ＣｈｅｎｇＺｈｅｎＸｕＪｉｎＺｈｏｕＫａｎｇ（１Ｃｏｌｌｅｇｅｏｆ

3、ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ３１００２３，Ｃｈｉｎａ；２ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃｓＥｎｇｉｎｅｅｒｉｎｇａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＰｅｋｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１００８７１，Ｃｈｉｎａ；３ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＰｈｙｓｉｃｓ，ＷｕｈａｎＰｏｌｙｔｅｃｈｎｉｃＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００２３，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＳｅｌｆ－ａｓｓｅｍｂｌｙｔｅｃ

4、ｈｎｏｌｏｇｙｗａｓｓｔｕｄｉｅｄｔｏｃｒｙｐｔａｎａｌｙｚｅｔｈｅＲＳＡ（ｒｉｖｅｓｔ，ｓｈａｍｉｒ，ａｄｌｅｍａｎ）ｐｕｂｌｉｃ－ｋｅｙｃｒｙｐｔｏｓｙｓｔｅｍ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｉｃｓｅｌｆ－ａｓｓｅｍｂｌｙｗａｓｕｓｅｄｔｏｄｅｃｏｄｅｔｈｉｓｃｒｙｐｔｏｓｙｓｔｅｍｂｙｍａｉｎｌｙｃｏｎｓｔｒｕｃｔｉｎｇｔｈｒｅｅｓｍａｌｌｓｙｓｔｅｍｓｗｈｉｃｈａｒｅｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃｇｕｅｓｓｓｙｓｔｅｍ，ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓｙｓ－ｔｅｍ，ａｄｄｉｔｉｏｎｓｙｓｔｅｍａｎｄｃｏｍｐａｒｉｎｇｓｙｓｔｅｍ．

5、Ｔｈｅｎ，ｔｈｅｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄｔｏｆａｃｔｏｒａｎｉｎｔｅｇｅｒｉｎｔｏｔｈｅｐｒｏｄｕｃｔｏｆｔｗｏｌａｒｇｅｐｒｉｍｅｎｕｍｂｅｒｓ．Ｔｈｉｓｍｅｔｈｏｄｃａｎｓｕｃｃｅｓｓｆｕｌｌｙｆａｃｔｏｒｉｎ－ｔｅｇｅｒｓｉｎｐｏｌｙｎｏｍｉａｌｔｉｍｅｗｉｔｈｃｏｎｓｔａｎｔＴｉｌｅｔｙｐｅｓ，ｔｈｅｎｃａｎｄｅｃｏｄｅｔｈｅＲＳＡｐｕｂｌｉｃ－ｋｅｙｃｒｙｐｔｏｓｙｓｔｅｍｂｙｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｏｆｓｅｌｆ－ａｓｓｅｍｂｌｙｍｏｄｅｌ．Ｋｅｙｗｏｒｄｓａｌｇｏｒｉｔ

6、ｈｍｉｃｓｅｌｆ－ａｓｓｅｍｂｌｙ；ｔｉｌｅｓｅｌｆ－ａｓｓｅｍｂｌｔ；ｆａｃｔｏｒｉｎｇｉｎｔｅｇｅｒｓ；ｄｅｃｏｄｉｎｇ；ｐｕｂｌｉｃ－ｋｅｙｃｒｙｐｔｏｓｙｓｔｅｍ［１］Ａｄｌｅｍａｎ首次利用ＤＮＡ计算解决了组合用ＤＮＡ分子来构成自组装Ｔｉｌｅ结构，并利用ＤＸ［５］［６］优化问题，开创了计算科学的一个新领域．以Ｔｉｌｅ结构建立多种复杂的算法模型．ＷｉｎｆｒｅｅＤＮＡ计算为主的生物计算具有超大规模并行计提出利用Ｔｉｌｅ自组装结构进行计算的重要思想，［２］算能力和巨整数据存储能力等优势，使其成为并证明了二维自组装模型有通用计算能力．Ｗｉ

7、ｎ－［７］发展非传统高性能计算的重要途径之一．ＤＮＡ自ｆｒｅｅ等提出线性、发卡和交叉ＤＮＡ自组装分组装是分子计算中很重要的计算方法，是一种由子结构能分别产生正则的、双线性的、上下文无关简单到复杂、从无序到有序、由多组分收敛到单一语言．研究者还用自组装算法构建不同形状的晶［３］［８］组分的不断修正的过程．在不需要任何外部条体机构，生成二进制计数器，创建三角形结［９］［１０］件干预下，自组装算法最终能使小瓦片精确组成构，并利用它们实现任意的逻辑电路．［４］地形较大且复杂的结构．Ｓｅｅｍａｎ首次提出了利本文通过深入分析ＲＳＡ公钥密码系统的特收稿

8、日期２０１０－０１－２６．作者简介程珍（１９８１－），女，博士，Ｅ－ｍａｉｌ：ｃｈｅｎｇｚｈｅｎ０７１６＠１６３．ｃｏｍ．基金项目国家高技术研究发展计划资助项目（２００９ＡＡ０１２４１３）；国