Parallelization For RSA Cryptanalysis Algorithms And NTRU-11 Algorithms

Parallel computing is mainly used to deal with large and complex computing problems quickly.When parallel computing is used to solve problems,we need to divide the problem first,design a parallel algorithm,and solve the problem finally.There are three ways to design parallel algorithms.(1)Detect,analyze and broaden the inherent parallelism in existing serial algorithms,and parallelize the serial algorithm.(2)Design a new parallel algorithm from the problem itself.(3)Modify the existing parallel algorithm to solve another similar problem.The first way is selected to discuss the parallelization of the problem in this thesis.NTRU-11 scheme and RSA cryptanalysis are used as the research object,based on the previous serial algorithm,the corresponding parallel algorithm is designed.NTRU-11 scheme is designed by Damien and others in 2011,which is based on R-LWE problem and constructed by modifying the ring structure of NTRU scheme.Specific work is as follows:(1)The main operations in NTRU cryptography are polynomial,multiplication.The multiplication is the most time-consuming,complexity is O(N~2),which affects the performance of the system seriously.The number theoretic transformation(NTT)is used in NTRU-11 scheme to optimize polynomial multiplication,which can decrease the number of operations,and reduce the complexity to O(N log N).The parallel structure in Matlab is used to design parallel algorithm for the serial algorithm of NTT,so as to achieve the parallelization of NTT.In order to further enhance the multiplication speed,the parallel NTT is applied to NTRU-11 scheme,and the parallel design of the scheme is realized.In the process of parallel processing,compared with the serial NTT,the algorithm can achieve linear speedup.(2)For RSA parameters cryptanalysis,integer factorization is the most direct method.In familiar the serial algorithm of integer factorization can be parallelized.The parallel algorithm can be designed by dividing or reducing the search range of integer factors.Therefore,the familiar algorithms of integer factorization are selected to discuss the inherent parallelism of these algorithms in this thesis.In addition,combined with the parallel structure in Matlab,parallel integer factorization algorithms can be designed and implemented.The results verify that these parallel algorithms are feasible.After parallel processing,we found the method to increase the efficiency of NTRU-11 scheme and accelerate the RSA cryptanalysis,and designed a efficient parallel scheme.