CODEWITHSUNDEEP
javarsabouncycastlekey-pair
Jswq
Jswq

Reputation: 776

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

I used BouncyCastleProvider(version is 1.54) to generate RSA keypair, and I want to test if the key is valid. According to wikipedia the RSA algorithm key as below:

  1. Choose two distinct prime numbers p and q
  2. Compute n = pq
  3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1)
  4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime
  5. Determine d as d ≡ e−1 (mod φ(n));This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))

Then I generate 1000 keypairs, which I found only about 30% keypairs fit with d⋅e ≡ 1 (mod φ(n)). However,I got 100% d⋅e ≡ 1 (mod φ(n)) when I don't use BC provider. Is that something wrong with BC 1.54version? And what's the problem if e*d(φ(n)) not equal to one. Can anybody help? Thanks a lot. and my test java code as below:

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

enter image description here

Upvotes: 2

Views: 454

Answers (1)

Jswq
Jswq

Reputation: 776

Finally I found that BC may use λ(n)=lcm(p−1,q−1)λ(n)=lcm(p−1,q−1) instead of φ(n). and I change my code :

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

And it works fine and all results are "e*d(mod fn)=1". Although I don't understant the the deepest of the theory now , the wikipedia's RSA algorithm is not the latest one maybe

Upvotes: 1

Related Questions