Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question
3  
Does the recipient know the public key of the sender? If so, you might be able to use symmetric encryption on a shared key computed via. Diffie-Hellman. –  CodesInChaos Jul 11 '13 at 7:34
    
Sorry, it's not clear what you mean by "cypher" and "shortage". –  Deer Hunter Jul 11 '13 at 7:35
    
16 characters is really short: what type of attack do you want to protect it against ? –  Stephane Jul 11 '13 at 7:39
1  
Signing an encryption are totally different operations. One is about confidentiality, one about authenticity and integrity. –  CodesInChaos Jul 11 '13 at 8:14
1  
You could look into BLS signatures at 2n bytes, or use standard DSA/Schnorr signatures at 4n bytes. There is also a straight forward variation of Schnorr signatures at 3n bytes where one component is hashed to n bytes. By increasing computational cost(verification and/or signing) you can decrease the signature size a bit further. –  CodesInChaos Jul 11 '13 at 11:17
show 2 more comments

1 Answer

up vote 3 down vote accepted

"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 2n 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).

share|improve this answer
    
The "shortcomings" seems to have a bad link –  makerofthings7 Jul 11 '13 at 16:00
    
The link works for me. Are you sure you know how to click ? –  Thomas Pornin Jul 11 '13 at 16:04
    
My aptitude for clicking has improved after lunch. Must have been my blood sugar, or a load balancer issue. –  makerofthings7 Jul 11 '13 at 17:46
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.