Implementation of 2048-bit RSA Modified Serial Montgomery Modular Multiplication without Transformation for A094358 Modulo Sequence in Field Programmable Grid 

Bagus Hanindhito¹, Nur Ahmadi², Hafez Hogantara³, Annisa Istiqomah Arrahmah⁴, Trio Adiono⁵
Department of Electrical Engineering, School of Electrical Engineering and Informatics
Institut Teknologi Bandung, Indonesia
Email : ¹hanindhito@bagus.my.id, ²nur.el.ahmadi@gmail.com, ³hafez.hogantara@students.itb.ac.id, ⁴annisa.istiqomah@students.itb.ac.id, ⁵tadiono@stei.itb.ac.id

Abstract—Public key cryptographic or asymmetric cryptography is a cryptographic algorithm that is used for secure data communication and exchange. This cryptographic algorithm uses two separates key, the private key which is kept safely and securely, and a public key which is distributed publicly. These two keys guarantee that people can encrypt their message using public key so that other people cannot see the encrypted message unless they have the private key to be used in the decryption process. With some mathematical formula, the private key cannot be generated easily from public key because its time complexity to do a calculation can reach hundreds of year using today’s computer power. Without knowing the private key, no people can decrypt the message which makes these methods of encryption looks promising to be used.

RSA (Rivest, Shamir, Adleman) is one of the asymmetric cryptography algorithm that is widely used by people around the world to encrypt data in the communication system. RSA algorithm consists of generates private key and public key elements by multiplying two large prime numbers. The time complexity to factorize the product of two large prime numbers is very high and virtually cannot be done using today’s computation power. One important step in RSA encryption or decryption process is its modular multiplication which is relatively expensive and time-consuming to be implemented in hardware.

This paper will describe our proposed design for modular multiplication architecture using serial montgomery multiplication to be implemented as a part of RSA encryption system. By limiting our modulo, that is the modulo that has a sequence of A094358, we can develop very simple and very fast modular multiplication hardware. Moreover, our modular multiplication is mainly aimed at 2048-bit RSA encryption. As a prototyping process, we will implement our design in FPGA. We also give an analysis on the implication of having limited modulo in RSA Encryption compared to conventional RSA Encryption.

Index Terms— RSA, Modular Multiplication, Montgomery Algorithm, Sequence of A094358, FPGA.