Don't like this style? Click here to change it! blue.css

Welcome .... Click here to logout

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.

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:

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: