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?

  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Jun 4 '12 at 17:20
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Jun 4 '12 at 17:20
  • $\begingroup$ @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. $\endgroup$ – Mehrdad Jun 4 '12 at 17:28
  • $\begingroup$ 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? $\endgroup$ – fgrieu Jun 4 '12 at 20:41
  • $\begingroup$ @fgrieu: Just because it was a handy scheme... I don't really mind that part if it's different though. $\endgroup$ – Mehrdad Jun 4 '12 at 21:01

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.

  • $\begingroup$ +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. $\endgroup$ – Mehrdad Jun 4 '12 at 17:32
  • $\begingroup$ @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. $\endgroup$ – poncho Jun 4 '12 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes 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.

  • $\begingroup$ 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? $\endgroup$ – Mehrdad Jun 4 '12 at 17:03
  • $\begingroup$ 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. $\endgroup$ – MPN Jun 4 '12 at 17:15
  • $\begingroup$ I personally consider the importance of the issue of processing efficiency to have been highly exagerated and IMHO in reality the issue is a non-issue at least for the common people whose (in particular important) communications with one another are invariably of messages of fairly small volumes. Thus I have written an RSA software, including encryption with signature, in Python which, being commonly interpreted, is certainly slow in comparison with e.g. C. See mok-kong-shen.de Could it ever be a concern for the said kind of users whether the encryption processing time is 10 sec or 0.1 sec?? $\endgroup$ – Mok-Kong Shen May 2 '17 at 9:53

If you came here like me because static code analysis flagged you with a security flaw for using ECB instead of CBC in code that looks like this:

Cipher c = Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding","SunJCE");

You might have to explain to someone that it's just a Java syntax thing and that ECB or CBC don't really do anything because RSA isn't breaking the message into blocks.

  • $\begingroup$ You point to and talk about some Java snippet. Since the Q doesn't mention Java anywhere, I'm not sure how this answers this 5 year old question if the described scheme is secure, what attacks would be possible on ECB mode, or how to make things safer. You probably should edit your answer to clarify that, answering the question too… if only, to avoid downvotes by other users. In case you missed it: the Q was asked 2012 and already hugs an accepted answer (with bounty reward) which indicates what kind of answer the asker expected to receive. TL;DR: Java is unrelated to this Q&A. $\endgroup$ – e-sushi Apr 30 '17 at 6:37

protected by e-sushi Apr 30 '17 at 6:42

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.