2
$\begingroup$

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

enter image description here

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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