How can a digital signature provide proof the authenticity (not integrity!) of a file?


First of all, authenticity and integrity are related especially when it comes to cryptography. The reason is simple: if an attacker can alter the file - void the data integrity - then the file is obviously not authentic / original anymore. Note that data integrity does not disallow replacing the signed file by another file signed with the same private key.

It is required to verify that the signature and file match to provide authenticity. The verification procedure most show that the signature was created by the entity that that was supposed to have signed the file. Usually asymmetric cryptography is used for this, where a key pair is generated by the signing party. The private key is kept by the signing party and the public key can be distributed to parties that need to perform verification.

The private key an be used to perform signature generation over the file. The public key can be used to verify that the file was signed by that particular private key because the public key and private key are mathematically related to each other. Generally the signature generation and verification both have to use a cryptographic hash over the file to calculate a statically sized, computationally unique value to represent the file; this unique hash is used in signature generation and verification rather than the file itself.

The verification shows that the file must have been signed using the private key that is part of the key pair. It is however of vital importance that the public key is trusted to belong to the private key of a particular party. Otherwise an adversary could simply substitute their own key pair and substitute both the public key and signature values. In other words, the signature value can only be trusted once the public key is trusted.

Note that cryptographers generally talk about message authentication. A file is just a persistently and sequentially stored message with a particular name. In cryptography a message can consist of any ordered amount of bits. We don't care how the bits are presented during signature generation / verification, as long as they are present when required.

  • 1
    $\begingroup$ “ if an attacker can alter the file - void the integrity - then the file is obviously not authentic / original anymore” — no, not necessarily. If there are two versions of the file, for example, the attacker can substitute one for the other. Both versions are authentic, yet this is an integrity violation. On the other hand, integrity does imply authenticity, because if it's impossible to alter the authentic copy then this copy remains authentic. $\endgroup$ – Gilles 'SO- stop being evil' Oct 21 '18 at 10:17
  • $\begingroup$ That seems to be more an issue of identification of the document in question. If that would be considered "integrity" then none of the schemes offering integrity and authentication would actually do so. That cannot be right, so your definition of integrity seems to go beyond the usual one considered for e.g. authenticated ciphers, i.e. integrity of a single message. Possibly there are other examples, but this ones seems to fail the usual definition. That all said, it is of vital importance to keep in mind that substituting a file with another one is a possible scenario. $\endgroup$ – Maarten Bodewes Oct 21 '18 at 15:33
  • $\begingroup$ In the terminology I'm used to, the most common way to ensure the integrity of a message is to store or transmit its hash securely. This protects against substituting one file for another. The second-most common way is to couple a MAC or signature to authenticate the message, with a nonce (e.g. session nonce plus message index, or version number) to protect against substitution, replay or rollback. I don't see what's unusual here. $\endgroup$ – Gilles 'SO- stop being evil' Oct 21 '18 at 19:02
  • $\begingroup$ I've changed it to data integrity and explained the above. The term data integrity is also present for e.g. MAC algorithms, so that should be correct. $\endgroup$ – Maarten Bodewes Oct 21 '18 at 22:22

Your paper signature is almost unique so that when you sign a paper, authorities can verify your signature from your previous signatures.

The digital signature started with the public key encryption. In which, everybody with the knowledge of your public key $k_{pub}$, can send you an encrypted message that only be decrypted by you. To begin with, you must generate your keys and distribute your public key through public servers, or see.

In public key cryptography, a message encrypted with a public key, only the related private key $k_{priv}$ owner can decrypt the message. With the following relation;

$$ Dec(k_{priv}, Enc(k_{pub}, m)) = m$$

So, question if, what will happen if you encrypt the message with your private key? Everybody can use your public key to see the message. In short, this is a digital signature. Only you can encrypt with the $k_{priv}$ and everybody can verify with $k_{pub}$

$$ Sign(m) = Enc(k_{priv}, m)$$

$$ Verify(Sign(m)) = Dec_{k_{pub}}(Enc(k_{priv}, m))$$

If the $ Verify(Sign(m)) = m$, than the digital signature is verified.

This is, in a true sense, a textbook definition of the digital signature. As Maarten gave in the comment, RSA Encryption is not the same as signature generation. The padding schemes are different, see PKCS#1.

"How forgery is not possible" so that one can digitally sign a message to forge your signature. If we assume that the underlying mathematical problems hard and your $k_{priv}$ is secured by you, then a forgery can possible if attacker either finds a weakness in the protocol or in the mathematical problem or steal your key.

If you stick to the standards as RSA-PSS ECDSA DSS and follow the recommendations you will be safe.

And, see the Maarten's answer for the other nice details.

  • 2
    $\begingroup$ Sorry, I have voted this down because signature generation is not encryption with the private key. $\endgroup$ – Maarten Bodewes Oct 20 '18 at 13:10
  • $\begingroup$ The original hash is not retrieved when performing (EC)DSA signature verification. The recalculated hash is used as input to the signature verification process. So the comparison as written in the answer is not carried out (sorry, made a mistake in the deleted comment, not trying to spam you). $\endgroup$ – Maarten Bodewes Oct 20 '18 at 13:54
  • $\begingroup$ @MaartenBodewes, It is always better to show the mistake(s) than ignore them. You are completely right. I wanted to give a text-book definition. $\endgroup$ – kelalaka Oct 20 '18 at 22:56
  • 2
    $\begingroup$ I guess that this is the way that it is present in many textbooks unfortunately you then have to unlearn that you cannot actually encrypt with a private key. There are plenty of instances where we get people making that mistake (and yes, in the early days we had the same discussions at the company where I started my journey into crypto for real). This is why I'm completely against simplifying signature schemes as hash-then-encrypt - and it is the reason why I wrote up that Q/A in the first place. $\endgroup$ – Maarten Bodewes Oct 20 '18 at 23:05
  • $\begingroup$ There is now at least the warning that it is not actually encryption, so that's enough to take away the main concern. I'd still rather not see an example without $Enc$ and $Dec$ but I know that describing the signature process is tricky without it. $\endgroup$ – Maarten Bodewes Oct 20 '18 at 23:28

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.