May 26, 2018

Provable Prime Number Generator suitable for Cryptographic Applications

This module implements Ueli Maurer’s algorithm for generating large provable primes and secure parameters for public-key cryptosystems. The generated primes are almost uniformly distributed over the set of primes of the specified bitsize and expected time for generation is less than the time required for generating a pseudo-prime of the same size with Miller-Rabin tests. Detailed description and running time analysis of the algorithm can be found in Maurer’s paper[1].

CryptPrimes is a pure perl implementation. It uses MathPari for multiple precision integer arithmetic and number theoretic functions. Random numbers are gathered with CryptRandom, a perl interface to /dev/u?random devices found on modern Unix operating systems.