RSA encryption with a psuedoprime

What happens if we accidentally get a pseudoprime when computing the parameters for the RSA public-key cryptosystem. Does it still work? Will we notice any problems?

On my original answer on Quora I cited a chapter from a cryptography text showing that RSA with Carmichael numbers would continue to decrypt correctly, but might not decrypt correctly otherwise.

I found that answer a little unsatisfying and tried an experiment with small numbers that showed that more than half the time, RSA would not decrypt properly if one of the parameters p or q was not a prime.

Tonight I scaled up that experiment with some C++ code using the GNU Multiprecision Library (GMP) to demonstrate that for larger numbers, RSA almost always fails to decrypt.

Results

To create a modulus of N bits, I used a prime of N/2 bits and two more primes of N/4 bits. Then I tried encrypting and decrypting random messages and counted the number of times the decryption produced the correct result. In addition to a correct or incorrect result, a third possibility is that the message shares a common factor with the modulus, allowing the modulus to be factored, effectively breaking the private key.

Modulus length	successes	failures	moduli broken
10 bits (5, 3, and 2)	11.12%	38.57%	50.31%
20 bits (5, 5, and 5)	2.87%	86.65%	9.48%
30 bits (15, 8, and 7)	0.07%	98.29%	1.64%
40 bits (20, 10, and 10)	0.005%	99.975%	0.243%
80 bits (40, 20, and 20)	< 0.0001%	99.9998%	0.00022%

Repeated runs showed similar results, with some variability.

Real RSA implementations use moduli of no less than 1024 bits, and preferably longer. (768 bits used to be standard but numbers of this size have been successfully factored.)

As a follow-up, we could explore other sorts of psuedoprimes; I don't know if semiprimes are more likely to fail Rabin-Miller than other sorts of composite numbers.

Source code

on Github

Please don't use my RSA implementation for anything important; I believe it's correct but that doesn't mean it's trustworthy or useful.

// To compile: g++ -o rsa_with_psuedoprimes rsa_with_psuedoprimes.cpp -lgmpxx -lgmp
#include <iostream>
#include <gmp.h>

gmp_randstate_t random;

void
randomPrime( mpz_t out, int nBits ) {
  mpz_init( out );
  do {
    mpz_urandomb( out, random, nBits );
    mpz_setbit( out, 0 );
    mpz_setbit( out, nBits - 1 );
  } while ( !mpz_probab_prime_p( out, 40 ) );
}

void
testSize( int nBits, int numSamples ) {
  // Generate the RSA parameters
  int pBits = nBits / 2;
  int q1Bits = pBits / 2;
  int q2Bits = nBits - pBits - q1Bits;

  std::cout << "*******************************************\n"
        << "Testing with "
        << pBits << "-, " << q1Bits << "-, " << q2Bits
        << "-bit primes" << std::endl;

  mpz_t p, q1, q2, q;
  randomPrime( p, pBits );
  randomPrime( q1, q1Bits );
  randomPrime( q2, q2Bits );
  mpz_init( q );
  mpz_mul( q, q1, q2 );

  mpz_t n, d, e, pminus1, qminus1, lambda, tmp, m;
  mpz_inits( n, d, e, pminus1, qminus1, lambda, tmp, m, NULL );
  mpz_mul( n, p, q );

  std::cout << "p=" << p << std::endl;
  std::cout << "q=" << q << std::endl;
  std::cout << "n=" << n << std::endl;
  
  mpz_sub_ui( pminus1, p, 1 );
  mpz_sub_ui( qminus1, q, 1 );
  mpz_lcm( lambda, pminus1, qminus1 );
  std::cout << "lambda=" << lambda << std::endl;

  if ( nBits < 17 ) {
    mpz_set_ui( e, 3 );
  } else {
    mpz_set_ui( e, 65537 );
  }

  mpz_gcd( tmp, e, lambda );
  while ( mpz_cmp_ui( tmp, 1 ) != 0 ) {
    mpz_urandomb( e, random, 16 );
    mpz_gcd( tmp, e, lambda );
  }
  std::cout << "e=" << e << std::endl;

  mpz_invert( d, e, lambda );
  std::cout << "d=" << d << std::endl;

  // Run an encryption + decryption cycle on a random message.
  // Count failures, successes, and number of times m shares a factor with n.
  int numSuccess = 0;
  int numFailure = 0;
  int numFactor = 0;

  for ( int s = 0; s < numSamples; ++s ) {
    mpz_urandomb( m, random, nBits  );
    mpz_gcd( tmp, m, n );
    if ( mpz_cmp_ui( tmp, 1 ) == 0 ) {
      mpz_powm( tmp, m, e, n );
      mpz_powm( tmp, tmp, d, n );
      if ( mpz_cmp( tmp, m ) == 0 ) {
    numSuccess += 1;
      } else {
    numFailure += 1;
      }
    } else {
      numFactor += 1;
    }
  }

  std::cout << numSamples << " trials\n"
        << numSuccess << " successes ("
        << ( numSuccess * 100.0 / numSamples ) << "%)\n" 
        << numFailure << " failures ("
        << ( numFailure * 100.0 / numSamples ) << "%)\n" 
        << numFactor << " modulus broken ("
        << ( numFactor * 100.0 / numSamples ) << "%)"
        << std::endl;
  
  mpz_clears( p, q1, q2, q, n, d, e, pminus1, qminus1, lambda, tmp, m, NULL );  
}

int
main( int argc, char *argv[] ) {
  gmp_randinit_default( random );

  int numSamples = 10000;
  testSize( 10, numSamples );
  testSize( 20, numSamples );
  testSize( 30, numSamples );
  testSize( 40, numSamples * 100 );
  testSize( 80, numSamples * 1000 );
  // testSize( 100, numSamples );
  // testSize( 300, numSamples );
  // testSize( 768, numSamples );
  // testSize( 1024, numSamples );
  
  return 0;
}