Why public key algorithms are slow?

Question

I'm studying for a test and I'm still didn't get it why public key algorithms are way slower than symetric algorithms.

Answer 1

Public-key cryptography is a form of asymmetric cryptography, in which the difference is the use of an extra cryptographic key.

Symmetric algorithms use a "shared secret" in which two systems each use a single cryptographic key to encrypt and decrypt communications.

Public-key cryptography does not use a single shared key, instead it uses mathematical key-pairs: a public and private key. In this system the communications are encrypted with the public key and is decrypted with the private key. Here is a better explanation from Wikipedia:

The distinguishing technique used in public key cryptography is the use of asymmetric key algorithms, where the key used to encrypt a message is not the same as the key used to decrypt it. Each user has a pair of cryptographic keys—a public encryption key and a private decryption key. The publicly available encrypting-key is widely distributed, while the private decrypting-key is known only to the recipient. Messages are encrypted with the recipient's public key and can only be decrypted with the corresponding private key. The keys are related mathematically, but the private key cannot feasibly (ie. in actual or projected practice) be derived from the public key. The discovery of algorithms that could produce public/private key pairs revolutionized the practice of cryptography beginning in the middle 1970s.

The computational overhead is then quite obvious: the public key is available to any system it's exposed to (a public-key system on the internet, for example exposes the public-key to the entire internet). To compensate, both public and private keys will have to be quite large to ensure a stronger level of encryption. The result, however, is a much stronger level of encryption, as the private decryption key (so far) cannot be reverse-engineered from the public encryption key.

There is more that can affect the "speed" of a public-key infrastructure (PKI). Since one of the issues with this system is trust, most implementations involve a certificate authority (CA), which are entities that are trusted to delegate key pairs and validate the keys' "identity".

So to summarize: larger cryptographic key sizes, two cryptographic keys instead of one, and with the introduction of a certificate authority: extra DNS look-ups, and server response times.

It's because of this extra overhead that most implementations benefit from a hybrid algorithm, where the public and private keys are used to generate a session key (much like a shared secret in symmetrical algorithms) to gain the best of both worlds.

Answer 2

Public key algorithms rely on "trapdoor" calculations, ones that are computationally expensive to encrypt and computationally intractable to decrypt with the secret key. If the first step is too easy (which correlates with speed), the second step becomes less hard (more breakable). Consequently, public key algorithms tend to be resource intensive.

Private key algorithms already have the secret during the encryption phase, so they don't have to do as much work as an algorithm with a public secret.

The above is an over-generalization but should give you a feel for the reasons behind the relative speed differences. That being said, a private key algorithm can be slow and a public key algorithm may have an efficient implementation. The devil is in the details :-)