El Gamal and Diffie Hellman Similarities

No comments

 

In terms for public key algorithms this post is about DL problems with Diffie Hellman as a key exchange mechanism and EL Gamal as a method of encryption.

Service                          Algorithm Family  
  Integer Factor DL / Zp* DL /Elliptic curve
Key Exchange RSA DH Elliptic Curve Diffie Hellman
Digital Signature RSA El Gamal + DSA ECDSA
Encryption RSA El Gamal Elliptic Curve El Gamal Variant

 

There are an additional 4 families of algorithms that were proposed in the 1970’s and 1980’s, but these are impractical to use in practice because of large keys and the slowness of them, these post-quantum cryptography algorithms are being considered now because of the increase in processing device speed.

Encryption with the DL problem.

Goal: Develop an encryption scheme from the DH key exchange scheme.

DH result is used an input for AES, but we just want to look at the handshake and DL problem and not use of AES.

For DH Key exchanges:

We have Alice and Bob with a set of domain parameters α,p that is known to both parties.

  • Alice computes her key A= αa mod p
  • Bob computes his Key B = αb mod p

These keys are then exchanged and both sides computing their session key KAB

  • With Alice calculating Ba = αab = KAB mod p
  • And Bob calculating Ab = αab = KAB mod p
Step Alice <- α,p -> (Step 5 in EG) Bob
DH Key Exchange 1 A= αa mod p (Step 7 EG) A <- (Step 9 EG)
2 ß B B = αb mod p
3 Ba = αab = KAB mod p (Step 8 EG) Both parties have KAB Ab = αab = KAB mod p (Step 11 EG)
Encryption 4 Y = x.KAB mod p (Step 9 EG) Y ->
5 X = Y.KAB -1 mod p (Step 12 EG)

 

Now since both parties have the same key, we can use 3DES or AES to encrypt messages between them using mod 2. But more interestingly we can use multiplication to encrypt messages, by using your plaintext message and multiplying it with your secret key KAB.

When Alice wants to encrypt a message ‘x’ using multiplication, she gets the cypher text Y =  x.KAB mod p. When Bob wants retrieve the original message, he would need to find the inverse (divide) X = Y.KAB -1 mod p.

Now this scheme is essentially the same as El Gamal, you use DH to establish a session key, then encrypt using multiplication. The only difference is the terms and the sequence of events are reordered.

EG Problem

Now if we look at El Gamal (EG) the domain parameters α and p are not public but its originating from bob, as he is the receiver of the message. In public key cryptography we have the notion of the receiver of the message would need to set up public and private keys and publish the public key.

In order to come up with a DL problem, it’s always: αx = A mod p, where x is always the private key Kpr and A is always the public key Kpub.

As Bob is the receiver he chooses p and a primitive alpha, he then picks an element in p as his private key, and uses his private key and his primitive to compute his public key. He then sends or publish his public key, p and alpha to Alice. With DH we have α and p as domain parameters, but because Bob generated them he needs to inform Alice what these parameters are. This step is equivalent to the domain parameters in DH.

Alice now would also need to compute her keys, so she chooses i from the set of p where i e {2, 3, … p-2} and calculates the ephemeral key KE = αi mod p which is the same as Alice public key calculated in step 1 of DH. Now step 3 in DH is the next step where a session key is calculated, and the same is done in EG, this is just renamed as a masking key KM. Now since Alice have all the keys she can now encrypt data.

Let’s assume she computes the cypher text y = x.KM mod p, in DH Multiplication encryption KM is KAB and these are equivalent. Alice now sends her encrypted data over to bob together with her ephemeral key. This sending over of information is the merging of sending A and Y in DH by sending over the session key and the encrypted data.

When bob receives the message he needs to decrypt the message, in DH we find the inverse of KAB to decrypt the message which is equivalent to finding the inverse of KM in EG. So Bob now needs to compute the masking key KM which is equivalent to the session key in DH Step 3. He does this by using his private key and ephemeral key received from Alice. When he calculates KM he uses the inverse of KM to decrypt the message.

DH and EG are essentially the same protocol, textbooks refer to DH and EG as two completely different encryption schemes but they are in fact the same with the order in which information is sent across is altered and new terms are introduced.

 

Step Alice Bob
1 Choose p and prime α
2 He computes his private key

Kpr = d e {2, 3,.., p-2}

3 He computes his public key

Kpub = β = αd mod p

5 ß (α, p, β) (Domain Params in DH)
6 Choose i e {2, 3, … p-2}
7 Calculates ephemeral key:

KE = αi mod p (Step 1 DH)

8 Calculate masking key

KM = βi mod p (Step 3 DH)

9 Encrypt Data:

y = x.KM mod p (Step 4 DH)

10 y,KE  -> (Step 1 and 4 of HD combined)
11 Computes masking key (Step 3 DH)

KM= KEd mod p

12 Decrypt message (Step 5 DH)

X = y.KM-1 mod p

 

Comparison between EG and DH computations

Area EG DH
Domain Parameters Parameters α, p, β originates from the receiver

 

Parameters α, p is public.  β is not provided

 

Ephemeral Key KE = αi mod p A= αa mod p
Session / Masking Key KM = βi mod p Ba = αab = KAB mod p
Encryption y = x.KM mod p Y = x.KAB mod p
Decryption X = y.KM-1 mod p X = Y.KAB -1 mod p

 

 

Proof of correctness for EG

So let’s see what bob decrypts are actually the original plaintext message that was encrypted by Alice.

Bob computes: x

y.KM-1 = y(KEd)-1   : because {KM = KEd}

= x.KM . KE-d : because {y = x.KM}

= x. βi . (αi)-d : Step 7 and 8 from EG

Now we are trying to compute x and we have allot of factors, all we have to prove is that all the factors is equal to 1, since x.1 = x.

= x(αd)i . (αi)-d since β = αd in step 3 of EG

= x. αid . α-id

= x. αid-id = x. α0 = x.1 = x

(mod p is implied)

Proof of correctness for DH

Alice computes:

Ba = (αb) a = αab mod p

Bob Computes:

Ab = (αa) b = αab mod p

Encryption and decryption is of course just inverses of each other, so there is no need to prove this.

El Gamal replacing 3DES (I work in the ATM industry so applying this to ATM is quite interesting)

El Gamal can be used in the current finance sector as a replacement 3DES with the use of ATM devices.

Currently 3DES capable ATM cash machine devices, have a Master Key (KMaster), that is inserted into the ATM manually using split knowledge. This is the first input for 3DES, the second input for 3DES is, when the ATM starts up it contacts the host and retrieves the session key(KSession). When a user does a transaction on the ATM, the Pin is encrypted using 3DES y = (x{E(KSession)D(KMaster)E(KSession)}).

The Host then decrypts or translates the pin using the inverse x = (y{D(KSession)E(KMaster)D(KSession)})

If we look at this closer, we can see the Master Key can be replaced by α, p, β when the terminal requests a session key and that the pinblock can be encrypted by y = x.KM mod p, eliminating the need for 3DES and manual encryption key entering.

By replacing 3DES with El Gamal there is no need to contact the host for new session key as the terminal would be changing the ephemeral key for every transaction. There is also no exposure to compromise the Master Keys.

  El Gamal 3DES
Step 1 No Keys inserted User enter Master key manually
Step 2 ATM Contract host for domain parameters α, p, β ATM Contact host for session key
Step 3 Pin encrypted y = x.KM mod p Pin encrypted (E, D, E)
Step 4 Host Decrypt Pin X = y.KM-1 mod p Pin decrypted (D, E, D)

 

Advertisements

What are your thoughts?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s