I am not able to understand that how the digital signature is verified. I know that digital signature will be attached to the message and sent by sender to receiver. then receiver uses the public key is used to verify it. Here are my questions:
OK, the answer so far are fundamentally on track, but I'm going to try to take your questions as they came in:
* where did this public key come from?
A public key is part of a key pair used in asymmetric cryptography. There are many encryption algorithms out there, but boils down to a public key and a private key which are mathematically linked. They can be used this way:
Encrypt(public key, original data) -> encrypted data
Decrypt(private key, encrypted data) -> original data
The nature of the mathematical relationship between private and public key are related to the cryptographic algorithm and quickly become a good topic for Math Overflow. :)
The pivotal part is that their is a pair of keys that were generated together.
Next, to deal with a digital signature, the sender sends:
The verifier performs the Decrypt operation above and compares his output with the original data. If the two are the same, he knows that the message was not tampered with, because only the sender has the private key, and there is no reasonable way to determine the private key from the public key.
taking this a little bit out of order...
* and what is the role of the certification authority in this process?
Anyone can make a private/public key pair. It's a pretty easy task, given today's toolkits. So giving you my public key, along with the encrypted data and signature as described is just about as trustworthy as giving you a business card that I had printed at Staples for $50. To really trust that I am who I say I am, and am therefore trust worthy, you need someone to sign off on my identity (like checking a driver's license).
That's the Certificate Authority's job (CA for short). The CA has it's own key pair - and it uses it's private key to sign a digital certificate for the key holder. The certificate includes the public key, as well as a bunch of information about the person or thing holding this private key. This is like my government making me a nice looking id with a picture that can't be easily faked without special equipment - you can believe my information because you trust the government... no because you trust me.
Usually when a system verifies a signature, it not only checks that the encrypted data matches the original data, but also that a certificate that vouches for the identity of the public key holder is also properly signed by a trusted source. Usually CA systems are organized in chains of CAs that originate from a Root. A collection of the more prominent root CAs (which are self-signed, ie, signed by their own private keys), can be found in your browser.
For highly secure systems, additional checks of up to the minute status information can be performed. It all depends on how important it is to be absolutely sure of the sender's status.
* and how is it (the public key) distributed to the receiver?
Double checking here - do you mean the receiver of the certificate or the holder of the key?
The sender (key holder) can get a key pair and a certificate in a variety of ways. The simplest way is to make them locally, and then apply to the CA for a certificate, submitting the public key data. In other cases, keys may be made centrally and distributed by secure channels to the key holders.
In most signature cases, the key pair are made by the key holder, because it limits the potential that the private key is exposed.
When a signature is created and sent to a recipient, it is typical for the public key to also be attached to the message (for example, a standard for this is XMLDSIG where one optional field in the element is a digital certificate, which includes the public key).
In cases where bandwidth is an issue, the public keys may be held in a central repository - like an employee database, or often an Active Directory or other LDAP server. Then the signature can reference the sender's identity and the verification process can include a request to the repository to retrieve the public key.
* how the public key is identified for the specific digital signature?
Usually through a digital certificate.
When the sender goes to create a digital signature, he typically has rules associated with what key pairs he can use for what purposes. In the X509 certificate standard, certificates identify a Key Usage field that spells out specific purposes for the key pair described by the certificate. One of those uses happens to be Digital Signature, and many software systems won't let you create a signature without that setting in the certificate.
The CA actually determines these settings before it signs the certificate. In many security policies, certain key usage settings cannot be granted without specific authentication processes, so the responsibility for figuring this out rests on the CA and the people in charge of it (typically RAs, Registration Authorities).
If, for some reason, you have a system that does not use digital certificates, there may be other ways to determine what key pair. In the end it comes down to the security policies in place and what is deemed appropriate for the given activity that required the signature.
Encrypt(public key, original data) -> encrypted data. Decrypt(private key, encrypted data) -> original data. If you want to sign a document, then encrypt with your private key (not public, as the answer says) to get encrypted data. The receiver will verify by decrypting the encrypted data with your public key. If the decrypted data matches original message, it proves that the encrypted data was obtained by encrypting message with your private key, which only you are supposed to have. So, it verifies that the message came from you.
Commented
May 4, 2017 at 20:58
The problem you refer to (how do we distribute public keys ?) is exactly what Public Key Infrastructures are meant to solve, and the PKI is, essentially, a bunch of Certification Authorities.
In a simple setup, we would have a central directory of the public keys of everybody; imagine it as a big marble slab in the middle of a public park, with the public keys engraved on it. Anybody can have a look at it, and be sure that it is "the genuine thing" because you cannot simply paint over something which was engraved.
A public part is not well-connected to the Internet at large, and computers cannot "see" that some information is engraved and thus "guaranteed correct". Also, there could be billions of key holders out there, which would require a rather large piece of stone. So the translation into the whole-computerized world is the certificate.
A certificate is a small structure which contains, in a conventional format:
The role of the CA is, precisely, to issue certificates, i.e. sign them. You can think of a certificate as a piece of the big marble slab which contains a specific public key. To use the public key, you first want to make sure that it contains the correct information; to do that, you verify the signature on the certificate, using the CA's public key. If that signature is correct, you know that the CA did, in fact, sign that certificate, and since the CA signs only certificates after having checked the key owner's identity (through a one-time physical protocol with them, e.g. the key owner showed an ID), you can be "convinced" that the public key in the certificate really belongs to the identified owner.
Now you could tell me that we have not solved the problem at all, just moved it around: to verify the certificate you must know the CA's public key; How do you obtain that key ? The answer is in the numbers: a given CA may sign several certificates, possibly millions of them. There could be, say, one hundred CAs, which issue certificates for the whole world. By knowing those one hundred public keys, you can potentially verify any certificate. In other words, we did not just move the problem, we also concentrated it: we turned the problem of distributing billions of public keys into a problem of distributing a hundred of them.
And, lo! That's precisely how it is done for HTTPS websites. During the initial phases of the connection between your browser and the webserver, the server sends its certificate. The browser then verifies the certificate against its list of hardcoded CA public keys (which have been included by courtesy of the browser (i.e. Firefox) or operating system itself (i.e. MacOS). Once the browser has verified the certificate, it knows that the public key sent by the server, in fact, belongs to the server, and uses it to establish the confidential tunnel with the server.
Digital signatures are typically made in a two-step process. The first step is to use a secure hashing algorithm on the data. SHA-2 algorithms would be an example of that. The second step is to encrypt the resulting output with the private signing key.
Thus, when a signature is verified by the public key, it decrypts to a hash matching the message. That hash can only be decrypted using the public key if it were encrypted with the private signing key.
Public keys are created by the keypair owner. Certificate authorities sign the public key's certificate. Server owners install that signed certificate. In SSL (which I assume you're referring to), the certificate including the key and signature from the certificate authority is passed by the server you're connected to. You software checks that the site it's connecting to matches the data in the certificate, and validates the certificate by checking its signature against the certificate authority's key. Certificate authorities use their keys for signing and servers use their keys for encryption.
Thus, when a signature is verified by the public key, it decrypts to a hash matching the message. That hash can only be decrypted using the public key if it were encrypted with the private signing key.
You know what is a public - private key, right?
You want to encrypt something to bob. So you'll need his public key. You go search for it in the internet, but you can't be sure that the public key you got really belongs to him.
So you take a different approach: get the key from someone that can assure you that one specific key belongs to bob. The CA does exactly that.
How the CA does that? Simple. bob identifies himself to the CA and send them his public key. This way, the CA have something that relates the "identity" of bob with this public key. And you can trust that the public key that you got really belongs to bob.
