Research On Algorithms And Hardware Implementations For Elliptic Curve Cryptography Over Binary Extension Fields

Elliptic curve cryptography?ECC?has become one of the most popular public-key crypto-graphic algorithms.It has been widely used in network communications,smartcards and terminal devices of Internet of Things?IoT?.This paper focuses on the high-performance hardware implementation of ECC over binary extension fields and makes a thorough study of the finite field arithmetic,scalar multiplication,and the reconfigurable coprocessor.The finite field arithmetic is the cornerstone of each ECC cryptosystem.Inversion is the most complex operation in the finite field and is known to be difficult to parallel.This paper proposes a modified ITA algorithm that allows part of operations to be computed in parallel.The idea is further generalized to inversion with arbitrary addition chains and the inversion based on the optimal addition chain can be obtained.Implemented on the Xilinx Virtex-4 device,for the binary fields m=163,233,283,the proposed designs using a bit-parallel finite field multiplier can achieve 60.9%,35.1%,94.9%better area-time product?ATP?compared to other equivalent designs.Scalar multiplication is the performance-critical operation in each ECC cryptosystem.For random binary curves,this paper proposes a high-performance pipelined architecture for scalar multiplication.The Montgomery ladder algorithm is modified to merge the execution paths.Scheduling schemes,datapath and critical path delay with different pipeline stages are considered and optimized.The three-stage pipelined architecture is shown to have the best performance.On Xilinx Virtex-5,a scalar multiplication for m=163,233,283,409,571 can be achieved in only 4.3,7.2,10.2,17.5 and 34.3?s,respectively.For Koblitz curves,to obtain faster scalar multiplication,the integer scalar k must be converted to a short and sparse?-adic expansion.Currently the conversion is costly both in time and area.This paper proposes mixed-form lazy reduction algorithms and?NAF algorithms,which can be combined to obtain a more compact scalar converter.The 4-stage double-digit pipelined converter on Xilinx Virtex-4 can achieve 46.6%better ATP on average compared to other designs.For scalar multiplication on Koblitz curves,by exploring parallelism in different operations,this paper proposes a high-performance pipelined architecture.Implementation results on Xilinx Virtex-5 show that the proposed architecture can perform a scalar multiplication in 2.50,4.09,5.81,9.50,18.51?s over the five NIST Koblitz curves K-163/233/283/409/571,respectively,which are faster than other reported results.In the end,for high-performance server-side applications,this paper presents an ECC coprocessor which allows both the elliptic curve parameters and algorithms to be reconfigured.Using the generic Montgomery modular multiplication algorithm,a fast method for calculating f^-1?x?mod x^mis proposed,which reduces the clock cy-cles of the precomputation from m-1 to?log₂m?.The design supports both single and double scalar multiplication over the binary extension fields and modular addi-tion/subtraction/multiplication/inversion over prime fields.By using an instruction set,it can implement custom-defined cryptographic algorithms.Targeted on Xilinx Kirtex-7,for the fields m=163,283,367,the ECDSA signature can achieve 52.7,30.4,23.4 kop/s,respectively and the ECDSA verification can achieve 32.1,18.5,14.3 kop/s,respectively.