Research On Cryptanalysis Based On Proving NP=P

Modern cryptography is based on the assumption that there is no effective algorithm to induce the plaintexts from the ciphertexts if the decryption key is unknown. Therefore the existence of the safe encryption algorithm depends on the assumption of P≠NP. If this assumption is not true, that is there exists a polynomial-time algorithm for NP-complete problem, modern cryptograghy would totally collapse according to Cook. In this context, the thesis has done some research on cryptanalysis based on proving P=NP.A new problem named MSP is introduced in literature [14], which Hamilton circuit problem can be polynomial reducible to. This thesis mainly focus on MSP problem and its polynomial-time algorithm which we called it Z-H. The main content of this thesis is as follows:1. This thesis reduces the proof of Z-H algorithm based on literature [14]. By defining new metrics, the thesis divides the giant proof into series of lemmas, which can be proved respectively and merged into a complete proof in the end. The contribution of the new proof is that we divide the giant proof in literature [14] into four parts and then combine them into an integrated proof, in order to make the new proof easy to read and grasp.2. Comparing to literature [14], the thesis improves on Z-H and its basic operators, as well as reduces its time complexity. By defining the structure variables, refining and simplifying algorithm, as well as enhancing the conditions and restrictions of Z-H algorithm, we improve and optimize the Z-H algorithm and its three basic operatos, so the time complexity of Z-H algorithm can be reduced from O(|V|¹5) to O(|V|²·|E|⁴).3. To verify the correctness of Z-H, a system which produces MSP testing examples and a validation program based on back-trace algorithm are designed and implemented in this thesis. The graph generation system can generate random graphs of 100 vertexes automatically, and the probability of repeated testing examples given by the graph generation system is not more than 1/2¹⁰⁰⁰⁰. The system has already completed several millions of testing examples continuously by ZH algorithm and back-trace algorithm respectively. Until now, the results are perfect.4. A large scale problem (|V|=200) is tested by the algorithm proposed in this thesis. Experimental results show that it only costs tens of minutes while no result is produced after several days'running when tested by back-trace algorithm. In fact, according to the theoretical estimation, for some selected examples, the results will not be produced by back-trace algorithm even if the seas go dry and rocks crumble. 5. The thesis realizes the idea how Z-H algorithm works by animation, including the three basic operators: [ES]_u^v, getR(u,v,l), and Comp(ES,v), which is helpful to the algorithm's comprehension and spread.