58
$\begingroup$

When using the RSA cryptosystem, does it still work if you instead encrypt with the private key and decrypt with the public key? What about in the case of using RSA for sender authentication?

$\endgroup$
9
  • 1
    $\begingroup$ It works, but it is not secure. Don't do it. $\endgroup$ Mar 18, 2012 at 17:31
  • $\begingroup$ @PaŭloEbermann thank you, but what I meant is that does the private key encryption in RSA is exclusively applied in sender authentication? because RSA is a public key cryptography and the encryption is done with a public key rather than a private key. $\endgroup$ Mar 18, 2012 at 17:36
  • 10
    $\begingroup$ Encryption with the private key is part of RSA signatures. But just like we don't use plain RSA for encryption, we don't use plain RSA for signing. Actual signature schemes use padding and hashing. $\endgroup$ Mar 18, 2012 at 17:51
  • 3
    $\begingroup$ @HumamShbib: Your question is too vague for an answer. However, computing ${\tilde m}^d\bmod n$ (where $\tilde m$ is a padded representative of message $m$, $d$ is the private exponent, and $n$ is the public modulus) is used a part of RSA signature of message $m$, including sometime for the purpose of sender authentication. See PKCS#1 or ISO/IEC 9796-2 for proper signature schemes. $\endgroup$
    – fgrieu
    Mar 18, 2012 at 18:37
  • 1
    $\begingroup$ Since no one mentioned it so far: By definition of the encryption scheme, the modulus $n$ is part of the public key. If you just have $d$ and no $n$, you can't "encrypt". About interchangeable $e$ and $d$: Yes it works, but usually $e$ is chosen to be small. This is okay. An easy to guess $d$ is not. $\endgroup$
    – tylo
    Jun 11, 2014 at 13:53

3 Answers 3

39
$\begingroup$

Mathematically it work just fine. "Encrypt" with the private key, "decrypt" with the public key. Typically, however, we say sign with the private key and verify with the public key.

As stated in the comments, it isn't just a straight forward signing of the message $m$. Typically a hash function and padding is involved. Also, often one has a separate key pair for signing.

As you can see, there are a number of caveats, but in general you are correct, it is used for sender authentication.

$\endgroup$
2
  • 3
    $\begingroup$ I'm probably splitting hairs, but "encrypt with the private key" is not a valid cryptographic operation. That usually get translated into a Signature Scheme with Recovery (or indicates that's what the OP wants). $\endgroup$
    – user10496
    Feb 28, 2015 at 19:26
  • $\begingroup$ Encryption is done with public key only, since the key is public, and only the holder of private key can decrypt it. If message is encrypted with private key, then everyone can decrypt it, since the public key is public. The point of encryption is that only the authorized recipient is to get the message, otherwise there's no point encrypting the message; save the time & computing resources, and just display the message to the public! $\endgroup$
    – Zimba
    Jun 21, 2021 at 15:26
27
$\begingroup$

Asymmetric encryption and signing are entirely distinct concepts. The security and construction requirements are completely different. (Encryption for instance, needs to be an injection, whereas signature verification needs to be a surjection towards the verified message space. As a further hint of how they are intrinsically different, note that it lasted quite a bit of time before ID-based encryption could be designed, whereas ID-based signatures were there from the beginning.)

To put it simply: there is no meaning for (understand definition for) the wording "encrypt with the private key". How would you do it?

By way of example, take the ElGamal encryption scheme: $s$ is your private key, $g^s$ your public key. To encrypt $m$, you draw a random $r$ and compute the ciphertext $(g^r,m*g^{r*s})$. Now, let's be practical: you've got this nice library implementing ElGamal. The API for encryption says the function takes two arguments: a message and a public key, that is a group element $g^s$ for some secret number $s$ and some group generator $g$. Now how do you "encrypt with the private key" $s$? You feed the function with $m$ and $s$? It does not comply with the API and it might even crash. Then let's be theoretical: how do you sign with the ElGamal encryption?

Eventually, this misconception probably arise from the specifics of the underlying mathematical structure of RSA (which has both signature and encryption variants, and where a private key of the same form can be used for decryption or signature, and the corresponding public key used for encryption of signature verification). But even there, a standard-compliant implementation will not allow you to "decrypt with the public key". Due to padding indeed, there is no way decryption will succeed. For the particular case of RSA, see also there.

So if you need to sign, use the signing function of a signature scheme with a private key. And if you need to encrypt, use the encryption function of an encryption scheme with a public key. After all, that's what they were designed for.

$\endgroup$
2
  • $\begingroup$ Why does a signature need to be a surjection? Does that mean that every byte-string of a given length should be a valid signature of something? $\endgroup$ Oct 13, 2012 at 10:45
  • $\begingroup$ I meant, the public function in an encryption scheme must basically be an injection (so that one can always decrypt) whereas the public function in a signature scheme must basically be a surjection (so that one can always sign). $\endgroup$
    – bob
    Oct 13, 2012 at 11:16
23
$\begingroup$

The two keys $(e,m)$ and $(d,m)$ in the RSA key pair are fully equivalent, in that $e$ and $d$ can be arbitrarily chosen integers (in the interval $0..m-1$) as long as they fulfill the well-known congruence $ed \equiv 1 \mod \phi(m)$. You can swap them and nothing will change.

A key becomes public the moment you (as the key generator) decide to disclose it, possibly to attackers too. By consequence, the one you decide not to disclose becomes the private key.

When you use the key pair for confidentiality purposes, you typically want everybody to be able to send confidential messages to a receiver, so that only such receiver can interpret them. In such case, everybody shares a key (which will be the public one by the definition above, used for encryption), whereas the receiver has got the one which is not shared with anybody else (which must be the private key, used for decryption).

The idea of using the public key for decryption undermines the very purpose of having a scheme in place for confidentiality as defined above. Why should you do encryption at all if anybody (including the attacker) can undo it?

If you are thinking "Maybe I could securely distribute the public key only to the intended receiver", then you are not disclosing any key at all, and the definition of public and private do not hold anymore: you use RSA as a sort of secret key cipher like AES.

On the other hand, when you use the key pair for authentication purposes, you typically want everybody (including any forger) to be able to establish with certainty that a message really comes from a certain originator, and not from anybody else. In such case, everybody shares a key (which is again the public one, used for verification), whereas the originator has got the one which is not disclosed to anybody else (which must be the private key, used for signing).

In the same way as before, using the public key for signing is contradictory.

Finally, it should be noted that the public key (in either case) takes a special form (3, 65537, etc). That is purely for efficiency purposes (since the key must be public anyway, why don't we pick one that is computationally easy to deal with?), and it is not related to security.

$\endgroup$

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