2
$\begingroup$

I need to encrypt a high number of short messages (30-200 bytes). The problem with usual algorithms, such as RSA, is that the size of the encrypted message tends to increase a lot, compared to symmetric encryption algorithms.

Ideally, this cryptosystem shoud accomplish:

  • Asymmetric
  • Size of the encrypted message must be at most 25% longer than the original
  • Should be fast encryption and decryption
  • It's not a problem if, after some work, some messages are decrypted
  • But private key must not be found so easily
  • It would ve good if it's a known algorithm with solid implementations in most common languages

The only solution I found until now is using RSA with short keys (64 bits), but I wonder what a better approach could be.

Improve this question
$\endgroup$
7
  • $\begingroup$ If you use RSA with short keys, you might as well use no encryption at all. Those keys are factored within extremely short time-spans. Oh and is it OK if messages would be padded to 200-bits (all), e.g. all ciphertexts would be around 256-bit? Because otherwise, you can't securely encrypt 30-bits asymmetrically with 25% message encryption. $\endgroup$
    – SEJPM
    Commented Aug 3, 2016 at 13:00
  • $\begingroup$ Are you certain that you can't use symmetric encryption in your use case? I'm pretty sure that no known public key encryption algorithm adds only 7-8 bytes (25%) to a 30 byte plaintext; if that's a hard requirement, well, you're out of luck. I can think of one that adds only 16 bytes (constant overhead, independent of plaintext length), but that's cutting pretty severely into the security (and so is nonstandard; we don't standardize on crypto with weak security...) $\endgroup$
    – poncho
    Commented Aug 3, 2016 at 14:54
  • $\begingroup$ Would it be allright if the client and server negotiate a key (e.g. via RSA), but after that the connection becomes stateless? (Meaning that the server does not need to keep track of keys) $\endgroup$
    – Daan Bakker
    Commented Aug 3, 2016 at 15:02
  • $\begingroup$ Do you mean RSA with short keys (64 bytes)? There are some who still use RSA with 64-byte i.e. 512-bit keys. However, it is totally too weak: 512-bit keys can be broken in approximately 1-2 hours. RSA with 64-bit keys can be broken within microseconds, and therefore provides no security at all. Minimum recommended key length (modulus length) for RSA would be 2048 bits. $\endgroup$
    – user4982
    Commented Aug 3, 2016 at 15:39
  • $\begingroup$ In "(30-200b)", is "b" bits or bytes? ​ ​ $\endgroup$
    – user991
    Commented Aug 3, 2016 at 15:39

1 Answer 1

Reset to default
6
$\begingroup$

Using RSA with short keys is a bad idea since it would make the encryption less secure.

The standard way to use asymmetric encryption is to only use the asymmetric encryption algorithm to encrypt a symmetric encryption key and then use that key to do the actual communication. In this case you only get the message overhead of the asymmetric encryption scheme once which can then be amortized over many small messages.

Is there any reason you can not use this approach in your application?

Improve this answer
$\endgroup$

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