计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (14): 119-124.

• 网络、通信与安全 • 上一篇    下一篇

一个可行的RSA密码破译方法

杜立智   

  1. 1.武汉科技大学 计算机科学与技术学院,武汉 430065
    2.智能信息处理与实时工业系统湖北省重点实验室,武汉 430065
  • 出版日期:2016-07-15 发布日期:2016-07-18

Useful method to decode RSA

DU Lizhi   

  1. 1.College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, China
    2.Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan 430065, China
  • Online:2016-07-15 Published:2016-07-18

摘要: 通过长年研究得到了快速高效的Hamilton路算法。利用多项式规约将3SAT问题转化为对Hamilton路的求解。尽管国际上已有过如何将3SAT问题转化为Hamilton路的方法,但那只是为了证明Hamilton路的NP完全性,因而只要求转化的结果是多项式,而不注重转化效率。为了得到将3SAT直接转化为Hamilton路的高效转化方法,以便有可能通过对后者的高效计算来实现高效计算3SAT,采取用无向图的两个节点模拟3SAT的一个变量,用13个节点的图形结构来模拟3SAT的一个子式的方法,最终实现了上述转化。该转化所需要的节点数及其边数是最优的。将大数的质因子分解转化为对3SAT的求解,从而最终通过求解Hamilton环达到破译RSA密码之目的。

关键词: 非确定性多项式(NP)完全, 多项式规约, Hamilton路, 3SAT, RSA密码

Abstract: It gets a fast algorithm on the Hamilton path. It transforms the 3SAT to the Hamilton path by a polynomial transform. Though there has been some methods to transform 3SAT to Hamilton path, that is only for NPC proof. It is polynomial but not the most efficient. In order to get the most efficient transform from 3SAT to Hamilton path, so as to calculate 3SAT efficiently by calculating the Hamilton path in a possibly good way, this paper uses two vertices to denote a variable in 3SAT, uses a good graph structure which contains 13 vertices to denote a clause in 3SAT, then realizes the above goal. It needs the least number of vertices and edges. It transforms the problem of large number of qualitative factors to 3SAT. So at last, it can decode the RSA by calculating the Hamilton path.

Key words: Non-deterministic Polynomial(NP) complete, polynomial transform, Hamilton path, 3SAT, RSA code