Prime field elliptic curve cryptography Processor with unified countermeasures

Abstract

Cryptography is an essential tool for building secure information systems. Different cryptographic modules are used to assure different parameters of such systems. For instance, symmetric cryptography modules are essential for assuring confidentiality, whereas asymmetric cryptography modules are used for authentication. In general, asymmetric cryptography algorithms are devised based on a mathematical hard problem such as Discrete Logarithm Problem or Large Prime Factorization. Such mathematical problems require relatively large numbers to be feasibly impossible to break. For many years, RSA is used as a standard asymmetric system until Elliptic Curve Cryptography (ECC) was introduced with much smaller key sizes. Nevertheless, substantial computational power is required to perform operations over ECC systems. Hence, hardware accelerators are necessary to speed up such computations. Also techniques to deal with side channel analysis attacks threat are needed. In this thesis, we present the design and implementation of a prime field ECC processor on FPGA. The proposed processor has the following parameters and features. First, the processor is of an Application Specific Instruction Set (ASIP) type with extendible instruction set to support various algorithms and coordinate systems. Second, redundant signed digit representation as a carry free arithmetic is adopted that allowed for high speed modular arithmetic operations. Furthermore, the processor operates over NIST (National Institute of Standards and Technology) recommended curves with extended reduction formula to accommodate the redundancy of the redundant signed digit. In addition, extensive pipelining techniques were introduced to the multiplier data path in order to achieve lowest critical path delay reported in the literature. Whereas a fully exportable design is achieved through the use of simple logic operations. Nevertheless, implementation on FPGA outperformed other processors in the literature that use embedded multipliers and DSP blocks extensively in terms of performance and maximum operating frequency. Implementation results on various devices and technologies are presented and showed competitive results to state of the art processors. More specifically, the proposed processor performs single point multiplication employing points in affine coordinates in 2.26 ms and runs at maximum frequency of 160 MHz in Xilinx Virtex 5 (XC5VLX110T) FPGA. Various countermeasures are proposed and applied to the ECC processor implementation at different abstraction layers. First, the carry free redundant signed digit representation is extended to provide resiliency against fault analysis attacks. Such digits are encoded by a one hot encoding scheme to provide consistent Hamming weight of the manipulated data that allowed for simple parity check process. Second, a pre-charge logic is combined with the one hot encoding scheme to provide unified countermeasures against differential power analysis and fault analysis attacks. Finally, an effective simple power analysis countermeasure is applied to the processor through unbalanced atomic blocks with minimal overhead. Simulated and real time fault and power analysis attacks showed high resiliency of the processor against such attacks.

Date of Award	2014
Original language	American English
Supervisor	Hamad Al-Qutayri (Supervisor)