Fog Creek Software
Discussion Board




Asymmetric encryption, limited usage?

I'm doing some basic reaserch/tinkering with asymmetric encryption with C# and I've noticed something strange in several docs on MSDN.  In one place they say:
"Asymmetric algorithms are usually used to encrypt small amounts of data such as the encryption of a symmetric key and IV."
(from http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpguide/html/cpcongeneratingkeysforencryptiondecryption.asp)

In another place they discuss a typical encrytion use-case and also suggest using asymmetric encryption just to create a symmetric key-- not for the entire communication session. 

Is there some reason why you would only use asymmetric encryption for small amounts of data?  Is it a performance issue?

Steve H
Tuesday, June 29, 2004

Yes, Asymmetric encryption is slow.  SSL, for example, uses asymmetric encryption to do key exchange and then all traffic is encrypted symmetrically with those keys.

Almost Anonymous
Tuesday, June 29, 2004

Yes, asymmetric encryption is very slow compared to symmetric encryption, so it's better to encrypt the session key with an asymmetric encryption, and continue from there with a symmetric encryption using that session key.

GD
Tuesday, June 29, 2004

(I am not even a self-proclaimed cryptography expert, let alone a real cryptography expert.  Can anyone verify/refute this?)

In addition to what earlier posters have said, an encryption scheme is typically easier to crack with a larger canon of encrypted data, provided the cracker knows the key hasn't changed.  Using asymmetric encryption to send the symmetric key dramatically reduces the amount of data that's encrypted with the private key.

schmoe
Tuesday, June 29, 2004

(I'm not a cryptographer either.)

My understanding is that the amount of data able to be encrypted through asymmetric encryption is limited to the size of the key (1024, 2048, 4096 bits etc.) without introducing techniques such as cipher block chaining (CBC) with an IV to maintain a bit of security where the data within blocks repeats itself. However, I've only ever seen those applied to symmetric ciphers, and it may not be feasible to apply such things to asymmetric cryptography anyway.

Performance is definitely an issue: by doubling the size of the key, the amount of processing required (for RSA algorithms) increases by a factor of eight. Symmetric keys, however, are typically much smaller (e.g. 128 or 256 bits) and are more efficient partly because of this; the maths involved is less dependent on expensive operations involving prime numbers, too (I'm as much a mathematician as I am a cryptographer, so please correct me here if I'm wrong).

From a security standpoint, and schmoe mentioned this already, with a suitably seeded PRNG, a fresh symmetric key can be generated and distributed in a secure manner for each session (SSL, PGP, etc.) and used to encrypt the same data with a completely different key. To maintain this security with asymmetric cryptography, it would be necessary to generate a fresh public and private key for each session (and you'd get the distribution, signing and revocation headaches which go with this), otherwise the same data after encryption would look identical to the previous sessions', which is basically a no-no.

Steve R
Tuesday, June 29, 2004

It's true that having a larger set of encrypted data makes it easier to find the key, but there are two important points here:
1. The size of the data we're talking about is typically around 2^32 bytes, sometimes more. I haven't seen a good crypto that had an attack on it with less than 2^32.
2. If you're doing a brute force attack, it doesn't matter how much data you have, you just need to know the plain text so you can check the results.

Also, the protection from the asymmetric crypto is not due to its long key size, but due to the way that they keys are generated. Where in a symmetric crypto you use the same key, in an asymmetric crypto, in order to reverse engineer the key, you'd need to figure which two primes created the asymmetric key, a problem that is mathematically hard. (though there's always the brute force ofcourse, but that's where key length comes into play)

GD
Tuesday, June 29, 2004

"Applied Cryptography" isn't all that bad you know.

Jonas B.
Wednesday, June 30, 2004

"you just need to know the plain text so you can check the results."

No, that's not true. How do you expect the receiver to check the results? Techniques like CRC and checksums are used. They're not failsafe, but at least you don't really have to know the plaintext.

Also, size is not a problem for asymm. encryption. If it were, you would just "chop" the source into several pieces and encrypt them seperately.

Janonymous
Wednesday, June 30, 2004

If you don't know the plain text, how do you calculate the crc in the first place?

GD
Wednesday, June 30, 2004

No - "You" don't calculate the CRC. It's already there when you decrypt a message, so the receiver can check its decryption.

Janonymous
Wednesday, June 30, 2004

The original question was if assymetric encryption (i.e the encryption algorithm) was slower than a symmetric algorithm., which of course it is (at least for all algorithms that I'm aware of).

Cyclic redundancy checks (CRC) uses a related but different type of cryptographic techique to produce a fixed length fingerprint of an input block, which may be encrypted or not.

This means that the CRC code can be applied to either plain text or cipher text.

I everyday language, when people speak of encryption algorithms, they usually refer to complete crypto systems, built from encryption/decryption algorithms, key generation/distribution techniques, cryptographic protocols, message digests (e.g CRC based on cryptographic hash codes), digital signatures etc.

Jonas B  mentioned 'Applied Cryptography', which explains the different parts somewhat detailed. I second that suggestion.

Implementing an encryption/decryption algorithm is not useful in itself. You need an entire crypto system. And that is not small feat to take on single handedly.

cheers
/H

Henrik Sidebäck
Wednesday, June 30, 2004

*  Recent Topics

*  Fog Creek Home