Tell me more ×
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.
up vote 9 down vote favorite
2

I'm looking for best practices when it comes to encrypting small (< 128 bytes) amounts of data with the RSA private key. Signing it would make the resulting payload too large.

share|improve this question
2  
If you tell us a lot more about your application, you're likely to get a more useful answer. What's the outer problem? Who or what is signing what for what purpose? Who has to verify it? What is the issue with a large payload? – David Schwartz Sep 14 '11 at 6:10
1  
Is RSA the only public key algorithm available to you? – jug Sep 14 '11 at 18:36
1  
@DavidSchwartz I am signing, or otherwise need to insure the integrity of, very small amounts of data. These are delivered to a (potentially offline) application, which needs to verify that the message was not tampered with in transit. Though I control both ends, I do not want to use symmetric encryption, as that would easily allow someone to generate fake messages. – joe Sep 19 '11 at 15:42
@jug No, I can use any any. I am aware that ECC may allow smaller keys. – joe Sep 19 '11 at 15:44

4 Answers

up vote 9 down vote

In any public key system, you don't encrypt with private key. You encrypt with public key, or sign with private key.

If your goal is signing (resp. encrypting) one small value with the RSA private (resp. public) key, keeping the signature small: forget about it, that's not directly possible. Under RSA, a cryptogram is always of size at least comparable to the key. You need another public key scheme. Edit: standard RSA signatures schemes have signatures about as wide as the public modulus; a state of the art RSA variant can about half that.

If you want to encrypt several small values with RSA, do that with a random secret key drawn for that purpose, and a symmetric cipher; and send the secret key, RSA-encrypted with the public key, using a proper padding scheme like OAEP.

If you want to sign several small values with RSA, concatenate them (each with length indication unless the lengths are agreed in advance), then sign the aggregate using a proper RSA signature scheme like PKCS#1 PSS. If you want to send the small values along and care about the total size, use a signature scheme with message recovery, such as ISO/IEC 9796-2 (but beware that the first of the three schemes in this standard, still the most used, has some flaws if the opponent can obtain the signature of enough chosen messages).

share|improve this answer
Thanks for the reply. I'm aware that the encrypted value will never be smaller than the key. And unfortunately, each value must be individually signed/authenticated, and I can't use symmetric encryption. I was looking at OAEP, but am wondering if the raw bytes of the hash data plays a role in the security of the resulting value (WRT the private key), e.g. can I replace the hash value with actual data? – joe Sep 12 '11 at 15:22
1  
@joe: There is still confusion at if you want to sign, or encrypt. OAEP is for encryption (ensuring confidentiality), not signing (ensuring authenticity). Please state your goal. – fgrieu Sep 12 '11 at 19:29
I am not worried about confidentiality of the data, I only need to verify the authenticity. Signing is the most logical, but I was hoping to encrypt the data (instead of the hash) with my private key, so that the public key can be used to verify that the data was not tampered with. – joe Sep 12 '11 at 20:20
2  
@joe: Encrypting with private key so that the public key can be used to verify that the data was not tampered with: congratulation you just re-discovered RSA signature with message recovery. It does allow you to convey about n-m-16 bits of authenticated data within an n-bit cryptogram, for an n-bit modulus, m-bit hash, and ISO/IEC 9796-2 formatting. E.g. 1776 bits for n=2048, m = 256. – fgrieu Sep 13 '11 at 6:36
1  
@joe: If you do not want to purchase ISO/IEC 9796-2 (free partial preview), you may look at IFSSR (Integer Factorization Signature Scheme with Recovery) in section 10.6 of IEEE 1363a. Subscribers to the P1363 mailing list are entrusted with the password necessary to download the drafts. – fgrieu Sep 14 '11 at 11:19
show 1 more comment
up vote 5 down vote

In general you shouldn't mess with standard algorithms/protocols, because of the innumerable ways you can break semantic security, like adaptive chosen ciphertext attacks.

Use optimal asymmetric encryption padding if you must roll something yourself.

share|improve this answer
up vote 2 down vote

If your goal is to sign (authenticate) the data, and if RSA signatures are too long, there are some exotic schemes out there that have shorter signatures. For instance, BLS signatures are about 170 bits long and give about 80 bits of security. However, these schemes are considerably slower and more complex to implement.

(An earlier version of this answer suggested that elliptic curve signatures could achieve 64-bit security with a 128-bit signature. That was incorrect. Thanks to @Thomas Pornin for pointing out my error.)

share|improve this answer
1  
How do you get 64-bit security with a 128-bit signature ? I mean, you can, with the BLS signature scheme, but that involves a pairing. With ECDSA, you get 64-bit security with a 128-bit curve, yielding a 256-bit signature (which is already small). – Thomas Pornin Sep 12 '11 at 10:39
@Thomas, you are quite right. What I wrote earlier was nonsense. Thanks for spotting and pointing out my mistake. I have updated my answer -- hopefully now it is accurate (fingers crossed). – D.W. Sep 13 '11 at 7:14
up vote 0 down vote

DSA produces much shorter signatures than RSA, and can generate them much faster. But the caveat is that verification is slower compared to RSA. If this is a problem depends on how you plan to use them, and how critical performance is. You could take a look at ECDSA, it may be the best of both worlds ;)

share|improve this answer

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.