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.
Cramer-Shoup |
Outline
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 (\(g_1\) \(g_2\))
- Alice select five random values ( \(x_1 , x_2 , y_1 , y_2 , z\) )
- Alice computes \(c = g_1^{x_1}g_2^{x_2}\), \(d = g_1^{y_1} g_2^{y_2}\),\(h = g_1^z\)
- Alice publishes ( \(c , d , h\) ), and shares \(g_1,g_2,p\). She keeps (\(x_1,x_2,y_1,y_2,z\)) secret.
Encryption:
- Bob creates a message (m) and uses Alice's public key.
- Bob creates a random number (k).
- Bob calculates \(u_1=g_1^k,u_2=g_2^k\)
- Bob calculates \(e=h^k m\)
Decryption:
- Alice decrypts with \(m=e/({u}_{{1}}^{{z}})\).
The following outlines some simple code:
import random import sys p=67 g1=34 g2=41 m=10 #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= pow(g1,k, p) u2= pow(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)