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?


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

  • $\begingroup$ Okay, so is $H(m)$ available to the receiver to compare? $\endgroup$ – john doe Oct 16 '17 at 14:10
  • $\begingroup$ @johndoe yes, the verifier knows how to compute $H$ and the message $m$ is given to the verifier, so $H(m)$ is easily obtained for comparison. $\endgroup$ – SEJPM Oct 16 '17 at 14:11
  • $\begingroup$ But if m is given to the verifier, if it is intercepted by some man-in-the-middle, it will ead to information leak? $\endgroup$ – john doe Oct 16 '17 at 14:14
  • $\begingroup$ @johndoe yes, signature algorithms do not hide the message. If you want to hide the message, you have to wrap the message and the signature into an encryption. $\endgroup$ – SEJPM Oct 16 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.