The Rabin-Williams cryptosystem

The RSA public key cryptosystem, as you know, derives its security from the difficulty of factoring large numbers. However, it’s still an open question whether the only way to break RSA is by factoring. Soon after the publication of the RSA system, Michael Rabin produced his own public key cryptosystem, the breaking of which is as provably hard as factoring. His original paper can be seen here. Briefly, it works as follows:

The private key consists of two large primes p and q, and the public key is their product N=pq. Messages are integers m<N. Encryption is by a single squaring:


Decryption is performed by finding the square roots of c modulo the individual prime factors p and q, and putting the results together with the Chinese remainder theorem. If both p and q are equal to 3 modulo 4, finding square roots is easy, and the decryption takes these steps:

  1. Compute c_p=c^{(p+1)/4}bmod{p} and c_q=c^{(q+1)/4}bmod{q}
  2. If s,t are such that sp+tq=1 then the four square roots are

    pm spc_qpm tqc_pbmod{N}.

This “four-to-one” aspect of the cryptosystem has been detrimental to its uptake, although in practice that’s not a problem. If some redundancy is built into – or added to – the original message, such as repeating bits or digits, then it will be possible to determine which of the square roots is the correct one.

Another problem with Rabin’s cryptosystem is that it is vulnerable to a chosen-ciphertext attack. If all the square roots s_1,s_2,s_3,s_4=pm spc_qpm tqc_pbmod{N} are known, then the computation of all possible gcd(s_i-s_j,N) will reveal the factors of N, and thus break the system.

To address these issue, Hugh Williams developed a version of this system which is one-one. To define it, we need to remind ourselves of the Legendre and Jacobi symbols. If p>2 is a prime then the Legendre symbol


is defined to be equal to:

{ }phantom{-}1 if abmod{p} is a quadratic residue of p,

-1 if abmod{p} is a quadratic non-residue of p, and

{ }phantom{-}0 if a=0bmod{p}.

The Jacobi symbol is a generalisation of the Legendre symbol for odd composite numbers: if n=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k} then the Jacobi symbol is defined as

displaystyle{left(frac{a}{n}right)= left(frac{a}{p_1}right)^{!a_1}left(frac{a}{p_2}right)^{!a_2}cdots left(frac{a}{p_k}right)^{!a_k}}

Now for the cryptosystem.

The private key consists of two primes p and q, chosen so that




and the public key, as before, is their product N=pq. The message space (all allowable messages) is not all numbers less than N, as for Rabin, but is restricted to be those values M for which 2(2M+1)<N when


and for which 4(2M+1)<N when


If we forget about the Jacobi values for the moment, we see that if 4(2M+1)<N, or that if M<N/8-1 then M is a legitimate message.

Encryption is performed in two steps:

  1. For the message M, determine the value of the Jacobi symbol


    If this is equal to 1, then set E_1=4(2M+1); if -1 then set E_1=2(2M+1). Note that even though our definition of the Jacobi symbol was defined in terms of the factorisation of N, it can in fact be computed by an efficient algorithm similar in style to Euclid’s algorithm for greatest common divisor, which does not require knowledge of the factorization of N.

  2. Set C=E_1^2pmod{N}. This value C is the ciphertext.

Decryption also takes two steps:

  1. Compute D_1=C^dpmod{N} where

    d=((p-1)(q-1)/4+1)/2. By definition of p and q, this value will be an integer.

  2. Then:

    M=(D_1/4-1)/2 if D_1=0pmod{4},

    M=((N-D_1)/4-1)/2 if D_1=1pmod{4},

    M=(D_1/2-1)/2 if D_1=2pmod{4},

    M=((N-D_1/2-1)/2 if D_1=3pmod{4}.

It is not hard to show that decryption does in fact return the original message; see for example Stewart Wagstaff’s book Cryptanalysis of Number Theoretic Ciphers.

For a quick experiment, we can use these simple Sage programs (note that Sage does not implement the Jacobi symbol as such, but it does implement the Kronecker symbol which is an extension to even composite numbers, and which includes the Jacobi symbol as a special case). First encryption:

def rwe(M,n):
    if kronecker_symbol(2*M+1,n)==1:
        if 4*(2*M+1)&lt;n:
            return (4*(2*M+1))^2%n
            print &quot;ERROR: not an allowed plaintext&quot;
        if 2*(2*M+1)&lt;n:
            return (2*(2*M+1))^2%n
            print &quot;ERROR: not an allowed plaintext&quot;

and decryption:

def rwd(C,p,q):
    d = ((p-1)*(q-1)/4+1)/2
    L = power_mod(C,int(d),p*q)
    return cases[L%4]

And now for a little test run. First we need to choose appropriate primes:

sage: while true:
....:    p=next_prime(randint(10^10,10^11-1))
....:    if p%8==3:
....:        print p;break

sage: while true:
....:    q=next_prime(randint(10^10,10^11-1))
....:    if q%8==7:
....:        print q;break

Then choose a message, encrypt it, and decrypt the ciphertext:

sage: N=p*q
sage: M=10^20
sage: C=rwe(M,N);C
sage: rwd(C,p,q)

And there ya go!

One thought on “The Rabin-Williams cryptosystem

Leave a Reply

Your email address will not be published. Required fields are marked *