0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Juan
    Commented Jun 9, 2023 at 13:33
  • $\begingroup$ @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'... $\endgroup$
    – poncho
    Commented Jun 9, 2023 at 13:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.