Design And Implementation Of Underlying Finite Field Primitives In Public Key Crypto-System

This thesis explores compact and efcient implementation of arithmetic componentsof public key cryptography on hardware platform over extended binary field. The pre-liminary operations of critic in public key cryto-systems are modular multiplication (fieldmultiplication) and modular inverse (multiplicative inverse). Efciency of a cryptographiccoprocessor is largely afected by the performance of these underlying finite filed primi-tives. The work presented in this thesis contributes in efcient algorithms design by utilizinghardware resources from ASIC or FPGA platform. Subsequently, these ideas are capturedin Verilog HDL and implemented in FPGA platform to demonstrate the efciency of theproposed method. It is aimed such work could be a reflection of hardware oriented algo-rithm design and analysis and facilitate in subsequent design exploration for cryptographiccoprocessors.To begin with, a fully parallelized and scalable RNS Montgomery multiplier overbinary field is presented in this thesis. By generalizing the RNS Montgomery Multiplication(RNS MM) and pseudo-Mersenne-like numbers, we are able to obtain a considerably highspeed in our FPGA implementation experiments with acceptable circuit area and modestcritical path delay. Furthermore, this design can be easily scalable by adjusting a variety offield sizes and field polynomials.In addition, this thesis develops a new multiplicative inverter over binary field withbetter time-area tradeof. By exploiting normal base representation over extended bina-ry field and Ito-Tsujii algorithm (ITA), a considerably high speed in our implementationexperiments is obtained. Meanwhile, ITA is further generalized into a fully parallelizedversion in favor of computing speed.Finally, a new architecture is proposed to provide high processing speed for RSA keygeneration on embedded platform with limited processing capacity in this thesis. ResidueNumber System (RNS) is introduced to accelerate RSA key pair generation. A cipherprocessor based on Transport Triggered Architecture (TTA) is proposed to realized theparallelism at the architecture level. Moreover, division procedure during the sieve functionis circumvented, reducing the expense of hardware implementation remarkably.