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:
“That Calvinistic sense of Innate Depravity and Original Sin, from whose visitations, in some shape or another, no deeply thinking mind is always and wholly free. For, in certain moods, no man can weigh this world, without throwing in something, somehow like Original Sin, to strike the uneven balance.”
—Herman Melville (1819–1891)