Exploring how quickly RSA breaks if one of the primes is a psuedoprime

rsa_with_psuedoprimes.cpp

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