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.

Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA.

(Note: I do realize that in practice this is done through an intermediate symmetric key, but this question assumes we only use asymmetric encryption.)

Say I try to do this: I slice up my data into 2n-byte blocks (padding with zeros [edit: padding appropriately] if necessary), append the block index to the block (to prevent the same plaintext from turning into the same ciphertext), then use my friend's public key to encrypt each block separately.

Is this a secure scheme, or does the fact that I'm re-using the key make it susceptible to some kind of attack? If so, is it used in practice in any existing algorithms? If not, is there any way to make it safe, aside from using a symmetric key?

share|improve this question
    
Why do you want to use such a scheme? I don't see an advantage of this scheme over hybrid crypto. If you're worried about per message size overhead, just use an EC-DH based scheme. –  CodesInChaos Jun 4 '12 at 17:20
    
What kind of integrity requirements do you have? Do you sign the messages or use a MAC? Without that, an active attacker can replace parts of the message with his own data. –  CodesInChaos Jun 4 '12 at 17:20
    
@CodeInChaos: It's just an encryption question -- I'm not worried about a per message overhead (as long as it's fixed), and I haven't worried about authenticity yet (I don't think signing would be a problem here). I'm just asking about the encryption part for now. –  Mehrdad Jun 4 '12 at 17:28
    
Why "splice up data into $2^n$-byte blocks" rather than the maximum allowed by the combination of the RSA random padding scheme used, the inclusion of the block number, and the public modulus size, which will likely combine into a block size that is not a power of two? –  fgrieu Jun 4 '12 at 20:41
    
@fgrieu: Just because it was a handy scheme... I don't really mind that part if it's different though. –  Mehrdad Jun 4 '12 at 21:01

2 Answers 2

up vote 7 down vote accepted
+50

Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.

However, if you fix the padding, there does exist one other potential problem; message malleability.

To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$. To send these, Alice actually sends:

$E(X_1), E(X_2)$

$E(Y_1), E(Y_2)$

Now, Eve can't modify each individual block (RSA with proper padding prevents that); what she can do is mix-and-match blocks, as so:

$E(X_1), E(Y_2)$

This would decrypt at $X_1, Y_2$, which might not be what Alice and Bob whats.

If you are silly enough to use RSA encryption in this manner, you do need something that binds the blocks together (or alternatively does some sort of integrity checking on the entire message).

As for whether people ever do this in practice, well, no they don't -- not because of security, but because it's so inefficient; using the RSA algorithm to communicate a symmetric key, and using that symmetric key to encrypt the message is far more efficient.

share|improve this answer
    
+1 thanks for the explanation. Just a question: do you happen to know any ballpark numbers on just how inefficient a scheme like RSA is? (e.g. in KB/s or something, or how many times slower than symmetric encryption, for a typical-sized key.) Just as a rule of thumb -- anything within an order of magnitude is great. –  Mehrdad Jun 4 '12 at 17:32
    
@Mehrdad: Well, while performance is pretty platform specific; for general numbers, we can look at cryptopp.com/benchmarks.html . According to that page, AES can be done at about 100MByte/second, while RSA decryption with a 1K key takes 1.46msec per 1kbit; or about 0.085MByte/second (not accounting for the fact that padding cuts into the 1kbit/message); that gives us about a factor of 10,000 or so. Note that this is, in a number of ways, an apples-to-oranges comparison; the real factor may be quite larger. –  poncho Jun 4 '12 at 17:42
    
Oh dang, ok thanks. :) –  Mehrdad Jun 4 '12 at 17:45
1  
AES-128 has a much larger security margin than RSA 1024, so the facter will be larger. Note that the problem with message mallability is possibly even larger with symmetric ciphers such as AES. Message integrity is always a good thing. Try e.g. AES in GCM mode, then encrypt the random AES key to avoid this. –  Maarten Bodewes - owlstead Jun 5 '12 at 23:30

Just happened to read the question and decided to write short answer.

RSA is partially malleable (see http://en.wikipedia.org/wiki/Malleability_%28cryptography%29), it can be said that RSA provides efficient cryptography only if used very carefully. Therefore, RSA shall always be used via existing RSA padding schemes (see e.g. PKCS#1), because those have been carefully designed to be secure.

The scheme described here (zero padding) likely does not provide as good security with RSA as recommendable.

Anyway, the usage of intermediate symmetric key is actually not to remove reuse private key, its goal is instead: performance. Public key operations are generally very slow compared to symmetric cryptography.

share|improve this answer
    
I don't understand what you mean by "re-using the private key". Isn't the private key, well, private? How do you 're-use' a private key? –  Mehrdad Jun 4 '12 at 17:03
    
Never mind (was thinking DSS). The scheme suggested can be ok, as long as proper padding scheme is used. Nevertheless, the appropriate restrictions of padding scheme shall be studied carefully and followed. –  MPN Jun 4 '12 at 17:15

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.