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 is 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, generating primes takes less than 200ms and safe primes about 10 seconds on modern hardware.

Installation

Add the following to your Cargo.toml file:

glass_pumpkin = "1.0"

Example

use glass_pumpkin::prime;

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

    let n = p * q;

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

You can also supply OsRng and generate primes from that.

use glass_pumpkin::prime;
use rand::rngs::OsRng;

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

    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 and uses the Baillie-PSW method:

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 with one of them using generator 2.
5. Run lucas test.

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

Prime Checking

You can use this crate to check numbers for primality.

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

fn main() {

    if prime::check(&BigUint::new([5].to_vec())) {
        println!("is prime");
    }

    if safe_prime::check(&BigUint::new([7].to_vec())) {
        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.

This crate is part of the Hyperledger Labs Agora Project.