In this paper, the authors present a new structure to develop 64-bit RSA encryption engine on FPGA that can be used as a standard device in the secured communication system. The RSA algorithm has three parts i.e. key generation, encryption and decryption. The algorithm also requires random prime numbers so a primality tester is also design to meet the needs of the algorithm. They use right-to-left-binary method for the exponent calculation. This reduces the number of cycles enhancing the performance of the system and reducing the area usage of the FPGA.