Missing check in prime generation?

Question

Missing check in prime generation?

darconeous opened this issue a year ago · 4 comments

I was reading the RSA key generation code and I couldn't seem to find the check where we make sure that $e$ is not a factor of $(q-1)$ or $(q-1)$.

Am I missing something? Without that check, it would seem that some small portion (~ $2/e$ ) of the generated keys would be invalid (the private key would be incapable of properly decrypting or signing).

I hope I'm just missing it.

Answer 1 · 2023-06-27T22:52:24.000Z

I believe it's here: https://github.com/RustCrypto/RSA/blob/823bb23/src/algorithms/generate.rs#L107

Answer 2 · 2023-06-27T22:56:12.000Z

See also: https://github.com/dignifiedquire/num-bigint/blob/2aade9d/src/algorithms/mod_inverse.rs#L12-L16

Answer 3 · 2023-06-27T23:10:40.000Z

Going to go ahead and close this. Reopen if you disagree.

Answer 4 · 2023-06-28T01:29:25.000Z

@dignifiedquire we might consider adding a comment about this to assist people looking for it in the future