# How is asymmetric cryptography safe if one of the keys is public?

Let's suppose $$A$$ is sending a message $$m$$ to $$B$$ using asymmetric cryptography.

To guarantee the authenticity of a message, $$A$$ encrypts $$m$$ with $$A$$'s private key: $$E(m, k_A) = m_A$$.

Then, $$A$$ sends $$m_A$$ to $$B$$.

$$B$$ can check that $$m_A$$ was sent by $$A$$ using $$A$$'s public key $$p_A$$, by doing $$D(m, p_A) = m$$.

If the public key $$p_A$$ is, by definition, public, if an attacker intercepts the communication and get $$m_A$$, he could easily find $$m$$.

How is asymmetric cryptography safe under these conditions?

• If $A$ is sending a message to $B$, the message would be encrypted with $B$'s public key for security and would be signed with $A$'s private key for authenticity. As you've shown, just doing one operation doesn't get you both. – Aman Grewal Mar 27 at 21:20

How is asymmetric cryptography safe under these conditions?

Well, you sort of outlined (but see kelalaka's corrections) how you would use asymmetric crypto to do authentication; that is, to make sure that the message was actually sent from $$A$$.

You ask "how does that provide privacy?". The answer, of course, is "if that's all you do, it doesn't".

If we want to do privacy, that is, generate an encrypted message that only $$B$$ can read is that $$A$$ encrypts $$m$$ with $$B$$'s public key, that is, $$E(m, p_B) = m_A$$. We then send $$m_A$$ to $$B$$. $$B$$ can then take his private key and compute $$D(m_A, k_B) = m$$, recovering the original message. No one else can read the message, because only $$B$$ knows $$k_B$$, and that's needed to decrypt the message.

Two notes:

• If we need to provide both authentication (only $$A$$ could have generated the message) and privacy (only $$B$$ could read the message), we do both; $$A$$ might generate the ciphertext $$E(m, p_B) = m_A$$, and then sign it with his private key $$Sign( m_A, k_A ) = s_A$$ and then send both $$m_A$$ and $$s_A$$. $$B$$ can then verify the signature (with $$A$$'s public key), and then decrypt the message (with $$B$$'s private key).

• In practice, if we need to encrypt a long message, what we generally do is pick a random symmetric key (which is short), and use the public key encryption to encrypt the key, and then use the symmetric key to encrypt the message. Symmetric encryption is far more efficient than public key crypto, and so this is a significant performance gain over using the public key encryption method multiple times to encrypt the message.

• It might be beyond the scope of this question, but it should be noted that $A$ signing the encrypted text doesn't prove that $A$ generated the plaintext. – Aman Grewal Mar 27 at 21:59
• That was super clear and makes perfect sense. Thank you. – Daniel Mar 27 at 22:20

Firstly, you misunderstood what is a signature and encryption with the public key.

A signature requires a hash then sign paradigm with the senders private key so that any receiver can verify the signature. The RSA paper gave the first idea to digital signatures that were insecure and the Rabin Signature released in 1979 is the fist secure signature that contains the hash and sign paradigm.

$$signature = \operatorname{Sign}(K_{prv}, \operatorname{Hash}(m))$$

$$\{Ok, Fail\} \leftarrow \operatorname{Verify}(K_{pub}, signature)$$

Encrypt with the private key misconception is due to the RSA trapdoor permutation that enables for both encryption and signature in the same mathematical way. However, keep in mind that that is only valid for textbook RSA.

Also, never use the same RSA key pairs for encryption end signature. Have a different pair for each with a different modulus that doesn't share even a prime.

• with $\operatorname{Hash}(m)$ you mean the encryption of the message $m$? – Daniel Mar 27 at 21:21
• @Daniel no. The Hash of the message. It is part of the security of the signature scheme. Also, how do you sign large messages? Always consider the signature as a different operation then encryption. – kelalaka Mar 27 at 21:25
• I believe that the original RSA paper (in 1978) described signatures. – poncho Mar 27 at 21:30
• I'm a newbie at this. I'm professional programmer but beginner in cryptography. I know that a hash function is and I used to understand cryptography as a function $E(k,m)$, but asymmetric cryptography is strange. My only doubt right now is how can it be safe if there is an exposed key. I'm not paying attention to signatures, message size or trapdoor permutation (whatever that is). – Daniel Mar 27 at 21:36
• @poncho refreshed my mind. Corrected. Thanks. – kelalaka Mar 27 at 21:37