Encrypt with private key decrypt with public key

Question

I want to sign and transmit a short message, which contains a few simple hashes. My objective is not to prevent an attacker from inserting a fake message, but to ensure that the attacker cannot define or craft the specific contents of such a fake message.

The conventional method involves creating a signature by first hashing the message to be signed, then encrypting the hash with the private key, and finally transmitting both the original message and the signature. A receiver can then verify the authenticity of the message by decrypting the hash with the public key, and comparing it to a hash computed from the received message. This process is detailed, for instance, in How does RSA signature verification work?

However, for the sake of bandwidth economy, I'm contemplating the feasibility of omitting the hashing step: could I directly sign the message with the private key and only transmit the resulting signature? The receiver (or any third party) will then be able to reconstruct the original message from the signature by decrypting it with the public key. My intuition is that a message created by an attacker will generally not decrypt or decrypt to random bytes.

Answer 1

I want to sign and transmit a short message, which contains a few simple hashes. My objective is not to prevent an attacker from inserting a fake message, but to ensure that the attacker cannot define or craft the specific contents of such a fake message.

I will assume that you don't care about the privacy of the message; instead only that adversaries can't inject messages of their own.

First obvious thing to ask is "do you care if the valid receiver could generate correct messages on its own?". Sometimes do you care (e.g. if there are multiple valid receivers which don't mutually trust each other), sometimes you don't (e.g. if there is a single receiver who is the only one that cares about whether a message is valid).

If you don't care, then the obvious solution is to have both the sender and the receiver share a symmetric key and then either send the message along with a Message Authentication Code, or (if you actually do care about privacy) encrypt the message with an authenticated encryption cipher. If either of these work for you, I can give you more details.

On the other hand, if you do care, then yes, you really do need a signature algorithm. There, you have two options:

• Use a signature algorithm "with message recovery"; RSA can be used in this mode.

• Use a shorter signature algorithm that doesn't have message recovery; BLS is currently the shortest

Here's the point, with RSA, you can put some (or possibly all) of the message into the signature; however RSA itself has a minimal size; if your goal is "128 bit security", that means an RSA key size of 3k bits, that is, the RSA signature itself will be 384 bytes.

In contrast, BLS signatures (using, say, the BLS12-381 elliptic curve, which also has circa 128 bit security) has 48 byte signatures. You will need to add the entire message (BLS doesn't allow message recovery at all), however unless your message is at least 300 bytes long, the BLS signature + message pair is always strictly shorter.

Answer 2

You could use a newer efficient hashing algorithm if you're worried about bandwidth (Poseidon etc is even ZK friendly), but SHA256 is pretty fast on baremetal. The reason for the hash is that

1. RSA signatures of an arbitrarily long message will take much longer, since number of exponentiations is proportional to log of the length of the message.
2. Hashes make your message uniformly random. If your preimages are not uniformly distributed at random, then there may be some structure in the exponentiations (i.e. if all of your messages are say even, then your security would be halved, vs with a hash you wouldn't be able to tell).
3. If i.e. there are only say 500 possible pre-images, an attacker could also directly try encrypting all of them to the RSA public key and checking if the cyphertext matches (vs if you put some nonce into a hash, then such an attack wouldn't work).