16 releases (stable)
Uses old Rust 2015
2.2.0 | Jan 1, 2019 |
---|---|
2.1.2 | Dec 20, 2018 |
1.0.7 | Dec 19, 2018 |
0.1.3 | Dec 16, 2018 |
#1058 in Cryptography
18KB
368 lines
bulk-gcd
This package provides and implementation of bulk GCD (Greatest Common Divisor) algorithm by D. Bernstein.
Why?
GCD is useful for identifying weak keys in a large set of RSA keys. Such
sets were collected by researches (e.g. this paper). In order to
find weak keys a pairwise GCD has to be executed on all RSA moduli (i.e.
products of two primes P
and Q
, pertaining to each RSA private key).
However, each separate GCD computation takes considerable amount of time and the
naive pairwise process doesn't scale well (O(n^2)
).
Instead of doing this search in a brute-force way, this module employs clever algorithm by D. Bernstein, that finds GCD of each moduli with a product of all other moduli. Through introduction of product and remainder trees, the computational cost becomes logarithmic instead of quadratic, which results in dramatic drop of the execution time.
Quick example
extern crate bulk_gcd;
extern crate rug;
use rug::Integer;
let moduli = [
Integer::from(15),
Integer::from(35),
Integer::from(23),
];
let result = bulk_gcd::compute(&moduli).unwrap();
assert_eq!(result, vec![
Some(Integer::from(5)),
Some(Integer::from(5)),
None,
]);
Using bulk-gcd
bulk-gcd
is available on crates.io. To use bulk-gcd
in your crate,
add it as a dependency inside Cargo.toml:
[dependencies]
bulk-gcd = "^1.0.0"
You also need to declare it by adding this to your crate root (usually
lib.rs
or main.rs
):
extern crate bulk_gcd;
Credits
Huge thanks to Michael Grunder for helping me make threads work in Rust.
Dependencies
~33MB
~624K SLoC