Project 4 (Diffie-Hellman)

• Gain an understanding of modular arithmetic and modular exponentiation.
• Learn how to use a BIGNUM library.
• Learn how asymmetric cryptography can be used to establish secure communications over an insecure channel

Diffie-Hellman key exchange and RSA public-key encryption both rely on functions like this:

( ( (g^a)%p )^b )%p

(^ denotes raising to a power, and % denotes modulus, the remainder after dividing).

The Diffie-Hellman key-exchange algorithm allows two people, Alice and Bob, to agree upon a number (to use as a key for encryption) without Eve knowing what it is, even though she sees everything that passes between Alice and Bob. It relies on the fact that:

(g^a)^b = (g^b)^a (which also = g^ab = g^ba)

The first equation above has the same property. Here's how the key exchange works:

Alice picks random(ish) numbers g, a, and p. p should be prime (in fact, (p-1)/2 should also be prime), and a should be large. 2 and 5 are the most commonly used values for g. She sends g, p, and the resulting value of (g^a)%p to Bob, but not a by itself.

Bob picks b (which should also be large), and sends (g^b)%p back to Alice. Eve, watching each exchange, now has g, p, (g^b)%p and (g^a)%p, but she can't get a or b from these. We hope. It would require that Eve know how to efficiently compute discrete logarithms, and the security of this algorithm (as well as that of RSA and most other public key algorithms) depends on nobody figuring out how to do that.

Bob takes the (g^a)%p that Alice sent him and raises it to b, then takes mod p, giving him ( ( (g^a)%p )^b )%p. Alice does the same thing and ends up with ( ( (g^b)%p )^a )%p - which is the same number. Alice and Bob can now use this number as a password for encrypting future communications.

Since g, a, b and p are usually very large numbers (hundreds of digits long), we need a fast way to compute (g^a)%p. That's where Modular Exponentiation comes in.

Incidentally, you can use dc to compute g^a%p to check your work:

% dc
2  8  255  |p
1

Means 2^8%255 (which equals 1). `man dc` for more information on dc, the UNIX desktop calculator.

The term modular exponentiation refers to the function:

(g^a)%p

We need to compute this function efficiently to use public key cryptography of the Diffie-Hellman or RSA variety.

If we calculate g^a as:

g^a = g*g*g*g.... (a times)

we'll spend a lot of time multiplying if a is large (which it usually is; often it's greater than the number of particles in the universe!). Here's how to get there faster.

Since we're dealing with computers here, let's assume we have a binary representation of a. If a = 42, we'd write it as

42 = 101010b (the b here means binary) = 1*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0

That means that:

if a=42,
g^a = g^(2^5 + 2^3 + 2^1) = g^(32) * g^(8) * g^(2)

Now we just need g^32, g^8 and g^2. But check this out:

g^2 * g^2 = g^4 and
g^4 * g^4 = g^8 and
g^8 * g^8 = g^16 and
g^16 * g^16 = g^32 and so on.

So by progressively multiplying the products by themselves, we can get g^(2^n) with just n-1 multiplications. Since there are only about log2(a) bits in a, we can find g^a with at most log2(a)-1 + log2(a) multiplication operations. (The second log2(a) comes from where we multiplied g^32 * g^8 * g^2 above).

So how does the modulus play into all of this? Well, it turns out that you can distribute the operation into the multiplication without changing the result, leaving you with smaller numbers to multiply, like this:

[g^32 % p * g^8 % p * g^2 % p] % p = (g^a)%p

You can do the same thing when computing g^(2^n). Why does it work? Look at it this way:

(3*4*5)%7 =? ( ( (3*4)%7 )*5 )%7
(12*5)%7
( (7+5)*5 )%7	split the product into a multiple of the modulus
(7*5 + 5*5)%7	and the remainder. The multiple divides out
( 5*5)%7	evenly, and you're left with what you'd have
( (12)%7 )*5 )%7	had if you had done the % after the first *.

In this lab you will use Diffie-Hellman key exchange to establish a secret key to use for communication with a server. Specifically:

• Select s and p. s and p must be at least 500 bits long. To be cryptographically strong, p must be a randomly generated prime, and (p-1)/2 should also be prime (although certain other combinations of p and the generator are also secure). p is the prime modulus, and s is your secret exponent. s and p should be cryptographically safe random numbers (i.e., not the result of a plain-vanilla rand() function). Reading from /dev/urandom on a Linux machine should be adequate to produce s. Other methods of generating random numbers will also be acceptable. Generating primes is a little more complicated. You may use a library (such as OpenSSL) to generate p.

• Write a routine to compute g^s%p, for g = 5. You may use a bignum library's multiply and modulus functions, but no composite functions like modular exponentiation or modular multiplication.

• Connect to the autograder, select Debug Mode, and send p and g^s%p, like this:

  p:     [your P value here]
  g^s%p: [your public value here]

where p and g^s%p are expressed in decimal. Note that the labels p: and g^s%p: are 2 of the lines, and the numbers are one (long) line each.

Debug Mode makes it easier to tell if your program is working properly.

In passoff mode, an eavesdropper won't be able to determine the shared secret, and the secret message will be readable only to you.

We will use an autograder to pass off your lab.

Submit a file with your source code to Learning Suite

If you want to write your client in Perl, you'll probably find the Math::BigInt library quite useful. There are also bindings for OpenSSL available.

If you are coding in Java then you will find the BigInteger object very useful. Python ints magically grow into bigints as needed with no user intervention.

OpenSSL includes a great bignum library. Some of this code might be helpful for using it: (includes example of how to generate a prime using OpenSSL). Note that you must link in the openssl libraries using “-lcrypto” when compiling. For example to compile your c program named dh.c with openssl, type “gcc -o dh dh.c -lcrypto”.

sample OpenSSL BIGNUM code

OpenSSL can be difficult to install on Windows machines for VC++. Here are some helpful hints on installing the OpenSSL library on your home computer.

OpenSSL Windows VC++ installation instructions

• The RSA lab will rely on a modular exponentiation routine. If you write good, modular code in this lab then you may be able to easily reuse the modular exponentiation routine in the next assignment.

• You will need to use a linux machine for passing off because we make you use an openssl command to decrypt some ciphertext. If you decide to run this on another OS then you are responsible to either move the files over to linux or figure out how to decrypt on another machine. This command is supplied to you in passoff mode after you submit your modulus and public values.

• Use a BigNum library's multiply function. Use a prime number generator. The only math that you must code yourself is the modular exponentiation.

• Make sure g = 5

• The ciphertext returned in passoff mode will have carriage returns. These are important characters! Do not remove them.