Research And Implementation Of Public Key Accelerator Library Over GF(p)

With increasing demands on information security, public key cryptography is being moreand more extensively applied in the field of information security. Up to now, RSA algorithm isthe most mature one in both theory and application. However, as the key size of RSA growingwith the speed of calculation, the implementations of RSA suffer from the hardware complexity.Comparing to RSA, Elliptic Curve Cryptography (ECC) is a better choice because it provides thehighest security strength per bit than any other currently exiting public key cryptosystems. But itis a great challenge to implement ECC because its high complexity, especially the ECC overGF(p).This paper proposes a System on Chip (SoC) oriented public key accelerator library overGF(p). The accelerator library can implement different modular arithmetic by reprogramming themicrocode instructions, such as modular exponentiation, scalar multiplication, RSA keygeneration and so on. This method can archive both high speed and small area for simpleapplication which aim at embedded systems. Besides, the clock-gating and input-gating whichare commonly used technique in low power design is used to reduce the energy consumption ofthe public key accelerator library.This paper has following contributions:1. Key generation is one of the difficult problems in RSA cryptosystem. It includes twoparts: prime number validation and secret key calculation. This paper presents an efficient primenumber validation which consists of the trivial division and Miller- Rabin probabilistic primalitytest. Besides, we propose a new algorithm to compute e^-1 Mod 2^|(?)(N)| which is needed in secretkey calculation. The advantage of the new algorithm is that it doesn't contain any modulararithmetic, but shift and subtraction operation.2. Modular multiplication is a core operation in the RSA and ECC cryptosystem. In thispaper, a new Montgomery modular multiplication is proposed, and is well suitable for theimplementation of Carry Save Adder (CSA) architecture. The implementation results showclearly that the proposed hardware of CSA architecture is very efficient: it requires less hardwarearea and achieves a high throughput.3. The choice of coordinate system has a considerable impact on the final speed of thescalar multiplication operation. After extensive research on all kinds of mixed coordinates, amathematical model is proposed to choose the best mixed coordinate. Using this model, the bestmixed coordinates is pointed out for scalar multiplication over the Montgomery domain.Keyword: Public Key Cryptography, Accelerator, Modular Multiplication...