1
$\begingroup$

How can RSA be used for digital signature with message recovery and encryption, providing transmission of a small message with confidentiality and authentication simultaneously, small cryptogram size, and little or no reliance on symmetric/hybrid encryption?

$\endgroup$
1
  • $\begingroup$ What is the source of this question? What did you search on our site and not clear for you? $\endgroup$
    – kelalaka
    Nov 2 '20 at 10:44
3
$\begingroup$

Re-using RSA key pairs for both encryption and signing is catastrophic, since it leaks the private key. So two pairs of keys will be needed.

RSAES-OAEP is a system that allows RSA to encrypt short (shorter than the modulus) messages. It's slow, and the length restriction is a big limit, but it does work.

RSASSA-PSS is a system for signing messages using RSA.

So encrypt using RSAES-OAEP and the recipient's encryption public key, then sign the ciphertext using RSASSA-PSS and the sender's private key.

A better solution is to use static-ephemeral ECDH to create a shared secret between the recipient's static key and the sender's ephemeral key, then encrypt the message using an AEAD like AES-GCM-SIV, and sign the whole ciphertext+IV+Tag using RSASSA-PSS.

$\endgroup$
3
  • 2
    $\begingroup$ Using an RSA key for both encryption and signing is a bad idea, but it isn't catastrophic. All the PKCS#1 modes of operation have domain separation so a ciphertext is never equal to a signature. Even without domain separation, it wouldn't leak the key. However, using a single private/public key pair for confidentiality and authenticity of the same message doesn't work (regardless of the scheme) as a public-key scheme since the decryptor needs a private key and the verifier needs a public key — hence the two-key-pair approach you describe. $\endgroup$ Nov 2 '20 at 12:53
  • $\begingroup$ Right, if they're using appropriate padding & modes of operation. But if they're re-using a key pair for signing and encryption (and thus giving away the private key to the decryptor) it's pretty damn catastrophic. $\endgroup$ Nov 2 '20 at 20:29
  • 1
    $\begingroup$ If they're using the private key to generate signatures, and to read RSA encrypted messages (that someone else encrypted with the public key), they have no need to send the private key to anyone. That is the normal meaning of "using the same key for encryption and signatures". $\endgroup$
    – poncho
    Nov 3 '20 at 17:28
2
$\begingroup$

Digital signature with message recovery does not provide confidentiality. It transmits a message with proof of origin and assurance of integrity, in a more compact way than transmitting the message and its signature separately. It happens that the message is unintelligible without the signer's public key, but since it is public, there's no assurance of confidentiality. In order to add confidentiality, we need encryption, and that requires another public/private key pair, this time owned by the receiver, for the additional encryption.


Say Alice wants to send a short message $M$ to Bob, signed and encrypted. I'll describe one option: encrypt-then-sign, with encrypt per RSAES-OAEP, and signature per textbook RSA signature (that is, with message recovery), which can be secure in this case.

Preliminaries:

  • Parties agree on an RSA modulus bit size $\ell$ (say 4096-bit) and RSAES-OAEP parameters (say SHA-512 hash, MGF1 with that hash, empty label). These choices define cryptogram size $k=\left\lceil\ell/8\right\rceil\,$bytes and maximum length of the message $k-2\,\text{hLen}-2\,$bytes (here 512-byte cryptogram holding up-to-382-byte message).
  • Alice draws a Public/Private RSA signature key pair $(n_{\text{As}},e_{\text{As}})$/$(n_{\text{As}},d_{\text{As}})$, with $3\cdot2^{\ell-2}<n_{\text{As}}<2^\ell$.
  • Bob draws a Public/Private RSA encryption key pair $(n_{\text{Be}},e_{\text{Be}})$/$(n_{\text{Be}},d_{\text{Be}})$, with $2^{\ell-1}<n_{\text{Be}}<3\cdot2^{\ell-2}$, thus $2^{\ell-1}<n_{\text{Be}}<n_{\text{As}}<2^\ell$, which we'll need for correctness.
  • Bob obtains Alice's $(n_{\text{As}},e_{\text{As}})$ in a way insuring he can trust it (that could be in a public-key certificate).
  • Alice obtains Bob's $(n_{\text{Be}},e_{\text{Be}})$ in a way insuring she can trust it (that could be in a public-key certificate).

Encryption and signature:

  1. Alice encrypts $M$ per RSAES-OAEP with Bob's public encryption key $(n_{\text{Be}},e_{\text{Be}})$, stopping after step 3b. That yields integer $c\gets m(M,\text{PS})^{e_{\text{Be}}}\bmod n_{\text{Be}}$, where $m$ has applied OAEP padding to $M$ with randomness $\text{PS}$.
  2. Alice textbook-RSA-signs $c$ as $s\gets c^{d_{\text{As}}}\bmod n_{\text{As}}$.
  3. Alice transforms $s$ to bytestring $S$ and outputs it, as in RSAES-OAEP encryption steps 3c and 4, and sends it to Bob in a manner such that he can presume the message is from Alice.

Signature verification and decryption

  1. Bob gets the alleged $S$ and that it is allegedly from Alice, thus fetches the corresponding trusted public key $(n_{\text{As}},e_{\text{As}})$
  2. Bob checks $S$ is $k$-byte as in RSAES-OAEP decryption step 1b
  3. Bob decodes $S$ into into $s$ as in RSAES-OAEP decryption step 2a
  4. Bob checks $s<n_{\text{As}}$
  5. Bob computes $c\gets s^{e_{\text{As}}}\bmod n_{\text{As}}$
  6. Bob performs RSAES-OAEP decryption with 1b and 2a modified as above, yielding $M$ or an error indication.

Bob has insurance that $M$ is from Alice and has been neither tampered with nor intercepted. Argument: after step 1 of encryption, $c$ is indistinguishable from random in range $[0,n_{\text{Be}})$ by anyone but Bob. That $c$ is thus in $[0,n_{\text{As}})$, so that textbok-RSA signature is correctly undone in decryption step 5; and is is sufficiently random in that interval for security of textbook-RSA signature followed by the stringent redundancy check of RSAES-OAEP operating on a different modulus.


As is, each participant needs a different key pair for signature and encryption. This is the academically correct way (one function, one key). But some practitioners want a single key pair for each participant.

Simplest:

  • Alice ensures that she's not encrypting with an $n_{\text B}$ matching her $n_{\text{A}}$, for that could break the confidentiality. This implies Alice can't encrypt toward herself (which is sometime useful, e.g. for a password, or the symmetric key of a large file).
  • Encryption step 1 is repeated until $c<n_{\text{A}}$.

One folklore method with the same limitation against encrypting to self, but avoiding iteration of encryption:

  • Signature step 2 is changed to $s\gets\left(\min\left(c,n_\text{B}-c\right)\right)^{d_{\text{A}}}\bmod n_{\text{A}}$
  • Conversely, in verification step 6, after step 2b of RSAES-OAEP decryption, it should be performed $m\gets\min(m,n_\text{B}-m)$. That will ensure decryption succeeds. But Bob should be careful not to leak information about $m$ in this extra step, in particular no measurable time dependency on the high-order bytes of $m$, otherwise a minor adaptation of Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 (in proceedings of Crypto 1998) can be used to decipher messages encrypted to Bob, or forge a signature by Bob.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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