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

Question

我使用了BouncyCastleProvider(version is 1.54)来生成RSA keypair，想测试一下是否有效。根据维基百科的 RSA 算法密钥如下：

选择两个不同的素数 p 和 q
计算 n = pq
计算 φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1)
选择一个整数 e 使得 1 < e < φ(n) 和 gcd(e, φ(n)) = 1；即，e 和 φ(n) 互质
确定d为d ≡ e−1 (mod φ(n))；更明确的表述为：求解 d 给定 d⋅e ≡ 1 (mod φ(n))

然后我生成了 1000 个密钥对，我发现只有大约 30% 的密钥对符合 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算法可能不是最新的

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

RSA KeyPairGenerator with BouncyCastleProvider e*d(φ(n)) not equal to one

java

rsa

bouncycastle

key-pair