Quickly checking signatures

[Hal <hfinney@shell.portal.com>]

Let me describe Shamir's method for quickly doing a probabilistic signature
check.  Since this was a rump session paper he didn't have it written up.

Shamir uses a variation of the Rabin system.  The Rabin encryption
system is similar to RSA, but instead of exponents which are relatively
prime to the predecessors of the factors of the modulus, the exponent
used is 2.  This requires somewhat different techniques.

A message M is encrypted by doing M^2 mod n.  The decryption is then
done by taking the modular square root.  There are a few technical
hitches that occur here but nothing major.  Similarly a message M is
signed by calculating its modular square root S such that S^2 = M mod n.
Note that with Rabin you can't just sign any arbitrary number as that
may allow the factors to be revealed.  However this is not a major problem
because practical systems in use today sign specially padded hashes,
not arbitrary numbers.

Now Shamir uses a slight modification to this.  Normally we have:

	S^2 = M mod n

This can be written as:

	S^2 = M + C*n

for some C, which is simply the definition of modular equality.  Now,
what he suggests is that instead of sending S as the signature of M, you
send C.  This is justified on 3 grounds:

	- C is the same size as S
	- C has the same security as S (knowing M and n you can derive C
	  from S and vice versa)
	_ C and S are equally easy to generate

However, by sending C as the signature of a message M it allows a fast
screening to be done.  The idea is that the message should be accepted if
M+C*n is a perfect square (because then S can be derived as the normal
square root - that is how you get S from C as mentioned above).  And this
is something that can be checked quickly.

In number theory there is a notion of a "quadratic residue" modulo some
number.  If a number is a quadratic residue that simply means that it has
a square root, that it is the square of some other number using the
modulus.  With a prime modulus half of the numbers are quadratic residues
and half are not.  For example, with modulus 7 the q.r.'s are 1, 2 and 4
and the non q.r.'s are 3, 5, and 6.  It turns out that testing whether a
number x is a quadratic residue modulo a prime p can be done by
calculating x^((p-1)/2) mod p.  This will be 1 if and only if x is a q.r.

Now, the key idea is this: if a number is a perfect square then the
result of taking that number modulo a prime must be a quadratic residue.
This means that we can quickly determine that C is a perfect square by
checking whether C mod p for various random small primes p is a quadratic
residue.

By picking p to be a single precision prime of say 16 bits, the q.r.
calculation can all be done without using multiple precision arithmetic
and so it will be very fast compared to actually checking a signature.

So, the procedure for the check is as follows: given n, M and C, choose a
small prime p and calculate M+C*n mod p.  Then raise this to the (p-1)/2
power mod p and see if the answer is 1.  If it is, we give a
"provisional" acceptance to the signature.  If it is not, we reject the
signature; it cannot be valid.  This test may be repeated a few times
with different values of p to improve the rejection of bad signatures.
Once we have taken the input numbers mod p the rest of the arithmetic can
be done with ordinary single precision integer variables.

(One thing I overlooked is the possibility that M+C*n will be a multiple
of p.  In that case M+C*n mod p will be 0 and this is a provisional pass.)

Of course checking the signature the old-fashioned way just takes a
single multi precision multiplication, which won't be all that slow.
So this puts a limit on the number of p's you can check this fast
way before it becomes slower.  Also, you'd have to choose the primes at
random as otherwise an attacker who knew your p's could conjure up a C
which would produce a quadratic residue for some small number of known
p's.

Hal