Digital Signature Schemes - Everyday Cryptography - page 233

algorithm and, from the results of this process, will need to be able to determine
whether the digital signature is valid. An important question to ask is: how will
the verifier know which data this digital signature matches?
This question is particularly relevant if the data being digitally signed has
no apparent recognisable structure (it could, for example, be an encrypted
cryptographic key). After all, the digital signature itself will hopefully not have any
apparent structure since it is the output of a cryptographic algorithm. This digital
signature could well have been modified by an attacker. When the verifier runs
the verification algorithm, the result that is output (assuming that this resembles
the underlying data) will also have no apparent structure. So how will the verifier
be able to determine whether the data that has been output is the correct data?
There are two different methods that are used to provide the verifier with this
assurance.
Send the verifier the data that is being digitally signed . Data that is digitally
signed is not, by default, confidential. Inmany situations it is acceptable to send
the data along with the digital signature. The verifier now verifies the digital
signature and is also able to see the data that was supposed to be digitally signed.
Digital signature schemes that use this technique are called digital signature
schemes with appendix because the data is sent with the digital signature as an
'appendix'.
Add redundancy to the data that is being signed . A more subtle technique is to
make the data that is being digitally signed 'recognisable' by adding redundancy
before computing the digital signature. In this case it now suffices to just send
the digital signature itself. On verification, the verifier will recover some data
from the digital signature. If this recovered data has the correct redundancy
format then the verifier will accept that data as being correct, otherwise they
will reject it. Digital signature schemes that use this technique are called digital
signature schemes with message recovery because the data can be 'recovered'
from the digital signature itself.
We will now look at examples of each of these two techniques. Both digital
signature schemes are based on RSA and, to an extent, on the naive digital
signature scheme that we proposed in Section 7.3.1. However, it is important
to recognise that RSA is rather special in this regard since the naive approach does
not generally work for arbitrary public-key cryptosystems.
7.3.4 RSA digital signature scheme with appendix
We require all signers and verifiers to agree on the use of a particular hash
function as part of this scheme. In the following we will deliberately use the terms
'encryption' and 'decryption' in quotes because, while they refer to applying the
RSA encryption and decryption algorithms, they do not refer to encryption and
decryption of data for confidentiality purposes.