A parallel processing method for implementing the RSA cryptosystem
Keiichi Iwamura, Tsutomu Matsumoto, Hideki Imai · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1993
Abstract Modular multiplication: R = A · B mod N (where A, B, N, and R are integers) is an essential operation used in public‐key cryptosystems such as RSA, El Gamal, and Rabin. Thus, if high‐speed modular multiplication circuits can be constructed, these cryptosystems can operate at high speeds. In this paper, we show how to construct, with a high‐speed modular multiplication circuit which employs parallel processing methods using systolic arrays, a circuit which performs modular exponentiation by repeated modular multiplication. In particular, we demonstrate its validity by using the RSA scheme as a first concrete example. Since a circuit using the method of this paper as its construction rule has simple and regular structure, it provides an optimal construction of a highspeed RSA chip in VLSI. The method is also applicable for a simple implementation of the RSA scheme with small‐sized chips. In this case, the number of chips needed by this method (the circuit size) allows the practical realization of proportionately higher speeds. Flexibility can be achieved for a change in the number of key bits by a corresponding increase or decrease in the number of chips.