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:
- Confidentiality: keeping information secret from unauthorized parties.
- Data integrity: ensuring that information has not been altered by unauthorized means.
- Message authentication (data origin authentication): corroborating the information source.
- 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:
- It is easy to compute by the signer.
- It is easy to verify by anyone.
- 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:
- One-to-one function: A function
f: X -> Y
is one-to-one if each element inY
is the image of at most one element inX
. - Onto function: A function
f: X -> Y
is onto if each element inY
is the image of at least one element inX
. - Bijection function: A bijection is both one-to-one and onto.
- One-way function: A function
f: X -> Y
is one-way iff(x)
is easy to compute for all elements inX
but for all elementsy
inY
it is computationally infeasible to find anyx
such thatf(x) = y
. - 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 anyy
inY
, anx
inX
such thatf(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
.