Efficient Hardware Design of Elliptic Curve Point Multiplication Accelerators

Abstract

In recent years, the evolution of technology has broadened the avenues of information sharing. The volume of sensitive and important information being exchanged over the insecuremediumhasincreaseddramatically. Ellipticcurvecryptography(ECC)hasbecomewidelyacceptedasanefficientmechanismtosecureprivatedatausingpublic-key protocols. The pivotal operation within ECC based crypto-systems is scalar point multiplication which is computationally expensive. Point multiplication can be achieved by iterative execution of point addition and point doubling groups operations which in turn are based on finite field arithmetic operations such as addition, subtraction, multiplication and division. These finite field arithmetic operations, especially the finite field multiplication are the bottleneck of any ECC based crypto-system. To reduce the computational cost of point multiplication operation, by optimizing these finite field arithmetic operations, is an active area of research. Efficient hardware implementations of Elliptic Curve Point Multipliers (ECPM) over several new platforms have been in the focal point of major research efforts for the last two decades. Field Programmable gate arrays (FPGA) due to its reconfigurable nature and less development time has become a very popular choice for hardware implementationofcryptographicalgorithms. ECPMarchitecturesonFPGAeitheronlyuseLook Up Tables (LUTs) or have utilized embedded Digital signal processing (DSP) blocks along with the LUTs. LUTs-only based designs are portable designs since they can be translated to any FPGA family or standard cell based Application Specific Integrated Circuits(ASIC).However,existingLUTsbaseddesignsareslowersincetheyarebased on finite field arithmetic components which have longer critical path delay and higher clock cycles consumption. DSP based ECPM designs may offer better performance at the cost of increased area. However, DSP based designs have portability issues. The prime objective of this dissertation is to design LUTs based high speed ECPM architectures. ThebottomlayerFp arithmeticoperationsespeciallytheFp multiplication are first optimized at both circuit level and architectural level. Subsequently, based on these optimized finite field arithmetic primitives, and by devising an efficient schedul ing strategy for elliptic curve group operations, this dissertation achieves high speed hardware architectures to perform elliptic curve point multiplication. Inthefirstcontribution,anovelhighspeedRedundant-Signed-Digit(RSD)basedECPM architecture for arbitrary curves over a general prime field is designed. It is based on a new high speed finite field multiplier architecture which employs different parallel computation techniques at both circuit level and architectural level. As a result of these optimizationstrategies,theproposedmultiplieroffersasignificantreductionincomputation time over the state-of-the-art. An efficient scheduling strategy is devised for PA andPDgroupoperationswhichreducedtherequirednumberofclockcyclesforECPM design. The ECPM architecture designed in this dissertation offers higher speed and lower area-time product than recent state-of-the-art ECPM designs. In the second contribution of this dissertation, an ECPM architecture for low area applications is developed. The ECPM design utilizes fewer resources while maintaining the competitive speed with other state-of-the-art ECPMs. The finite field multiplier developed in this dissertation offers lower area-time product than recent contemporary designs. Basedonthisfinitefieldmultiplierandapipelinedfinitefieldadder/subtractor, an ECPM architecture is designed that offers lower area-time product than recent stateof-the-art ECPM designs. The third contribution presents a high speed ECPM architecture for National Institute of Standards and Technology (NIST) recommended primes. Different strategies such as RSD representation, segmentation and pipelining are used to reduce the critical path delayandrequirednumberofclockcyclesforthefinitefieldarithmeticprimitives. The implementation results demonstrate that the proposed ECPM architecture outperforms other state-of-the-art designs in terms of speed and area-time product metrics. Finally, an ECPM architecture for the Curve448 is developed in the last contribution of this dissertation. Curve448 is recently recommended by the Internet Engineering Task Force (IETF) for future cryptography. The only existing ECPM architecture over the Curve448isaDSPbaseddesignandlacksportability. TheECPMarchitecturedesigned inthisdissertationisthefirstLUTsbasedimplementationfortheCurve448. Thedesign is optimized with a focus on both performance and resource utilization. A comparison with the state-of-the-art ECPM designs shows that ECPM design in this dissertation provides higher speed and can be adopted in time-critical applications.