Architecture Optimizations for the RSA Public Key Cryptosystem: A Tutorial

The Rivest Shamir Adleman (RSA) cryptosystem, named after its creators, is one of the most popular public key cryptosystems. The RSA cryptosystem has been utilized for e-commerce, various forms of authentication, and virtual private networks. The importance of high security and faster implementations paved the way for RSA crypto-accelerators, hardware implementations of the RSA algorithm. This work consists of describing various approaches to implementing RSA crypto-accelerators based on the “textbook” version of the RSA cryptosystem and comparing their area requirements. Many of the techniques described here have applications elsewhere such as in digital signal processing and error correcting codes. This paper presents the four fundamental architectures: the bit- serial squaring architecture, two bit-serial systolic array modular multiplication architectures, and the interleaved modular multiplication architecture.