In public-key encryption, if the decryption algorithm is


where $k_i$ = receiver's private key and $K_i$ = receiver's public key

what would be the algorithm for encryption? Would it be


Just looking for some clarification.


2 Answers 2


The question's formula $\text{Dec}(k_i,\text{Enc}(K_i,p))=p$ is for both encryption and decryption.

Encryption is $p\mapsto\text{Enc}(K_i,p)=c$.

Decryption is $c\mapsto\text{Dec}(k_i,c)=p$.

Note that $\text{Dec}$ can be a true function, but $\text{Enc}$ likely has a hidden random argument. Otherwise encryption would be deterministic, and deterministic encryption is vulnerable to chosen-message attack, especially public key encryption. If a name on the public class roll is encrypted with deterministic public-key encryption (such as textbook RSA encryption), anyone can find the name from the ciphertext, simply by enciphering all names on the class roll and comparing with the ciphertext.

In a textbook RSA context, $\text{Enc}(K_i,\text{Dec}(k_i,c))=c$ would be equivalent to textbook RSA signature of message $c$ followed by textbook RSA signature verification. But it is using a confusing notation, that won't work in most other signature contexts (e.g. Schnorr signature, DSA, ECDSA, EdDSA).


Since the private key belongs to person $i$ only they can perform the decryption. It will turn out signature, hey, wait there.

This expression is commonly used to express the RSA operations public key encryption and decryption, digital signatures, and verification of the digital signature. This created the confusion that still remains over the net and even some lecturer slides.

The confusion comes from the fact that RSA is a trapdoor permutation that can be used both public key encryptions and digital signatures in the same way!!!. We call it the textbook RSA and that should not be used ever!.

The bold title is from Cornell University, it is published to warn people about the mistake;

Firstly, We cannot sign arbitrarily long messages since the output size will be at least as long as the message $m$. Instead, we use the hash-then-sign paradigm. So the equation will turn

$$Enc(K_i, Dec (k_i, hash(m))) = hash(m)$$

Secondly, correct the other mistake; in RSA, the signature requires special padding to be secure namely RSA-PPS, now let turn the dec and enc into proper names sign and vrfy for digital signature in RSA. The RSA digital signature operation;

$$ s = sign (k_i, hash(m))$$ And, the RSA digital signature verification;

$$ (hash(m)|\perp) = vrfy( K_i, s)$$ either accept the signature, or halt $\perp$ if the signature is not valid. Note that, the $sign$ and $vrfy$ implicitly includes the PSS encoding and verication. Any error in the decoding must not be ignored.

So, the operation is the digital signature and verification of the signatures if properly used.

Similarly, for encryption RSA requires padding to be secure, there are two common paddings; PKCS#1 v1.5 padding and the Optimal Asymmetric Encryption Padding OAEP. The former has lots of problems and hard to implement correctly, prefer the OAEP.

Actually, we don't use the public key for encryption, instead, prefer the hybrid cryptosystem, Key exchange with DHKE or RSA-KEM then a Keu Derivation Function (KDF) to derive a ley to use in symmetric-key encryption schemes that have the authenticated encryption like AES-GCM, ChaCha20-Poly1305.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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