Curves, Elliptic

An efficient scalar multiplication algorithm is vital for elliptic curve cryptosystems. The first part of this dissertation focuses on a scalar multiplication algorithm based on scalar recodings resistant to timing attacks. The algorithm utilizes two recoding methods: Recode, which generalizes the non-zero signed all-bit set recoding, and Align, which generalizes the sign aligned columns recoding. For an ℓ-bit scalar split into d subscalars, our algorithm has a computational cost of ⌈⌈ℓ logk(2)⌉/d⌉ point additions and k-scalar multiplications and a storage cost of kd−1(k − 1) – 1 points on E. The “split and comb” method further optimizes computational and storage complexity. We find the best setting to be with a fixed base point on a Twisted Edwards curve using a mix of projective and extended coordinates, with k = 2 generally offering the best performance. However, k = 3 may be better in certain applications. The second part of this dissertation is dedicated to constant-time polynomial inversion algorithms in Post-Quantum Cryptography (PQC). The computation of the inverse of a polynomial over a quotient ring or finite field is crucial for key generation in post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. Efficient algorithms must run in constant time to prevent side-channel attacks. We examine constant-time algorithms based on Fermat’s Little Theorem and the Extended GCD Algorithm, providing detailed time complexity analysis. We find that the constant-time Extended GCD inversion algorithm is more efficient, performing fewer field multiplications. Additionally, we explore other exponentiation algorithms similar to the Itoh-Tsuji inversion method, which optimizes polynomial multiplications in the BIKE/LEDACrypt setup. Recent results on hardware implementations are also discussed.

Cryptographic algorithms are being developed and incorporated into network security protocols to provide secure communication over vulnerable mediums like the Internet. These protocols utilize secret and public key mechanisms to carry out data integrity, confidentiality, authentication, and non-repudiation.
The urge to deploy cryptosystems on low-end devices, based on the constantly growing Internet of Things (IoT) world, requires optimal design and implementation of cryptographic algorithms and protocols to achieve small communicational and computational cost, while preserving the privacy of the transmitted data. Scenarios of low bandwidth, constrained memory, and limited processing power are common when targeting embedded devices; however, security requirements are still present due to the sensitive information that may be communicated. In this thesis, we address the need for optimal cryptographic primitives implementation design in terms of computing capabilities, energy and power consumption, and memory usage to accommodate the deployment of cryptographical systems on resource-constrained devices.

To address the increased interest in crypto hardware accelerators due to performance and efficiency concerns, implementing hardware architectures of different public-key cryptosystems has drawn growing attention. Pure hardware methodology enhances architecture’s performance over a hardware/software co-design scheme at the cost of a more extended design cycle, reducing the flexibility, and demands customized data paths for different protocol-level operations. However, using pure hardware architecture makes the design smaller, faster, and more efficient. This dissertation mainly focuses on designing crypto accelerators that can be used in embedded systems and Internet-of-Things (IoT) devices where performance and efficiency are critical as a hardware accelerator to offload computations from the microcontroller units (MCU). In particular, our objective is to create a system-on-chip (SoC) crypto-accelerator with an MCU that achieves high area-time efficiency. Our implementation can also be integrated as an off-chip solution; however, other criteria, such as performance, are often as important or more important than efficiency in the external crypto-chip design, which is beyond of this work. Not only does our architecture inherently provide protection against timing and simple power analysis (SPA) attacks, but also some advanced security mechanisms to avoid differential power analysis (DPA) attacks are included, which is missing in the literature. In a nutshell, the contributions are summarized as follows:

Elliptic curves have played a large role in modern cryptography. Most notably,
the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Elliptic Curve
Di e-Hellman (ECDH) key exchange algorithm are widely used in practice today for
their e ciency and small key sizes. More recently, the Supersingular Isogeny-based
Di e-Hellman (SIDH) algorithm provides a method of exchanging keys which is conjectured
to be secure in the post-quantum setting. For ECDSA and ECDH, e cient
and secure algorithms for scalar multiplication of points are necessary for modern use
of these protocols. Likewise, in SIDH it is necessary to be able to compute an isogeny
from a given nite subgroup of an elliptic curve in a fast and secure fashion.
We therefore nd strong motivation to study and improve the algorithms used
in elliptic curve cryptography, and to develop new algorithms to be deployed within
these protocols. In this thesis we design and develop d-MUL, a multidimensional
scalar multiplication algorithm which is uniform in its operations and generalizes the
well known 1-dimensional Montgomery ladder addition chain and the 2-dimensional
addition chain due to Dan J. Bernstein. We analyze the construction and derive many
optimizations, implement the algorithm in software, and prove many theoretical and practical results. In the nal chapter of the thesis we analyze the operations carried
out in the construction of an isogeny from a given subgroup, as performed in SIDH.
We detail how to e ciently make use of parallel processing when constructing this
isogeny.