68

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?
schroeder
  • 123,438
  • 55
  • 284
  • 319
n92
  • 869
  • 2
  • 9
  • 9

4 Answers4

41

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

abhishek
  • 103
  • 4
bethlakshmi
  • 11,606
  • 1
  • 27
  • 58
  • 2
    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 09 '16 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. – temporary_user_name Apr 04 '16 at 16:54
  • 3
    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 = https://en.wikipedia.org/wiki/Digital_signature#Explanation – bethlakshmi Apr 18 '16 at 20:20
  • 3
    "The verifier performs the Decrypt operation above". How could verifier perform decrypt operation without having private key? If it's him generating private-public key pair, then why would public key be sent to him with a certificate? – Sasha Oct 07 '16 at 12:03
  • Article https://www.globalsign.com/en/blog/how-do-digital-signatures-work/ helped me to understand answer to my question, but I don't think your answer explains that clear enough. Thanks anyway. – Sasha Oct 07 '16 at 12:37
  • "A signature provides integrity, not confidentiality" - Actually, a signature without any proper certificate or secure public key exchange mechanism does not provide any security at all against man in the middle attacks, since everybody can create key pairs with self signed certificates – Mike76 Oct 08 '16 at 17:22
  • 8
    The following is wrong in this answer. `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. – Ajoy Bhatia May 04 '17 at 20:58
  • 2
    @AjoyBhatia As the first comment states, the answer gets confused between the two different concepts of encryption & signing. Signing a document does not encrypt it. The roles of the keys are somewhat reversed between these [two very different use cases](https://en.wikipedia.org/wiki/Public-key_cryptography#Description) of public key cryptography. – Phil_1984_ May 06 '17 at 17:35
30

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

Govind Rai
  • 105
  • 4
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    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? – temporary_user_name Apr 04 '16 at 17:00
  • @Aerovistae very late to the party, I know. Every common OS, including [iOS](https://support.apple.com/en-us/HT204132) has its own hard-coded list of trusted CAs. Depending on the OS, browsers may use only their own list or complement it with the OS one, see [this answer](https://security.stackexchange.com/a/102684/100201). Also, of course this is a useful answer, it's Thomas Pornin we're talking about :) – A. Darwin Apr 21 '18 at 11:59
  • "a digital signature computed over the two previous parts by a Certification Authority" (c). So how "digital signature" counts? Is it result of hash function of identity (name + info)+public key encrypted with CA's private key? – ipeacocks May 06 '18 at 22:57
  • Is this statement accurate: The receiver decrypts the signature on the certificate provided by the web server, which was signed with the private key, using the public key provided with the cert. The contents of the decrypted signature is a hash of the certificate itself. The web browser will then compare this value against the one stored by the web browser for the certificate authority to verify that the certificate is valid (from a trusted CA), and thus the source is trusted. – alexD Jan 10 '20 at 20:20
  • @Thomas Pornin I have the same understanding like alexD so could you please confirm if this is a correct understanding – Mohamad Haidar Feb 05 '20 at 18:30
  • 1
    @alexD The server sends over its public key signed by a CA (this is the digital certificate). The browser verifies the cert by comparing the signature, decrypting the signature using the CA's public key. If it is able to decrypt the signature of the digital certificate, it can trust the server's public key. Then the browser can generate a symmetric key, encrypt it with the server's public key and send it the server. The server can decrypt that message using its private key. Now both parties can safely communicate and encrypt/decrypt messages using the symmetric key. – Govind Rai Sep 08 '20 at 20:08
14

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.

Jeff Ferland
  • 38,090
  • 9
  • 93
  • 171
  • 1
    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
  • I think this is the only answer that explains what one would expect to be explained by reading the title of the question - `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.` – zgulser May 05 '20 at 10:18
  • @JeffFerland So that means that signature validation schemes have to employ some sort of hash validation in the end, right? If so, that also presents a fundamental difference between how decryption and signature validation in terms of verification. – zgulser May 05 '20 at 10:23
  • 1
    @zgulser https://crypto.stackexchange.com/questions/71355/signature-verification-vs-decryption – Jeff Ferland May 05 '20 at 18:40
8

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.

woliveirajr
  • 4,462
  • 2
  • 17
  • 26