Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
The question would have been better with "use a key of up to 256 bits on the best case"; and "Explain the reason for the difference in key size". $\;$ One reason that the answer miss the point (as it does) could be that the reader did not catch that the question was about key (rather than data) size. On the other hand, one knowing that AES, DES, and Blowfish, have a data size of at most 128 bits should have figured out that the question was about key. –  fgrieu Dec 10 '14 at 22:58

3 Answers 3

up vote 3 down vote accepted

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).

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
"key size is not important here" is just not true. Key size is always important. Having any encryption algorithm with a 1-bit key means, that decrypting with either 0 or 1 yields the correct cleartext. The more bits your cleartext message has, the more probable it becomes, that just one of both alternatives is a meaningful cleartext and hence the searched cleartext for the ciphertext. –  Thekwasti Dec 11 '14 at 8:02
    
I didn't meant that it is not important at all. You're right in your comment. I was meaning to say that related to this question the importance is not a key size. That's it :) –  Alexey Vesnin Dec 17 '14 at 21:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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