| Public-key cryptography is a fundamental component of modern security infrastructure, enabling applications such as Internet e-commerce and virtual private networks. Particularly popular are public-key algorithms based mathematically on modular exponentiation, such as the RSA cryptosystem. From a performance standpoint, current special and general-purpose hardware adequately address client-side applications due to relatively static design constraints. However, server-side performance demands are mushrooming as a direct result of the burgeoning popularity of network-based services, and current hardware systems are not poised to meet this challenge. In this thesis, several new algorithmic and architectural methods are presented which directly contribute to the goal of maximizing performance in modular-exponentiation-based cryptosystems. Regarding algorithms, a unified, general-radix iterative method is presented for the evaluation of the primitive modular multiplication and reduction operations. This new class of methods is premised on a paradigm apart from iterative division, and efficiency gains are thereby achieved due to the elimination of quotient evaluation. Fine-grain parallel methods for modular multiplication are also introduced based on both bi-directional and uni-directional evaluation. Hardware architecture is addressed through the specification of new scalable design methodologies for systolic and semi-systolic arrays. Application is made to both binary and high-radix modular multiplication. Finally, the residue number system is exploited, resulting in newly demonstrated parallelism advantages over weighted arithmetic systems implementing massively-parallel public-key cryptography. |
