10

I know encrypting something with my private key is used for signing. To prove that the message is indeed coming from me.

But what about if I sign something with my public key? That would mean that only I could decrypt it with my private key.

Suppose I did this and I sent over my ciphertext (encrypted with my public key) over to somebody. Will he be able to decrypt it?

Áron Pop Adorján
  • 495
  • 5
  • 9
  • 7
    In RSA terminology, you "**sign with the private key**" (so other people can verify it using your public key) and "**encrypt with the public key**" (so only the holder of the private key can decrypt it). If you encrypt with your own public key, only you can decrypt it. – Marc Oct 06 '20 at 12:00
  • 2
    Generalising @Marc's point: if /anybody/ encrypts a message with your public key, then only you can read it. That has obvious value if the message is to be broadcast over an open channel. – Mark Morgan Lloyd Oct 06 '20 at 20:44
  • Note that when signing, the "something" you encrypt is not (usually) the message, but a digest of it. – OrangeDog Oct 07 '20 at 10:01
  • I've heard that sometimes someone would send an anonymous message encrypted with a public key, and later _reveal_ the private key to prove it was them at a later date, but iI can't recall why, or the details. Obviously one would use a throwaway private key for this. – Mooing Duck Oct 07 '20 at 18:58
  • @MooingDuck it is called commitment schemes in Cryptography. See the famous one Pedersen Commitment. – kelalaka Oct 08 '20 at 00:02
  • @OrangeDog the digest is not enough in RSA to prevent the forgeries. RSA is multiplicative. Neither the encryption nor the signature should never be used without proper padding, see them iin my answer. – kelalaka Oct 08 '20 at 00:13

3 Answers3

14

There is a common misconception that signing a message is the same as encrypting the message with the private key. This notion is fundamentally incorrect, as pointed out by Thomas Pornin at If the public key can't be used for decrypting something encrypted by the private key, then how do digital signatures work?. As Pornin explains, encryption/decryption and signing/verification are in fact two different algorithms. A private key can be used to decrypt a message that was encrypted using the correspoding public key, or to sign a message; but a private key cannot be used to encrypt a message.

By the same logic, the notion of signing a message with the public key is also fundamentally incorrect. A public key can be used to encrypt a message, or to verify a signature made on a message using the corresponding private key; but a public key cannot be used to sign a message.

mti2935
  • 19,868
  • 2
  • 45
  • 64
  • 5
    As [Wikipedia](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Signing_messages) puts it "The keys may be swapped without loss of generality, that is a private key of a key pair may be used either to: 1) Decrypt a message only intended for the recipient, which may be encrypted by anyone having the public key (asymmetric encrypted transport). 2) Encrypt a message which may be decrypted by anyone, but which can only be encrypted by one person; this provides a digital signature." So in RSA cryptosystem terms it is NOT a misconception. What you are saying is only true in the context of PKCS1 spec – Andrew Savinykh Oct 07 '20 at 02:17
  • Except the PKCS#1 spec is, by definition, the RSA cryptosystem, originally published by RSA the corporation. The underlying primitive of modular exponentiation is reversible. If wikipedia conflates the primitive with the actual cryptosystem as standardized and used in practice, it just means somebody with the common misconception is the one who wrote those words. – Michael Snook Oct 07 '20 at 03:39
  • 1
    @MichaelSnook are you saying that those words are wrong? Because I don't think they are. In the context they are spoken in, what you refer to as "the underlying primitive", they are not wrong at all. And if they are not wrong, there is no misconception. – Andrew Savinykh Oct 07 '20 at 04:35
  • 1
    Thanks guys, ultimately what I wanted to know is if I make this mistake to sign/encrypt a message with my own public key and send it over, will the recipient be able to verify/decrypt it? Will he be able to somehow exploit my mistake to his/her advantage? Or is it just a "no big deal" mistake made on my part. – Áron Pop Adorján Oct 07 '20 at 06:25
  • 3
    To answer your comment - if you encrypt something with your public key, it is no problem. Your private key is still safe and the message cannot be decrypted by anyone else - so the content is also safe. You have not revealed anything by accident. – Falco Oct 07 '20 at 07:20
  • @ÁronPopAdorján What is the 'mistake' and what is 'normal' for you? If you normally encrypt something with your private key, anyone with the public key could decrypt it, right? And if you sign the message with your public key, anyone with your public key could do that... – Jason Goemaat Oct 07 '20 at 18:37
  • @JasonGoemaat Normal is when you use RSA like its intended to. meaning you encrypt your message with someone else's public key if you want to communicate with him/her. Then he/her can decrypt it easily. My "mistake" would be if I dont use his/her public key but my public key. – Áron Pop Adorján Oct 08 '20 at 06:09
  • @AndrewSavinykh See https://security.stackexchange.com/questions/159282/can-openssl-decrypt-the-encrypted-signature-in-an-amazon-alexa-request-to-a-web/159289?noredirect=1#comment490486_159289 – mti2935 Oct 09 '20 at 02:12
7

There are lots of mixing terminology here. In short RSA Signing is Not RSA Decryption by Cornell CS.

RSA is a trapdoor permutation, unfortunately, that can be both used for encryption and signature. This makes a common confusion.

First of all, although, RSA can be used for encryption, we don't. We prefer hybrid-encryption where a public key cryptosystem is used for key exchange and the key used in the symmetric algorithm. DHKE-AES AES and RSA-KEM AES are examples.

If one really wants to send a message with RSA encryption, they should forget to use the textbook RSA, which doesn't use a padding mechanism to be secure. PKCS#1 v1.5 and OAEP padding can be used for RSA encryption. The latter is preferable since the former is hard to implement correctly that caused many attacks.

If you want to sign a message, you should use the Probabilistic Signature Scheme (PSS). And when signing we don't' sign the message, we sign the hash of the message. This is necessary since the message can be very long and for the security proof.

What happens when I encrypt something with my RSA Public Key?

If you encrypt it with the public key without padding, the cube-root attack works if the public key is 3. Now forget encryption without padding. With correct padding, you have sent the message yourself, nothing more.

I know encrypting something with my private key is used for signing. To prove that the message is indeed coming from me.

But what about if I sign something with my public key? That would mean that only I could decrypt it with my private key.

The public keys are small and assumed to be known if you really use it for signature, this means there is a digital signature forgery. An attacker takes your public key (e,n) and produce a signature forgery.

The correct terminology is not decryption it is the verification of the signature. For signatures, we have sign and verify functions.

Suppose I did this and I sent over my ciphertext (encrypted with my public key) to somebody. Will he be able to decrypt it?

For signatures, the decryption is not the operation. The verification and forgery are the operations. If you use the public key then they will make forgeries.

Final note: Although RSA enables encryption and digital signatures, we don't use the same key for the different operations. You need two different sets for this in RSA.

For the curious reader here the Dan Boneh's article on the RSA attacks.

Community
  • 1
kelalaka
  • 5,409
  • 4
  • 24
  • 47
0

I’m going to assume that RSA has the security properties that we hope it does. In particular, I’ll assume that, if someone knows a message p, a public key pubKey, and the value of enc(p,pubKey), then it will be hard for them to calculate the corresponding private key, priKey. And, even if they have lots and lots of plain text / cipher text pairs, your private key still will be hard to compute. Hard to compute here means they’d either need a lot of time or a lot of hardware or both. (There is no proof of this assumption, but it seems to be true that know one knows of a way to break RSA when enough bits are used.)

Suppose you encrypt (rather than sign) a message m with your public key, and send someone the result enc(m, pubKey). And suppose that they know your public key too. From the assumption in the first paragraph, with m in the role of p, your private key will be safe. And even if they somehow know m, it will still be safe.

Signing usually means encrypting a hash of your message with your private key, i.e., you send (m, s) where s = enc(h(m), privKey). Then the recipient with your public key can check that dec(s, pubKey) = h(m), which means that s is enc(h(m), privKey) and so (almost certainly) must have been computed by someone who knows privKey.

(This chain of inference in the previous paragraph actually relies on a property of RSA and h that wasn’t stated in the first paragraph, namely that, if someone knows pubKey, but not privKey, it is hard for them to compute a pair (m,s) such that dec(s, pubKey)=h(m). But this is completely irrelevant because the question is about signing with the public key.)

If you mistakenly sign with your public key, then you send (m, enc(h(m), pubKey)). Now the recipient or eavesdropper will know h(m), enc(h(m), pubKey) and, presumably, pubKey. This is the same as the situation described in the first paragraph with h(m) playing the role of p. So again your private key is safe. (The recipient also knows m, but knowing m shouldn’t be of any help unless the message says something like “my private key is ... .“)

Theodore Norvell
  • 101
  • 2
  • As @kelelaka’s answer explains, the functions used for encryption/decryption of messages and for encrypting/decrypting the hash used in signing could be different; I’ve called them enc and dec in both cases, but they could be different function pairs. It doesn’t really matter as long as the assumption in the first paragraph remains reasonable. Also my description of signing might be a bit simplistic; it’s how I understand signing and it agrees with the Cornell lecture notes that @kelelaka mentions, but it might not reflect current practice. – Theodore Norvell Oct 07 '20 at 23:50