Glass Pumpkin

A random number generator for generating large prime numbers, suitable for cryptography.

Purpose

glass_pumpkin is a cryptographically-secure, random number generator, useful for generating large prime numbers. This library was inspired by pumpkin except its meant to be used with rust stable. It also lowers the 512-bit restriction to 128 bits so these can be generated and used for elliptic curve prime fields. It exposes the prime testing functions as well. This crate uses num-bigint instead of ramp. I have found num-bigint to be just as fast as ramp for generating primes. On average a prime is generated in less than 200ms and safe primes about 10 seconds on modern hardware.

Installation

Add the following to your Cargo.toml file:

glass-pumpkin = "0.3"

Example

extern crate glass_pumpkin;

use glass_pumpkin::prime;

fn main() {
    let p = prime::new(1024);
    let q = prime::new(1024);

    let n = p * q;

    println!("{}", n);
}

You can also supply OsRng and generate primes from that.

extern crate glass_pumpkin;
extern crate rand;

use glass_pumpkin::prime;

use rand::rngs::OsRng;
use rand::thread_rng;

fn main() {
    let mut rng = OsRng::new().unwrap();
    let p = prime::from_rng(1024, &mut rng);
    let q = prime::from_rng(1024, &mut rng);

    let n = p * q;
    println!("{}", n);
}

Prime Generation

Primes are generated similarly to OpenSSL except it applies some recommendations from the Prime and Prejudice paper:

1. Generate a random odd number of a given bit-length.
2. Divide the candidate by the first 2048 prime numbers. This helps to eliminate certain cases that pass Miller-Rabin but are not prime.
3. Test the candidate with Fermat's Theorem.
4. Runs log2(bitlength) + 5 Miller-Rabin tests.

Safe primes require (n-1)/2 also be prime.

Prime Checking

You can use this crate to check numbers for primality.

extern crate glass_pumpkin;
extern crate num_bigint;

use glass_pumpkin::prime;
use glass_pumpkin::safe_prime;
use num_bigint::BigUint;

fn main() {

    if prime::check(&BigUint::from(5)) {
        println!("is prime");
    }

    if safe_prime::check(&BigUint::from(7)) {
        println!("is safe prime");
    }
}

Stronger prime checking that uses the Baillie-PSW method is an option by using the strong_check methods available in the prime and safe_prime modules. Primes generated by this crate will pass the Baillie-PSW test when using cryptographically secure random number generators. For now, prime::new() and safe_prime::new() will continue to use generation method as describe earlier.