Commutative Encryption with ElGamal Encryption[ElGamal Home][Home]
With commutative encryption, we can apply Bob's public key to a message, then 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 public key encryption process, and where we would decrypt using the reverse of the application of the keys.
|
Outline
With commutative encryption, we can apply Bob's public key to a message, then 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. So, for this, we will use this paper [1][here]:
Key generation
Initially, Alice generates a private key of \(x_1\) and a public key of:
\(Y_1=g^{x_1} \pmod p\)
Bob generates a private key of \(x_2\) and a public key of:
\(Y_2=g^{x_2} \pmod p\)
Encryption
If we have a message (\(M\)), then Alice will encrypt with:
\(c_{11} = g^{r_1} \pmod p\)
and:
\(c_{21} = M.Y_1^{r_1} \pmod p\)
Alice will pass \(c_{21}\) to Bob, and who will create:
\(c_{12} = g^{r_2} \pmod p\)
and:
\(c_{22} = c_{21}.Y_2^{r_2} \pmod p\)
The encrypted values are \(c_{11}\), \(c_{12}\) and \(c_{22}\).
Decryption (Bob then Alice)
To decrypt, Bob can take his key off with:
\(Enc_{Bob\_removed} = \frac{c_{22} } { {(C_{12})}^{x_2} }\)
and then recover the message with:
\(M_{recovered} = \frac{ Enc_{Bob\_removed} } { {(C_{11})}^{x_1} }\)
Decryption (Alice then Bob)
To decrypt, Alice can take her key off with:
\(Enc_{Alice\_removed} = \frac{c_{22} } { {(C_{11})}^{x_1} }\)
and then recover the message with:
\(M_{recovered} = \frac{ Enc_{Bob\_removed} } { {(C_{12})}^{x_2} }\)
Generalisation
The method is fairly simple, and where each person (\(i\)) divides the cipher by their value of:
\(c_i={(g^{r_i})}^{x_i}\)
and where \(x_i\) is the private key of person (\(i\)), and \(r_i\) is their random value.
Here is the generalisation:
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:
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
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.