Electronic Thesis and Dissertation Repository

Efficient Hardware Architectures For Public-key Cryptosystems

Mohammadamin Saburruhmonfared, The University of Western Ontario

Abstract

Finite field arithmetic plays an essential role in public-key cryptography as all the underlying operations are performed in these fields. The finite fields are either prime fields or binary fields. Binary field elements can mainly be represented on a polynomial basis or a normal basis (NB). NB representation offers a simple squaring operation, especially in hardware. However, multiplication is typically complex, and a particular subset of NB called Gaussian Normal Basis (GNB) features an efficient multiplication operation used in this work. The first part of this thesis has focused on improving finite field arithmetic architectures over GNB. Among different arithmetic operations, multiplication, inversion and exponentiation operations are computationally the most time-demanding field operations used in public-key cryptosystems. In this thesis, we design several new efficient hardware architectures for binary exponentiation using GNB multipliers. Our designs are also supported with novel countermeasures against side-channel analysis (SCA) and fault attacks that require minimal implementation overhead. Then, We have proposed a new finite field square-multiply architecture over GNB, which performs concurrent squaring and multiplication without any delay. Besides, we present three new inversion architectures to improve the performance of the inversion’s implementation. First, an improved architecture for the classic inversion scheme using a single multiplier is proposed. Then, we propose two new inversion architectures to improve the efficiency and speed of inversion operation using the interleaved connection of two GNB multipliers to perform the two multiplication operations simultaneously to reduce the number of required iterations. We have conducted ASIC based implementations of the different schemes using the 65nm CMOS technology libraries. In the final part of this thesis, we introduce a new architecture for computing the point multiplication on Koblitz Curves by utilizing the proposed inversion architecture as our design’s computation core. The proposed architectures are implemented on FPGA. Our evaluation shows that the newly proposed architectures improve the efficiency of existing hardware architectures for computing point multiplications on Koblitz Curves by 17%.