Digital certificates: What is the difference between encrypting and signing
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?
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 in Y is the image of at most one element in X.
- Onto function: A function f: X -> Y is onto if each element in Y is the image of at least one element in X.
- Bijection function: A bijection is both one-to-one and onto.
- 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.
- 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.
Message Encryption makes the whole message unreadable to anyone but the owner of the corresponding private key.
When you sign a message, then it creates something like a checksum of the message content in combination with data from the key, which can be verified against a public key. This does not make a message unreadable to anyone, but can verify that the message really originated from the sender and was not altered since.
Of course this requires you to trust the public key, but that is another story.
To your first question: AFAIK it is theoretically possible to create a public key collision, but highly unlikely.
public keys encrypt, private keys decrypt for encryption and for digital signatures, it is the reverse. Tip: Imagine public key as padlock and private key as key which opens the padlock.
Two of the best-known uses of public key cryptography or asymmetric cryptography are digital signature and Public key encryption. In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of the private key.
To use a Digital Signature or Public key Encryption we must have a digital id or digital certificate or pubic key certificate or identity certificate. It is an electronic document used to prove the ownership of a public key.
Digital Signatures in which a message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key. This verification proves that the sender had access to the private key, and therefore is likely to be the person associated with the public key. This also ensures that the message has not been tampered with, as a signature is mathematically bound to the message it originally was made with, and verification will fail for practically any other message, no matter how similar to the original message. An analogy for digital signatures is the sealing of an envelope with a personal wax seal. The message can be opened by anyone, but the presence of the unique seal authenticates the sender.
Public Key Encryption in which a message is encrypted with a recipient's public key. The message cannot be decrypted by anyone who does not possess the matching private key, who is thus presumed to be the owner of that key and the person associated with the public key. This is used in an attempt to ensure confidentiality. An analogy to public key encryption is that of a locked mail box with a mail slot. The mail slot is exposed and accessible to the public – its location (the street address) is, in essence, the public key. Anyone knowing the street address can go to the door and drop a written message through the slot. However, only the person who possesses the key can open the mailbox and read the message.
- A Public Key Infrastructure (PKI) is a set of roles, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates and manage public-key encryption.
img src Registration Authority (RA), Certificate Authority (CA) and Validation Authority (VA)
DES (Data Encryption Standard) and Triple DES (a stronger variant of DES), AES(Advanced Encryption Standard) are Symmetric key cryptosystems. Which uses the same key for encryption and decryption.
DSA(Digital Signature Algorithm) and RSA(Ron Rivest, Adi Shamir and Leonard Adleman) are public-key cryptosystems, which are widely used used for secure data transmission. DSA provide only digital signatures and RSA provide both digital signature and encryption.
Any private key has one public key and any public key has one private key its always one to one mapping.
Signing the message is only create a finger print for the message just to make sure that the content hasn't been altered, but it has no effect on the message it self and the message will never be encrypted.
While encrypting the message will do the encryption. you can encrypt a message and sign it at the same time.
As already mentioned in the other answers, public and private key are coupled with each other. Actually in many encryption context you have a pair of numbers with certain properties and can choose which you want to use as private and which as public key. Thus, there is a certain degree of uniqueness here. (Details may vary according to the algorithm in question.)
When talking about PKIs, though, you often do not consider public keys but certificates which essentially are bundles of information (issuer, subject, validity interval, usage constraints, ...) with a public key. When creating certificates, you of course can build different certificates for the same public key.
Thus, while private and public keys essentially are one-to-one, private keys and certificates may be one-to-many.
Maybe this is the cause of your one-to-one confusion.