# how digital signature verification process works

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:

• where did this public key come from?
• and how it is distributed to the receiver?
• how the public key is identified for the specific digital signature?
• and what is the role of the certification authority in this process?
-

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 two key pair used in assymetric 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 original data, the encrypted data, the public key, and information about how to verify the signature (for example, what algorithm is being used)

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.

-
I think you're mixing up "encrypted data" and "signature" which aren't the same thing. I can provide a signature on a plaintext message so that, if you have my public key, you can verify it came from me; there's no requirement that the data is encrypted. Other than that, I like where the answer is going, but could you clarify it a bit? The OP seems to be asking just about signatures are verified, not how messages are encrypted/decrypted with the keys. – redOctober13 Feb 9 at 15:23
What? "Next, to deal with a digital signature, the sender sends: the original data, the encrypted data," ... the sender is sending the original data unencrypted over a network? I don't understand. – Aerovistae Apr 4 at 16:54
A signature provides integrity, not confidentiality - there is more than one kind of security in the world. If you wanted confidentiality, you would add another security mechanism (like encryption) to the transmission. Integrity assures that it has come from the sender, unchanged. That is all that a signature does. Explanation of a digital signature = en.wikipedia.org/wiki/Digital_signature#Explanation – bethlakshmi Apr 18 at 20:20

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:

• an identity (the name of the key owner);
• a public key (purportedly owned by that person);
• a digital signature computed over the two previous parts by a Certification Authority.

The role of the CA is to, precisely, issue certificates, i.e. sign them. You can think of a certificate as the piece of the big marble slab which contains a specific public key. To use the public key, you first want to make sure that this it contains correct information; to do that, you verify the signature one the certificate, using the CA's public key. If that signature is correct, then you know that the CA did 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 public key; how do you know that key ? The answer is in the numbers: a given CA may sign several certificates, possibly millions of them. So there could be, say, one hundred CA, which issue certificates for the whole World. By knowing that hundred public keys, you can potentially verify any certificate. In other worlds, we did not just moved the problem, we also concentrated it: we turned the problem of distributing billions of public keys into the problem of distributing a hundred of them.

And, lo! that's precisely how it is done for HTTPS Web site. During the initial phases of the connection between your browser and the Web server, the server sends his certificate. The browser then verifies the certificate against its list of hardcoded CA public key (which have been included courtesy of the browser or operating system vendor). Once the browser has verified the certificate, it knows the server public key, and uses it to establish the confidential tunnel with the server.

-
Oh my god this is such a more useful answer than the top one. I was totally stuck on that "Wait, why do we trust the CA then, haven't we just moved the problem?" Had no idea certificates were included in browser code. Found the list in my settings. Fascinating. Is that generally true of all software then, that it has to include a list of CAs in order to make use of digital signatures? For instance, how do iOS apps handle it-- do they each include a list separately, or rely on one list hard-coded to the OS? – Aerovistae Apr 4 at 17:00

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.

-
As a note - not every asymmetric key pair is created by the end entity. In a system requiring key escrow, for example, the key is often made centrally and distributed to the owner. It is only critical that the owner be the only key holder in non-repudiation requiring systems. – bethlakshmi Oct 11 '11 at 20:17
I think the question refers to message signing e.g. S/MIME as opposed to SSL. – Bernie White Oct 12 '11 at 10:33
Possible, though I went by focusing on a duplicate (now deleted) question by the same asker that mentioned SSL. In either case, the distribution of the certificate is directly from the target system / individual. – Jeff Ferland Oct 12 '11 at 15:28

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`.

-