Original Algorithm
The algorithm relies on a collision-resistant hash function
- Key Generation
- The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
- S then chooses a random b in .
- The public key is (n,b)
- The private key is (p,q)
- Signing
- To sign a message m the signer S picks random padding U and calculates H(mU)
- S then solves
- If there is no solution S picks a new pad U and tries again. If H is truly random the expected number of tries is 4.
- The signature on m is the pair (U,x)
- Verification
- Given a message m and a signature (U,x) the verifier V calculates x(x+b) and H(mU) and verifies that they are equal
Read more about this topic: Rabin Signature Algorithm
Famous quotes containing the word original:
“The history of literature—take the net result of Tiraboshi, Warton, or Schlegel,—is a sum of a very few ideas, and of very few original tales,—all the rest being variation of these.”
—Ralph Waldo Emerson (1803–1882)