Design and implement fast algorithm of RSA decryption using java

Abstract EN

Based on the principle of RSA, RSA cryptosystem using Chinese Remainder Theorem (CRT) and square-multiply method is designed and implemented, including large integer, generation of big primes and computing extended greatest common divisor (EGCD) of big Integer.

The system designed as threads to include the necessary operation to realize operation of computing decryption exponent of RSA algorithm which specifies the number of modular multiplications needed to perform the exponential process and the modulus to determine the size of the intermediate results, hence; make use of the properties stated by the CRT and Fermat's theorem.

This paper focus on increasing RSA speed in the decryption part based on CRT.

The design of a class for generating special prime big Integer to construct a special decryption keys and a class built as a thread to generate special CRT modular exponentiations to construct the decryption keys.

A sequence of squaring and multiplications are used to decrease the time to perform modular exponentiation on each generated prime Big Integer instead of using exponentiation.

A Miller-Rabin probabilistic test is used to run on the Big Integers.

It is used to test an algorithm which generates a random integer with a primly probability at a specific bit-length.

Large random numbers were generated and then a test for primarily using Miller-Rabin was tested.