java - 带有 BouncyCaSTLeProvider e*d(φ(n)) 不等于 1 的 RSA KeyPairGenerator

Question

我使用了BouncyCaSTLeProvider(version is 1.54)来生成RSA keypair，想测试key是否有效。根据 wikipedia 的 RSA 算法 key 如下:

1. 选择两个不同的质数p和q
2. 计算 n = pq
3. 计算 φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1)
4. 选择一个整数 e，满足 1 < e < φ(n) 和 gcd(e, φ(n)) = 1；即，e 和 φ(n) 互质
5. 将d确定为d ≡ e−1 (mod φ(n));更明确地说:求解 d 给定 d⋅e ≡ 1 (mod φ(n))

然后我生成了 1000 个 key 对，我发现只有大约 30% 的 key 对符合 d⋅e ≡ 1 (mod φ(n))。但是，当我不使用 BC 提供程序时，我得到了 100% d⋅e ≡ 1 (mod φ(n))。 BC 1.54版本有问题吗？如果 e*d(φ(n)) 不等于 1，会有什么问题。有人可以帮忙吗？多谢。和我的测试 java 代码如下:

public void testRSAKey() throws NoSuchAlgorithmException {
        KeyPairGenerator rsa = KeyPairGenerator.getInstance("RSA", new BouncyCastleProvider());
        rsa.initialize(1024,new SecureRandom());
        int total=0;
        int isOne=0,notOne=0;
        BigInteger one=  new BigInteger("1");
        while (total<1000) {
            KeyPair keyPair = rsa.generateKeyPair();
            PrivateKey privateKey = keyPair.getPrivate();
            BCRSAPrivateCrtKey privateCrtKey = (BCRSAPrivateCrtKey) privateKey;
            BigInteger primeP = privateCrtKey.getPrimeP();
            BigInteger primeQ = privateCrtKey.getPrimeQ();
            BigInteger p1 = primeP.add(new BigInteger("-1"));
            BigInteger q1 = primeQ.add(new BigInteger("-1"));
            BigInteger fn = p1.multiply(q1);
            BigInteger publicExponent = privateCrtKey.getPublicExponent();
            BigInteger privateExponent = privateCrtKey.getPrivateExponent();
            BigInteger mod = publicExponent.multiply(privateExponent).mod(fn);//mod  ought to be one
            if(mod.equals(one)) {
                System.out.println("e*d(mod fn)=" + mod);
                isOne++;
            }else {
                System.out.println("e*d(mod fn) not equal to one");
                notOne++;
            }
            total++;
        }
        System.out.println("total=" + total);
        System.out.println("isOne=" + isOne);
        System.out.println("notOne=" + notOne);
    }

Answer 1

最后我发现BC可以用λ(n)=lcm(p−1,q−1)λ(n)=lcm(p−1,q−1)代替φ(n)。然后我更改我的代码:

   BigInteger fn = (p1.multiply(q1)).divide(p1.gcd(q1));

它工作正常，所有结果都是“e*d(mod fn)=1”。虽然我现在还不明白最深奥的理论，但维基百科的RSA算法可能不是最新的