# Can the original data be extracted from an RSA private key signed message

I'm working on a system that the main objective is to verify the message was written by the right person, but it would also be desirable if the message can't be understood by anyone sniffing it.

It runs on Java/Android using RSA/ECB/PKCS1Padding (so it's not textbook RSA, but a real implementation) and the data is guaranteed not bigger than the RSA 2048 bits.

The public key on this case is not really public, it is sent to the server over standard SSL/HTTPs with certificate pinning and kept there.

The desired message is later sent over an insecure channel signed with the private key and the server can verifies the sender.

The question: can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?

edit:

Adding here to give a more complete explanation to Martin Boner.

I'm mostly a Android developer with general notion of cryptography, that's why I'm making sure to ask questions that might be dumb for some, but it's better be sure I'm not messing up important things.

For that reason, I'm not sure the direct answer to Martin, so I'll just show the code. It's Android/Kotlin code, but it's standard Java APIs:

private const val TRANSFORMATION = "RSA/ECB/PKCS1Padding"

internal fun rsaEncrypt(data: String, keyPair: KeyPair): String {
val cipher = Cipher.getInstance(TRANSFORMATION)
cipher.init(Cipher.ENCRYPT_MODE, keyPair.private)
val bytes = cipher.doFinal(data.toByteArray(Charsets.UTF_8))
return Base64.encodeToString(bytes, 0)
}


So this returned String is what's being sent. I manually tested that val bytes when converter back to string is unreadable and I have the inverse operation (below) that runs on my tests that I know the original data can be reconstructed with the public key.

internal fun rsaDecrypt(data: String, keyPair: KeyPair): String {
val cipher = Cipher.getInstance(TRANSFORMATION)
cipher.init(Cipher.DECRYPT_MODE, keyPair.public)
val bytes = Base64.decode(data, 0)
val decrypted = cipher.doFinal(bytes)
return String(decrypted, Charsets.UTF_8)
}


How the other end exactly is doing, I don't know because that was up for the Ruby developers, but it's perfectly reasonable to assume it's very similar to the above.

With this edit in mind, I'll add a secondary question:

1. (original question) Can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?
2. (Bonus) Is there any other security concern/issue here? For example, could someone after sniffing a few messages over the insecure channel, be able to regenerate or fake the private key and pretend be the proper user?
• Do you mean just the signature is sent over the insecure channel, or the message and the signature are sent over the channel? If the former, how does the recipient retrieve the message; if the latter, then the message is visible in plain-text. – Martin Bonner Jun 18 at 14:18
• Hi @MartinBonner I've edited my question with some detailed information. Thanks for looking up my question. – Budius Jun 18 at 19:52

Whenever you see the letters ECB, you should run away screaming. This is a telltale sign that something has gone terribly, horribly wrong. The code fragment you quoted implements what we sometimes call ‘textbook RSA’, which is a polite way to discreetly announce to the cocktail partygoers that you are desperately in need of a professional cryptographer.

This is not your fault: whoever designed the Java API that requires you to specify ECB in a string and which you will use to ‘encrypt with the private key and decrypt with the public key’ (which is a contradiction in terms that makes cryptographers twitch involuntarily, sometimes leading to a cocktail dribbling down your face and shirt) did not have the decency to ask for a professional opinion—which is what you are more or less doing now!—before they inflicted a monumentally wrong confusion of ideas into an API set in stone.

Let's back up a moment. What do you and your peer have in common, and what security do you want?

• If you share a secret already, and you want to exchange unforgeable and possibly secret messages, what you want is a symmetric-key authenticator like HMAC-SHA256, or a symmetric-key authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305. But you mentioned public keys, so maybe you and your peer don't share a secret yet—maybe all you have is your respective public keys, which are known to be correct but are not secret.

• If you share a public telephone book with public keys, and you want to exchange unforgeable and possibly secret messages, what you want is public-key key agreement like X25519, which is a way for you to use your private key and your peer's public key in the telephone book to compute a secret, which can also be computed by your peer using their private key and your public key in the telephone book so that you and your peer have a shared secret; or you want public-key authenticated encryption, like NaCl crypto_box_curve25519xsalsa20poly1305, which works by stringing together public-key key agreement (X25519) and symmetric-key authenticated encryption (crypto_secretbox_xsalsa20poly1305).

• If your peer has a public telephone book where you are named, and you want to send a message to your peer that your peer can show to a third party and convince the third party it came from you, then what you want is public-key signatures like Ed25519.

You could also use an RSA-based signature scheme like PKCS#1 v2.1 RSASSA-PSS, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer Ed25519, unless the cost of verification is your principal bottleneck.

• If you have a public telephone book where your peer is named, and you want to send a message to your peer anonymously so that only your peer can read it but not necessarily verify it came to you, then what you want is public-key anonymous encryption like NaCl crypto_box_curve25519xsalsa20poly1305 with an ephemeral public key.

You could also use an RSA-based encryption scheme like PKCS#1 v2.1 RSAES-OAEP, strung together with an authenticated cipher like AES-GCM, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer NaCl crypto_box_curve25519xsalsa20poly1305 with ephemeral keys, unless the cost of encrypting messages is your principal bottleneck.

But OK, let's suppose you are using some RSA signature scheme.

Any serious RSA-based signature scheme involves hashing the message. The simplest one, RSA-FDH, uses a hash function $$H$$ that hashes messages into all or nearly all of the set $$\{0, 1, 2, \dots, n - 1\}$$; a signature under public key $$n$$ on a message $$m$$ is an integer $$s$$ such that $$s^3 \equiv H(m) \pmod n$$. From the signature $$s$$, even if you don't have the message $$m$$, you can recover $$H(m)$$ simply by computing $$s^3 \bmod n$$, but if $$H$$ is a good hash function this doesn't help to recover $$m$$.

With RSASSA-PSS, the equation is more like $$s^3 \equiv 2^t r + H(r \mathbin\| H(m)) \equiv n$$, where $$H$$ is a smaller hash function like SHA-256. Again, you can recover $$H(r \mathbin\| H(m))$$ this way, but not $$m$$.

There are some ‘message-recovery’ variants of RSA signature schemes, in which some part of the message $$m$$ is embedded in $$s$$ alongside $$H(m)$$, but they are not widely used and you would probably know if you were using one.

All that said: Usually what you do is send a signed message, i.e. a message alongside its signature; otherwise, how does the recipient act on the message, or even find what message the signature corresponds to? And if you do that, there is nothing a priori that prevents anyone but the intended recipient from reading the message—after all, in a signature, only the sender's keys are involved.

You can combine public-key signature and public-key encryption, but this is usually a bad idea for two reasons:

1. A secure composition is hard to get right; OpenPGP and S/MIME got it wrong.
2. Public-key signature also usually guarantees that third parties can verify messages, which is usually not what you want for private conversations.

So, you are most likely better off using NaCl crypto_box_curve25519xsalsa20poly1305, which does it all in one: combines you private key, your peer's public key, a 192-bit message number, and a message, and returns a ciphertext that your peer and only your peer can check for forgery and decrypt.

• How thorough, clear, and useful! – Patriot Jun 19 at 2:40
• One shouldn't always run away screaming from "ECB". I've just written some secure code using ECB (at least I think it's secure). ... It implements CTR. I accept that this is the only usage that won't cause raised eyebrows from cryptographers. – Martin Bonner Jun 19 at 5:25