Can I save space for short messages by using encryption with private key instead of a signature?

Question

Let's say I have a message, a Private Key and a Public Key.

Normally if you want to see if the message is unaltered and is from the sender you would have the message part + signature part, which you can verify using the senders Public key.

This will lead to some extra data, which I want to work around

[ message (1 kb) ] [ verification part (?? bytes) ]

My solution to this problem is to encrypt the message using the private key, and to decrypt it using the public key.

This way it should be certain that:

• The message is unaltered
• The message is really from the sender

In short:

Sender: Encrypt Message using Private Key

Receiver: Decrypt Message using Public Key

Is this safe? So is this a way to:

• Check the senders identity (is it really from the sender (is it really signed by the Private Key))
• The message is unaltered

Answer 1

In general, no.

First, with an arbitrary public key scheme, the public and private keys might have quite different formats, and there might be no such thing like "encryption with a private key".

For example, with (generic) ElGamal, the public key is a member of the group, the private key is a natural number used as exponent.

With RSA, the public and private keys both consist of the same modulus, and additionally a public or private exponent. (The public exponent is usually something small like $3$ or $2^{16}+1$, while the private exponent is of the same order as the modulus.) The core of an encryption or decryption operation is a modular exponentiation with the (public or private) exponent, and yes, this part is easily swapped around, so you can use a private exponent for something which resembles encryption (and you then can use the decryption operation with the public key to undo it). And as is known, the core of the RSA signature operation is just this exponentiation with the private exponent, while verification uses the exponentiation with the public exponent.

Note that this is not a secure use of encryption, i.e. does not provide confidentiality. Does it provide integrity and authentication?

Real live RSA is not only the core exponentiation operation, but additionally a padding operation, to destroy homomorphic properties. There are several padding schemes, both randomized and deterministic, but these padding schemes are different for signature and encryption, for a reason.

Note also that usually public-key encryption is used in a hybrid scheme: encrypt a random symmetric key using the public key algorithm, then encrypt the actual message using the symmetric key. The resulting message thus will have this format:

[ encrypted key ][ encrypted message ]

The encrypted key has (for RSA) a size same as the modulus (which is the same as a signature), the message itself will have about the size of the plaintext message (maybe also including some padding, and hopefully a MAC). This means you will not save anything compared to the standard signature scheme.

What you actually need is a signature with message recovery, i.e. a signature from which (the unknown part of) the signed message can be extracted. But this only works (or saves space) for a message which is small enough to fit in the signature (and often a bit smaller due to overhead), so for your 1 KB message you would need an RSA key of similar size. I suppose these schemes are only useful for small messages, like in implicit certificates, where the message is the public key to be certified.

Answer 2

If you "decrypt with a public key" then it is not "encrypted" in the usual sense, since the public key is public: anybody can use the public key, and, therefore, the message cannot be considered confidential in any way.

For the message confidentiality to be preserved, the decryption operation must be available only to the receiver, and, as such, MUST use some value that only the receiver knows -- as it were, a private key (or, at least, a secret shared between sender and receiver). Similarly, for the message integrity to be verifiable, power of sending a message which can be validated MUST be limited to the sender. There again, a secret value must exist, but on the sender side this time (or, again, as a secret shared between sender and receiver).

Shared secrets are expensive to distribute. Asymmetric cryptography is about solving that. The classical solution is to use an asymmetric key exchange (with the receiver's public key) and to add a signature (with the sender's private key). The key produced by the key exchange algorithm is then a shared secret sufficient to do symmetric encryption. Deployed, well-vetted algorithms would be:

• Elliptic Curve Diffie-Hellman for the key exchange;
• ECDSA for the signature;
• AES in CTR mode for the actual data encryption;

for a total size overhead of 96 bytes. I am using the usual "128-bit" security level which is safe against tomorrow's three-letter agencies; that's then 256 bits for the ECDH, 512 bits for ECDSA. AES-CTR will induce no extra overhead, assuming that each message has its own ECDH key exchange: this allows us to use a fixed, constant IV, and the ECDSA signature nullifies the need for a MAC.

Important warning: it is not totally obvious to slap all these algorithms together, depending on the security properties to be achieved. If you need the signature to be a proof verifiable by a third party, e.g. a judge, then the signature will need to be computed over the cleartext data, but this may leak information on that data. Also, to avoid replay attacks, you might want to include a sequence number in the signature computation. Please exercise caution; I am here describing possibilities, but specification would need more thinking.

Can we do better ? Yes we can; there are several ways. The generic problem of efficiently combining public-key encryption (or key exchange) with a signature is called signcryption. This is still rather new, so no standard way has emerged yet.

In practice, you can reduce the signature overhead by using RSA with ISO 9796-2: this is a signature algorithm with recovery which can be used to piggyback some data transport on the signature itself. If the underlying hash function has output size n bits, then the signature overhead is n+16 bits. There are constraints (the overhead is higher is the message is quite shorter than the RSA key) and there are known weaknesses which reduce the actual security level (with a 256-bit hash function, you would not get 128-bit security, rather something like 100-bit, which is already quite good). See this answer for details and pointers.

With ECDH and RSA/ISO-9796-2, we are down to 66 bytes of overhead. We can get lower by acknowledging that 128-bit security is, realistically, quite some overkill. Let's target 100-bit, which is still way beyond current technology (see that answer for more discussion on this). We can also use BLS signatures with an appropriately chosen elliptic curve. This can bring overhead down to 200 bits for ECDH, and another 200 bits for the signature. 400 bits is 50 bytes. Note that BLS verification is substantially more expensive than ECDSA signature verification (nothing serious for a PC, but this can be troublesome for embedded systems, in particular smartcards), and involves a non-trivial amount of non-trivial mathematics. And there is no industrial-level standard on BLS. Yet.

Getting lower than that looks challenging. There has been some work on multivariate quadratic equation systems, with a few proposal for signature schemes with short signatures (see HFE, Quartz and Sflash). Most were broken, using Shamir's relinearization. It is still believed that it is possible to get signatures shorter than 2n bits with a n-bit security level, but we have no candidate algorithm in which security we feel confident enough. Yet.