Class 16: Diffie-Hellman and Chinese Remainder Theorem

Overview

In this lesson we will go over the Diffie-Hellman key exchange algorithm. We will also take a look at a network capture of a Diffie-Hellman key exchange.

Diffie-Hellman

Looking back at block ciphers, such as DES and AES, they use a shared secret key. Block ciphers use the same key to encrypt and decrypt, so If I have an encrypted message that I want you to decrypt, how do I share the secret key with you?

That’s where Diffie-Hellman comes in! Diffie-Hellman allows two people to generate a shared secret together across s public channel, so that anyone listenting to the messages being sent across the channel will not be able to determine the secret.

The reason this works? The Discrete Log problem, similarly to RSA. Given the values of A, g, and p, with A = g^a mod p, calculating the value of a is a hard problem.

The Algorithm

Alice

Alice, the initiator, generates a strong prime p
Alice also generates a base g, which is usually just the number 2
Alice generates a private random number a which shares no factors with p
Alice calculates a public A with A = g^a mod p
Alice sends (p, g, A) to Bob, a is kept private

Bob

Bob receives (p, g, A) from Alice
Bob generates a private random number b which shares no factors with p
Bob calculates a public B with B = g^b mod p and sends to Alice

Calculating the Secret

With the B received from Bob, Alice computes the shared secret s with s = B^a mod p
With the A received from Alice, Bob computes the same shared secret s with s = A^b mod p

p, g, A, and B are public values, and a, b, and s are private values.

Only Alice can compute s = B^a mod p because only Alice knows a.

Only Bob can compute s = A^b mod p because only Bob knows b.

Further, Alice is computing s = (g^b)^a mod p and Bob is computing s = (g^a)^b mod p.

g^ba = g^ab mod p

Try It

Pick a partner. One of you will be Alice and the other will be Bob. Perform the Diffie-Hellman key exchange in the Slack channel as described above. Verify that you generated the same secret.

Here’s some Python code to get you started:

from Crypto.Util.number import *

g = 2
p = getStrongPrime(512)
while True:
    a = getRandomRange(2, p-2)
    if GCD(a, p-1) == 1:
	break

A = pow(g, a, p)

Challenge

Solve this CTF challenge!

Forensics Challenge: Cheater

Solve the Cheater challenge.

Chinese Remainder Theorem

Let’s play a game. A random number is picked and you can only learn the remainder of that number modulo single digit moduli. Your goal is to find the number in the fewest number of guesses.

Play the game here!

There is a perfect mapping from Z_N↔Z_q1×⋯Z_qk whenever the pairwise GCD of q_i is 1 and N=q₁⋯q_k.

Example:

Given that x≡2 mod 5, x≡1 mod 3 then x must be equivalent to 7 mod 15.

You can code your own Chinese Remainder Theorem algorithm in Python or head to CoCalc (Python with cool and powerful math stuff) and use the built-in crt function. Now compute the smallest positive number which is 3 mod 9, 8 mod 13, 6 mod 25, and 36 mod 121

Crypto Challenges

CRT
Broadcast

Pohlig-Hellman

I want to introduce a feasible attack on the discrete log problem. That is, given A = α^x mod p, p, α find x.

This attack will teach us about what makes a prime strong enough, cyclic groups, and the Chinese Remainder Theorem.

Example

The big idea is this, the multiplicative subgroup of integers mod p has size p−1. If we know the factors of p−1 (and they are all small) then we can convert this into a smaller problem.

Imagine that q divides p−1 then (g^(p−1)/q)^x = h^(p−1)/q is another equation involving x but now the possible answers for x aren’t mod p−1 but are mod q.

Given p = 31, g = 3, h = 26 = g^x find x.

We could try every value of x from 1 to 30 until we got 26 mod 31. In this case that would be cheap and not a problem, BUT it won’t scale to the larger problem.

So we start by factoring p−1 = 30 = 2⋅3⋅5. We will convert the discrete log problem into a three smaller problems that we can Chinese Remainder to find the final solution.

Start with q = 2 which divides p−1. Since we are looking for x which satisfies the relationship that 3x ≡ 26 (mod 31) then if we replace 3 and 26 by 3¹⁵ and 26¹⁵ then we’ll get another relationship 3^15x ≡ 26¹⁵ (mod 31).

If we look at this a little deeper we know that 3³⁰ ≡ 1 (mod 31) based on what we know about cyclic groups. So this new relationship actually only gives us an answer mod 2. Here’s what I mean. Suppose x were odd, then 3^15x is exactly equivalent to 3¹⁵ and if x is even then 3^15x is always equivalent to 1. So either 3^15x is equivalent to 3¹⁵ or it is equivalent to 1. That means that we have learned a solution to the equation x ≡ r(mod 2).

In this case we just check 26¹⁵ (mod 31) and we get 30 which matches 3¹⁵ (mod 31).

So we know that x ≡ 1 (mod 2).

Now let’s try q = 5. We raise both 3 and 26 to the (p−1)/5-th power. We get 3^6x ≡ 26⁶ ≡ 1 (mod 31). Now try every remainder of x (mod 5) until we find the right power.

3⁰ ≡ 1, 3⁶ ≡ 16, 3¹² ≡ 8, 3¹⁸ ≡ 4, 3²⁴ ≡ 2 (mod 31), so we now know that x ≡ 0 (mod 5) and that x ≡ 1 (mod 2) which tells us that x ≡ 5 (mod 10).

Using the last prime factor, 3, raise both 3 and 26 to the (p−1)/3 and deduce the remainder of x (mod 3), and using all three clues deduce the value of x (mod 30).

Problem

Solve this discrete log problem: Given p = 125301575591, g = 115813337451 , h = g^x mod p = 73973989900, solve for x.

Sage

Sage can do this for us!

p = 125301575591
g = 115813337451
h = 73973989900 
R = IntegerModRing(p)

x = discrete_log(R(h), R(g))

Crypto Challenge: Distinct Chunk Of Wood

Solve the Distinct Chunk of Wood challenge

ELEG 467/667

Pentesting & CTF's