How does being able to factor large numbers determine the security of popular encryption algorithms?

Question

How is the encryption algorithm's security dependent on factoring large numbers?

For example, I've read on some math-programming forums that by using the Quadratic Sieve or the General Number Field Sieve, one can factor a 256 bit number with relative ease on commercially available hardware.

How does this translate to being able to break the security of algorithms such as RSA, AES, etc? Is being able to factor numbers the length of the key enough?

Is there anyone knowledgeable in cryptography and encryption algorithms who could shed a little light on it?

Answer 1

RSA, the cryptoalgorithm, relies on number theory, specifically the multiplication of two large primes and the fact this is difficult to factor, to differentiate between public and private keys.

Here's a question on Yahoo answers where someone has given some detail: http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

It relies on a few facts:

• n=p.q is easy to calculate but hard to reverse
• Fermat's little theorem: http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
• Various results of number theory.

It is not factoring large numbers that is difficult, it is factoring two large numbers whose only factors are themselves large primes, because finding those primes is difficult.

A quick search through my bookmarks gives me this: the mathematical guts of rsa encryption if you're interested in how it works. Also, some explanation here too - just re-read my num-theory notes to be clear.

• n = p*q gives you a large number given p,q prime.
• phi(n) = (p-1)(q-1). This is an extension of Fermat's little theorem More on why we need this and why it works on my blog here: http://vennard.org.uk/weblog/2010/02/a-full-explanation-of-the-rsa-algorithm/
• Which means, if we choose a number E coprime (no common prime factors) to (p-1)(q-1) we can find Es inverse mod phi(n).

• Which we do, we find DE = 1(p-1)(q-1) or rather we solve using euclid's greatest common divisor algorithm, extended version.

• Now, given all of the above, if we take T^E (pq) we get C. However, if we take (T^E)^D (pq) we get T back again.

AES isn't the same - it isn't public key cryptography. AES takes one key and uses that in both directions, encryption and decryption. The process is basically very difficult to undo, rather like a hash but designed to be reversible. It however, does not rely on factoring large numbers into primes for its security; it relies entirely on the strength of the key and the inability to deduce either the key from the algorithm or the key given known plaintext and the algorithm.

Wikipedia has a good article on AES for high level with a good link that shows you how it works - see here and here. I particularly like the latter link.