d * e mod phi == 1 对于 RSA 密钥对并不总是正确的

Question

使用以下程序（见下文）使用 Bouncycastle 生成 RSA 密钥时，为什么

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

密钥派生的实现（实际上与所有 modern 实现一样）使用 Carmichael totient 函数 lambda(n) = lcm(p-1, q-1)，而不是欧拉总函数 phi(n) = (p-1)*(q-1).

如果使用 Carmichael totient 函数执行测试，则满足条件 d*e = 1 (mod lambda(n)) 全部测试：

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

欧拉与卡迈克尔 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

d * e mod phi == 1 对于 RSA 密钥对并不总是正确的

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

java

cryptography

rsa

bouncycastle