[Top] [All Lists]

Re: Why Rabin algorithm has mostly been ignored?

1997-11-22 18:23:08
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 
(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

<Prev in Thread] Current Thread [Next in Thread>