Rabin Signature Algorithm - Modern Terminology

Modern Terminology

In modern presentations, the algorithm is often simplified as follows

The hash function H is assumed to be a random oracle and the algorithm works as follows

• Key Generation
  • The signer S chooses primes p,q each of size approximately k/2 bits, and computes the product
  • The public key is n
  • The private key is (p,q)

• Signing
  • To sign a message m the signer S picks random padding U and calculates H(mU)
  • If H(mU) is not a square modulo n, S picks a new pad U
  • S solves the equation
  • The signature on m is the pair (U,x)

• Verification
  • Given a message m and a signature (U,x) the verifier V calculates x2 and H(mU) and verifies that they are equal

In some treatments, the random pad U is eliminated and instead we add two numbers a and b to the public key with and where denotes the legendre symbol. Then for any r modulo n exactly one of the four numbers will be a square, and the signer chooses that one for his signature.