60

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)
7
  • 1
    what algorithms have you tried so far? If this is for a number theory class there should be a chapter or two in your text on crypto algorithms. Nov 2, 2010 at 15:00
  • This is for an Information Security course. The professor has not explained how to do this but is offering it for a little extra credit. I haven't tried any algorithm yet because I'm not sure how to approach it.
    – Donald T
    Nov 2, 2010 at 15:02
  • With the private key given there is a fast method for factoring n.
    – starblue
    Nov 2, 2010 at 17:23
  • 1
    NOTE: I wasn't asking for a solved problem here but rather trying to discover how to perform the necessary calculations.
    – Donald T
    Nov 10, 2013 at 23:11
  • 1
    @DuncanJones: Was crypto.stackexchange.com in existence when this question was asked almost a decade ago?
    – Donald T
    Sep 24, 2019 at 15:18

12 Answers 12

151

Your teacher gave you:

Public Key: (10142789312725007, 5)

which means

n = 10142789312725007
e = 5 

where n is the modulus and e is the public exponent.

In addition, you're given

Private Key: (10142789312725007, 8114231289041741)

meaning that

 d = 8114231289041741

where d is the decryption exponent that should remain secret.

You can "break" RSA by knowing how to factor "n" into its "p" and "q" prime factors:

n = p * q

The easiest way is probably to check all odd numbers starting just below the square root of n:

Floor[Sqrt[10142789312725007]] = 100711415

You would get the first factor in 4 tries:

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

So we have

 p = 100711409

Now,

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

Why is this important? It's because d is a special number such that

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

We can verify this

d * e = 40571156445208705 = 1 mod 10142789111302176

This is important because if you have a plaintext message m then the ciphertext is

c = m^e mod n

and you decrypt it by

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

For example, I can "encrypt" the message 123456789 using your teacher's public key:

m = 123456789

This will give me the following ciphertext:

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

(Note that "e" should be much larger in practice because for small values of "m" you don't even exceed n)

Anyways, now we have "c" and can reverse it with "d"

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

Obviously, you can't compute "7487844069764171^8114231289041741" directly because it has 128,808,202,574,088,302 digits, so you must use the modular exponentiation trick.

In the "Real World", n is obviously much larger. If you'd like to see a real example of how HTTPS uses RSA under the covers with a 617-digit n and an e of 65537, see my blog post "The First Few Milliseconds of an HTTPS Connection."

9
  • 6
    This is still a brute force solution that wouldn't work for larger numbers. Nov 3, 2010 at 1:13
  • 9
    Yeah, for larger ones you'd need something like the Number Field Sieve. I was just trying to give something that'd be practical for this particular problem that you could do with calc.exe :)
    – Jeff Moser
    Nov 3, 2010 at 2:12
  • 1
    Hi. I was just reading how you are finding the factors by using: "Floor[Sqrt[10142789312725007]] = 100711415" I was just wondering, what if one of the factors is as small as 5? Then your solution wouldn't work, would it? I know small factors should be avoided, but I guess they are possible to appear.
    – Janman
    Dec 5, 2012 at 15:58
  • 1
    @Aerovistae I used WolframAlpha.
    – Jeff Moser
    May 1, 2016 at 22:11
  • 1
    Important note for people programming this. Ensure the result of Floor[Sqrt[n]] is an int data type. Many languages require an explicit cast! Leaving it as a float could cause the program to take hundreds of times longer to execute.
    – James L.
    Jul 15, 2017 at 16:24
16

Here's a relatively simple way to look at it (and one that is doable by hand). If you were to factor the number completely, then the highest factor you would need to consider is sqrt(N):

sqrt(10142789312725007) = 100711415.9999997567

The first prime below this is 100711409, just 6 below the sqrt(N).

10142789312725007 / 100711409 = 100711423 

therefore these are two factors of N. Your professor made it pretty easy - the trick is to recognize that no one would choose a small p or q so starting your check from the bottom (as in the python script someone posted) is a bad idea. If it's going to be practical by hand, the large p and q must lie near sqrt(N).

1
  • You're right, starting from the maximum looks like a better approach. I didn't thought of that.
    – Juri Robl
    Nov 2, 2010 at 15:22
14

There are various fast algorithms to solve the problem of factoring n given n, e, and d. You can find a good description of one such algorithm in the Handbook of Applied Cryptography, Chapter 8, section 8.2.2. You can find these chapters online for free download here. The algorithm is essentially a careful elaboration of Henno Brandsma's answer to this very question.

UPDATE Sep 25, 2019:

In the comment below, user Imperishable Night suggests an alternative method which should be at least conceptually easier to understand.

He notes that usually e is small. In fact e is almost always 65537. In the case that e is small you can develop a quadratic equation in the unknown prime p and thus easily solve for it using e.g. the quadratic formula. To proceed, lets set x=p and solve for x, just to stick with convention. We know that ed = 1 mod phi(n), or equivalently ed - 1 = k * (p-1)*(q-1). Now setting x=p, and therefore n/x=q, multiplying both sides by x and rearranging terms we have
k*x2 + (d*e - k*n - k - 1)*x + k*n = 0.
Now we have an equation of the form ax2 + bx + c = 0 and we can solve for x using the quadratic formula. So we can try values of k in a small range around e and there should be only one integer solution to the quadratic, the solution for the correct k.

Notes:

  1. Everything must be an integer, thus the discriminant must be a perfect square or we can discard k and try the next one. Also, the numerator must be divisible by 2*k.
  2. Sometimes the Carmichael lambda function is used in place of the Euler phi function. This complicates things just a little bit because we must now also guess the g = gcd(p-1, q-1). g is always even, is often 2, and is otherwise almost always a small multiple of 2.

UPDATE Sep 26, 2019:

Finding k is actually very easy when e is small. By taking the equation ed - 1 = k * (p-1)*(q-1) and dividing both sides by n it is fairly easy to see that floor((ed-1)/n) + 1 == k. Now using equations 31 and 32 of M.J. Wiener's "Cryptanalysis of Short RSA Secret Exponents" one can directly recover p and q.

2
  • 1
    I think there is a conceptually simpler solution when e is small, which usually is the case in real applications of RSA. In those cases ed-1 is a small multiple of (p-1)(q-1), which should be very close to n, so you can brute-force all the sensible values of (p-1)(q-1), from which and n=pq you can solve a simple quadratic system of equations to find p and q. Feb 18, 2018 at 11:53
  • @ImperishableNight: I finally got around to examining your comment and I have to agree with you, your method is conceptually simpler. I will edit my answer to include your method as well. Sep 25, 2019 at 16:55
11

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.

8
  • Just providing the answer doesn't help the OP... Wolframalpha certainly won't be available to him/her on a test. Nov 2, 2010 at 15:02
  • 1
    Well, that certainly gives me the answer! If no one else explains how to do this by hand, I'll give you the green checkmark.
    – Donald T
    Nov 2, 2010 at 15:03
  • 16
    StackOverflow is not a giant calculator site. The goal of the site is to help people understand how to do things. It's not a place where you ask people to code or calculate for you. Nov 2, 2010 at 15:08
  • 1
    @Juri the homework tag should have tipped you off that just providing the factors regardless of what the OP asks for is not best practice. Nov 2, 2010 at 15:16
  • 1
    All questions should be evaluated to see how they best need to be answered — notice Silence's comment doesn't distinguish homework from the rest. If the poster needs to provide more information (i.e. this question is sparse, any way you slice it), then you have to ask. Tagging homework doesn't tell you anything. For example, if I asked this question (and I definitely don't do homework anymore), I'd want explanation rather than the two factors.
    – Roger Pate
    Nov 8, 2010 at 12:44
4

The definition of RSA tells you that the modulus n = pq. You know n so you just need to find two numbers p and q that multiply to produce n. You know that p and q are prime, so this is the prime factorisation problem.

You can solve this by brute force for relatively small numbers but the overall security of RSA depends on the fact that this problem is intractable in general.

2
  • Not true! When the decrypt exponent is given, as it is in this case, the problem is easy. Nov 3, 2010 at 1:14
  • Well, when the decrypt exponent is given you have the private key, somewhat defeating the purpose. Does knowing d make the factorisation easier? If so, can you explain? Nov 3, 2010 at 17:11
4

Here is a Java implementation of the fast factoring method from the Handbook of Applied Cryptography chapter 8 section 8.2.2 (thanks to GregS for finding it):

/**
 * Computes the factors of n given d and e.
 * Given are the public RSA key (n,d)
 * and the corresponding private RSA key (n,e).
 */
public class ComputeRsaFactors
{
    /**
     * Executes the program.
     *
     * @param args  The command line arguments.
     */
    public static void main(String[] args)
    {
        final BigInteger n = BigInteger.valueOf(10142789312725007L);
        final BigInteger d = BigInteger.valueOf(5);
        final BigInteger e = BigInteger.valueOf(8114231289041741L);

        final long t0 = System.currentTimeMillis();

        final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE);
        final int exponentOfTwo = kTheta.getLowestSetBit();

        final Random random = new Random();
        BigInteger factor = BigInteger.ONE;
        do
        {
            final BigInteger a = nextA(n, random);

            for (int i = 1; i <= exponentOfTwo; i++)
            {
                final BigInteger exponent = kTheta.shiftRight(i);
                final BigInteger power = a.modPow(exponent, n);

                final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE));
                if (!factor.equals(BigInteger.ONE))
                {
                    break;
                }
            }
        }
        while (factor.equals(BigInteger.ONE));

        final long t1 = System.currentTimeMillis();

        System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0);
    }


    private static BigInteger nextA(final BigInteger n, final Random random)
    {
        BigInteger r;
        do
        {
            r = new BigInteger(n.bitLength(), random);
        }
        while (r.signum() == 0 || r.compareTo(n) >= 0);
        return r;
    }
}

A typical output is

100711423 100711409 (3ms)
4

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.

3

These two papers could possibly come in useful

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

1

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.

1
  • He is given the private exponent in his problem. Factoring n without using the additional information won't work for the large integers in real-world RSA systems. Sep 26, 2019 at 12:34
1

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.

0

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.

0

There is a lot of bad speculation about factorization of large semi primes which go into brute force or sieving neither of which is required to factorise the semi prime. 64 bit takes 1 - 2 seconds on my pc, and 256 bit generally less than 2 days

2
  • 2
    could you explain how you do it?
    – wake-0
    May 31, 2017 at 12:50
  • I will but not until I have cracked the RSA challenge numbers. Currently I'm trying to get my head around c+, cuda and visual studios. I'm a pascal programmer by nature. Meantime if u need 64 bit breaking drop me an email with details.
    – Mick Press
    Jun 1, 2017 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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