# Class 16: DHKE wrap-up and El-Gamal

Overview: In this lesson we'll make an encryption scheme that works entirely in a public key style. Unlike the last lesson this is not just about key swapping but sending encrypted messages to a public key listener. This part of the lesson is a preface to remind you of how to do modular inverses and share one new method in the DH context.

### The Goal (our preface to El Gamal)

We want to play the role of Bob who knows $$g, p, b, A, B, K$$. Our goal is to compute $$g^{-ab} \pmod{p}$$.

So how do we calculate inverses modulo a prime? Well I think we've got several ways to do it this.

•  xgcd(p, K)  will give us $$1,s,t$$ such that $$1 = s \cdot p + t \cdot K$$.
• $$K^{\Phi(p) - 1 } \cdot K \equiv 1 \mod{p}$$ and $$\Phi(p) = p-1$$ so  pow(K, p-2, p)  is an answer.
• The new one is this: We know that $$g^{p-1} \equiv 1$$ and even $$g^{(p-1) \cdot i} \equiv 1$$ for any $$i$$. So if we know $$b$$ but not $$a$$ so $$g^{p-1-b}$$ will be the power such that $$g^{b} \cdot g^{p-1-b} \equiv 1$$. So $$A^{p-1-b} = g^{-ab} = K^{-1}$$.

Just do it: Given the following parameters for a Key Exchange and the role of Bob, compute $$K^{-1} \pmod{p}$$ using each of the three methods here. Confirm that you've got the right number.

Overview: In this part we use the El Gamal scheme to do our first end-to-end public key encryption. The idea is just one small adjustment from the DHKE scheme we saw in lesson 1.

So ElGamal takes advantage of the fact that $$m \cdot K \pmod{p}$$ doesn't reveal anything about $$m$$ or $$K$$ provided $$m$$ is large enough.

It goes like this:

• Someone calculates and publishes $$p, g$$
• Alice picks $$a$$ and calculates $$A = g^{a} \mod{p}$$ and publishes $$A$$.
• Bob picks $$b$$ and calculates $$B = g^{b} \mod{p}$$ and publishes $$B$$.
• Alice calculates $$K = B^{a} \mod{p}$$ and keeps it secret.
• Bob calculates $$K = A^{b} \mod{p}$$ the same secret.
• Alice picks a message $$m$$ as an integer smaller than $$p$$ (but not much significantly smaller than $$p$$).
• She calculates the ciphertext: $$C := m \cdot K \mod{p}$$ which she publishes
• Bob gets $$C$$ and calculates $$K^{-1}$$ and $$C \cdot K^{-1} \mod{p}$$ which is $$m$$.

Do it: use the prime $$p=$$ E912ECF78A51FC5BBFA26A00E07A0CEC5ECEB897891643DD7DDD8056A51C71124258D52DAEF464B929F6397101F00C67CFC09B3D068B522E1C8B566431936C3A606A47928582F0D8D6B23F9019FF06A900CD5AD97E02CD3DEAA0495C968A2345858C6556623A61124C711DC0708999C08D5A349592F37DFE07A49C0D82241403 the generator $$g = 2$$. Calculate and store your private key, $$x$$, and public key $$g^{x} \mod{p}$$. Publish your public key in our chat window. Compute a message by taking no more than 127 character ascii message $$m$$ and our usual trick of  int(binascii.hexlify(m), 16)  to get an integer. Pick a partner, compute the shared secret, and the cipher text, send it back out in the public channel and decrypt their message.

Overview: We want to show why El-Gamal needs a new key swap with every message. Of course we use our favorite trick, breaking it when things are done wrong!

In a multiple-encryption environment we know that messages need to be randomized with some sort of nonce/IV. But ElGamal needs one additional randomization, which is a new exponent for every message.

Imagine that you can observe 2 consequtive encrypted texts $$c_1, c_2$$ which correspond with two messages $$m_1, m_2$$. If you know $$m_1$$ then you can find $$m_2$$ if Bob and Alice didn't update their modular exponents. Here's how:

• $$c_1 = m_1 \cdot K \mod{p}$$ where $$K$$ is their shared secret.
• If I know $$m_1$$ then I can compute $$K \equiv m_1^{-1} \cdot c_1 \mod{p}$$ which I can invert again to get $$K^{-1}$$.
• Now when I observe $$c_2$$ I am as powerful as Bob: $$c_2 \cdot K^{-1} \mod{p}$$ is $$m_2$$.