Are asymmetric encryption and decryption same function?

tl flag

In asymmetric key encryption, we have 2 functions, encrypt(m,k) and decrypt(m,k), and 2 keys, public_key and private_key.

And it must hold true that decrypt(encrypt(msg, public_key), private_key)) = msg.

Question 1: Are the encrypt(m,k) and decrypt(m,k) functions different, or are they the same function?

Question 2: Must it also hold true that encrypt(decrypt(msg, private_key), public_key)) = msg?

my flag

In asymmetric key encryption, we have 2 functions, encrypt(m,k) and decrypt(m,k), and 2 keys, public_key and private_key.

Well, if we dig down to the next level, we see that this is not quite true.

encrypt(m,k) is never a function, that is, is determanistic. If it were, then someone with a ciphertext $c$, the public key $k$ could verify if it corresponded to a guess $m'$ by simply checking if $\text{encrypt}(m', k) = c$

Because we want public key encryption to be secure even if we encrypt low entropy plaintexts (that is, ones that could be guessed), we always make the encryption function nondeterministic; that is, it can generate a large number of ciphertexts corresponding to a specific plaintext, key; this prevents the above attack.

If we were to express this in function notation, we have $c = \text{encrypt}(m,k,r)$ (where $r$ is a random value that changes what $c$ is, but not what it decrypts to).

Because public key decryption has no such security requirements, it doesn't take such a random input.

Given that fuller explination of how public key encryption works in practice, I believe that it should be easy to deduce answers to the two questions you asked.

Juan avatar
tl flag
I heard RSA encryption is `m^public % n`, and decryption is `m^private % n`. So it seems that they are indeed the same function (`m^key % n`). I can't figure the answer to my second question though, but I guess it must be true or else certificate signing wouldn't work
poncho avatar
my flag
@Juan: that is 'raw RSA encryption'; because it is not randomized, it is not secure (as I pointed out). RSA isn't the only algorithm that implements public key encryption. And, in practice, when we use RSA for encryption, we use randomized padding, both to cover this vulnerability, and some others that raw RSA encryption has - this padding makes the encryption and decryption different. As for signatures, well, there are lots of other ways to implement signatures other than 'private key encryption'...
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.