Buying A Ticket With Privacy — using the ElGamal Method

With the ever increasing number of breaches, we are moving to a world where companies should not hold any personally sensitive information…
Photo by Dylan Mullins on Unsplash

Buying A Ticket With Privacy — using the ElGamal Method

With the ever increasing number of data breaches, we are moving to a world where companies should not hold any personally sensitive information, as it is just too risky. So how could we create a trustworthy system, where someone can show up with a ticket, and where we can trust it, without actually revealing any personal information about where the person has booked their seat?

So how can we generate a receipt of the booking, but not give away your identity, or the details of the booking? Let’s take an example of booking a seat in a theatre at the festival, and how your privacy can be respected, but where the theatre will trust the ticket.

Booking a ticket

Let’s say there are 100 seats in a theatre, and I want to book one of them, but I don’t want the theatre company to know which seat I’ve booked, or my identity. I also want a receipt of purchase that they can verify my booking. One way would be to get a trusted agent to look after the bookings, but I don’t trust them either. So how can we do this?

Well it can be done with commutative encryption.

The steps would be:

  • Initially the theatre company generates 100 receipts for each of the seats, and then encrypts them with its public key.
  • Next when I want to make a booking they send me the encrypted receipts that they have left, and I select one at random, and then encrypt it with my public key.
  • I send them all back, including the one I’ve encrypted.
  • The theatre checks to see which one has been changed, and then decrypts it with its private key, and sends it back to me.
  • I decrypt with my private key, and I can now view the receipt for my booking, and the theater company cannot determine which seat I have, but I will have the receipt of my booking.

So here is an example where the theatre encrypts all the seats with its key, the person then selects one, and encrypts with their key, and sends them all back again. Then the theater decrypts the one that has changed, and sends it back for the person to decrypt, and we have a booking. The theatre thus does not know who has booked the seat:

Commutative encryption

All this is made possible with commutative encryption and where we can encrypt and decrypt in any order. commutative encryption allows us to decrypt in any order. For this we can use the ElGamal public key encryption method [1]:

With ElGamal encryption Bob creates a random value (x) as his private key, and then computes his public key with:

His public key is then (Y, g, p) and his private key is x. If Alice wants to encrypt data for Bob, she takes a message (M) and a random nonce (k), and computes two values:

She can then send these values to Bob, and who will then use his private key (x) to discover the message:

This is practically implemented here.

Commutative Encryption

Now, let’s use the ElGamal encryption method to implement communative encryption [2][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)

If we allow Bob to decrypt first, he can take his key off with:

and then Alice can recover the message with:

Decryption (Alice then Bob)

If we allow Alice to decrypt first, she can take her key off with:

and then Bob can recover the message with:

Coding

Now, let’s code the modified ElGamal method with Python [here]. The only tricky bit is to implement the division part — and which we go with an inverse mod operation, and then just multiply the value:

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

How it would work …

The theatre (Alice) will encrypt all the tickets with her public key, and where Bob can then select the ticket that he wants, and then add his public key to that ticket. He passes this back, and Alice removes her public key (using her private key), and sends the ticket back to Bob, who then decrypts with his private key. Alice then marks the ticket as being sold:

Conclusions

So, happy, that Tahir ElGamal is coming to talk to our students this week, and I hope his work will inspire a whole new generation to believe in the power of public key encryption to change our flawed digital world.

If you want to implement the method I have outlined, it is here:

https://asecuritysite.com/elgamal/el_comm

References

[1] ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4), 469–472.

[2] 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.