I am using the Java Bouncy Castle provider to generate RSA key pairs. I want to test if the generated keys are valid.

According to Wikipedia the RSA key pair is generated as follows:

  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 $\operatorname{gcd}(e, φ(n)) = 1$; i.e., $e$ and $φ(n)$ are co-prime
  5. Determine $d$ as $d ≡ e−1 \mod φ(n)$;This is more clearly stated as: solve for $d$ given $d⋅e ≡ 1 \mod φ(n)$.

When trying to generate 1000 key pairs, I found that $d⋅e ≡ 1 \mod φ(n)$ is only valid for 30% of key pairs.

Test code in Java 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);
            }else {
                System.out.println("e*d(mod fn) not equal to one");
        System.out.println("total=" + total);
        System.out.println("isOne=" + isOne);
        System.out.println("notOne=" + notOne);

enter image description here

  • 3
    $\begingroup$ Try using $\lambda(n)=lcm(p-1,q-1)$ instead of $\varphi(n)$. $\endgroup$ Commented Jan 23, 2017 at 7:28
  • $\begingroup$ @CodesInChaos thanks, It's there any articles or document I can read about this theory? $\endgroup$
    – Jswq
    Commented Jan 23, 2017 at 7:45

1 Answer 1


As CodesInChaos notes in the comments, the necessary and sufficient condition for $m^{ed} \equiv m \pmod{n}$ to hold for all messages $m$ is that $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the Carmichael reduced totient function of the modulus $n = pq$.

As it happens, the Euler totient $\varphi(n) = (p-1)(q-1)$ is an integer multiple of $\lambda(n)$, so if $ed \equiv 1$ modulo $\varphi(n)$, then this also holds modulo $\lambda(n)$. Thus, when generating an RSA key, it's OK to compute the private exponent $d \equiv e^{-1}$ modulo $\varphi(n)$ rather than modulo $\lambda(n)$, and indeed quite a few introductory texts on RSA (including, apparently, Wikipedia) do that for some reason, perhaps because it's arguably a bit easier to explain the math that way, or perhaps simply because the authors also mistakenly think that the necessary condition for key validity is $ed \equiv 1 \pmod{\varphi(n)}$.

However, this is not actually the case, and it's indeed quite possible for $(n,e,d)$ to be a valid RSA key even if $ed \not\equiv 1 \pmod{\varphi(n)}$, as long as $ed \equiv 1 \pmod{\lambda(n)}$. Since using $\lambda(n)$ also yields the smallest valid (positive) private exponent $d$ for any given $e$ and $n$, and since computing $\lambda(n)$ is not significantly more difficult than computing $\varphi(n)$, most practical RSA implementations indeed do just that.

  • $\begingroup$ Why using $\lambda(n)$ we get the smallest valid exponent $d?$ $\endgroup$
    – 111
    Commented Jan 25, 2017 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.