Next: Footnote from the parallel
Up: A Whirlwind Tour of
Previous: One way and collision-free
Is there a functional equivalent to a handwritten signature for
a digital document?
Should be:
- easy for a legitimate signer to create
- hard for anyone else to create
- easy for anyone to verify the signature
- dependent on the message and the signer (or his key)
Definition A digital signature scheme consists of:
- a set of possible messages M
- a set of possible signatures S
- for each entity A, a signing function SA:M -> S,
- for each entity A, a verification function VA: S x M -> {0,1}
Example (RSA)
A user A chooses a pair of primes p,q, and
publishes n=pq, keeping p and q secret. He also chooses d
with gcd(d,phi(n))=1, and computes e with ed=1 (mod phi(n)).
He then publishes e and keeps d secret.
Take M =S =Z/nZ, and define
Note that e and n are public, so anyone can compute VA, but
we hope that only A can compute SA.
In practice, we replace m by h(m) where h is a strongly collision
free function.
Kevin McCurley
1/23/1998