Remove use of Binary Extended Euclidean Algorithm for inversion

Instead use two specialized algorithms, one for odd modulus and the
other for power of 2 modulus, then combine the results using CRT.

1 files changed, 1 insertions, 2 deletions

diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index bff1a1c15..bce6fae0f 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -298,11 +298,10 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
    const BigInt q_minus_1 = q - 1;
 
    const BigInt phi_n = lcm(p_minus_1, q_minus_1);
-   // FIXME: this uses binary ext gcd because phi_n is even
    d = inverse_mod(e, phi_n);
    d1 = ct_modulo(d, p_minus_1);
    d2 = ct_modulo(d, q_minus_1);
-   c = inverse_mod(q, p); // p odd, so uses const time algorithm
+   c = inverse_mod(q, p);
 
    RSA_PublicKey::init(std::move(n), std::move(e));