Hardware Implementations of Elliptic Curve Cryptography Using Shift-Sub Based Modular Multiplication Algorithms

Yamin LiCryptogr 2023 · DOI

TL;DR

This paper presents hardware implementations of modular multiplication algorithms for faster Elliptic Curve Cryptography (ECC). The authors introduce two new algorithms, SSMMPRE and SSMMCSA, which offer improved performance over existing methods, leading to more efficient ECC implementations for hardware security modules.

What Problem Does This Paper Address?

Elliptic Curve Cryptography (ECC) is a cornerstone of modern secure communication, offering strong encryption with shorter key lengths compared to traditional methods like RSA. A critical bottleneck in ECC performance, especially in hardware implementations, is the modular multiplication operation, which is performed repeatedly during scalar point multiplication. Existing hardware implementations of modular multiplication, while functional, can be optimized for speed and efficiency. This paper aims to address this by proposing and evaluating new, faster modular multiplication algorithms and integrating them into ECC hardware designs.

Methods

The paper focuses on developing and evaluating hardware implementations of modular multiplication algorithms. The authors compare several algorithms:

  • Interleaved Modular Multiplication (IMM): A standard approach.
  • Montgomery Modular Multiplication (MMM): Efficient for modular exponentiation but requires domain transformations.
  • Shift-Sub Modular Multiplication (SSMM): A promising algorithm that uses shifts and subtractions.

Building upon SSMM, the paper introduces two novel algorithms:

  • SSMMPRE (Shift-Sub Modular Multiplication with Advance Preparation): This algorithm pre-computes values in previous clock cycles to reduce the critical path in the current iteration.
  • SSMMCSA (Shift-Sub Modular Multiplication with CSAs and Sign Detection): This approach replaces standard adders with Carry-Save Adders (CSAs) and introduces a novel sign detection mechanism, aiming to further speed up computations.

The authors implement these algorithms in Verilog HDL and evaluate their performance (frequency, latency) and cost (ALMs, registers) on an FPGA. They then integrate these modular multiplication modules into ECC implementations for affine, projective, and Jacobian coordinates, comparing the overall ECC performance.

Datasets

Not discussed in the paper. The paper focuses on algorithmic design and hardware implementation, using standard ECC parameters (Secp256k1) for evaluation.

Key Insights and Ideas

  • Shift-Sub is Key: The SSMM algorithm provides a good balance of performance and hardware cost, forming the basis for further optimizations.
  • Pre-computation Pays Off: SSMMPRE demonstrates that preparing intermediate values in advance can significantly reduce the critical path, leading to faster execution.
  • CSAs and Smart Sign Detection are Crucial: SSMMCSA, by leveraging CSAs and a clever sign detection method, achieves the highest frequency among the modular multiplication algorithms. This highlights the importance of optimizing even seemingly minor operations like sign determination.
  • Coordinate Choice Matters for ECC: While faster modular multipliers are developed, the choice of coordinate system (affine, projective, Jacobian) for ECC significantly impacts overall performance and hardware resource usage. Projective coordinates, despite requiring more resources, offer a good trade-off for performance.
  • Modular Multiplication is the Bottleneck: The paper consistently shows that the performance of the modular multiplication algorithm directly influences the overall ECC performance.

Key Results

  • Modular Multiplication Performance:
    • SSMM is 1.80 times faster than IMM.
  • SSMMCSA is 3.27 times faster than IMM.
  • SSMMCSA achieves the highest frequency (116.58 MHz) among the modular multiplication algorithms, albeit with the highest hardware cost.
  • ECC Implementation Performance:
    • ECC implementations using SSMM, SSMMPRE, and SSMMCSA generally achieve higher clock frequencies than those using IMM.
  • The ECC implementation in projective coordinates using SSMM exhibits the lowest latency among all evaluated ECC implementations.
  • Despite SSMMCSA having the highest frequency for modular multiplication, its integration into ECC designs does not always yield the highest ECC frequency due to the latency of other ECC modules.

Limitations and Future Work

  • Limitations:
    • The paper focuses on 256-bit ECC, and the performance gains might vary for different key sizes.
  • While SSMMCSA offers high frequency for modular multiplication, its integration into the full ECC design doesn't always translate to the highest ECC frequency due to other module latencies.
  • Future Work:
    • Investigate and shorten the critical path in SSMMCSA to further improve its ECC performance.
  • Explore high-radix SSMM algorithms for potential further speedups.
  • Apply these optimized algorithms to other elliptic curves, such as NIST P-256 (Secp256r1).
  • Further research into optimizing other ECC modules to complement the fast modular multiplication.

Summary updated

BibTeX
@article{li2023hardware,
  author = {Yamin Li},
  title = {{Hardware Implementations of Elliptic Curve Cryptography Using Shift-Sub Based Modular Multiplication Algorithms}},
  journal = {Cryptogr.},
  year = {2023},
  doi = {10.3390/cryptography7040057},
}
Figure