Commutative Encryption using a Modified ElGamal Method

Commutative Encryption using a Modified ElGamal Method

My first real interaction with cryptography was a PhD related to the usage of commutative encryption:

It used a derivative of the RSA method, and which is known as SRA. But, this method struggles with its security (as we need to keep the modulus secret).

And, so, this week the mighty Tahir ElGamal is coming to give a guest talk to our students, so let’s implement commutative encryption using the ElGamal method.

Commutative encryption with a modified ElGamal method

So, for this, I will use this paper [1][here]:

With commutative encryption, we can apply Bob’s public key to a message, then encrypt with Alice’s public key. We can then decrypt with Bob’s private key, and then Alice’s private key, or decrypt with Alice’s private key and then Bob’s public key. This differs from the normal encryption process, and where we would decrypt using the reverse of the application of the keys.

Key generation

Initially, Alice generates a private key of x_1 and a public key of:

Bob generates a private key of x_2 and a public key of:

Encryption

If we have a message (M), then Alice will encrypt with:

and:

Alice will pass c_21 to Bob, and who will create:

and:

The encrypted values are c11, c12 and c22.

Decryption (Bob then Alice)

To decrypt, Bob can take his key off with:

and then recover the message with:

Decryption (Alice then Bob)

To decrypt, Alice can take her key off with:

and then recover the message with:

Coding

The coding is [here]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import random
import libnum
import sys
import hashlib
    
def primitive_root(p_val: int) -> int:
    while True:
        g = random.randrange(3, p_val)
        if pow(g, 2, p_val) == 1:
            continue
        if pow(g, p_val, p_val) == 1:
            continue
        return g
    
bits=512
M="hello"
if (len(sys.argv)>1):
    M=sys.argv[1]
if (len(sys.argv)>2):
    bits=int(sys.argv[2])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
    
m = int.from_bytes(M.encode(),byteorder='big' ) 
        
g = primitive_root(p)  
x1 = random.randrange(3, p)  
Y1 = pow(g,x1,p)
x2 = random.randrange(3, p)  
Y2 = pow(g,x2,p)
r1=random.randrange(3, p)  
r2=random.randrange(3, p)  
print (f"Message:\nm={M}")
print (f"Bob's Public key: g={g}, Y={Y1}, p={p}\nBob's Private key: x={x1}, r1={r1}")
print (f"\nAlice's Public key: g={g}, Y={Y2}, p={p}\nAlice's Private key: x={x2}, r2={r2}")
c11=pow(g,r1,p)
c21=(pow(Y1,r1,p)*m) % p
c12=pow(g,r2,p)
c22=(pow(Y2,r2,p)*c21) % p
print (f"\nEncrypted\nc11={c11}\nc12={c12}\nc22={c22}\n")
print("First removing Alice's key then Bob's")
Alice_remove=(c22*libnum.invmod(pow(c12,x2,p),p)) % p
M_recovered=(Alice_remove*libnum.invmod(pow(c11,x1,p),p)) % p
m_rec= int.to_bytes(M_recovered,len(M),byteorder='big' ) 
print (f"\nResult: {m_rec.decode()}\n" )
print("First removing Bob's key then Alice's")
Bob_remove=(c22*libnum.invmod(pow(c11,x1,p),p)) % p
M_recovered=(Bob_remove*libnum.invmod(pow(c12,x2,p),p)) % p
m_rec= int.to_bytes(M_recovered,len(M),byteorder='big' ) 
print (f"\nResult: {m_rec.decode()}" )

A sample run for 80-bit primes [here]:

Message:
m=hello
Bob Public key: g=519160996672834189197519, Y=417750015375163083516967, p=782807293314142598778109
Bob Private key: x=10563390121140597427918, r1=239056617387655559337834
Alice Public key: g=519160996672834189197519, Y=179500691043752261889260, p=782807293314142598778109
Alice Private key: x=391602381004385515058281, r2=146527017737232627328209
Encrypted
c11=198485335807018340575441
c12=408062838808129045896002
c22=363755194689760736958184
First removing Alice key then Bob
Result: hello
First removing Bob key then Alice
Result: hello

Conclusions

Commutative encryption has so many applications, such as:

Reference

[1] Huang, K., & Tso, R. (2012, August). A commutative encryption scheme based on ElGamal encryption. In 2012 International Conference on Information Security and Intelligent Control (pp. 156–159). IEEE.