### 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 |

#**535** in Cryptography

**89** downloads per month

**MIT**and LGPL-3.0+

17KB

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

and `P`

, 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 (`Q`

).`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

is available on crates.io. To use `bulk-gcd`

in your crate,
add it as a dependency inside Cargo.toml:`bulk-gcd`

`[``dependencies``]`
`bulk-gcd ``=` `"`^1.0.0`"`

You also need to declare it by adding this to your crate root (usually

or `lib .rs`

`main``.`rs

):`extern` `crate` bulk_gcd`;`

## Credits

Huge thanks to Michael Grunder for helping me make threads work in Rust.

#### Dependencies

~20MB

~499K SLoC