java - d * e mod phi == 1 对于 RSA key 对并不总是正确

Question

当使用 BouncycaSTLe 使用以下程序生成 RSA key 时(见下文)，原因是

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

在大多数情况下不为真(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

Answer 1

key 导出的实现(就像几乎所有现代实现一样)使用 Carmichael totient 函数lambda(n) = lcm(p-1, q-1)，而不是 Euler totient 函数phi(n) = (p-1)*(q-1)。

如果使用 Carmichael totient 函数执行测试，则所有测试都满足条件d*e = 1 (mod lambda(n)): p>

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);

与 ( 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;
}

Euler 与 Carmichael totient 函数的引用，例如:
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