---

Cryptography

---

New software speed records for cryptographic pairings

In the paper New software speed records for cryptographic pairings we describe an implementation of cryptographic pairings over a Barreto-Naehrig curve that sets new speed records for cryptographic pairings on many amd64 processors. We put the software into the public domain.
To download and build the latest version of the software do the following:

This will produce 6 binaries: bilintest-check, bilintest-c, bilintest-as, speedtest-check, speedtest-c, and speedtest-as.
The binaries ending on -check perform all arithmetic with included overflow check as described in the paper. The files ending on -c are non-optimized implementations in C and the implementations ending on -as have all speed-critical functions implemented in qhasm.
The bilintest binaries perform NTESTS bilinearity (and non-degeneracy) tests, the value NTESTS is defined in the Makefile. The speedtest binaries measure the cycles counts of the most speed-critical functions.

Caution: The software as described in early versions of the paper (versions 2010-05-28 [pdf] and 2010-04-06 [pdf]) has a bug: The parameter u=1966080 used to construct the curve we use for the pairing does not generate a Barreto-Naehrig curve; the order of the group E(F_p) is not prime. We thank Francisco Rodríguez- Henríquez and Jean-Luc Beuchat for pointing out this bug.
The software from version 20100618 now uses a different curve generated with u=1868033, the speed of this updated software is similar, actually even slightly faster.
For verification of the performance numbers the old version of the software is still available as dclxvi-notsecure.tar.bz2; do not use this software for cryptographic purposes.

Update: An even faster pairing implementation has been presented by Jean-Luc Beuchat, Jorge Enrique González Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríquez-Henríquez and Tadanori Teruya.
But our software is a bit (read: one bit) more secure.

---

Cleaned-up implementation of FSB-256

Based on the reference implementation for ebash, I implemented a somewhat cleaned-up, faster version of FSB-256.

---

curve25519 for the Cell Broadband Engine

In joint work with Neil Costigan I implemented a version of the elliptic-curve Diffie Hellman key exchange software curve25519 for the Cell Broadband Engine. There is a paper describing the details of the implementation.
The software is available for download; it's following the eBATS API.

---

Cache-timing resistant AES-GCM for 64-bit Intel processors

Emilia Käsper implemented very fast and cache-timing-attack resistant AES in counter mode. I ported this code to qhasm and we jointly implemented AES-GCM based on this fast AES code. For details of the implementation please refer to the paper "Faster and Timing-Attack Resistant AES-GCM".
The code follows the eSTREAM API, the following versions are avaible:

• AES-CTR, constant-time key setup,
• AES-CTR, non-constant-time key setup,
• AES-GCM, constant time,
• AES-GCM, fast (not constant time).

The assembly versions of the code are available on Emilia's website. The qhasm version uses macros, so you will need maq, a preprocessor for qhasm, to rebuild the code (the resulting assembly file is included).
You will furthermore need an extended AMD64 machine-description file for qhasm, it just goes to the qhasm directory.

---

AES implementations

D. J. Bernstein and I implemented AES in Counter mode for different architectures, namely ppc32, x86, sparcv9 and amd64. For several microarchitectures this code is setting new speed records. Details about how these speed records are achieved can be found in our joint paper "New AES software speed records" (PDF).
The software is now available as part of the estreambench toolkit (in the subdirectory /benchmarks/aes/aes-128/schwabe). We have placed the software into the public domain; feel free to integrate it into your own AES applications!

---

HECTOR

HECTOR is an implementation of a key exchange and a signature scheme based on a hyperelliptic curve over the binary field F_2¹¹³ for the eBATS project. HECTOR is joint work with Peter Birkner. For details of the implementation please refer to the documentation in pdf format.
To download and build HECTOR, first install the GMP library, then do the following:

This builds two binaries, hector_dh and hector_sig, both need random bytes as input, they can for example be started with

respectively.

---

BN curves

A BN curve is an elliptic curve E: Y²=X³+b defined over F_p such that the group of F_p-rational points has prime order n. BN curves have embedding degree k=12 with respect to n. The BN family of pairing-friendly curves is parametrized by the following polynomials in the indeterminate u:

p=p(u)=36u⁴+36u³+24u²+6u+1,
n=n(u)=36u⁴+36u³+18u²+6u+1.

The trace of Frobenius over F_p is given as t(u)=6u²+1. To find a BN curve just choose integer values of the suitable size for u until both p(u) and n(u) are prime. Then test values for the coefficient b until the curve has the correct order. A generator of the group E(F_p) is any nonzero F_p-rational point, but it can be chosen to be G=(1,y) for y a square root of b+1. For more detailed information see [1]. BN curves have sextic twists and are therefore suitable for very efficient pairing implementation. It is also possible to compute pairings on BN curves in a compressed form, see [2].

[1]	Paulo S. L. M. Barreto, Michael Naehrig, Pairing-Friendly Elliptic Curves of Prime Order, Selected Areas in Cryptography -- SAC'2005, Lecture Notes in Computer Science 3897, Springer-Verlag (2006), pp 319--331. Preliminary version: Cryptology ePrint Archive, Report 2005/133.
[2]	Michael Naehrig, Paulo S. L. M. Barreto, Peter Schwabe: On compressible pairings and their computation, Progress in Cryptology - AfricaCrypt 2008 , Lecture Notes in Computer Science 5023, Springer-Verlag (2008), pp 371--388. Cryptology ePrint Archive, Report 2007/429.

---

Pairing computation on BN curves

bn256 is an implementation of different cryptographic pairings on a 256 bit BN curve.
In order to build it, you need the GMP library with header files, for Debian (Lenny) systems it can be installed with

For speed measurement we include cpucycles written by D. J. Bernstein.

To build bn256, do the following:

After the build process has finished you find a binary called bn256 in the bin/ directory, whose usage should be self-explanatory. From the corresponding source file src/bn256.c you can see how to call the functions for pairing computation.
We note, that the generation of random points is based on the GMP functions for random number generation and must not be used for cryptographic purposes.
Parts of this code have been developed in the context of a UMIC project at the Institute for Theoretical Information Technology at RWTH Aachen University.

---