Symmetric vs. asymmetric

[Pavel Kubal]

Hi,

sorry if this question doesn't belong here.

I would like to know why are asymmetric keys so large (256b +) in comparison to symmetric? I don't need detail implementation of all algorythms, just overview. I searched, but without success.

[Reid M. Pinchback]

I think the basic issue is that asymmetric keys involve sharing one half of a key pair, and you don't want to be able to crack the second key just because you already have the first key. Example, in public key systems that involve large prime/pseudo-prime pairs you always want to be able to give away one key without it comprising the matching member. More bits increases the search space for the second key.

None of this is an issue for symmetric keys = private keys. There you don't have the key, just the encrypted data. Cracking the key involves decrypting the data, not analyzing the primary key itself (because you don't have a copy of it unless you are one of the parties exchanging messages).
[ March 18, 2006: Message edited by: Reid M. Pinchback ]

[Pavel Kubal]

Thanks for the explanation.

[Henry Wong]

I just read 2 paragraphs that made absolutely little sense... Anyway, to answer your question...

Symmetric keys simply means that the key that encrypt the data is the same key that will be decypting the data. Asymmetric keys means that the algorthm uses a different key to encrypt and decyprt the data. The size of the keys have little to do with whether the keys are symmetrical vs asymmetrical -- for example, triple DES is symmetrical, and the keys are huge. The size of the keys are related to the "strength" of encryption algorithm.

As for the two paragraphs...

Assymetric keys are generally broken down to public and private keys (In truth, they are interchangable, but generally one is chosen as the public and one is chosen as the private). Since the key that does the encryption is not the same as the key that does the decryption, you can literally make one key the public key -- meaning send it in the clear.

If I give my public key to someone who then uses it to encypt a message, he can send that message to me without fear that it will be seen. People that are monitoring us only has the public key and the encypted message. Since the encrypted message was done with the public key (that I sent over), it can only be decrypted by the private key, that I have kept private.


Symmetric keys have a problem with this (or at least used to). It is very difficult for me to send the key, or get the key, since the key is used for both encrypt and decrypt, it needs to be protected. Once it is released, the protection is lost.

This have been fixed with what is called key exchange. This is a process where two machines generate random numbers, send calculate values to each other based on the value, and arrive at the same value which can then be used as the encryption and decryption keys. Anyone monitoring will only see the two calculated values, and neither random number, and will not be able to arrive at the key value... pretty cool mathematics.

Henry

[NOTE: It has come to my attention, via private message, that the first sentence of the first paragraph of this post is offensive. It was certainly *not* my intention to offend, and I apologize, if it has been taken that way.

I merely wanted to say that Mr. Pinchback's response was incorrect. But my personality sometimes causes me to throw in a snide remark. ]
[ March 23, 2006: Message edited by: Henry Wong ]

[Reid M. Pinchback]

And somehow all of that never addressed the original question... is it not the case that in typical usages of asymmetric approaches that you see larger keys? I'm with the poster, I've seen the same thing over the last 20-ish years of their use, particularly in public-key infrastructures, which are particularly amenable to attacks based on the key distribution system.
[ March 19, 2006: Message edited by: Reid M. Pinchback ]

[Henry Wong]

And somehow all of that never addressed the original question... is it not the case that in typical usages of asymmetric approaches that you see larger keys?

I don't see how one implies the other... (key length vs key symmetry)

Algorithms that use asymmetric keys tend to take longer to use. This makes it cumbersome to use for stuff like VPNs. Symmetric algorithms tend to be faster, but have the initial key exchange problem.

Furthermore, longer keys take longer to process -- just mathematics.

So... Typical uses of symmetric keys tend to be when speed is an issue. And hence, the keys tend to be configured smaller too.


But I don't see how just because algorithms that use symmetric keys tend to be configured to use smaller keys, lead to the conclusion that symmetric keys are inherently smaller.

The size of the keys is dependant on the desired "strength" of the encryption, not whether the keys are symmetric or asymmetric.

Henry
[ March 19, 2006: Message edited by: Henry Wong ]

[Reid M. Pinchback]

Still not getting it. If algorithms using symmetric keys are faster, then for the same amount of time you could afford to use a *longer* key. Also, why can you have public key systems that use DES or DES-like transforms as the core of the message encryption? If DES-style bit manipulations are fast enough for a symmetric key, what made it all of a sudden hugely slow for an asymmetric key? An extra mod'ing of the bits at the right point between the symbol swaps isn't that big of a deal.

In shifting from symmetric to asymmetric keys, aren't you simply shifting from encrypting with a key that provides its own inverse to instead using a key whose inverse is determined by a harder-to-compute congruence relationship? You only compute that relationship once when generating the keys, so for a fix key length and known keys, the performance difference should be on the order of single-digit percentages (as in communications/IO bandwith variability should be more of a factor, e.g. when using spread spectrum in a noisy environment). Creating the key pairs is very slow, but using them isn't intrinsically slow, only particular choices of public key infrastructure implementation.

This position only makese sense if you believe that asymmetric approaches to encryption have to be intrinsically slower than DES in order to encrypt the bits. I worked on one of these beasties once. Such definitely wasn't the case. There are definitely very strong encryption algorithms that you may choose to use that definitely are slow in software, and I vaguely recall one family of them out of UoWaterloo that were non-RSA based yet would involve asymmetric keys being strong+slow, but holding all other variables in the problem equal, simply choosing symmetric versus asymmetric keys doesn't universally change performance in a huge way. The schemes for managing keys and the schemes for encrypting the messages themselves influence performance... but even for DES with private keys that has been true for over 20 years. Different DES variants have tradeoffs between performance, encryption strength via controlling the # of iterations, and recovery to communications noise bursts. The extra features influence the performance, the length of key influences the performance, but the choice of symmetric vs asymmetric key for a specified length doesn't have to change it materially.
[ March 19, 2006: Message edited by: Reid M. Pinchback ]

[Henry Wong]

Wow... lots of data... I'll try to address some at a time...

Still not getting it. If algorithms using symmetric keys are faster, then for the same amount of time you could afford to use a *longer* key. Also, why can you have public key systems that use DES or DES-like transforms as the core of the message encryption? If DES-style bit manipulations are fast enough for a symmetric key, what made it all of a sudden hugely slow for an asymmetric key? An extra mod'ing of the bits at the right point between the symbol swaps isn't that big of a deal.

Asymmetric key algorithms "Tend to be" or "arguably" slower. Hard to actually say so, as it is like comparing apples and oranges.

DES is a symmetric key algorithm. There is no such thing as DES with asymmetric keys.

I agree that DES is used to encrypt stuff in public key systems, but it can't be used as the "public" key stored in those systems. It doesn't have a concept of public/private keys, as it is a symmetric algorithm.

As for why people won't choose DES with a longer key, than a asymetric key algorithm. I have no idea.

Henry

[Henry Wong]

In shifting from symmetric to asymmetric keys, aren't you simply shifting from encrypting with a key that provides its own inverse to instead using a key whose inverse is determined by a harder-to-compute congruence relationship? You only compute that relationship once when generating the keys, so for a fix key length and known keys, the performance difference should be on the order of single-digit percentages (as in communications/IO bandwith variability should be more of a factor, e.g. when using spread spectrum in a noisy environment). Creating the key pairs is very slow, but using them isn't intrinsically slow, only particular choices of public key infrastructure implementation.

Symmetric key based algorithms and asymetric key based algorithm are different algorithms. I don't know if it is possible to generate a key pair, that are equal, as the key pair generation (for asymmetric algorithms) are designed so that you can't decipher the other key, given one of the keys. And even if you could, why would you want to do it? If you want symmetric keys, wouldn't it be easier, (and faster) to use an algorithm that uses symmetric keys?

Henry

[Henry Wong]

This position only makese sense if you believe that asymmetric approaches to encryption have to be intrinsically slower than DES in order to encrypt the bits. I worked on one of these beasties once. Such definitely wasn't the case. There are definitely very strong encryption algorithms that you may choose to use that definitely are slow in software, and I vaguely recall one family of them out of UoWaterloo that were non-RSA based yet would involve asymmetric keys being strong+slow, but holding all other variables in the problem equal, simply choosing symmetric versus asymmetric keys doesn't universally change performance in a huge way. The schemes for managing keys and the schemes for encrypting the messages themselves influence performance... but even for DES with private keys that has been true for over 20 years. Different DES variants have tradeoffs between performance, encryption strength via controlling the # of iterations, and recovery to communications noise bursts. The extra features influence the performance, the length of key influences the performance, but the choice of symmetric vs asymmetric key for a specified length doesn't have to change it materially.

I guess I will have to agree... As I am pretty sure that if there was actually an encyption algorithm that allows you to choose whether to used symmetric or asymmetric keys, that the choice of using one or the other, would have little affect on speed of encryption.

As for the current state of affairs, it is like comparing apples and oranges. You can probably find cases where asymmetric based algorithms are faster -- I am just saying that when speed is a concern, the symmetric algorithm tends to be chosen most of the time.

IMHO, putting special cases aside... an average asymmetric key based algorithm, is *slower*, perhaps hundreds of times slower, than an average symmetric key based algorithm.

Henry
[ March 19, 2006: Message edited by: Henry Wong ]