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.