The Research On Parallel Algorithms Of Knapsack Cryptosystem And Elliptic Curve Cryptography

With the rapid development of informatization and internet,information security becomes more and more vital. The public key cryptosystem or the asymmetric cryptosystem is an important way to implement and ensure information security. The knapsack public key cryptosystem based on NP completeness problem and the elliptic curve cryptography (ECC) based on discrete logarithm problem (DLP) are two significant ones, which plays an crucial role in the development and research of computer cryptology. In the thesis a parallel algorithm for knapsack problem in the knapsack cryptosystem and that of selecting the base point of ECC over GF(p) are studied in order to improve the speed of encryption and decryption.After the existing algorithms for knapsack problem and selecting the base point of ECC over GF(p) are deeply analyzed, a parallel algorithm for knapsack problem and that of selecting the base point of ECC are respectively proposed. The proposed algorithm for knapsack problem is based on MIMD. The sort algorithm by sampling is introduced in the sorting stage. The stages of generating subset-sum and searching are also optimized. Theoretic analyses and experimental results on cluster-based IBM P690 supercomputer show that the improved algorithm definite decreases the communication cost, that it has good load balance and memory locality of reference. Its parallel efficiency can be over 60% when solving the larger scale knapsack ( n≥40). The improved parallel algorithm for selecting the base point of ECC over GF(p) is implemented by 2m ( m∈N,m≥1) processors, m circular buffers and one shared table, which comprises two sub-algorithms: parallel finding the random points of ECC and parallel judging whether or not the random point is the base point. It is proved by its performance analysis and experimental results that the utilization of processors is increased, that all processors have better load balance. Therefore the efficiency of computing scalar multiplication is heightened. When the ratio of the execution time of point additions to that of point doublings is 3 during computing scalar multiplication, the parallel efficiency of the proposed algorithm could be best, 90%.