title: RSA KeyPairGenerator with BouncyCastleProvider e*d(φ(n)) not equal to one
body: <p>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:</p>
  
  <ol>
  <li>Choose two distinct prime numbers p and q</li>
  <li>Compute n = pq</li>
  <li>Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1)</li>
  <li>Choose an integer e such that 1 &lt; e &lt; φ(n) and gcd(e, φ(n)) = 1;
  i.e., e and φ(n) are coprime</li>
  <li>Determine d as d ≡ e−1 (mod φ(n));This is more clearly stated as:
  solve for d given d⋅e ≡ 1 (mod φ(n))</li>
  </ol>
  
  <p>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:</p>
  
  <pre><code>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&lt;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);
      }
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/7X6ry.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7X6ry.jpg" alt="enter image description here"></a></p>