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 and , and the public key is their product . Messages are integers . Encryption is by a single squaring:

.

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

1. Compute and
2. If are such that then the four square roots are

   

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 are known, then the computation of all possible will reveal the factors of , 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 is a prime then the Legendre symbol

is defined to be equal to:

if is a quadratic residue of ,

if is a quadratic non-residue of , and

if .

The Jacobi symbol is a generalisation of the Legendre symbol for odd composite numbers: if then the Jacobi symbol is defined as

Now for the cryptosystem.

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

and

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

and for which when

.

If we forget about the Jacobi values for the moment, we see that if , or that if then is a legitimate message.

Encryption is performed in two steps:

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

   .

   If this is equal to , then set ; if then set . Note that even though our definition of the Jacobi symbol was defined in terms of the factorisation of , 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 .

2. Set . This value is the ciphertext.

Decryption also takes two steps:

1. Compute where

   . By definition of and , this value will be an integer.

2. Then:

   if ,

   if ,

   if ,

   if .

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)<n:
            return (4*(2*M+1))^2%n
        else:
            print "ERROR: not an allowed plaintext"
    else:
        if 2*(2*M+1)<n:
            return (2*(2*M+1))^2%n
        else:
            print "ERROR: not an allowed plaintext"

and decryption:

def rwd(C,p,q):
    d = ((p-1)*(q-1)/4+1)/2
    L = power_mod(C,int(d),p*q)
    cases=[(L/4-1)/2,((p*q-L)/4-1)/2,(L/2-1)/2,((p*q-L)/2-1)/2]
    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
..........:         
30745157899

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

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

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

And there ya go!

About these ads