Decrypt a public encrypted message and Sign a signature, how the math is different?

Question

As I understand, when you want to send a confidential message to someone, you encrypt the message with his public key. And he use his private key to decrypt the message.

At the same time, one can use his private key to sign a message, and other people use his public key to verify that it's him who sign it.

How the math is different between decrypt the message and sign a message?

Answer 1

The simplistic view that signing uses the same math as decryption is descriptive with textbook RSA; has some relation to practice in safe use of RSA; and is just wrong with most other common asymmetric cryptosystems, beside the commonality that a private key is involved.

---

In textbook RSA, the math to decrypt an encrypted message and compute a signature is the same: it is applied the textbook RSA private key function $x\to y=x^d\bmod N$, with $(N,d)$ the private key, and $x$ the encrypted message in decryption, or the message to sign in signature. Problem is, textbook RSA is unsafe for both encryption and signature.

When we move to secure use of RSA, the math becomes different:

• To decrypt we check the bound of the cryptogram $x$, apply the above textbook RSA private key function, then
  • Extract the encrypted message from the result $y$, in a certain way that removes random padding that was added at encryption (and perhaps checking certain fields). There are at least two common classes of RSA encryption padding and corresponding decryption removal, defined in PKCS#1, and several implementation variants (not all are safe). That can be enough for very small messages (like few hundred bytes).
  • And/or what we really obtain is a secret key, which is then used to decipher the bulk of the message using symmetric-key cryptography (that's hybrid encryption).
• To generate a signature we typically hash the message to sign then add redundancy in a certain way, then apply the above textbook RSA private key function to obtain the signature $y$ (in some variants we further keep $\min(y,N-y)$ ). There are at least three common classes of RSA signature padding: two in PKCS#1, and ISO/IEC 9796-2, which comes with several variations.

---

When we move to asymmetric cryptosystems other than RSA, one thing remains: the private key is involved in decryption, and/or computing a signature. Other than that, there is typically profound disjunction between decryption and computing a signature (one notable exception is the Rabin cryptosystem, which can be seen as a variant of RSA with even public exponent); and very often, one of the two features is just not offered by a particular cryptosystem.

For example, we have DSA, ECDSA, and Lamport signatures, but these cryptosystems do not offer encryption.

The converse can be true: we have Pailler encryption, but no useful signature analog. We have NTRUEncrypt, which latest versions are unbroken; but it is quite different from the related NTRUSign, and last time I checked work on the later stopped in the broken phase of multiple break/repair cycles.

Answer 2

Actually, the theoretical math is not really different:

Formally speaking, a public key cryptosystem is given by:

• a set $M$ of possible plain messages, and a set $C$ of possible ciphertexts; often $M=C$;
• a set $K$ of possible keys;

• for each $k \in K$, a pair of function $E_k: M \rightarrow C$ and $D_k: C \rightarrow M$ such that:

  1. $D_k(E_k(m))=m$ for all $m \in M$ and $E_k(D_k(c))=c$ for all $c \in C$;
  2. $\forall m \in M $ $E_k(m)$ is easy (and computationally fast) to compute, and $\forall c \in C$ $D_k(c)$ is easy (and fast) to compute;
  3. knowing only $E_k$, it is computationally infeasible to find $D_k$;
  4. knowing $k$, it is easy to find $E_k$ and $D_k$.

The functions $E_k$ and $D_k$ are called encryption and decryption functions associated with the key $k \in K$.

In practical application, a user Bob chooses a key $k \in K$ and computes the functions $E_k, D_k$; he then makes $E_k$ public (e.g. on the internet), and keeps $D_k$ secret. Thanks to property (4), it should be difficult for anyone except Bob to get $D_k$. Now, suppose that a user Alice wants to send a message $m$ to Bob, and wants no one else but Bob to be able to read it: she looks for Bob's public encryption function $E_k$ on the internet, computes $c=E_k(m)$, sends $c$ trough the communication channel, Bob receives it and computes $D_k(c)$, obtaining the original message $m$ (thanks to property (1)). Even if the communication channel is not secure, any eavesdropper (say Eve) cannot deduce the message $m$ from $c$, and $c$ is the only thing that pass trough the channel.

(For the sake of clarity: usually, when dealing with a specific public key cryptosystem, the functions $E_k$ and $D_k$ are obtained from $k \in K$ in a standard way: for example, in the RSA cryptosystem, $k$ is a triple $(n, e, d)$ and the $E_k(x)=x^e$ (mod $n$), while $D_k(x) = x^d$ (mod $n$). It is clear that, if everyone knows that this cryptosystem is being used in a specific situation, keeping $D_k$ secret and making $E_k$ public is equivalent to keeping $d$ secret, and making $(n,e)$ public. This is why, in many situations, we will talk of a public key and a private key instead of a encryption function and a decryption function, but we should be aware this is exactly the same setting.)

Now, when instead of encrypting messages we want to sign messages, we just switch the use of $D_k$ and $E_k$:

Now Bob wants to put his signature onto a message $m$ (say, some kind of contract with Alice), so he computes $y=D_k(m)$ and send the pair $(m,y)$ to Alice. Everyone (included Alice) now can verify that the message was signed by Bob, simply computing $E_k(y)$ (recall $E_k$ is publicly known!) and checking this equals $m$ (again, by property (1), this is true if Bob did it right).

In conclusion, when we have a cryptosystem, it is easy to create a signature scheme, so actually the math is not different at all! And indeed, when we have an encryption system (RSA, ElGamal, NTRU,...) , we usually also have a corresponding signature scheme (RSA Signature, ElGamal Signature, NTRUSign,...)