The 64-Bit Fast Implementation Of RSA Algorithm

At present, the network information security has become increasingly prominent, the urgency of RSA algorithm as an important tool in the field of information security has been widely used and promoted. In protocol communication, RSA as key transmission encryption tool has become the most difficult to decipher the communications security system. In 1976, Diffie and Hellman at Stanford university, based on the discrete logarithm problem (DLP) published titled "New Directions in Cryptography" [15] as public key Cryptography in the first article. In 1977, Rivest, Shamir and Adlemanin the Massachusetts institute of technology based on the theory, put forward a feasible and digital signature scheme can practice [12], along with the people of the project, its security and performance is people’s consistent affirmation. Hence named after three people for RSA,RSA has become one of the most popular public key cryptosystems. In order to enhance the security of RSA, the need to continually expand the scale of the key, but the bigger keys, such problems as its operation speed and efficiency will be lower. In 2011, the official is recommended to use RSA N size is 2048. As a result, effectively improve the RSA cryptographic algorithm of computing speed has become one of hot issues.This article mainly discusses the mathematical background involved in the public key cryptosystems. The multiplication of large numbers, modular multiplication and modular exponentiation problems are studied. In the current popular 64 words long operating systems, with 232 and 2s4 as basic programming realized each algorithm RSA operations involved in the program, and in the process of implementation multiplication of large numbers, the traditional method are compared with those of the efficiency of Karatsuba algorithm. Especially in the Karatsuba algorithm implementation, we test out the critical value d0, when the word length is 32, the product ofN is2048, d0 is 32; when the word length is 64, the product of N is 2048, d0 is 16, but the product of N is 8092, dois 64. At the same time, this paper determined, when a computer word length can be divided exactly by d0 and the quotient is the smallest, most computing efficiency is highest.In addition, this paper also discussed the RSA algorithm parameters generated by the specific methods. This paper discusses the Montgomery modular multiplication and the optimized algorithm, and the combination of exponential algorithm and Montgomery, test environment and test results are given, using C language to realize the running of the algorithm, and compiles dynamic libraries.