Efficient hardware architecture for scalar multiplications on elliptic curves over prime field

摘要

Suitable cryptographic protocols are required to meet the growing demands for data security in many different systems, ranging from large servers to small hand-held devices. Many constraints such as computation time, silicon area, power consumption, and security level must be considered by the designers of hardware accelerators of the cryptogrpahic protocols.ududElliptic curve cryptography (ECC) proposed by Koblitz and Miller, has been widely accepted. It is now considered as one of the best Public-Key Cryptography (PKC) algorithms and provides higher security strength per bit than RSA, with considerably smaller key sizes. For example, a 256-bit ECC can provide the same security strength as 3072-bit RSA. Due to its much smaller key sizes, ECC based crypto-systems are better in terms of bandwidth utilization, power consumption, and implementation cost as compared to the traditional RSA based crypto-systems. However, PKC algorithms, especially ECC are relatively expensive as compared to their symmetric-key counterparts in terms of computation time. It is an open area of research to reduce their computation cost, so that they could be used for secure communication in commercial internet based applications. Efficient implementation of elliptic curve cryptography over several new platforms have been explored in the last few decades.ududThis work presents efficient design strategies to perform elliptic curve scalar multiplication, the fundamental operation in all ECC based crypto-systems. Finite field arithmetic is the bottleneck in the computation of the EC scalar multiplication operation. Especially, finite field multiplication is the most time-critical operation in projective coordinates, a technique which eliminates modular inversion/division from elliptic curve group operations.ududTwo efficient design strategies to perform finite field multiplication are presented. The first design strategy proposes modifications to the interleaved modular multiplication algorithm using radix-4, radix-8 and Booth encoding techniques to reduce the required number of clock cycles to perform a finite field multiplication. However, higher-radix techniques incur longer critical path delay so performance is limited.ududSubsequently, parallel optimization techniques are incorporated in the modified interleaved modular multiplication algorithms which enable concurrent execution of the critical operations. So the higher-radix parallel modular multipliers are optimized in terms of required number of clock cycles and critical path delays. It is observed that using Booth encoding in the parallel modular multipliers can reduce resource requirements with a slight degradation in the speed performance.ududBased on the presented finite field multipliers, low latency flexible architectures to perform elliptic curve point multiplication over general prime field GF(p) is developed. On a system level, standard double-and-add and double-and-always-add techniques are adopted. The implementation results show that the presented elliptic curve scalar multiplier architectures in this work are good trade-offs between performance and flexibility. The presented designs support general prime field so these can be used in many ECC applications.