# Given a Message and Decryption Key, is it possible to find the Cipher in RSA?

This is a slight reversal from the norm but...

Suppose Alice wants to ensure that everyone knows that a message will be from her. Instead of giving out the encryption key, she broadcasts the decryption key, and encrypts her messages privately. She doesn't care that anybody can read her messages, only that someone can't imitate her.

So if I want to imitate Alice, and all I have is a decryption key and the message, is it possible to fake a message from Alice?

Edit: so to clarify, we'll assume a literate message is valid. We'll also add the constraint that the attacker wants to mimic a specific Message (M), not just any message, or previous messages will do.

• This seems to be trying to reinvent RSA signature, but in a way that I do not quite get. Suggestion: precisely state what receivers do to decide if something received is accepted as coming from Alice; then try to fool that, possibly assuming availability of cryptograms genuinely produced by Alice. For a start, do receivers get one or two numbers? Assuming one, on what grounds exactly will a receiver accept or refuse $0$? $1$? $42$? $N-1$, where $N$ is Alice's public modulus? $C+N$, where $C$ is genuinely from Alice? Assuming two, what about $(0,0)$? $(1,1)$? etc..
– fgrieu
Oct 3 '17 at 20:23
• I'll edit the question, but for the purposes of the question, lets assume a literate message is valid. I'll also add that+ the attacker has a specific message M which they want to use, and can't just use any message they like. Oct 3 '17 at 20:34

TL;DR: don't go here, it's a common mistake by starting cryptographers.

This is a reinvention of a signature scheme, as fgrieu mentions. If you want to integrate (part of) the message into the signature then you are talking about signature schemes giving (partial) message recovery.

The decryption key is the private key. It contains the modulus and private exponent, plus possibly all the CRT parameters and the public exponent. Now the public exponent doesn't need to be easy to guess, but it is if all the parameters or the exponent itself is given. Besides that, usually the public key exponent is set to a small prime number, which is easy to guess. Usually it is just 65537, the fourth prime of Fermat (F4). In other words, anybody who has the private key can generate the public key as well.

You can of course flip the public and private key and give out the public key instead. Even then there are problems with the scheme, take a look at my self answered question here - and note that I wrote this Q/A because many StackOverflow errors before.

And of course, just distributing the keys is not enough; the key of Alice must be trusted to be the key from Alice. Otherwise anybody can distribute keys instead of Alice. It may be tricky to find a scheme that protects public keys instead of private keys, if that is used.

• I figured that scheme seemed too good to be true to solve my problem. Thank you for steering me towards RSA-Signing though, I think that will solve what I need. Oct 3 '17 at 21:42
• Great. Note that signature generation usually includes hashing the data, signatures using message recovery are not common outside very restricted environments such as smart cards. Oct 3 '17 at 21:47