Before Elliptic Curve Became King of the Hill, Cramer-Shoup Looked Like a Winner

In 1998, Bruce Schierner wrote a blog on the Cramer-Shoup public key encryption method [here]:

Before Elliptic Curve Became King of the Hill, Cramer-Shoup Looked Like a Winner

In 1998, Bruce Schierner wrote a blog on the Cramer-Shoup public key encryption method [here]:

Bruce wrote:

Cramer-Shoup is good work and a good academic paper. The results are suprising: provable security against adaptive chosen ciphertexts and only twice as slow and four times the data expansion. But the proofs are based on something called the Diffie-Hellman Decision Problem (not the Diffie-Hellman Problem), which is much weaker.

And:

The news was glowing, and predicted that this new algorithm would replace SSL, save the Internet, and cure cancer. Hype was everywhere, and facts were few

But time has shown the RSA continued it domiance, and Elliptic Curve has since taken over to be the King of the Hill (and even taking over SSL for its default key exchange — ECDH).

So what was it: Cramer-Shoup is a public key encryption method that is an extension to ElGamal but adds a one-way hashing method which protects against an adaptive chosen ciphertext attack. The following shows the basic key generation, encryption and decryption parts.

Key generation:

  • Alice generates two random generators in the range 1 to p-1 (g1,g2).
  • Alice select five random values ( x1,x2,y1,y2,z)
  • Alice computes c=g^x1 g^x2, d=g^y1g^y2, h=g^z1
  • Alice publishes (c,d,h), and shares g1,g2,p. She keeps (x1,x2,y1,y2,z) secret.

Encryption:

  • Bob creates a message (m) and uses Alice’s public key.
  • Bob creates a random number (k).
  • Bob calculates u1=g^k1,u2=g^k2
  • Bob calculates e=h^k m

Decryption:

  • Alice decrypts with m=e/(u^z1).

The following outlines some simple code [here]:

import random
import sys
p=67
g1=34
g2=41
m=3
#Safe generators are Selecting G for  67: 
#2   7   11   12   13   18   20   28   31   32   34   41   44   46   
#48   50   51   57   61   63  	
if (len(sys.argv)>1):
	m=int(sys.argv[1])
print 'Alice calculates:'
x1= random.randint(3, 12)
x2= random.randint(3, 12)
y1= random.randint(3, 12)
y2= random.randint(3, 12)
z= random.randint(3, 12)
c = ((g1**x1)*(g2**x2)) % p
d = ((g1**y1)*(g2**y2)) % p
h =  ((g1**z)) % p
print 'g1=',g1
print 'g2=',g2
print 'c=',c
print 'd=',d
print 'h=',h
print 'Alice sends c,d,h'
print 

k= random.randint(3, 12)
u1= (g1**k) % p
u2= (g2**k) % p
e= ((h**k)*m)  % p
print 'Bob calculates:'
print 'k=',k
print 'u1=',u1
print 'u2=',u2
print 'e=',e
print 
#m_rec = e/(u1**z)
m_rec = ((u1**(p-1-z))*e) % p
print '----'
print 'Message sent: ',m
print 'Message received: ',m_rec

A sample run is:

Alice selects:
g1= 34 , g2= 41
Alice creates random numbers:
x1= 4 , x2= 4 , y1= 4 , y2= 7
z= 6
Alice calculates:
c= 19 , d= 51 , h= 22
Alice sends c,d,h
Bob creates a random number:
k= 10
Bob calculates:
u1= 60 , u2= 4 , e= 64
— — 
Message sent: 1
Message received: 1

And there’s the magic!