This report presents the RSA encryption and decryption schemes and discusses several methods for expediting the computations required, specifically the modular exponentiation operation that is required for RSA. A hardware implementation of the CIOS (Coarsely Integrated Operand Scanning) algorithm for modular multiplication is attempted on a XILINX Spartan3 FPGA in the TLL-5000 development platform used at the University of Texas at Austin. The development of the hardware is discussed in detail and some Verilog source code is provided for an implementation of modular multiplication. Some source code is also provided for an RSA executable to run on the TLL-6219 ARM-based development platform, to be used to generate test vectors. / text

This thesis is the real time implementation of the new, unified field, dual&ndash / radix Montgomery modular multiplier architecture presented by SavaS et al, for performance comparison with standard Montgomery multiplication algorithms. The unified field architecture operates in both GF(p) and GF(2n). The dual radix capability enables processing of two bits of the multiplier in every clock cycle in GF(2n) mode, while one bit of the multiplier is processed in GF(p) mode. The new architecture is implemented in a Xilinx FPGA on the custom printed circuit board. The windows user interface is developed in Borland Builder environment and the ethernet interface is implemented by Ubicom IP2022 controller. The algorithms are compared from operating clock frequency, silicon area cost and multiplication time perspectives. The new architecture multiplies two times faster in GF(p) and four times faster in GF(2n), compared to the previous architectures as expected. The operand length is increased from 8 bits to 1024 bits, with the compromise of decreasing the operating clock frequency from 150 Mhz down to 15 Mhz.

In this paper, new software and hardware designs for the NTRU Public Key Cryptosystem are proposed. The first design attempts to improve NTRU's polynomial multiplication through applying techniques from the Chinese Remainder Theorem (CRT) to the convolution algorithm. Although the application of CRT shows promise for the creation of the inverse polynomials in the setup procedure, it does not provide any benefits to the procedures that are critical to the performance of NTRU (public key creation, encryption, and decryption). This research has identified that this is due to the small coefficients of one of the operands, which can be a common misunderstanding. The second design focuses on improving the performance of the polynomial multiplications within NTRU's key creation, encryption, and decryption procedures through hardware. This design exploits the inherent parallelism within a polynomial multiplication to make scalability possible. The advantage scalability provides is that it allows the user to customize the design for low and high power applications. In addition, the support for arbitrary precision allows the user to meet the desired security level. The third design utilizes the Montgomery Multiplication algorithm to develop an unified architecture that can perform a modular multiplication for GF(p) and GF(2^k) and a polynomial multiplication for NTRU. The unified design only requires an additional 10 gates in order for the Montgomery Multiplier core to compute the polynomial multiplication for NTRU. However, this added support for NTRU presents some restrictions on the supported lengths of the moduli and on the chosen value for the residue for the GF(p) and GF(2^k) cases. Despite these restrictions, this unified architecture is now capable of supporting public key operations for the majority of Public-Key Cryptosystems.