# RSA KeyPair generation with Bouncy Castle provider: $e*d(φ(n))$ not equal to one

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


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

## 1 Answer

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.

• Why using $\lambda(n)$ we get the smallest valid exponent $d?$
– 111
Jan 25 '17 at 15:21