An improved Montgomery's algorithm for high-speed RSA public-keycryptosystem

摘要

We revise Montgomery's algorithm such that modular multiplicationncan be executed two times faster. Each iteration in our algorithmnrequires only one addition, while that in Montgomery's requires twonadditions. We then propose a cellular array to implement modularnexponentiation for the Rivest-Shamir-Adleman cryptosystem. It hasnapproximately 2n cells, where n is the word length. The cell containsnone full-adder and some controlling logic. The time to calculate anmodular exponentiation is about 2n2 clock cycles. Thenproposed architecture has a data rate of 100 kb/s for 512-b words and an100 MHz clock