What exactly is a digital signature?

Question

I am aware of basics of public key encryption algorithms , for eg. RSA. If A wants to send a message to B, A uses the public key of B to encrypt the message A wants to send to B, and only B can decrypt the message using his private key.

What I don't understand is that what exactly is the digital signature, if for eg. A is sending an email to B? Is it the email id? The message that A wanted to send to B? IP address? Is it a random text or string? If it's random, how does B know it was A who sent it?

Answer 1

$\newcommand{opn}{\operatorname}$ Formally, a digital signature scheme is a triple of algorithms $(\opn{KeyGen},\opn{Sign},\opn{Verify})$ where the first two are probabilistic and the last is deterministic such that the following logical statement holds except in a negligible amount of cases: $$\forall \lambda\in\mathbb N:\forall (pk,sk)\gets \opn{KeyGen}(1^\lambda):\forall m\in\mathcal M:\opn{Verify}(pk,m,\opn{Sign}(sk,m))=1$$

That is, by its very definition, the receiver can verify the signature of a message using a public key associated to a specific private key. If you are looking for standard security definitions, have a look here.

So, how can we instantiate these triples? As you already know RSA, I shall discuss this using RSA-Full Domain Hashing (RSA-FDH), which is conceptually the easiest, provably secure signature algorithm.

• $(pk,sk)\gets\opn{KeyGen}(1^\lambda)$, this is the non-deterministic algorithm, that given a security parameter $n$, returns a public ($pk$) and a private key ($sk$) for use with the cryptosystem. For RSA this would be $(n,e)$ as the public key, with $n$ having length $\lambda$-bits, as well as a note on which hash algorithm is to be used. The private key would be the public key with $d$ added.
• $\sigma\gets\opn{Sign}(sk,m)$, this is the (potentially) non-deterministic algorithm that given a secret key $sk$ and a message $m$, returns a signature $\sigma$. For RSA-FDH this would be $\sigma =H(m)^d\bmod n$ with $H:\{0,1\}^*\to\mathbb Z_n$ being essentially a hash function that outputs a hash as large as $n$. Practically one can use SHAKE128 (the arbitrary-length version of SHA3) here.
• $b=\opn{Verify}(pk,m,\sigma)$, this is the deterministic algorithm that given a public key $pk$, a message $m$ and an alleged signature $\sigma$ on $m$ decides whether $\sigma$ is indeed a valid signature, produced using the private key associated to the given public key on the given message. The result is a yes/no answer, encoded as 1/0 in $b$. For RSA-FDH this would be $\sigma^e\bmod n\stackrel{?}{=}H(m)$.

As for the correlation between a signature and a sender, assuming we have a trusted binding between the public key and the sender and assuming the sender hasn't leaked their private key, only they could potentially have created a valid signature for the given public key, meaning we can be sure this message is from them.