Random (safe) prime generation, how to go about it?

[jellevos]

Hi @tarcieri and others. Thanks for all the hard work; I see so many changes since I last checked the repository!

For the scicrypt crate and e.g. the RSA crate it is necessary to generate (safe) primes. I also saw that this feature is on the feature wishlist.

Design considerations
I want to try my hand at implementing it but I would like to hear your opinion about a few design decisions:

1. What primality test to use? I suggest the Baille-PSW test, for which no pseudoprimes are currently known. It is also implemented in GMP.
2. Should the test run in constant time? I suggest a solution that is constant time only if the number is actually prime. I.e. if the test finds that the number is not prime, it can abort early.
3. How do we generate a random prime?

I want to elaborate a bit on the last point:
Given a constant-time primality test (or one that only runs in constant time when the number is actually prime), the only way I imagine being free of timing side-channels is to keep generating random potential primes until finding one that passes the test. However, this is very slow. A much faster approach (like in OpenSSL) is to sieve: We would first compute the residues of the potential prime modulo many small primes. If any equals 0, we increase all residues by 2 (or 4 for a safe prime), and try again. In this way we can weed out many composite numbers without having to run the primality test. However, this probably causes timing patterns that one might exploit to learn more about the random prime. I also don't know any papers about this that could help us.

My suggestion
I suggest that I implement:

• The Baille-PWS test, which is only constant-time if the number is prime.
• Random (safe) prime generation, which is not leaky by generating random numbers and testing if they are prime.
• Random (safe) prime generation, which is leaky since it uses a sieve. (In this case, it might be considered wasteful that the underlying primality test runs in constant time.)

I am curious to hear your thoughts. I'm happy to help out where possible!

[tarcieri]

I believe @fjarri already has an implementation of random prime functionality although I don’t think it’s public yet

[jellevos]

Oh that's good to know! I think it's https://github.com/entropyxyz/crypto-primes. Exciting work!

[fjarri]

I am not sure BPSW test can be made constant time, since both of its constituents are data-dependent:

• Miller-Rabin requires the number of iterations equal to the number of trailing zeros in n - 1,
• Lucas (strong) requires one to do a number of checks equal to the number of trailing zeros in n + 1 (although it may be possible to make Lucas-V constant-time)

Moreover, is some usable information actually leaked this way?

[jellevos]

It's my understanding that the first test in Baille-PSW is simply a Fermat primality test base 2, but that might be wrong. However, if this is the case, then that part sounds easy to do in constant time. For the Lucas test I was thinking about computing the right element of the Lucas sequence, similar to the Montgomery ladder. I'm curious to hear your thoughts.

[fjarri]

No, the first test is more involved, it's Miller-Rabin test, and it has a variable number of iterations depending on n.

For the Lucas test, yes, the binary step is used to propagate the sequence, and it can be made branch-free - but it only needs to be propagated to such odd r that r * 2^k = n + 1, so again it depends on n. Although, as I mentioned, it does not apply to the Lucas-V test.

I filed entropyxyz/crypto-primes#17 if you want to continue the discussion there.

[fjarri]

I think this can be closed, since all the relevant discussion is in the crypto-primes issue above.