Collection of primality certificates and an open source tool that can be used to verify them (not yet finished).
Application can verify Atkin-Goldwasser-Kilian-Morain Certificate, Pocklington certificate and Brillhart, Lehmer, Selfridge certificate (Theorem 15) based primality proofs, commonly generated by the Primo application.
Read more on primality testing
When verifying primality certificates, it also checks if the number is not vulnerable to Special Number Field Sieve, as primes of this form have effective bit size reduced by a third (i.e. 3072 bit SNFS-vulnerable prime is about as easy to attack as a 2048 bit prime).
Clone this repository:
git clone https://github.com/tomato42/ecpp-verifier.git
cd ecpp-verifier
Install dependencies (for example on Fedora):
dnf install python3-ecdsa python3-gmpy2
Or from PyPI:
pip install ecdsa[gmpy2]
Make sure you have installed ecdsa package version 0.15 or newer. Older
versions have significant performance issues and certificate verification
will take ages.
Run ecpp for the first time:
./ecpp --help
To verify you have primality certificates for all the primes in your OpenSSH
moduli file, you can use ecpp with -m switch:
./ecpp -m /etc/ssh/moduli
This will succeed for example for moduli file released with OpenSSH 8.2p1, listing certificates for each prime.
If there are some primes without primality certificates, you can generate
input files for Primo into in/ directory.
./ecpp -m /etc/ssh/moduli -p
Now, open Primo downloaded from link above, extract archive and start GUI on a reasonably powerful machine (at this moment, Primo can work with up to 64 cores).
- From Menu, select Setup..., set number of cores your system have (multithreading is not much useful)
- In tab Certification, select 3000 dd (decimal digits) in Trial Division Parameters and click Build prime table button.
- Then click Load. Select all the
.infiles in thein/directory created by previous step and click Open. - After long time, you will get certificates in
*.outfiles in the same directory.
In previous step, we got certificates for primes. Now we need to verify them. This can be done with the following command for one certificate:
./ecpp -i in/primo-B412D0397A9D9-07E.out
The job can be simply parallelized so if we want to verify all the certificates we got, we can use GNU parallel to get results in parallel, in this example using 16 parallel processes:
parallel -j16 "echo {} && ./ecpp -i {}" ::: in/*.out
Now, we can add the primality certificates to certificates/ directory
Running ecpp again as in the first example should confirm we have
a certificate for each prime in the moduli file now.
./ecpp -m /etc/ssh/moduli