Join GitHub today
GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.Sign up
Fastgcd is a C implementation of an efficient algorithm to compute the pairwise GCDs of a collection of integers. The algorithm is due to Bernstein and is a simplified version of (http://cr.yp.to/papers.html#smoothparts).
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Type||Name||Latest commit message||Commit time|
|Failed to load latest commit information.|
fastgcd ------- Nadia Heninger J. Alex Halderman Fastgcd is a C implementation of an efficient algorithm to compute the pairwise GCDs of a collection of integers. The algorithm is due to Bernstein and is a simplified version of (http://cr.yp.to/papers.html#smoothparts). The input to the program is a file listing the collection of integers (e.g., RSA moduli). The algorithm will compute the GCD of each input integer with the product of every other input integer, and output the nontrivial common divisors along with a list of input integers which had a nontrivial common divisor. In the simplest case for RSA moduli, the common divisor will be a single prime factor. We leave it as an exercise to deal with cases where the divisor is composite. This program was used in "Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices" to discover weak RSA keys. For more information, and a copy of the paper, see https://factorable.net/ Install ------- To install fastgcd (in current directory), simply run ./install.sh The install script will download and install a local copy of gmp-5.0.5 and extract and apply our patch to GMP. This patch modifies GMP to add an integer output format that can accommodate integers larger than 2^32 bytes, which is necessary for large inputs to the algorithm. This means that the temporary files written to disk in the course of the algorithm by our patched GMP are not compatible with the standard GMP output format. Running ------- To run a fresh instance of fastgcd, use ./fastgcd input.moduli On completion, fastgcd will output: vulnerable_moduli - list of moduli that had a nontrivial common divisor with any input modulus, in hex, one per line. gcds - list of the common divisor of each modulus in vulnerable_moduli with the product of every other modulus in input.moduli, in hex, one per line. We have provided a sample input: input.moduli - list of moduli, in hex, one per line. Note: these must be unique. Sample output produced by running fastgcd on the provided input.moduli file are contained in sample.out/.