How to encrypt a short string to a short ciphertext using an asymmetric encryption?

Question

I am using RSA to encrypt some text, so my system has already generated private and public keys.

These keys I would like to use to encrypt/decrypt a short text (16 chars).

• The main condition is: the ciphertext should be as short as possible.
• Minimal length of the ciphertext is more event more important than total security. The attacker won't be able to choose plaintext.

Question: Is there a method, which would allow to create a short ciphertext using RSA private key?

EDIT: What I really want is to be sure that the text has not been changed and that it really comes from the application. The typical solution would be - to sign the text. But the usual RSA signature would be too long to be entered into mobile clients, where I would implement this system.

My idea was to encrypt a known text with a private key, so that it can be decrypted with a public key. This would provide enough safety to trust, that the encrypted text comes from base, since you need the private key for encryption.

Advantage: you only need to enter a short ciphertext string to validate the encryption, assuming that I can find an encryption method which can preserve the text length after encryption.

Answer 1

"Encrypt with the private key, so that it is decrypted with the public key": this is a flawed analogy, by which RSA signatures were first described, but even with RSA it does not work.

What you want is really a signature algorithm, however you want to call it. It is possible to define signature algorithms based on the RSA core operation, and it has been done, and it is called RSA. Anything which is RSA-based will involve some modular exponentiations working on, and yielding, big integers of the same size as the modulus. So a RSA-based signature with a RSA key worth that name (i.e. at least 1024 bits) will necessarily include a 1024-bit integer, so its size will not be lower than 128 bytes.

There is a possible twist in that RSA is a signature algorithm "with recovery": though the signature will have size at least 128 bytes, it is possible to embed in it some extra data (part of the message which is signed). There is a standard called ISO 9796-2 which does that; it has some shortcomings but it can be used. However, though this standard will make the total signature size overhead rather small, it won't please you, because you want to limit the size of that which is entered by a human user. The benefits of ISO 9796-2 are for long messages.

Algorithms producing short signatures are an active research area. Roughly speaking, if you target a security level of n bits (meaning: an attacker would have to invest in a computational effort of size 2ⁿ to be able to produce a fake signature -- but the effort may possibly enable him to produce millions of fake signatures for the same cost):

• With DSA and derivatives (e.g. ECDSA), the signature size is 4n bits.
• With BLS, the signature size is 2n bits (but the maths are hard to understand and there is no standard yet).
• There is an absolute theoretical minimum of n bits.
• We don't know good algorithms between n and 2n bits, although we know some of questionable security.

---

You might be able to fix that, though, by changing your models. Signature algorithms are meant for one thing: to allow someone to verify a signature without giving him the power to produce signatures. Depending on your exact context, it is possible that you do not really need this separation of roles. Maybe it is not a problem if whoever verifies a "signature" could potentially create signatures of his own. If that is the case, then you can use a MAC which can be considerably shorter (e.g. 32 bits might be sufficient in your case) and also much easier to implement (hint: use HMAC/SHA-256 and truncate to the desired size).