Hyper-Threaded Modular Multipliers (HTMM)

version 1.0, May 2018

Credits

General Description

Implementing optimized modular multipliers on FPGAs using DSP slices is a complex task for cryptographic designers. Several algorithms and architectures have been proposed in the scientific literature.

Hyper-threaded modular multipliers (HTMMs) are proposed as fast, but small, very efficient GF(P)\mathrm{GF}(P) multipliers for elliptic curve cryptography (ECC) and hyper-elliptic curve cryptography (HECC) (see paper in reference for details and documentation).

Hyper-threading is used to efficiently compute several independent multiplications in the same time. Multiple logical multipliers (LMs) are available in the same physical unit. They share the same resources (DSP slices) without “bubbles” in the pipeline. In a HTMM, all clock cycles are used to compute the result(s) as depicted in the figure below. In this figure, the behavior for 3 LMs and 2 words per field element is illustrated.

HTMM behavior for 3 logical multipliers and 2-word field elements (picture from reference)
HTMM behavior for 3 logical multipliers and 2-word field elements (picture from reference)

For flexibility purpose, HTMMs support generic primes (i.e. PP has an arbitrary and dense binary representation) which can be changed at run-time.

This website presents a tool, distributed as open source software, for the generation of HTMMs on several types of FPGAs for a large range of input parameters for efficient design space exploration.

Reference

The motivations, analysis of the state of the art, proposed HTMM algorithm and architecture are detailed in the paper:

 "Generation of Hyper-Threaded GF(P) Multipliers for Flexible Curve based Cryptography on FPGAs"
 (currently under submission to a Journal).

Please cite this paper as the main information source for HTMM generator.

HTMM generator

HTMM generator is a set of Python (2.7) programs and bash scripts working as a command line interface.

Generator input

The HTMM specification provided by the user includes:

Generator output

The generated output includes:

Current limitations

HTMM generator version 1.0 only supports the Virtex-4, 5, 7, and Spartan-6 FPGAs as well as ISE (14.7) CAD tools all from Xilinx. However, users can easily extend HTMM generator to other FPGAs and CAD tools in the scripts.

Access to the generator

Link to the generator: archive file HTMM_generator.tar.gz in the Files tab/pane of the HTMM repository.

License

CeCILL-B

Usage

The main script is: htmm_generator.sh in the root directory.

Each target HTMM is specified in a dedicated file provided by the user. If several specifications are provided, all the corresponding HTMMs will be generated (simulated and implemented for result analysis).

Specification examples are presented below.

Proof of the latency reduction optimization

In the Files tab/pane of the HTMM repository, we provide a short proof (proof_latency_reduction.pdf) of the latency reduction optimization proposed in the paper reference.

Results Examples

A set of 36 HTMMs specifications, with commonly used specifications, have been generated and implemented on several Xilinx FPGAs. The corresponding inputs and outputs are accessible as archive files in the Files tab/pane of the HTMM repository.

Acknowledgments

This work was done in the HAH project partially funded by Labex CominLab, Labex Lebesgue and Brittany Region. We sincerely thank Xilinx for University Program donations.