Digital certificates: What is the difference between encrypting and signing

Question

I am relatively new to PKI, certificates and all related stuff.

As far as I understand in public-key cryptography one encrypt with a public key and decrypt with a private key. Only one private key can correspond to any public key but the opposite is not true. Is it correct? Or is it one to one mapping?

So, the way digital signature works is that the content of a certificate is hashed and then "signed" with a private key. The signature is verified then with the corresponding public key.

So, here is where I get confused. What is the difference between encrypting a message with a public key and signing a message digest with a private key?

Answer 1

Difference between Message Encryption and Signing

I think information security objectives are essential to realize the difference between message encryption and signing. To define a few objectives:

1. Confidentiality: keeping information secret from unauthorized parties.
2. Data integrity: ensuring that information has not been altered by unauthorized means.
3. Message authentication (data origin authentication): corroborating the information source.
4. Non-repudiation: preventing the denial of previous actions.

Message encryption provides confidentiality.

Message signing binds the identity of the message source to this message. It ensures data integrity, message authentication, and non-repudiation altogether.

I find the fourth objective, non-repudiation, I find it distinguishing so please allow me to elaborate on it. Alice could at some point in time deny having signed a message or Bob could falsely claim that a message signature was produced by Alice. A digital signature permits an unbiased trusted third party (agreed upon in advance) to resolve the dispute without requiring access to the signers' secret information (private keys).

The digital signature system you mention in your question is referred to as digital signature from reversible public-key encryption. All in all, any digital signature scheme should have the following properties:

1. It is easy to compute by the signer.
2. It is easy to verify by anyone.
3. It is secure from forgery until it is no longer needed (the signature lifespan).

As for encryption systems, Kerckhoffs defined a set of requirements that are still, for the most part, useful today. Please read up on the wiki.

Types of Functions Used in Cryptography

Regarding the types of functions that are used for key generation and encryption/decryption, let's again give a few definitions:

1. One-to-one function: A function f: X -> Y is one-to-one if each element in Y is the image of at most one element in X.
2. Onto function: A function f: X -> Y is onto if each element in Y is the image of at least one element in X.
3. Bijection function: A bijection is both one-to-one and onto.
4. One-way function: A function f: X -> Y is one-way if f(x) is easy to compute for all elements in X but for all elements y in Y it is computationally infeasible to find any x such that f(x) = y.
5. Trapdoor one-way function: It is a one-way function f: X -> Y in which the knowledge of extra information (trapdoor information) makes it feasible to find for any y in Y, an x in X such that f(x) = y.

A bijection is used as the tool for encrypting messages and the inverse bijection is used to decrypt.

A trapdoor one-way function is used for key pair generation in public-key cryptosystems and digital signature schemes.

A Trapdoor Concrete Example

In RSA, the public key is (e,n) where n =pq and p and q are two large, distinct prime numbers . e is randomly chosen in the range 1 < e < (p - 1)(q - 1). Given the knowledge of (p - 1)(q - 1), the unique private key d is obtained through the application of the extended Euclidean algorithm. It is a trapdoor one-way function that enables us to obtain d from (e,n).

If you don't know (p - 1)(q - 1) and still would like to discover d, then you need to factor n. If p and q are large and carefully chosen, factoring n should be intractable. This is the RSA problem (RSAP).

But where is the trapdoor? As you may have noticed, the trapdoor is the factors of n. If you know these factors you can easily invert the one-way function and reveal d.