How to (pre-)compute a ladder

This is a C-language software library that provides optimized implementations of the Diffie-Hellman functions known as X25519 and X448 (RFC-7748) for 64-bit architectures.

This source code is part of the research work titled: "How to (pre-)compute a ladder" by the authors:

• Thomaz Oliveira, Computer Science Department, Cinvestav-IPN, Mexico.
• Julio López, University of Campinas, Brazil.
• Hüseyin Hisil, Yasar University, Turkey.
• Armando Faz-Hernández, University of Campinas, Brazil.
• Francisco Rodríguez-Henríquez, Computer Science Department, Cinvestav-IPN, Mexico.

Research Resources

A peer-reviewed paper was presented in the 24th Annual Conference on Selected Areas in Cryptography (SAC2017).

• Paper [DOI]
• Slides [PDF].
• Pre-print (IACR ePrint Archive) http://iacr.eprint.org/2017/264 [PDF]

To cite this work use:

@inproceedings{oliveira_sac2017,
    author    = {Thomaz Oliveira and Julio L\'opez and
                 H\"useyin H{\i}\c{s}{\i}l and Armando Faz-Hern\'andez and
                 Francisco Rodr\'iguez-Henr\'iquez},
    editor    = {Adams, Carlisle and Camenisch, Jan},
    title     = {How to (pre-)compute a ladder},
    booktitle = {Selected Areas in Cryptography – SAC 2017:
                 24th International Conference, Ottawa, Ontario,
                 Canada, August 16 - 18, 2017, Revised Selected Papers},
    year      = {2018},
    publisher = {Springer International Publishing},
    pages     = {172-191},
    doi       = {10.1007/978-3-319-72565-9_9},
}

Implementation Details

• Prime field arithmetic is optimized for the 4th and 6th generation of Intel Core processors (Haswell and Skylake micro-architectures).
• Efficient integer multiplication using MULX instruction.
• Integer additions accelerated with ADCX/ADOX instructions.
• Key generation uses a read-only table of 8 KB (25 KB) for X25519 (X448).
• It follows secure coding countermeasures.

Pre-requirements

This library is a standalone C-language code. However, for tests we use C++ code.

• C and C++ compilers.
• git
• cmake

Compilation

First, clone the repository and configure project using the CMake tool:

 $ git clone https://github.com/armfazh/rfc7748_precomputed
 $ cd rfc7748_precomputed
 $ mkdir build
 $ cd build

To specify an alternative C/C++ compiler set the following variables:

 $ CC=gcc CXX=g++ cmake ..

Also, to specify a custom install directory (install_dir) use:

 $ cmake -DCMAKE_INSTALL_PREFIX=install_dir ..

Finally, compile and install:

 $ make
 $ make install (optional)

Running Companion Programs

Once compilation was done, you can run some companion programs.

For running a sample program use:

 $ bin/sample_x25519
 $ bin/sample_x448

For running a performance benchmark (in clock cycles) use:

 $ make bench
 $ bin/bench

For running the Google benchmark tool use:

 $ make gbench
 $ bin/gbench --benchmark_repetitions=10 --benchmark_display_aggregates_only=true

For running the Google Test tool use:

 $ make tests
 $ bin/tests

Fuzzing Test

In the fuzz folder, there are several tests against gmp library and the HACL project. Read the compilation instructions at fuzz/README.md for more information.

Timings

Benchmark performance on 64-bit Intel architectures (table entries are clock cycles).

Haswell is a Core i7-4770 processor.

Skylake is a Core i7-6700K processor.

License

BSD-3 Clause License (LICENSE)

Contact

To report some issues or comments of this project, please use the issues webpage [here].