How does a public key verify a signature?

Question

I am trying to get a better grapple on how public/private keys work. I understand that a sender may add a digital signature to a document using his/her private key to essentially obtain a hash of the document, but what I do not understand is how the public key can be used to verify that signature.

My understanding was that public keys encrypt, private keys decrypt... can anyone help me understand?

Bratislava

Nice Question. :) – Pippas

I didn't want to add this as an answer and risk the ensuing flames but if you're use of the word "how" really means "how do I verify a signature" then one possibility is to download gpg4win. Once installed, you can right-click a file and verify it. It is a suite of products that integrate into the Windows shell. One such utility is Kleopatra that will look up certificates online to do the validation. – Reunion

Public keys aren't used to encrypt, they're used to sign. The terminology is important because if something is "encrypted", it means it's almost impossible for any person (who doesn't have the private key) to get back the original message. This obviously isn't the case if you sign something with a private key because anyone can get the public key and decrypt the ciphertext to get back the original message. – Esquibel

This tutorial might help: medium.com/gitconnected/… – Esquibel

Answer 1

Your understanding of "public keys encrypt, private keys decrypt" is correct... for data/message ENCRYPTION. For digital signatures, it is the reverse. With a digital signature, you are trying to prove that the document signed by you came from you. To do that, you need to use something that only YOU have: your private key.

A digital signature in its simplest description is a hash (SHA1, MD5, etc.) of the data (file, message, etc.) that is subsequently encrypted with the signer's private key. Since that is something only the signer has (or should have) that is where the trust comes from. EVERYONE has (or should have) access to the signer's public key.

So, to validate a digital signature, the recipient

1. Calculates a hash of the same data (file, message, etc.),
2. Decrypts the digital signature using the sender's PUBLIC key, and
3. Compares the 2 hash values.

If they match, the signature is considered valid. If they don't match, it either means that a different key was used to sign it, or that the data has been altered (either intentionally or unintentionally).

Chuckchuckfull

My understanding was that the keys were not symmetric... that is, objects encrypted with a public key are able to be decrypted by the private key, but that this relationship did not work inversely... more specifically, I did not think objects encrypted with the private key could be decrypted by the public key. If that is indeed the case, than this definitely answers my question. – Bratislava

The keys work inversely to each other. Encrypted something with your public key? Decrypt it with your private key. Conversely, if you encrypted something with your private key, you decrypt it with your public. Such is the nature of asymmetric cryptography. – Chuckchuckfull

Symmetric just means that the same key is used to encrypt/decrypt. Assymetric means that one key encrypts and a different key decrypts (and that the reverse is also true). – Martineau

@PetrDvořák Who is talking about JWT here? The question was about asymmetric cryptography and how it works – Chuckchuckfull

@Chuckchuckfull +1 - I am sorry for the confusion here, this answer was linked from another question discussing how JWT with asymmetric cryptography works. I will remove my comment and write another one. – Secretory

@Chuckchuckfull You can "encrypt" the using the public key (encryption is about hiding the contents) and "sign" using the private key (signing is about proving authenticity). The other party than can "decrypt" data using private key, and "validate signature" using public... – Secretory

(2) decrypts the digital signature using the sender's PUBLIC key -- how public key can be used to decrypt data? if it's so, why can't I decrypt a secret message for Leon using Leon's public key? – Mucky

My original understanding about Asymmetric key was the same as the first comment from @jcampos8782, but it seems like both private and public key can encrypt and decrypt data from the discussion. Then my question is what would be the purpose to use private the decrypt the data while anyone can obtain the public key and decrypt it? – Playpen

@DinoTw this is useful in cases like DKIM, where the public key is sourced from DNS and DNS alone, to verify that a signature was in fact encrypted on a server owned by that domain. – Prig

@Martineau "If they don't match, it either means that a different key was used to sign it," How can the signature be decrypted if the private key used to signed is different? – Pippas

@Jodimoro, Technically a message is NOT "Secret" if it's encrypted with a private key. If it's encrypted with a private key anyone with the publicially available "public" key can decrypt the message. – Contraceptive

@Mucky The only reason the hash is encrypted with a private key into a signature is to ensure the hash is not changed... not to ensure it's "secret". – Contraceptive

Why is this not marked as the answer. This is short and to the point unlike the other answers which make things more confusing. – Spirketing

I understand this perfectly, but could someone tell me then how this is different from the thing explained here: "learnmeabitcoin.com/guide/digital_signatures_signing_verifying"? – Heteronomy

@Heteronomy Thanks for leaving that link (reference). That was the only article that truly explained this topic IMO. If public-key cryptography ensures that a public key can be derived from a private key, but a private key cannot be derived from a public key, then you might wonder, how can a public key decrypt a message signed with a private key without the sender exposing the private key to the recipient? Answering this question without mentioning elliptic curve multiplication seems incomplete IMO. – Aspiration

@Chuckchuckfull this post changed my life; I was literally trying to grasp the difference but never realized its that simple :) – Ecclesiolatry

Answer 2

The keys work inversely:

Public key encrypts, private key decrypts (encrypting):

openssl rsautl -encrypt -inkey public.pem -pubin -in message.txt -out message.ssl
openssl rsautl -decrypt -inkey private.pem       -in message.ssl -out message.txt

Private key encrypts, public key decrypts (signing):

openssl rsautl -sign -inkey private.pem       -in message.txt -out message.ssl
openssl rsautl       -inkey public.pem -pubin -in message.ssl -out message.txt

Below is an example script to test this whole flow with openssl.

#!/bin/sh
# Create message to be encrypted
echo "Creating message file"
echo "---------------------"
echo "My secret message" > message.txt
echo "done\n"

# Create asymmetric keypair
echo "Creating asymmetric key pair"
echo "----------------------------"
openssl genrsa -out private.pem 1024
openssl rsa -in private.pem -out public.pem -pubout
echo "done\n"

# Encrypt with public & decrypt with private
echo "Public key encrypts and private key decrypts"
echo "--------------------------------------------"
openssl rsautl -encrypt -inkey public.pem -pubin -in message.txt         -out message_enc_pub.ssl
openssl rsautl -decrypt -inkey private.pem       -in message_enc_pub.ssl -out message_pub.txt
xxd message_enc_pub.ssl # Print the binary contents of the encrypted message
cat message_pub.txt # Print the decrypted message
echo "done\n"

# Encrypt with private & decrypt with public
echo "Private key encrypts and public key decrypts"
echo "--------------------------------------------"
openssl rsautl -sign    -inkey private.pem -in message.txt          -out message_enc_priv.ssl
openssl rsautl -inkey public.pem -pubin    -in message_enc_priv.ssl -out message_priv.txt
xxd message_enc_priv.ssl
cat message_priv.txt
echo "done\n"

This script outputs the following:

Creating message file
---------------------
done

Creating asymmetric key pair
----------------------------
Generating RSA private key, 1024 bit long modulus
...........++++++
....++++++
e is 65537 (0x10001)
writing RSA key
done

Public key encrypts and private key decrypts
--------------------------------------------
00000000: 31c0 f70d 7ed2 088d 9675 801c fb9b 4f95  1...~....u....O.
00000010: c936 8cd0 0cc4 9159 33c4 9625 d752 5b77  .6.....Y3..%.R[w
00000020: 5bfc 988d 19fe d790 b633 191f 50cf 1bf7  [........3..P...
00000030: 34c0 7788 efa2 4967 848f 99e2 a442 91b9  4.w...Ig.....B..
00000040: 5fc7 6c79 40ea d0bc 6cd4 3c9a 488e 9913  [email protected].<.H...
00000050: 387f f7d6 b8e6 5eba 0771 371c c4f0 8c7f  8.....^..q7.....
00000060: 8c87 39a9 0c4c 22ab 13ed c117 c718 92e6  ..9..L".........
00000070: 3d5b 8534 7187 cc2d 2f94 0743 1fcb d890  =[.4q..-/..C....
My secret message
done

Private key encrypts and public key decrypts
--------------------------------------------
00000000: 6955 cdd0 66e4 3696 76e1 a328 ac67 4ca3  iU..f.6.v..(.gL.
00000010: d6bb 5896 b6fe 68f1 55f1 437a 831c fee9  ..X...h.U.Cz....
00000020: 133a a7e9 005b 3fc5 88f7 5210 cdbb 2cba  .:...[?...R...,.
00000030: 29f1 d52d 3131 a88b 78e5 333e 90cf 3531  )..-11..x.3>..51
00000040: 08c3 3df8 b76e 41f2 a84a c7fb 0c5b c3b2  ..=..nA..J...[..
00000050: 9d3b ed4a b6ad 89bc 9ebc 9154 da48 6f2d  .;.J.......T.Ho-
00000060: 5d8e b686 635f b6a4 8774 a621 5558 7172  ]...c_...t.!UXqr
00000070: fbd3 0c35 df0f 6a16 aa84 f5da 5d5e 5336  ...5..j.....]^S6
My secret message
done

Vociferance

Thanks for adding the script - definitely helped clear things up. – Kvass

Thanks a lot, it's always easier for me to understand with ecample – Jaclynjaco

Answer 3

If I had to re-phrase your question from how I understand it, you are asking the following:

If public key cryptography ensures that a public key can be derived from a private key, but a private key cannot be derived from a public key, then you might wonder, how can a public key decrypt a message signed with a private key without the sender exposing the private key within the signed message to the recipient? (re-read that a few times until it makes sense)

Other answers have already explained how asymmetric cryptography means that you can either:

1. Encrypt with public key, decrypt with matching private key (pseudocode below)

var msg = 'secret message';

var encryptedMessage = encrypt(pub_key, msg);

var decryptedMessage = decrypt(priv_key, encryptedMessage);

print(msg == decryptedMessage == 'secret message'); // True

2. Encrypt with private key, decrypt with matching public key (pseudocode below)

var msg = 'secret message';

var encryptedMessage = encrypt(priv_key, msg);

var decryptedMessage = decrypt(pub_key, encryptedMessage); // HOW DOES THIS WORK???

print(msg == decryptedMessage == 'secret message'); // True

We know that both example #1 and #2 work. Example #1 makes intuitive sense, while example #2 begs the original question.

Turns out, elliptic curve cryptography (also called "elliptic curve multiplication") is the answer to the original question. Elliptic curve cryptography is the mathematical relationship that makes the following conditions possible:

1. A public key can be mathematically generated from a private key
2. A private key cannot be mathematically generated from a public key (i.e. "trapdoor function")
3. A private key can be verified by a public key

To most, conditions #1 and #2 make sense, but what about #3?

You have two choices here:

1. You can go down a rabbit-hole and spend hours upon hours learning how elliptic curve cryptography works (here is a great starting point)... OR...
2. You can accept the properties above--just like you accept Newton's 3 laws of motion without needing to derive them yourself.

In conclusion, a public/private keypair is created using elliptic curve cryptography, which by nature, creates a public and private key that are mathematically linked in both directions, but not mathematically derived in both directions. This is what makes it possible for you to use someone's public key to verify that they signed a specific message, without them exposing their private key to you.

Aspiration

Your 3 conditions explain it all. I just read this terme 'elliptic curve' ans I was like wtf – Jaclynjaco

so, this should be the answer? – Reportage

wow, this is a great answer. Thank you so much. – Ambassadoratlarge

This answer is what I was looking for. There is literally no explanation of this on anywhere else on whole internet. – Sepaloid

Answer 4

The public key encrypts and only the private key can decrypt it, and the reverse is true. They both encrypt to different hashes but each key can decrypt the other's encryption.

There are a few different ways to verify that a message came from some expected sender. For example:

The sender sends:

1. The message

2. The hash of the message encrypted with their private key

The receiver:

3. Decrypts the signature (2) with the public key to obtain a message, supposedly the same message as (1) but we don't know yet. We now have two messages that we need to verify are identical. So to do this, we will encrypt them both with our public key and compare the two hashes. So we will ....
4. Encrypt the original message (1) with the public key to obtain a hash
5. Encrypt the decrypted message (3) to get a second hash and compare to (4) to verify that they are identical.

If they aren't identical it means either the message was tampered with or it was signed with some other key and not the one we thought...

Another example would be for the sender to use a common hash that the receiver might know to use as well. For example:

The sender sends:

1. A message
2. Takes a known hash of the message, then encrypts the hash with the private key

The receiver:

3. Decrypts (2) and gets a hash value
4. Hashes the message (1) with the same hash used by the sender
5. Compares the two hashes to make sure they match

This again ensures the message wasn't tampered with and it is from the expected sender.

Keck

How would step 5 in the first example, hash of an already hashed message, generate the same hash as step 4? – Stumble

Answer 5

Thought I'd provide a supplemental explanation for anyone looking for something more intuitively revealing.

A big part of this confusion arises from naming 'public keys' and 'private keys' as such because how these things actually work is directly at odds with how a 'key' is understood to be.

Take encryption for example. It could be thought of as working like so:

• The parties that want to be able to read the secret messages each keep a key hidden (i.e. a private key)
• The parties that want to be able to send secret messages all have the ability to obtain an unlocked locked (i.e. a public lock)
• Then sending a secret message is as easy as locking it with an unlocked lock, but unlocking it afterwards can only be done with one of the hidden keys.

This allows secret messages to be sent between parties, but from an intuitive standpoint here, 'public lock' is a more suitable name than 'public key'.

However, for sending digital signatures the roles are somewhat reversed:

• The party that wants to sign messages is the only one with access to the unlocked locks (i.e. a private lock)
• The parties that want to verify the signature all have the ability to obtain a key (i.e. a public key)
• Then what the signer does is create two identical messages: the one that anyone can read and one to accompany it, but which they lock with one of their private locks.

• Then when the receiver gets the message, they can read it, and then use the public key to unlock the locked message and compare the two messages. If the messages are the same, then they know that:

  1. The unlocked message wasn't tampered with during travel and,

  2. The message must have been from the person who has the matching lock to their public key.

• And finally, this entire system only works if anyone who wants to validate a signer's signature has an authoritative place to go to to get the matching key to the signer's locks. Otherwise, anyone can say "Hey, here's the key to so-and-so's private lock", send you a message pretending to be them but lock it with their private lock, you perform all the above steps and believe the message must actually be from the person you thought, but you're fooled because you were mislead as to the true owner of a public key.

So long as there's a trust-worthy source for retrieving a signer's public key, you'll know who the rightful owner of a public key is, and will be able to validate their signature.

Jonna

Changing 'key' to 'unlocked lock' just adds to the confusion. – Deca

@EJP I don't change key to 'unlocked lock'. It's changed to 'lock'. 'Unlocked locked' is only used for the purpose of expressing the item's use. Regardles, that is your opinion, and if you have any long-term experience in the crypto community, it is likely extremely biased because the existing terms are how you've grown to understand the technology. Why don't you let people who are just starting determine whether or not the analogy is useful? – Jonna

I think the analogy with locks and keys are quite good to provide a first understanding of this matter. Once you visualize the locks and the keys, they can be exchanged different integers that are assembled to rsa (or other type of) keys. – Culbertson

I personally think this insight is the best one, I've read so far. And definitely see how adding lock instead of key to private/public makes whole system intuitively self-explanatory for regular new comers. While at the moment it is not at all. We are seasoned devs (just with no direct touch to crypto until now) and we argued about the purpose of public/private for some time. I was saying that private is used to encrypt, while he was saying that public is used to encrypt :D – Culosio

Answer 6

To your question - i was looking at the RSA implementation. And got more clarity on the way a public key is used to verify the signature using a private key. Undoubtedly, the private key is not exposed. Here is how...

Trick here is to hide the private key within a function. In this case, (p-1)*(q-1).

Consider p to be the private key and e to be the public key. p is encapsulated within another function to make it hidden.

E.g., `d = (p-1)(q-1); d * e = 1` (d is the inverse of e - public key)

Data sent = [encrypted(hash), message] = [m ^d, message];

where m is the message Suppose

'Data sent' = y

To check for the integrity we find y^e to get m. Since m ^(d*e) = m ^1 = m.

Hope this helps! :)

Shayla

This is the strangest answer I ever seen on stackoverflow. Answering to OP with a math formula... – Selfmortification

Answer 7

Practically, it's important to note that there are some assumptions in this process. To demonstrate this, let's write the model again:

1. Side A has data d, public key E and private key D
2. Side A computes H(d) for a known hash function H (to make the signature object size to be independent on the data size) and signs it with private key D(H(d)) := x
3. Side A publishes the pair (d,x) alongside with it's public key and hash function (E,H)
4. Side B who want to verify data integrity compares locally computed H(d) to E(x) = E(D(H(d))) and given that the comparison is valid side B knows that the data is valid.

Examples for cases that demonstrate some of the assumptions/ known weaknesses:

1. Assumption: you believe that Side A is who he claims to be: I.e. under a man-in-the-middle threat, where side C might be pretending to be side A, the attacker C can just publish (m,s) alongside with (E',H) where m is malicious data and s is m's signature using the attacker private key D'. It's clear that side B will be obliged to think that this data is valid. To know more about identity integration read about certificate authorities. The basic notion here is that you have some root of trust (practically, list of keys installed in your browser for example) that can be used to expand trust further.
2. Assumption: Finding hash preimage is a "tough" task: Under some H function that is easily inverted, one can find some other data d' such that H(d')=H(d), and then the pair (d',x) is considered as valid. This basically means, that sometimes it's enough for the attacker to convince the victim to use weak hash function to be able to make this process invalid.
3. Assumption: It is hard to forge a signature: I will give a known example for an RSA weakness called malleability. Under RSA, given a signed value x^D and another signed value y^D an immediate result is that x^D*y^D=(xy)^D is a valid signed message xy that can be forged without knowing anything about x,y. This opens a room for attacks (e.g. bleichenbacher), and an immediate result of this attribute is that one must not use the same key for signing and decrypting.

Larimore

This is a great description of public/private key data signing. I believe E' in this case is the malicious public key that is compatible with the s made using the attacker's matching malicious private key D'. The beauty seems to be that E(D(x)) = x for matching keys. Am I right in any of the following: that D(E(x)) <> E(D(x)) is either true, or E(x) is an invalid transform somehow. – Vince

@JCollins, good question. It does not have to satisfy that in every scheme! For example, consider Hash-Based signatures: The basic idea is having a public hash function h, and when side A want to sign some data d what he does is to take a random value x, compute h(x) and publish h(x) as his public key. Now, for signing the data d side A publishes alongside d also the hash preimage x so that now everyone can verify that h(x)=h(x). However note that this public key is one time key! Now, in this case E=h and we don't even have an explicit D = h inverse. – Larimore

Answer 8

I think the big issue in the misunderstanding is that when people read "Asymmetric", in their heads they think "Ok, one key encrypts and the other decrypts, hence they are asymmetrical". But if you understand that Asymmetrical actually means "IF key A encrypted data, then its "sister" key B can decrypt data. If Key B was used to encrypt data, then key A can now only decrypt." Symmetric means the same key that was used to encrypt the data can be used to decrypt the data.

Nootka

Answer 9

If I encrypt some text with my private key then anyone who has my public key can decrypt it. Public key being public, anyone can have it (including thieves and cheats), so what is the point of encrypting a text with my private key (given it can be decrypted with my public key, which is available publicly)?

Well it gives us authenticity. I mean, If you were able to decrypt a message with my public key, then you can say the message was by me. But, there is a but. Suppose someone decrypted a message with my public key and got the message "Hi!", does it mean I said "Hi!". It is possible that some other private key was used to encrypt a message, and coincidentally my private key decrypt it as a meaningful text instead of gibberish.

Well this is why we also need to provide the exact message with our public key. So that, the receiver can compare it with the decrypted message.

So, we provide

• Public Key
• Original Message
• Encrypted Message

If Original Message = Decrypt(Encrypted Message, Public Key) then the message inside was definitely by me as only I have the private key.

Bonus:

Always sending the "Original Message" is not convenient. The "Original Message" can be a 4GB ISO file. It is better to calculate a hash (A one-way hash function, also known as a message digest, is a mathematical function that takes a variable-length input string and converts it into a fixed-length binary sequence that is computationally difficult to invert—that is, generate the original string from the hash) of the original message and send it.

So, now we are sending:

• Public Key
• Hash of the Original Message
• Encrypted Hash of the Original Message

Now If Hash(Original Message) = Decrypt(Encrypted Message, Public Key) then the message inside was definitely by me as only I have the private key.

Caffey

If we encrypt some text with private key then any one who has a public key can decrypt it. Public key being public, anyone can have it (including thieves and cheats), so what is the point of encrypting a text with public key? I don't think this statement makes sense - you mean what's the point of decrypting it with public key, right' – Autocrat

@tilz0R I have fixed the answer, please check it now. – Caffey

Answer 10

Here is an example(public key -> (e,n), private key -> (d,n)) using RSA algorithm in python demonstrate:

• encrypt using public key, decrypt using private key
• encrypt using private key, decrypt using public key

p = 11 # random prime number
q = 47 # random prime number
n = p*q
e = 17 # random number that is coprime with phi
phi = (p-1)*(q-1)
d = pow(e, -1, phi) # mod_inverse

# encrypt using public key
enc = pow(123,e,n)
# decrypt using private key
print(pow(enc,d,n))

# encrypt using private key
enc = pow(123,d,n)
# decrypt using public key
print(pow(enc,e,n))

Fantasist