Abstract
In this dissertation, bit-level systolic arrays for RSA public key cryptosystem are designed based on improved Montgomery's algorithm. The improved Montgomery's algorithm guarantees that the partial products in all modular multiplications fall in the range [0,2^{n+1}), and hence the post adjustment needed in the Montgomery's algorithm is removed. Since the post adjustment in the original algorithm is removed, the improved algorithm leads to both simpler architecture and better performance. An RSA cryptosystem chip was designed and simulated, which implements a 512-bit RSA cryptosystem. The time to calculate a modular exponentiation is about 2n^2 clock cycles,where n is the word length, and the clock cycle is roughly equal to the delay time of a full adder. The utilization of the multiplier is 100% by interleaving the square and multiplication in modular exponentiation. Moreover, local interconnection, regularity, and modularity make the proposed architecture suitable for VLSI implementation. Furthermore, we propose a radix-4 modular multiplication algorithm based on Montgomery's algorithm, and a radix-4 cellular-array modular multiplier based on Booth's multiplication algorithm. The radix-4 modular multiplier can be used to implement fast RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than the cellular-array modular multiplier based on the original Montgomery's algorithm. The time to calculate a modular exponentiation is about n^2 clock cycles. For the purpose of hierarchical system test, an IEEE 1149.5 Module Test and Maintenance (MTM) Bus Slave module interface core is presented, which is used for direct access from the system bus to the IEEE 1149.1 chip-level or on-chip buses to facilitate hierarchical system test and diagnosis. The hierarchical test methodology also is presented, which is applicable to the system-on-chip environment. All the standard 1149.1 instructions, such as SAMPLE/PRELOAD, EXTEST, BYPASS, and even RUNBIST, can be performed within three 1149.5 Read/Write-Data message cycles. The messages are transmitted between the MTM-Bus Master module (M-module) and the Slave module (S-module). We adopt the Full TAP Control method to activate the 1149.1 Boundary-Scan paths via the 1149.5 MTM-Bus. Our S-module interface circuit implements 16 CORE commands and one Read/Write Data command. It has been prototyped using an FPGA chip and implemented by a full-custom chip. Hierarchical test of multiple 1149.1 compatible boards has been experimented and verified.