Section 5.1 Introduction to digital signatures
We now look at an application of cryptographic ideas to digital signatures, a method for verifying that digital information comes from the correct source. The basic idea is that a source provides a document \(D\) and a signature \(D^{sig}\) generated with a private key \(k_{priv}\) to a user. The user should be able to use \(D, D^{sig}\) as well as a key \(k_{pub}\) to calculate if the file comes from a valid source.
A scheme like this has issues that need to be addressed.
- Given \(k_{pub}\text{,}\) it must be hard to find a \(k_{priv}\) that produces the same signature.
- Given \(k_{pub}\) and a list \((D_1, D_1^{sig}), \ldots, (D_n, D_n^{sig})\) it should be hard to construct a signature \(D^{sig}\) for a document \(D\) not in the list.
- Most documents are way too large to be signed. So instead, typically we apply signature algorithms to hashes of documents.
Hash functions will be treated in a later section. For now, think of a hash function \(H\) as an operation that takes documents and produces fingerprints that represent the documents. The fingerprints are numbers of a fixed size -- say 256-bit. The basic idea of a hash function is that it is “one-way”: that is, easy to compute and hard to reverse, in the sense that it is extremely difficult to find two inputs that produce the same output. Typical hash functions include \(MD5 (broken), SHA-1 (broken), SHA-2, \ldots\)
Algorithm 5.1.1.
- A signer Sam takes a document \(D\) and applies a hash function to it, getting \(D_H = H(D)\text{.}\)
- Using a private key, Sam applies a signing algorithm to get a signature \(D_H^{sig}\text{.}\)
- Sam provides the document \(D\text{,}\) the signature \(D_H^{sig}\text{,}\) and a public key \(k_{pub}\text{.}\)
- The verifier Vera wants to verify the document. She first computes \(D_H\) using the hash function \(H\text{.}\)
- Vera uses a verification algorithm applied to \(D_H, D_H^{sig}, k_{pub}\text{.}\) If the signature is valid, she gets a result of TRUE. If the signature is not valid, she gets a result of FALSE.
In the next sections we'll discuss how the discrete log problem in \(\F_p\) and the Elgamal encrpytion scheme sits underneath the Digital Signature Algorithm, one of the signing schemes in common use.