Difference between Symmetric and Asymmetric. Is this answer correct, based on a written test?

Question

I asked the following question on a final exam:

Symmetric Ciphers (e.g. AES, DES, Blowfish) use up to 256 bit on the best case, which are considered strong against brute-force attacks. On the other hand, asymmetric cryptography (e.g. RSA, DSA, Elgamal) use a higher amount of bits (~2048). Explain the reason of the bit difference between Symmetric and Asymmetric Ciphers.

His answer was:

Asymmetric Ciphers use more bits because generally it uses powers, which generates a bit increase. Additionally, Asymmetric Encryption requires more processing time than Symmetric, which leads to a higher cost on a bit level.

By “powers”, he meant “math powers”. He quotes the following from the internet to support his answer:

"The algorithm is slow, since it uses math operations which have a high cost and works with big key sizes. Part of the problem is on the choice of the exponent"

And finally:

"Although is not mathematically exact, the first operation could be accepted as linear since the number of operations is directly proportional to the size of both operands. On the other hand, the second operation is an exponential type because doubling the input size, the number of operations to make does not double, it increases exponentially in time."

Although the answer is here, I see that part of his statements are correct, but is he answering the question correctly?

Answer 1

I don't believe he is answering the right question. You essentially asked "why are public keys so much larger than symmetric keys", and after his first sentence (which started to address the question, but was a bit vague), he tried to answer the distinct question "why are public key operations so much slower" (not that he got the details of that correct; his last sentence appeared to imply that public key operations take an exponential amount of time).

Answer 2

I don't think it is right. The reason why RSA in particular uses such a high bit count, is that RSA's security is based on factorization of integers and integers with up to 100 digits (roughly 300 bits) can be "easily" factorized with the Quadratic Sieve.

In general, there are asymmetric ciphers like those based on elliptic curve cryptography that also use low bit counts of about 160 bits.

The reason, why most asymmetric algorithms use high bit counts is the following: Most of them are based on algebraic calculations and hence there are ways (or at least the probability is high) to find a shortcut around the algorithm and crack it (like factorizing the RSA public key).

Symmetric algorithms on the other hand often are intentionally "unalgebraic". For example AES does lots of bit XORing, shifting, mixing etc to prevent easily exploitable mathematical relations between cleartext and ciphertext.

Summary: A keyspace of 256-bits is more than large enough to be considered safe. But while most symmetric algorithms leave (almost) no other attack vector but bruteforcing the key, most asymmetric algorithms have well known attack vectors, that make cracking the algorithm way easier then just bruteforcing the key. Hence the keyspace must be much bigger to gain the same security.

Answer 3

symmetric ciphers are based on exactly the same and ONE and ONLY key on both sides. asymmetric ones are based on one or more exactly the same keys on both sides and at least one truly private key on each side, if we're talking about a bidirectional communication. key size is not important here.