Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Doctor of Philosophy

Program

Electrical and Computer Engineering

Supervisor

Arash Reyhani-masoleh

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%.

Summary for Lay Audience

Cryptography plays a crucial role in establishing confidential communications between mobile terminals and back-end servers. As a result, the lightweight implementation of public-key cryptographic protocols on resource-constrained systems is a long-term challenge. Cryptography can be categorized into two main groups, symmetric key and public-key. In symmetric-key cryptography, the secret key must be known only to the sender and receiver to secure the process, and it is challenging for the two parties to exchange the secret key. Public-key cryptography resolves the key distribution problem using two mathematically related keys, the private key and the public key. Elliptic curve cryptography (ECC) is an efficient method used for the implemataion of public-key cryptosystems for resource-constrained embedded devices. Point multiplication is the most time-demanding operation in ECC, which is calculated using finite field arithmetic operations. 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. In the first part of this thesis, we have mostly focused on improving field arithmetic architectures. We have proposed fully secure and efficient exponentiation architectures using GNB. We have then proposed a new architecture that performs concurrent squaring and multiplication without any delay. We have also proposed three new efficient inversion architectures using GNB multipliers to improve the performance of the inversion’s implementation. 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. The newly proposed architectures improve the efficiency of existing hardware architectures for computing point multiplications on Koblitz Curves.

Creative Commons License

Creative Commons Attribution 4.0 License
This work is licensed under a Creative Commons Attribution 4.0 License.

Share

COinS