D. J. Bernstein
Authenticators and signatures
Zmodexp

The Zmodexp library interface

Warning on x86 FPU precision control: In the current implementation of Zmodexp, zmodexp512 and zmodexp512_init set the precision control to 64 bits; zmodexp512_load, zmodexp512_store, zmodexp512_square, and zmodexp512_multiply assume that the precision control is still 64 bits.

Exponentiating

     #include <zmodexp.h>

     uint32 m[16];
     uint32 r[16];
     unsigned char *e;
     unsigned int elen;
     zmodexp512_tmp tmp;

     zmodexp512(m,r,e,elen,&tmp);

zmodexp512 computes the e[0] + 2^8 e[1] + ... + 2^(8(elen-1)) e[elen-1] power of r[0] + 2^32 r[1] + ... + 2^480 r[15] modulo m[0] + 2^32 m[1] + ... + 2^480 m[15], and puts the result back into r. m[15] is required to be at least 2^30.

zmodexp512 stores temporary data in tmp. Do not reuse tmp inside signal handlers.

The time taken by zmodexp512 is independent of the contents of r, s, and m on processors with constant-time floating-point arithmetic, specifically the Pentium, Pentium MMX, Pentium Pro, and Pentium II.

The current implementation of Zmodexp uses the simplest radix-16 exponentiation method, so its time for fixed elen is essentially independent of the contents of e except for cache effects.

The current implementation of Zmodexp on x86 chips requires that tmp be aligned to an 8-byte boundary for good performance. Make sure to use gcc -malign-double.

Initializing a modulus

     #include <zmodexp.h>

     zmodexp512_m m;
     uint32 m32[16];

     zmodexp512_init(&m,m32);

zmodexp512_init reads the integer m32[0] + 2^32 m32[1] + ... + 2^480 m32[15] and initializes a modulus m to that integer. m32[15] is required to be at least 2^30.

You can run zmodexp512_init again with a different integer to change m. zmodexp512_init does not allocate any memory.

The zmodexp512_m type is first-class and can be copied.

The current implementation of Zmodexp on x86 chips requires that m be aligned to an 8-byte boundary for good performance. Make sure to use gcc -malign-double.

Loading and storing a remainder

     #include <zmodexp.h>

     zmodexp512_m m;
     zmodexp512_r r;
     uint32 r32[16];

     zmodexp512_load(&m,&r,r32);
     zmodexp512_store(&m,&r,r32);

zmodexp512_load reads the integer r32[0] + 2^32 r32[1] + ... + 2^480 r32[15] and initializes a remainder r modulo m to that integer. m must already have been initialized with zmodexp512_init.

You can run zmodexp512_load again with a different integer to change r. zmodexp512_load does not allocate any memory.

The zmodexp512_r type is first-class and can be copied.

zmodexp512_store reads a remainder from r and sets r32[0], r32[1], ..., r32[15] accordingly. The resulting integer r32[0] + 2^32 r32[1] + ... + 2^480 r32[15] is guaranteed to be smaller than the modulus.

zmodexp512_load and zmodexp512_store may store temporary data inside m. Do not reuse m in signal handlers.

The current implementation of Zmodexp on x86 chips requires that r be aligned to an 8-byte boundary for good performance. Make sure to use gcc -malign-double.

Multiplying and squaring

     #include <zmodexp.h>

     zmodexp512_m m;
     zmodexp512_r r;
     zmodexp512_r s;

     zmodexp512_square(&m,&r);
     zmodexp512_multiply(&m,&r,&s);

zmodexp512_square sets the remainder r to the square of r modulo m.

zmodexp512_multiply sets the remainder r to the product of r and s modulo m.

zmodexp512_square and zmodexp512_multiply may store temporary data inside m. Do not reuse m in signal handlers.

The time taken by zmodexp512_square and zmodexp512_multiply is independent of the contents of r, s, and m on processors with constant-time floating-point arithmetic, specifically the Pentium, Pentium MMX, Pentium Pro, and Pentium II.