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?

Nephrosis

It has nothing to do with AES. – Mezzorelievo

Also, to those who are voting to close. Encryption algorithms and cryptography is a strong field of computer science. Even if this doesn't relate to your programming doesn't mean it doesn't relate to programming. – Nephrosis

Encryption is indeed a programming topic, but this is a questions about number theory. – Beneficial

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.

Targett

+1, but this needs a bit of editing. I think some of your notation in that last set of bullet points got mangled. "n2 = (p-1)(q-1)", perhaps you meant phi(n) = (p-1)(q-1)? And if someone were to obtain p,q by factoring n, they could calculate phi(n), and then your decryption key D = E^-1 mod n, knowing only your public key (n,E). Therefore the security of RSA encryption depends on the fact that factoring is hard. – Structuralism

I'd say cryptographic algorithms definitely has to do with programming. – Substandard

Answer 2

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

The missing phrase is "public-key", as in "How is the public key encryption algorithm's security..."

In modern cryptography there two major categories of ciphers, symmetric (secret key) and public-key (which uses a public/private key pair).

Within each category, you will find the key sizes relatively close. For public-key systems like RSA and DH/DSA, both used in OpenPGP e-mail encryption, common key sizes are 1024-bit and larger these days (early 2010). This has to do with the mathematical requirements of suitable keys used to encryption and decrypt messages. For RSA, in short, it is many time easier to generate a factor of two random large prime numbers and do multiplication with them, compared to factoring of very large number that has no small factors. As you've discovered the factoring of very large numbers is the "problem" or approach needed to break RSA via brute force.

Diffie-Hellman / Digital Signature Algorithm (DH/DSA) are based on a different mathematical problem, calculating discrete logarithms.

Due to properties of the public and private key pairs, the search space is limited to factors of large primes numbers, which becomes incredibly sparse, so it makes sense to try to be far more intelligent then simply trying to factor every very large number.

Whereas with symmetric ciphers like AES, RC6, RC4, Twofish, DES and Triple-DES, these algorithms use a random key of a given bit length. Any non-trivial (i.e. 0x000...000 may be a poor key choice) random key is suitable. So these systems, if there is no attack against the algorithm itself, you can simply search brute force through the key space (i.e. try all 2^256 possible keys) to decrypt a message without the secret key. Since any key is suitable, the density of keys is 2^256.

I'm ignoring Quantum Computing (theoretic and practical), mainly because a) I can't give a solid answer, and b) it represents a large paradigm shift that turns much applied mathematics and computer science of computational complexity potentially on its head, that basic understanding is still a moving target. Oh, and most of my enemies don't have a quantum computer yet. :)

I hope that explains the general difference between the two types of crypto systems, such as RSA and AES.

Sidebar: Cryptography is a rich and complex topic, where the basics may be simple enough to understand, and even write a naive ("textbook") implementation, the complex subtleties of a secure implementation makes it best for programmers who are not cryptography experts to use high level crypto-systems including using well-known standard protocols to improve your chances that the cryptography of a system is not the exploitable flaw in a system.

Gamete

I think the Diffie-Hellman and DSA algorithms actually rely on the difficulty of calculating discrete logarithms, rather than the difficulty of factoring. But the public key algorithms do seem to come from a more number-theoretic perspective than the symmetric ciphers you mentioned. – Structuralism

@Jim: If factoring were broken (ie. an efficient algorithm for factoring were found), the discrete logarithm would be broken as well, but not necessarily the other way around. In fact, it is possible that RSA could be broken without efficient-factoring being solved as well; see here: en.wikipedia.org/wiki/RSA_problem – Agnesagnese

@Jim @BlueRaja: Quantum algorithms exist that would defeat cryptography based on both factoring and discrete logarithms. We just don't have a quantum computer to run the algorithms on. – Crowberry

Thanks for the comments. I've edited my answer to try to incorporate your feedback, and hopefully not detract from the clarify (which would be my fault). Thanks again. – Gamete

Answer 3

AES is much different, AES creates a SPN, Substitution Permutation Network. It generates s-boxes (substitution boxes) based on polynomial functions generated at encryption time. It runs it through 10-14 rounds of byte-level substitution and bit-level permuting, the bit length of the key determining the number of rounds and the round keys.

RSA is based on factors of large prime numbers which are extremely hard to do computationally, but quite easy to initially encrypt.

Mohamedmohammad

based on factors of large prime numbers - prime numbers have only themselves and one (1) as integer factors (over natural numbers). This is a common mistake, Bill Gates made the same mistake in one of his books. RSA is concerned secure in a practical sense, because factoring of very large numbers into their prime factors is hard (and both a very old and thus well studied problem in the area of number theory in mathematics). – Gamete

The more basic distinction is that AES is a symmetric cipher that uses a single secret, whereas RSA is a public-key crypto-system, that has two keys, one public, one private. – Gamete

I agree, my description of RSA was lacking, but the distinction between public key crypto systems and single key secrets wasn't really the question. – Mohamedmohammad

Key sizes tend to be similar within these types of ciphers. I.e. AES, Twofish, RC6, and other AES candidates have similar key sizes, whereas public key cryptography uses key-pairs based on large numbers that are 1024 to 4096 (largest serious key size I've seen used for RSA) bits in length (binary representation, I forget the length in decimal, but very large). I believe the difference is more helpful to understanding the difference than details about the SP-network, and the number of rounds of substitution. – Gamete

Answer 4

RSA is broken by factoring. Actually, RSA is two algorithms, one for (asymmetric) encryption and one for digital signatures; both use the same primitive. In RSA, there is a public value (the modulus, often noted n) which is a product of two (or more) distinct prime factors. Factoring n reveals the private key. Factoring becomes harder when the size of n increases. The current record (published earlier this year) is for a 768-bit integer; it took four years of big computing and hard work by very smart people. The same people openly admit that they have little clue of how they could try the same stunt on a 1024-bit integer (there is a part of the best known factorization algorithm which requires an awful lot of fast RAM, and for a 1024-bit integer that would require a ludicrously huge machine). Current recommendations of key length for RSA are 1024 bits for short term, 2048 bits for long term security. Note that computational cost of RSA increases with key size as well, so we do not want to use really big keys without a good reason. A basic PC will produce about 1000 RSA signatures per second (and per core) with a 1024-bit key, and eight times less with a 2048-bit key. This is still quite good.

There are other asymmetric encryption algorithms, and digital signature algorithms. Somewhat related to RSA is the Rabin-Williams encryption algorithm; factoring also breaks it. Then there are algorithms based on discrete logarithm (in the multiplicative group of numbers modulo a big prime): Diffie-Hellman (key exchange), DSA (signature), El Gamal (encryption)... for these algorithms, factorization is no direct threat; but they rely on the same parts of number theory, and the best known algorithm for discrete logarithm is very similar to the best known algorithm for factorization (and has the same name: GNFS -- as General Number Field Sieve). So it is suspected that an advance in factorization would result from an advance in number theory which would be likely to shed some light on discrete logarithm as well.

The discrete logarithm algorithms can be applied to other groups, the most popular being elliptic curves. Elliptic curves are not impacted by factorization. If factorization became easy, thus scraping RSA and indirectly jeopardizing DSA and Diffie-Hellman, then we would switch to ECDH and ECDSA; standards and implementations exist and are deployed.

"Symmetric cryptography", i.e. hash functions (MD5, SHA-256...), authentication code (HMAC, CBC-MAC...), symmetric encryption (AES, 3DES...), random number generation (RC4...) and related activities, are totally unaffected by factorization. For these algorithms, keys are mere bunches of bits, without any special structure; there is nothing to factor.

Margenemargent