d * e mod phi == 1 not always true for RSA key pair

user_136452 0
Viewed 121

When generating RSA keys with Bouncycastle with following program (see below) why is

d * e mod phi == 1 where phi := (p - 1) * (q - 1)

not true in most of the cases (value of check1)?

import java.math.BigInteger;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;
import java.security.Provider;
import java.security.Security;
import org.bouncycastle.jcajce.provider.asymmetric.rsa.BCRSAPrivateCrtKey;

import org.bouncycastle.jce.provider.BouncyCastleProvider;

public class TestRsaKey1 {

    private static Provider BC_PROVIDER;

    static {
        BC_PROVIDER = new BouncyCastleProvider();
        Security.insertProviderAt(BC_PROVIDER, 1);
    } // static

    public static void main(String[] args) throws NoSuchAlgorithmException {
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
        keyPairGenerator.initialize(512);
        for (int i = 0; i < 10; i++) {
            boolean check0, check1;
            KeyPair keyPair = keyPairGenerator.genKeyPair();
            BCRSAPrivateCrtKey kPriv = (BCRSAPrivateCrtKey)keyPair.getPrivate();
            BigInteger n, e, d, p, q;
            n = kPriv.getModulus();
            e = kPriv.getPublicExponent();
            d = kPriv.getPrivateExponent();
            p = kPriv.getPrimeP();
            q = kPriv.getPrimeQ();
            
            // phi := (p - 1) * (q - 1)
            BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); // phi := (p - 1) * (q - 1)
            
            // following check p * q == n ?  is true in 100% of cases
            check0 = n.equals(p.multiply(q));   

            // following check d * e mod phi == 1 ?  is true only in ca. 30% of cases
            check1 = BigInteger.ONE.equals(d.multiply(e).mod(phi));

            System.out.println(check0 + " " + check1);
        }
    } // main

} // class
bouncycastle rsa cryptography java
1 Answers

The implementation of the key derivation (like practically all modern implementations) uses the Carmichael totient function lambda(n) = lcm(p-1, q-1), instead of the Euler totient function phi(n) = (p-1)*(q-1).

If the test is performed with the Carmichael totient function, the condition d*e = 1 (mod lambda(n)) is fulfilled for all tests:

BigInteger lambda = lcm(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));
boolean check2 = BigInteger.ONE.equals(d.multiply(e).mod(lambda)); // d * e mod lambda == 1 ?  <-- true for ALL cases
System.out.println(check0 + " " + check2);

with (here)

private static BigInteger lcm(BigInteger a, BigInteger b) {
    BigInteger mul = a.multiply(b);
    BigInteger gcd = a.gcd(b);
    BigInteger lcm = mul.divide(gcd);
    return lcm;
}

References for Euler vs. Carmichael totient function, e.g.:
RSA (cryptosystem) - Key generation
Do Carmichael's and Euler's totient functions in RSA generate the same keys?
Main purpose for Carmichael's Function in RSA
Why do we need Euler's totient function φ(N) in RSA?
lcm versus phi in RSA

user_90140970
Related