Finance and capital markets
- Bitcoin: What is it?
- Bitcoin: Overview
- Bitcoin: Cryptographic hash functions
- Bitcoin: Digital signatures
- Bitcoin: Transaction records
- Bitcoin: Proof of work
- Bitcoin: Transaction block chains
- Bitcoin: The money supply
- Bitcoin: The security of transaction block chains
A high-level explanation of digital signature schemes, which are a fundamental building block in many cryptographic protocols. Created by Zulfikar Ramzan.
Want to join the conversation?
- How is the verification actually made? How can we know that Alice actually has the correct private key and how can we tell when someone tries to forge it? It would be very interesting with a minimal example of what that mathematical relationship could look like, even if the example has none of the necessary security measures.(13 votes)
- If you go to the applied math section on the Khanacademy site and look under the modern cryptography section, Brit Cruise does a very detailed explanation of the algorithm for RSA encryption. It takes him numerous videos to explain it fully though.(30 votes)
- At about5:12it is said that the Public Verification Key basically outputs a "yes" or "no" for accepting a signature. How does this work ?(1 vote)
- The check function has an output, which may be the signature, for example. I may want to tell you my garage key code 47913 and note, so you can be sure it's me, ER (Exponentially Radical). If we see E as 14 (i.e. E may be 14, in hexadecimal or something) and R as 27 (i.e. R is the 18th letter of the alphabet, add 9 to avoid mixing letters with numbers). My message 47913 ER would be read, by the checking program, as 4-7-9-1-3 and 14-27. The checker may add the digits in the first part of the message 4+7+1+9+3=24 and multiply the digits, in the second part 14*27=378. Since the checkers like to limit digits to say 2 digits, this checker may add the numbers 3+7+8 to get 18. The check function may be designed, to subtract the smaller part, from the bigger part 24-18=6. But 6 is just one digit. To maintain a two-digit digest, the program may consistently append an A So I'd send:
and you'd be able to verify that 47913 ER really makes 6A so you have the correct garage code (perhaps, to deliver me chocolates, while I'm away), you'd know it was from E R, and you'd know it would have been impractically difficult to forge. If 47913 ER doesn't make 6A, the message is a fake!
If you were to change the message, from ER, my initials, to EB, your initials, the signature becomes 14, which is very different, from 6A. The changed message is clearly a forgery. As long as the checker function is much more complex than the one I described or its operations remain secret, then covertly forging messages will stay practically impossible.(8 votes)
- Does it mean that every signature would be different for each message? And would Alice have any say how the signature will look like or is it just randomly generated combination of letters and numbers? And what happens if Alice forgets her signature or does she have to remember it at all?(3 votes)
- That's correct. If you have two distinct messages, then with overwhelming likelihood, their signatures will be different. Note that the number of signatures is finite for typical digital signature schemes since the output length for them is fixed. However, the number of possible messages is infinite. So it is theoretically possible that two different messages will have the same signature. However, for a well designed digital signature scheme, it should be infeasible to find two such messages that have the same signature. (By infeasible, I mean that it would require an astronomical amount of computation and would not be remotely practical.) Also, typical digital signature schemes have some randomness incorporated in them. This way even two instances of a signature by the same person on the same message will look different. The "Digital Signature Standard" (DSS), which is what bitcoin uses, has this property that a random sequence of numbers is generated whenever a message is to be signed. This sequence of numbers is incorporated into the signature to help ensure that it looks different each time. I hope this helps answer your question.(6 votes)
- What exactly links the verification key to Alice? What would prevent me from taking her public key and claiming it is mine (as such, messages signed by her would be claimed to be signed by me)? I guess what I am asking is: how can you verify that a public verification key belongs to a certain identity?(4 votes)
- Alice will have to do her best to keep her private/signing key safe and secure (also, most key algorithms allow encrypting the key itself with a password). In a non-bitcoin use of this crypto, you and Alice would probably meet and exchange keys, therefor guaranteeing its source. In bitcoin-land you don't actually care if the key belongs to Alice or not, although Alice will have to keep her private key private, or otherwise people could spend her money.(2 votes)
- Why is it important to create a short hash for your message rather than just using the original value? How exactly do you create a hash for your message?(1 vote)
- You need to hash together your message and your private key in order to create a digital signature. The entire message is hashed into the digital signature for two reasons: first, so that you have a different digital signature every time, and second, so that no one can change the message along the way.
This second reason is worth elaborating on. When you broadcast a transaction to all the nodes, what you are really doing is broadcasting a transaction to eight nodes, and then expecting the eight of them to relate that transaction to seven more nodes each, and expecting all of those to relate that transaction to seven more nodes, and so on. So, if one of the earlier nodes decided to change the transaction, you would have two competing transactions, one of which is fake. So, we have you hash the entire message along with your private key to create a digital signature, so that if someone does try to change the transaction, the digital signature would be invalid.(4 votes)
- Checking my understanding of collision resistance:
If you have a message that says 2+2 you can never have another message that says 3+1. Am I right?
Also, If I just want to use Bitcoin, do I need to know this stuff? Is it this hard to use? I ask because I'm finding it really hard to find videos online of how to actually use Bitcoin that actually display its use and describe it in a way that avoids jargon. This is despite the fact that the community calls for new users to carefully research things like how to be secure in ones use of Bitcoin.
With new technology like this I would normally just dive in and try it out, but I'm really apprehensive about approaching it in this way. The tendency for the community to talk in this kind of jargon is a huge barrier to the uptake of the tech.(3 votes)
- You actually don't need to know anything about the specifics. You can just create a wallet and start using bitcoin. But these things are helpful to understand the technology behind bitcoin and why it works.(0 votes)
- Let me get this straight. For signature verification, both the message, and it's signed hash are sent over plain, and then are verified by "unsigning" the hash, and comparing that to the hash of the received message?(2 votes)
- The original message and the signature are both sent over. The receiver uses the public key (aka verification key in the video) to verify that the signature is in fact of the message.
Signatures are not use to encrypt - they are used to verify that nothing has changed during transit.(1 vote)
- At1:48, Alice generates the signing key and the verification key. Is this analogous to a user deciding a on a secret password, then transforming it through a function to produce a public key? Does this mean that there is a chance that more than one person can come up with the same signing key through random chance alone? I guess it is also possible for people with the same name to have the same physical signatures... But for digital signatures, is there a way to distinguish people with the same signing keys?(1 vote)
- Yes. The way it works is your computer will randomly generate a private key and then use that to figure out the public key. And while it is possible that two people can have the same key, it is incredibly unlikely. There are 2^160 public keys, or 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976. That large number is enough to prevent any collisions.(2 votes)
- How is the verification key delivered to safely to the recipient? Is it sent with the message or is somewhere online?(1 vote)
- This may sound trivial, but at about4:12shouldn't the Sm as the signature really be Sk? To me, the way it's drawn implies you must first sign the message with Sk, then use your signed message to sign another message, but this time also include the public verification key? Thanks.(1 vote)
- No. Sk is your private signing key, which you don't want to sign your message with. The private key must remain private. Sm is the digital signature, which is what you actually sign your message with. It is the result of hashing together the private key (Sk) and the message (M).
Then, someone else can use the message (M), the digital signature (Sm), and the public verification key (Vk) in order to verify that the person who sent that transaction knew the private key.(2 votes)
Voiceover: A digital signature is basically the mathematical mechanism for essentially combining a public sequence of numbers with a given digital message, and you can really think of a digital signature in many ways as the electronic analog of a physical signature. In a physical signature, you'll typically affix, let's say, a sequence of characters representing your name or identity to a document. This process effectively binds your identity to that document and more so by formulating the characters in your name, and maybe some particular to unique or peculiar way that's unique to you. The hope is that nobody will be able to forge your name on that document. Now in a digital signature scheme, it turns out you can achieve these kinds of properties mathematically. Now, some of the more well-known digital signature schemes include things like the RSA digital signature scheme, which stands for the Rivest-Shamir-Adleman scheme. There's also a scheme known as DSS, which is the digital signature standard, actually. And, actually, if you were to use a scheme like RSA or DSS, in my mind, it's actually a lot harder to forge these digital signatures than it is to forge a handwritten signature. So in this particular video, I'll try to describe the overall higher-level mechanics, if you will, of a digital signature scheme, but I won't actually go into or describe the underlying mathematical details of, let's say, a specific scheme like RSA or DSS, at least not in this video. The way that a digital signature scheme works is let's say you have a user, and I'm going to call her Alice, and let's say Alice wants to, digitally sign a document. In the scheme, in a digital signature scheme, Alice is going to first generate two keys, and these two keys are known as the signing key, the signing key, which is a private key, so I'm going to use red to denote it, and we'll abbreviate the signing key as SK. And then Alice is also going to generate a separate key known as a verification key. Now the actual process of coming up with a signing key and a verification key kind of happens concurrently. Alice will generate these two keys at the same time, and they're going to have a mathematical relationship but the interesting thing is that you want it to be the case that the verification key is public, and the signing key will be private but more so, in a digital signature scheme, it should be hard to come up with the verification key, or rather, it should be hard to come up with the signing key, rather, if you only see the verification key. Now, let's consider what a digital signature on a message will entail. So basically, if you have a message, and let's call this message M, and you wish to digitally sign that message. What you're going to basically do is apply a mathematical transformation, Alice is going to apply a mathematical transformation to the message M and her signing key SK, and the result of that transformation, the output of that transformation will be a special sequence of numbers that we call the signature. The signature on the message M. Now, the interesting thing here is that the signature basically is one that is derived from a combination of the message M together with the signing key, the private signing key of Alice, and it's going to effectively produce a short, a relatively short sequence of numbers as an output. In particular, digital signature schemes should be designed, or they typically are designed so that only the person who possesses the signing key, that private signing key is capable of generating this type of an output, this type of a signature, S of M on the message M. Now, the verification process is kind of analogous to the signing process, but it involves the public verification key. So in the verification process, you actually have three different inputs, so the first input will be the message that you want to verify the signature of. You also need in addition to the message, you need to get as input the signature on that message. What does that S of M look like, and then finally, the input, the final input to the verification scheme will be the public key, the public verification key that belongs to Alice. These three inputs are put in, and there's a mathematical transformation that's applied to these inputs, and basically what that mathematical transformation is trying to ascertain or to check is that the signature that you see corresponding with the message M is one that would have been produced by Alice's private signing key. And this private signing key, in turn, corresponds to Alice's public verification key. Now, what I think is really remarkable is that you can actually carry out this process with just the verification key, that you don't actually need the signing key to validate the digital signature. You don't even need it inadvertently or indirectly. You can do everything. you can verify everything with knowledge of only the public verification key. And the verification procedure basically outputs kind of a yes or no. It tells you, "Should I accept the signature, "or should I reject it?" It's a basic validation procedure. And so, as you can see, the process of signing effectively will bind this public verification key. It binds the public verification key to Alice, somehow, because Alice is the one who published this verification key and told the whole world, "Hey, this is my verification key in the system, "and only I will be able to sign messages "that will be considered valid "with respect to that verification key." Because the message is now being essentially bound to this public key, and if you think of the public key as an identifier of sorts, maybe and identifier for Alice, then you can think of digital signing as a process that basically binds an identity to an underlying message, and that really gives us, in the mathematical sense, it gives us the analog of a traditional handwritten signature. Now, I want to make two remarks, and I think they're particularly relevant. First of all, you'll notice that the transformation that produces the actual digital signature itself, this transformation right here that produces S of M, this transformation basically takes the message. It takes the message as one of its inputs, and what that means is that the signature is dependent on the message. If you change the message, you'll get a different signature. Now, in this sense, a digital signature is actually different from a traditional handwritten signature. Your handwritten signature probably doesn't change. It more or less stays the same regardless of what it is you're signing. But your digital signature is very sensitive to what you're signing, and it will vary depending on what you sign. If you sign a different message, you'll get a different signature as an output. The second remark I want to make is that digital signatures are often associated with a cryptographic hash function, and I've already done a video on cryptographic hash functions, and, in fact, I mention in that video, and I'll reiterate here that the first cryptographic hash functions were actually designed specifically with digital signatures in mind as their killer application, if you will. So, in particular, what typically happens is that before you actually sign an arbitrary message, let's say you have a huge message here that you want to sign. Before you sign this message, you're going to basically apply a cryptographic hash function to that message and you're going to get an output from that function, that cryptographic hash function, you'll get a shorter output, the digest of that cryptographic hash function, and then what you do in a signing algorithm is that rather than signing the original message, you will first hash it and then sign the hash of the message. You'll sign the resulting digest instead of the original message. This two-step paradigm of doing kind of hashing and then signing, really ends up simplifying the process of digital signing since you effectively are no longer dealing with an arbitrary length input, but instead, you're working with a fixed-length quantity. And this hashing sign paradigm actually is safe as long as it's hard to find two messages that map to the same output under the application of the hash function. In other words, you can't come up with two messages that are different, but whose output when the hash function is applied to them are identical. In other words, the hash function, as long as it's collision resistant, it will result in a secure signature scheme for this hash and sign paradigm. Okay, now you can probably think about this for a moment, but if you could find, let's say, two input messages that are distinct and that map to the same output under an application of the hash function, that would, in fact, lead to some bizarre problems because a signature on the first message would then be identical to a signature on the second message since in both cases, what you're doing is you're not signing the actual message. You're signing the hash of the message. So, if the hashes are identical, you'll end up with the identical signature on two different messages, and that could create problems like making it easy for maybe a particular message to be forged under this digital signature approach, and that's obviously something that you don't want. you don't want someone to be able to come up with a signature on a different message, as opposed to maybe the one that you initially intended to sign. Now, it is possible, and I just want to make this clear, it's possible to describe digital signatures with a lot more mathematical formalism, but my hope with this video really was to give you a flavor, if you will, without drilling into all of the underlying nuances in mathematics.