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

X25519	Haswell	Skylake
Key Generation	92,400	69,500
Shared Secret	145,800	108,700

X448	Haswell	Skylake
Key Generation	401,902	322,040
Shared Secret	670,747	528,470

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

---