encrypt rsa + sign it

Question

I cannot quite grasp my head around this

Basically, RSA encrypts by having public key (e, n) and private key (d, p, q) Where n = pq

Signatures are done by: Signed = Message^d mod n Hence, to verify you would do Signed^e mod n = Message

You would get the Message. How do you encrypt the message and have a signature at the same time? What am I missing..? I know you would hash the message, but then again. How would you hash the message?

I want to encrypt the message, but if I send over the Signature, the attacker can simply reverse the signature to find out what the message is.... no?

Answer 1

You have correctly identified why the stupid ‘do you even RSA, bro‽’ cryptosystem is trivially vulnerable to forgery and/or decryption by an adversary if you naively use the same key for naive encryption and naive signature—although it doesn't apply in a single instance: you use your private key to sign a ‘message’, and your friend's public key to encrypt it. But if someone can get you to sign a ‘message’ which is actually an encrypted message to you, they have just got you to decrypt the message for them.

This is why nobody in their right mind who takes the time to listen to cryptographers actually uses this stupid cryptosystem. Unfortunately, many textbook authors document this stupid cryptosystem and call it ‘RSA’ and leave it at that. This is why some people use the insufficiently derisive term ‘textbook RSA’.

What you should do instead is use independent keys for RSA-based signature and encryption, and use them in sensible RSA-based cryptosystems.

The post I linked to summarizes some alternative modern RSA-based cryptosystems. In another answer, I summarized in simple terms a modern RSA-based signature scheme called RSA-FDH.

These may even be safe to use with the same key, as long as you choose independent hash functions for the signature scheme and for the signature scheme—however, I'm not aware of a security reduction to the RSA problem for the use of the same key in any pair of sensible RSA-based encryption scheme and signature scheme. So I recommend using independent keys, just to be on the safe side.

Or don't use RSA at all, because securely composing signature and encryption into authenticated-encryption is hard (archived), and additionally leaks verifiability to third parties, which may or may not be what you want. Instead, consider using a NaCl crypto_box_curve25519xsalsa20poly1305.

Answer 2

No, sending a signed RSA message is not bound to allow an adversary to decipher it, for three reasons:

• When enciphering and signing a message with RSA, the same key (and modulus $N$) is normally not used for both operations, because one uses the recipient's key for encryption, and one's own key for signature.
• RSA encryption as practiced is not computing $C=M^e\bmod N$ (that's textbook-RSA encryption). For a start, that would allow anyone to check a guess of the message $M$, which is often unwanted (name of someone on a public class roll, PIN of a Smart Card..). Also, that system is not directly fit for large messages (see this).
• RSA signature as practiced is not computing $S=X^d\bmod N$ and sending $S$ along $X$ (that's textbook-RSA signature). For a start, anyone knows the signature for the three message $X=0$, $X=1$, and $X=N-1$ (that's $X$ itself), and the signature for $X=(42^e\bmod N)$ (that's $42$ ). Also, that system is not directly fit for large messages (signing a standard hash of the message with textbook RSA is not safe).

Something bad would indeed happen if one sent a signed secret message to oneself, used textbook-RSA for signature and encryption, and signed the encrypted message (in which case signature would be the message) or signed the original message (in which case enciphering the signature reveals the message, as noted in the question). But again, textbook RSA should not be used. Sound use of RSA uses encryption and signature methods as in PKCS#1, or others.

Further, sending the signature of a message and replacing the message (which normally comes along the signature) by an enciphered version is generally a very poor idea: it allows anyone to check a guess of the message. Good practices are signing the encrypted message; or enciphering the message and its signature.

Also: it is often recommended (but not always practiced) to have different keys for encryption and signature; otherwise, there could be a risk that revealing the signature of a message an adversary choose could unwillingly help decipher another secret message; or vice versa. There are heuristic arguments that this disaster scenario is only theoretical for sound RSA signature and encryption as used in practice, though.