Rabin Signature Algorithm - Original Algorithm

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