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\).

A NEW FLAG HAS APPEARED