Jon Callas wrote:
It's in there now. Obviously, there needs to be more discussion of what
kind of Rabin you want, straight Rabin, Williams's variants, or what.
Please bring this up on the list.
Jon, thanks for putting it in.
I think the Rabin algorithm may use the following specifics,
which can be found in "Handbook of Applied Cryptography" by
Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone.
1) In key generation, generate two primes p and q such that
p=3 mod 8 and q=7 mod 8. The public key is simply n=p*q and the
private key is p and q. Quantities a, b satisfying a*p+b*q=1
and d=(n-p-q+5)/8 may also be calculated at the stage of key
generation and stored as private key data (to simplify decryption
and signature generation calculations).
2) Encryption:
c=m**2 mod n.
Note: It is necessary to have some salt and redundancy in m.
Since m is at least 512 bits and the symetric key is something
around 128 bit, there is plenty of room to put redundancy and
salt in ESK. At this time, it is probably sufficient to specify
that the first octet of m signifies the salting and redundancy
scheme. (Redundancy will prevent the chosen ciphertext attack
mentioned by Hal Finney.)
3) Decryption:
compute the four square roots of c.
r=c**((p+1)/4) mod p
s=c**((q+1)/4) mod q
x=(a*p*s + b*q*r) mod n
y=(a*p*s - b*q*r) mod n
where a and b are intergers satisfying a*p+b*q=1.
Then use the redundancy information in m to determine which
of r,s,x,and y is the decrypted message m.
4) Signature generation:
(a) Compute m1=R(m) where R(m) is the redundancy function
specified by ISO/IEC-9796. Note: This ensures that m1=6 mod 16.
(b) Compute Jacobi symbol J=(m1,n).
(c) If J=1 then the signature is s=m1**d mod n.
(d) If J=-1 then the signature is s=(m1/2)**d mod n.
5) Signature verification:
(a) Compute m2=s**2 mod n.
(b) If m2=6 mod 8 take m1=m2.
(c) If m2=3 mod 8 take m1=2*m2.
(d) If m2=7 mod 8 take m1=n-m2.
(e) If m2=2 mod 8 take m1=2*(n-m2).
(f) Verify that m1 has the correct format specified in
ISO/IEC-9796.
(g) Recover signed message m=Rinv(m1), where Rinv is the
inverse function of R.
I think the above Rabin scheme is pretty neat. It does not
double the ciphertext as ElGamal does. It is extremely fast
in encryption and verification. Althogh the decryption and
signature generation is slightly more complicated than RSA,
the complication is not in the computation intensive part,
and therefore, does not affect the efficiency of the algorithm.
I have implemented the above algorithm without much difficulty
and found that the decryption and signature generation are
just as fast as RSA but the encryption and verification are
much faster.
The above may be the scheme you call "straight Rabin". we
probably should also reserve a number for Williams's variant,
which takes modular cube instead of modular square.
Gary Liu