Validating digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents.
A valid digital signature, where the prerequisites are satisfied, gives a recipient very strong reason to believe that the message was created by a known sender (authentication), and that the message was not altered in transit (integrity).
The Digital Signature Algorithm (DSA), developed by the National Institute of Standards and Technology, is one of many examples of a signing algorithm.
In the following discussion, 1 denotes that A has access to the oracle, S(sk, · ), Q denotes the set of the queries on S made by A, which knows the public key, pk, and the security parameter, n, and x ∉ Q denotes that the adversary may not directly query the string, x, on S.
To create a forgery, the attacker picks a random signature σ and uses the verification procedure to determine the message, m, corresponding to that signature.
In practice, however, this type of signature is not used directly, but rather, the message to be signed is first hashed to produce a short digest, that is then padded to larger width comparable to N, then signed with the reverse trapdoor function.
In 1976, Whitfield Diffie and Martin Hellman first described the notion of a digital signature scheme, although they only conjectured that such schemes existed based on functions that are trapdoor one-way permutations.
Universities including Penn State, University of Chicago, and Stanford are publishing electronic student transcripts with digital signatures.
Trapdoor permutations can be used for digital signature schemes, where computing the reverse direction with the secret key is required for signing, and computing the forward direction is used to verify signatures.
Used directly, this type of signature scheme is vulnerable to key-only existential forgery attack.
Several early signature schemes were of a similar type: they involve the use of a trapdoor permutation, such as the RSA function, or in the case of the Rabin signature scheme, computing square modulo composite, N.
A trapdoor permutation family is a family of permutations, specified by a parameter, that is easy to compute in the forward direction, but is difficult to compute in the reverse direction without already knowing the private key ("trapdoor").
The strongest notion of security, therefore, is security against existential forgery under an adaptive chosen message attack.