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've been told that asymmetric cryptography requires that the message to be encrypted be smaller than its key length. Why is this?

I know about hybrid encryption, which uses symmetric encryption to resolve this problem. But I still want to know why public-key cryptography needs the data to be shorter than the key length.

share|improve this question
2  
Welcome to Crypto.SE. I encourage you to read the FAQ. In particular, we expect you to have "done your homework" before posting a question. This particular question must have been asked a dozen times on this site. Did you try a search? Also try looking at the questions in the Related bar. For instance, the 3rd in the list is crypto.stackexchange.com/q/586/351 which seems to answer your question satisfactorily. –  D.W. Dec 19 '12 at 21:20
    
Thanks for the answers but it does not directly answer my question: Why does it need to have data smaller than it's key length. I know it takes a lot of CPU compared to Symmetric Encryption but it's not the answer I'm looking for unless you are indirectly telling me it needs data smaller than it's key length because of CPU usage. –  K_X Dec 20 '12 at 20:04
    
Sorry, I'm not sure what you mean by "it". Are you asking, why does public-key encryption need to encrypt data that is smaller than its key length? If so, you should revise your question, because that's not what I'm getting out of your question at all. –  D.W. Dec 20 '12 at 21:53
    
"Why does Asymmetric Cryptography need data smaller than it's key length" is my unequivocal question. –  K_X Jan 3 '13 at 18:01
    
@K_X: I now address this in an extension of my earlier answer. –  fgrieu Jan 3 '13 at 20:49
add comment

2 Answers

up vote 9 down vote accepted

There are two main reasons why asymmetric cryptography is practically never used to directly encrypt significant amount of data:

1) Size of cryptogram: symmetric encryption does not increase the size of the cryptogram (asymptotically), but asymmetric encryption does. If we take the example of RSAES-OAEP in PKCS#1v2 with a 1024-bit key and 160-bit SHA-1 hash, a 1024-bit cryptogram can convey a maximum of 688 bit of useful information. Thus data enciphered in this way would cost 49% more space to store, or more time to move over a given link.

2) Performance: on a modern CPU with hardware AES support, encryption or decryption speed is over 2000 megabyte/second (per core); while decryption of a 1024-bit cryptogram in the above scheme can perhaps run at 4000 per second (per thread of a comparable CPU), thus a throughput of 0.4 megabyte/second, 5000 times slower; that's also moreless the ratio of power usage. That ratio tends to get even worse as security increases. While there are more efficient schemes, it is safe to say that a symmetric scheme is orders of magnitude faster and less power hungry than an asymmetric one, at least for decryption (some asymmetric schemes, including RSA with low public exponent, are considerably faster on the encryption side than they are on the decryption side, and can approach the throughput of some symmetric cryptography).


Addition: Asymmetric Cryptography does not "need data smaller than its key length". For example, the public key in an RSA scheme can be reduced to about half the cryptogram / modulus size by fixing high-order bits of the modulus $n$, and setting $e$ to a fixed value, thus can have a cryptogram nearly half the public key size. The private key can be compressed even further, ultimately to the seed of a PRNG.

However, any public-key encryption schemes is bound to increase the size of the data that it enciphers: if it did not, there would be a single ciphertext for any given plaintext, and thus an adversary could test if the plaintext is a certain value, simply by enciphering that value (using the public key) and comparing to the ciphertext. Public-key encryption schemes typically increase the cryptogram size by $k$ bits to resist such attack with a strength of $2^k$ encryptions.

share|improve this answer
    
Sorry but those AES-NI numbers are ludicrous and are heavily artificial. The latest processors can get a per-core throughput of 800-900MB/s at best in a real implementation with a proper mode of operation. Your point still stands but remember marketing benchmarks are not representative of real life performance. –  Thomas Dec 20 '12 at 8:30
    
@Thomas: I agree that real implementations tend to be 2-3 times slower than "marketing benchmarks". That's in a large part because real implementations seldom use assembly language all over the critical data path, trading performance for simplicity and portability. At least I'm comparing two "marketing benchmarks" against each others, and I think that my ratio of 5000 is not inflated. –  fgrieu Dec 21 '12 at 10:59
2  
No, the ratio is fine, but I was just noting that the speeds you quoted are generally only obtained when you hardcode everything in a very tight loop, with zero function calls or parameters, in assembly. In any realistic application this is simply not logistically viable - you need the code to be modular and flexible so that it can be reused easily. OpenSSL uses a decently optimized AES-NI implementation and AES-128-CBC runs at 720MB/s per core on my overclocked i5 (openssl speed -evp aes-128-cbc). –  Thomas Dec 21 '12 at 11:12
add comment

Symmetric encryption is generally faster than asymmetric encryption. That is the basic reason to use symmetric encryption with larger amounts of data. The time difference between the two methods will increase linearly as the amount of data increases.

From Wikipedia on computional cost of Public-key cryptography:

Computational cost

The public key algorithms known thus far are relatively computationally costly compared with most symmetric key algorithms of apparently equivalent security. The difference factor is the use of typically quite large keys. This has important implications for their practical use. Most are used in hybrid cryptosystems for reasons of efficiency – in such a cryptosystem, a shared secret key ("session key") is generated by one party, and this much briefer session key is then encrypted by each recipient's public key. Each recipient then uses the corresponding private key to decrypt the session key. Once all parties have obtained the session key, they can use a much faster symmetric algorithm to encrypt and decrypt messages. In many of these schemes, the session key is unique to each message exchange, being pseudo-randomly chosen for each message.

share|improve this answer
1  
Not to mention, asymmetric encryption with a 2,048-bit key isn't necessarily more "secure" than symmetric with a 256-bit key. –  Stephen Touset Dec 19 '12 at 22:28
add comment

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.