hyperledger-labs / agora-glass_pumpkin Goto Github PK

View Code? Open in Web Editor NEW

19.0 4.0 11.0 16 KB

agora-glass_pumpkin

Home Page: https://wiki.hyperledger.org/display/labs/Agora

License: Apache License 2.0

Rust 100.00%

agora-glass_pumpkin's Introduction

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:

Generate a random odd number of a given bit-length.
Divide the candidate by the first 2048 prime numbers. This helps to eliminate certain cases that pass Miller-Rabin but are not prime.
Test the candidate with Fermat's Theorem.
Runs log2(bitlength) + 5 Miller-Rabin tests with one of them using generator 2.
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.

agora-glass_pumpkin's People

Contributors

Stargazers

Watchers

Forkers

weichweich e-ivkov 4meta5 milapsheth aumetra davidp94 fjarri maurges berendsliedrecht andrewwhitehead mikelodder7

agora-glass_pumpkin's Issues

Lucas Test is broken

Lucas test (and by extension the Baillie-PSW test used in "strong_check") flags some primes as composites. A cursory search found no composites that passed (given the rarity of even 2-SPRPs beyond 2^64 this is fully expected) ,however the aforementioned behavior is sufficient to demonstrate that the test does not perform as predicted and may pass more composites than a correct implementation. Below is one example.

N
18446744073710004191
Claim
true

Witness
8300848561679324618

Factorization of n-1
2, 5, 1844674407371000419

Performance of safe prime generation order of magnitude worse than openssl

First, thanks for the nice library! I'm using it to implement a threshold variant of paillier (code is here https://github.com/robinhundt/pht-crypto but still under construction).
I've noticed that my key generation takes a considerable amount of time due to the generation of safe primes being slow (taking minutes for safe primes of size 2048 bits on my machine). I've noticed that openssl is considerably faster in generating safe primes (using https://docs.rs/openssl/0.10.36/openssl/bn/struct.BigNumRef.html#method.generate_prime ).
If there is interest, I could send a PR with benchmarks comparing the openssl implementation and this one :) Maybe there are some easy improvements which could bring the performance closer to the one offered by openssl.

Can not get prime if length<16

if length<16, check prime will also pass that r % p == 0 if r==p. The biggest prime of first 2048 prime is 16bit long.

This problem exist in almost every prime generation crates

API was changed in recent release, and now downstream crates (unknown_order with rust backend) don't build

This is because in #17 I was incorrect to assume that the API doesn't change: I didn't notice that some functions were reexported, since I didn't use them myself. Sorry! :(

Redundant primality test in gen_safe_prime

The function to generate a safe prime, gen_safe_prime, performs another primality test on the random prime that was just generated.

Specifically, in gen_safe_prime, gen_prime returns a probable prime, but the next check _is_safe_prime(...) && lucas(...) tests again that candidate is a prime. This is already done in gen_prime, so we now only need to check if (candidate - 1)/2 is also prime.

Why large minimum bit length?

I am using glass_pumpkin for a teaching demo, and really just want 32-bit primes. Is there some reason for the restriction to 128 bits or more? Sure would be great to remove it for my use case.

Intermittent 'attempt to subtract with overflow' panic

https://github.com/mikelodder7/glass_pumpkin/blob/412a51b8235187c980a0194b6eae44ff02ac89aa/src/common.rs#L176

Encountered an intermittent panic when calling glass_pumpkin::prime::strong_check():

thread 'main' panicked at 'attempt to subtract with overflow', /home/jnichols/.cargo/registry/src/github.com-1ecc6299db9ec823/glass_pumpkin-0.5.0/src/common.rs:176:25

trials may be zero, so the subtraction in the range definition can underflow.

If I understand the Miller Rabin algorithm properly, then I think a larger issue lies in rewrite():

https://github.com/mikelodder7/glass_pumpkin/blob/412a51b8235187c980a0194b6eae44ff02ac89aa/src/common.rs#L192-L202

I think rewrite() is trying to find r (aka trials) and d from the following line in the algorithm, as given on wikipedia:

write n as 2^{r}·d + 1 with d odd (by factoring out powers of 2 from n − 1)

However the current rewrite() function simply returns trials = 0 and d = candidate - 1 (making d always positive) whenever candidate is odd.

Minimum bit length typo in docs

The glass_pumpkin::safe_prime::new docs state that

Note: the bit_length MUST be at least 512-bits.

But the crate supports 128-bits or more.

Unnecessary allocations in miller_rabin

I'm trying to adapt this crate for no_std (and for use with crypto_bigint), and I'm wondering why in the miller_rabin test do we need to allocate all bases at once, instead of generating them on the fly with iterators?

Safe prime size is occasionally off by a few bits

When generating safe primes with a specific size via safe_prime::new, the resulting Integer sometimes has a size which is off by one or two bits.

Possible error in MR test

The decomposition function for MR, rewrite() reads:

fn rewrite(candidate: &BigUint) -> (u64, BigUint) {
    let mut d = candidate - 1_u32;
    let mut trials = 0;

    while d.is_odd() {
        d >>= 1;
        trials += 1;
    }

    (trials, d)
}

It seems that it should be while d.is_even() instead (otherwise it always returns trials = 0, and perhaps that's why miller_rabin() sets trials to at least 5), but if I make that change is_prime_tests() fails. The strange thing is that those tests fail because the MR test fails, but the Lucas test still passes - but that may be an effect of #16? I am not sure how those test numbers were obtained, perhaps you can shed some light on it.