Cracking short RSA keys

Question

Given the following RSA keys, how does one go about determining what the values of p and q are?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

Answer 1

Wolframalpha tells me that the factors are 100711409 and 100711423

I just wrote a naive Python script to bruteforce it. As amdfan pointed out, starting from the top is a better approach:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

This could be heavily improved, but it still works without a problem. You could improve it by just testing primfactors, but for small values like yours this should be enough.

Answer 2

These two papers could possibly come in useful

• Andrej Dujella - A Variant of Wiener's Attack on RSA
• Andrej Dujella - Continued Fractions and RSA with small secret exponent

Came across them when I was doing some basic research on continued fractions.

Answer 3

Sorry for the necromancy, but a friend asked me about this, and after pointing him here, I realized that I didn't really like any of the answers. After factoring the modulus and getting the primes (p and q), you need to find the totient, which is (p-1)*(q-1).

Now, to find the private exponent, you find the inverse of the public exponent mod the totient.

public_exponent * private_exponent = 1 mod totient

And now you have your private key, that easy. All of this except for the factorization can be done almost instantly for huge integers.

I wrote some code:

// tinyrsa.c
//
// apt-get install libgmp-dev
// yum install gmp-devel
//
// gcc tinyrsa.c -o tinyrsa -lm -lgmp

#include<stdio.h>
#include<gmp.h>

int main()
{
  // declare some multi-precision integers
  mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime;

  mpz_init_set_str(pub_exp,"5",10);
  mpz_init_set_str(modulus,"10142789312725007",10);

  mpz_init(priv_exp);
  mpz_init(totient);
  mpz_init(fac_p);
  mpz_init(fac_q);

  // now we factor the modulus (the hard part)
  mpz_init(next_prime);
  mpz_sqrt(next_prime,modulus);
  unsigned long removed=0;
  while(!removed)
  {
    mpz_nextprime(next_prime,next_prime);
    removed=mpz_remove(fac_p,modulus,next_prime);
  }

  mpz_remove(fac_q,modulus,fac_p);
  // we now have p and q

  // the totient is (p-1)*(q-1)  
  mpz_t psub, qsub;
  mpz_init(psub);
  mpz_init(qsub);

  mpz_sub_ui(psub,fac_p,1);
  mpz_sub_ui(qsub,fac_q,1);
  mpz_mul(totient,psub,qsub);

  // inverse of the public key, mod the totient..
  mpz_invert(priv_exp,pub_exp,totient);

  gmp_printf("private exponent:\n%Zd\n",priv_exp);

}

The factorization algorithm I used is stupid, but concise, so grain of salt there. In this particular example the code runs almost instantly, but that is largely because the instructor in question provided an example that uses two primes in a row, which isn't really realistic for RSA.

If you wanted to cut out my stupid iterative search, you could put in some real factorization algorithm, and factor keys likely up to around 256 bits in a reasonable amount of time.

Answer 4

I suggest you read about the Quadratic Sieve. If you implement one yourself, this is surely worth the credit. If you understand the principles, you already gained something.

Answer 5

The algorithm to do this is (and this will work for any example, not only this small one that can be factored easily by any computer):

ed - 1 is a multiple of phi(n) = (p-1)(q-1), so is at least a multiple of 4.
ed - 1 can be computed as 40571156445208704 which equals 2^7 * 316962159728193, and we call s=7 and t = 316962159728193. (in general: any even number is a power of 2 times an odd number). Now pick a in [2,n-1) at random, and compute (by successive squaring modulo n) the sequence a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. until at most a^((2^7)*t) (mod n), where the last one is guaranteed to be 1, by the construction of e and d.

We now look for the first 1 in that sequence. The one before it will either be +1 or -1 (a trivial root of 1, mod n) and we redo with a different a, or some number x which does not equal +1 or -1 mod n. In the latter case gcd(x-1, n) is a non-trivial divisor of n, and so p or q, and we are done. One can show that a random a will work with probability about 0.5, so we need a few tries, but not very many in general.

Answer 6

You need to factorize the modulus, that's the first parameter of the public key, 10142789312725007. Brute force will do (check every odd number from 3 to sqrt(n) if it's a factor), although more sophisticated/fast algorithms exist.

Since the number is too big to fit into a conventional integer (even 64-bit), you might want a numeric library that supports arbitrary-lenth integers. For C, there's GMP and MPIR (more Windows-friendly). For PHP, there's Bignum. Python comes with a built-in one - the built-in integer datatype is already arbitrary-length.