0
$\begingroup$

Imagine one's computer clearsigned a message by encrypting the message with one's private key and storing the two (the plaintext and the ciphertext) together in a folder (and publishing the public key). Would the encrypted message that is serving as the digital signature (whether or not that would be correct term for it) be as short as the result of a hash being generated and encrypted (which is the normal way), in the case where the message is very short and therefore, since there is no need to generate a hash at any stage, be quicker?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Fixing the question

"clearsigned" is PGP or S/MIME vocabulary. The correct wording in a cryptographic context is signed with appendix, meaning the message remains unchanged and the signature is separate.

The question's "encrypting the message with one's private key" is a serious error in terminology. Encryption is never with a private key. Decryption often is. When we do asymmetric encryption, that's always with a public key. When we do symmetric encryption, that's with a secret key. Because the intend of encryption is making data unintelligible to adversaries, and adversaries are assumed to know the public key, which would allow to undo the "encryption".

It is meant signing the message with one's private key per textbook RSA. We know it's RSA since encrypting the message with one's private key is just not possible in other asymmetric encryption schemes supported by PGP (and to my knowledge S/MIME).

Also, it's not stated the public key must be published thru a channel of trusted integrity. If it's not, an adversary can generate a public/private key pair and do just as the legitimate sender does, with any message of their choice. The message and signature need not go thru a channel of trusted integrity: the whole point of digital signature is avoiding that past establishment of a trusted public key.

And, the normal/right way of signing with RSA is not just hashing and signing. When using a common hash such as SHA-256, for this to be secure by the common criteria of Existential UnForgeability under Chosen Message Attack, we need at least to pad the hash (as in RSASSA-PKCS1-v1_5, or RSA-FDH), or (slightly) better use RSASSA-PSS.

Finally the title asks about less work, and the question asks about if the signature would be as short, which are different things.

So I'll rewrite the question as:

Assume we published the public key $(n,e)$ thru a channel with integrity. Imagine we use our computer to sign with appendix a short message $m$ by applying the textbook RSA private key function directly, as $s\gets m^d\bmod n$, storing the message $m$ and the signature $s$ together in a folder. Would the digital signature be as short as signing the message the normal way, that is with a signature padding involving a hash? And would it require less work?

Answering the fixed question

TL;DR: Yes, yes, but don't do that.

What's proposed would be just as short: in both cases the signatures adds the same $\left\lceil\log_2(n)\right\rceil$ bits. It would require less work, because we do not have to hash and pad.

However the work saving is negligible, since padding is typically much less costly than the RSA private key operation. Even the saving on signature verification is typically marginal.

Another bad news is that there's a severe size limitation to the message: $m$ must be at most $\left\lfloor\log_2(n)\right\rfloor$ bit. We are talking less than 256 bytes with RSA-2048.

The apparently good news is that we can save significantly on size by modifying the method slightly: we can remove the message itself from our folder/transmission, for it can be recovered¹ as a byproduct of signature verification, using that $m=s^e\bmod n$. We would be in good company doing this: the original RSA article did just that.

But the terminally bad news is that the signature system becomes susceptible to many plausible attacks. That's entirely independently of if we remove $m$ or not: the adversary is assumed to be able to change $m$ at will (else why would we sign?). Textbook RSA signature (without padding) still offers some assurance if the signers generates the messages that they sign all by themselves, and there is a lot of redundancy in the messages, and it's carefully checked over the full width of $m$ by the verifiers. But if we remove some of that, all hell can break loose.


¹ That recovery is exact if $m$ is of known size. If not, we can get back $m$ including it's size, by loosing some of the maximum message size. One possibility eating just 1 bit is to left-pad the message with a single 1 bit on signature, and remove that bit on message recovery.

$\endgroup$
1
  • 1
    $\begingroup$ In addition to PGP, S/MIME also has clear-signing. Both of these were designed for email decades ago when people naively thought email would be used to communicate useful information to recipients rather than to spam, phish, infect, spy on, harass and otherwise attack and harm people as is now the case. $\endgroup$ May 31, 2021 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.