### 16 releases (6 stable)

1.5.0 | Oct 19, 2022 |
---|---|

1.3.0 | Sep 19, 2022 |

1.2.0 | Sep 28, 2021 |

1.0.0 | Apr 26, 2021 |

0.3.3 | Feb 19, 2019 |

#**181** in Algorithms

**1,168** downloads per month

Used in **14** crates
(6 directly)

**Apache-2.0**

44KB

719 lines

# Glass Pumpkin

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

# Purpose

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 `glass_pumpkin`

. I have found
`ramp`

to be just as fast as `num-bigint`

for generating primes. On average, generating primes takes less
than 200ms and safe primes about 10 seconds on modern hardware.`ramp`

# Installation

Add the following to your

file:`Cargo .toml`

`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

and generate primes from that.`OsRng`

`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

are generated similarly to OpenSSL except it applies some recommendations from the Prime and Prejudice paper and uses
the Baillie-PSW method:`Primes`

- 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

methods available in the `strong_check`

and `prime`

modules. Primes generated by this crate will pass the Baillie-PSW
test when using cryptographically secure random number generators. For now,
`safe_prime`

and `prime ::`new

`(`

`)`

`safe_prime``::`new`(``)`

will continue to use generation
method as describe earlier.#### Dependencies

~1MB

~22K SLoC