Symmetric vs. Asymmetric cryptographic approaches to data security

Question

I know the basic differences between Symmetric vs. Asymmetric cryptography, but I'd love to know more details:

1. Exactly why is the asymmetric approach slower than the symmetric?
2. Why does it make use of longer keys?
3. Why does it require more processing power, etc, etc?
4. In what ways does it trump the symmetric approach?

Thanks, in anticipation, for your answers - I'm writing a BSC project on this issue.

Answer 1

The simple answer to "why are asymmetric algorithms more costly than symmetric algorithms" is because we have more requirements for asymmetric algorithms, and those additional requirements cost something to satisfy.

The requirement for (say) a symmetric encryption algorithm is "if you encrypt a message with the key, then someone without the key cannot infer anything about the message (apart from the length), but someone with the key can recover the exact message".

Now, asymmetric algorithms also meet this requirement. If we replace "key" with "the public and private keys", then we can encrypt messages (with the public key portion), and no one without the private key portion can deduce anything about the encrypted message.

On the other hand, we place additional requirements on asymmetric algorithms; someone with the public key still cannot decrypt messages, even though they can encrypt. This implies that the public key and the private key must be related (because they are, in some sense, inverses of each other), but it can't be in an obvious way.

This means that the efficient constructions we use for symmetric algorithms (xor'ing in a keystream, Feistel networks, or SP-networks) just won't work, because those are easily invertable (given the key) by construction. For symmetric operations, we can pick operations rather arbitrary, limited only by their efficiency, and how well they are disguised by a secret key. Instead, we also need to limit ourselves to operations which have nonobvious relationships; these mathematical constructions (which is where we find this nonobviousness) are considerably less efficient.

As for when asymmetric operations "trump" asymmetric ones; the rule is simple: if you need the additional properties that asymmetric operations provide, they're better; if you don't, then they're not needed.

Answer 2

1. This is mainly due to the underlying problems used in each. For symmetric, you can get sufficient confidentiality with simple operations (substitutions, permutations, etc). For asymmetric, the underlying problems (factoring, discrete log, etc) require very large numbers (thousands of bits) and much more expensive operations (exponentiation, etc).
2. Typically recommended key sizes come from the speed of known attacks. You look at the fastest algorithms available to break a cryptosystem and pick a key size that is large enough so that these attacks are not feasible. Thus, the algorithms we know of to break asymmetric systems are much faster than the algorithms we know of to break symmetric systems (speaking generally). That said, elliptic curve systems have key sizes fairly close to symmetric algorithms.
3. See #1 and #2.
4. see Why do we need asymmetric algorithms for key exchange?, but in short, they each have their advantages and disadvantages.