Re: Can a table of p*q numbers be used to crack a pub. key encrypted message?

Dear Thomas,

To answer your question, let's assume we are talking about a very commonly used public key cryptosystem called RSA, developed in the seventies by Ron Rivest, Adi Shamir and Len Adleman at MIT.

The details of how this system works are a bit technical and can be found in almost any discrete math textbook, so I won't go into them. For now, we just need to know two things:

(1) The public key, used to encrypt a message, is a product of two very large prime numbers, p and q, which are not public.

(2) So far, no one has been able to find a way to decipher an encrypted message (without knowing the decryption key) using a method that would NOT involve factoring n into p and q.

Assuming these two things, the only way to crack the code is to factor n into p and q. You're asking if we could use a table containing the products of primes. My discrete math textbook tells me that encryption algorithms commonly use primes with as many as 200 digits. Knowing that, let's just consider a table containing the products of all pairs of 200 digit primes. We now face two questions:

(1) Could we store such a large table in our computer?

(2) Having the table, could we decrypt a message without knowing the decryption key?

Fortunately for whoever encrypted the message, the answer to both questions is no:

(1) Suppose we have some nice way of generating all 200 digit primes. How many are there? According to the prime number theorem, "the number of primes not exceeding x is asymptotic to x/ln(x)," where ln(x) is the natural logarithm of x (see the Prime Pages link below). The number of 200 digit primes is the difference between the number of primes with at most 200 digits and the number of primes with at most 199 digits. Using the prime number theorem, the number of 200 digit primes is approximately

10²⁰⁰/ln(10²⁰⁰) - 10¹⁹⁹/ln(10¹⁹⁹)

which is about 10¹⁹⁷ prime numbers. To get an idea of just how large that number is, suffice is to say that the number of atoms in the universe is estimated at about 10⁷⁹ (see the National Solar Observatory link below) - even if we could generate the table, we wouldn't be able to fit it into the universe!

(2) Suppose now that we somehow managed to overcome the obstacles posed by (1). Could we use the table to crack the code? We would have to try, in an average case, about half the numbers in the table before arriving at the correct one. Even the fastest computers that we now have would take billions of years to do such a huge computation. Incidentally, it would also take billions of years to factor a 400-digit encryption key n into the prime factors p and q, which is what we were trying to avoid in the first place.

Finally, here are some references that you can check out for more details:

* A good discrete math textbook: Discrete Mathematics and its Applications by Kenneth H. Rosen

* The original RSA paper: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems by Rivest, Shamir and Adleman - http://theory.lcs.mit.edu/~cis/pubs/rivest/rsapaper.ps

* A website with lots of interesting readings about security, etc (including a copy of the above paper): http://www.cs.virginia.edu/~jones/cs551S/cs551_reading.html

* The Prime Pages: All you ever wanted to know about primes: http://www.utm.edu/research/primes/

* Answers to some questions about the universe (hosted by the National Solar Observatory): http://www.sunspot.noao.edu/sunspot/pr/answerbook/universe.html

I hope this helps!

Tomas
http://www.ai.mit.edu/people/tomas

[Admin Note: Also, please see this site for how to figure out how many primes there are. -- RJS]