The Diffie-Hellman protocol is widely used within the session setup portion of cryptographic protocols.

Steps:

1. Alice and Bob agree on a prime p, and a base g. These can be exchanged in the clear.
2. Alice computes secret a, and sends Bob A = g^a mod p.
3. Bob computes secret b and sends Alice B = g^b mod p.
4. Alice computes s = B^a mod p.
5. Bob computes s = A^b mod p.

At this point they should both hold the same value of s which can be used as the shared secret with which to encrypt all subsequent exchanges.

What is interesting to note is that for simple (read small) values the algorithm can be implemented quite naively. However, for any kind of security usage, the values for a, b need to be sufficiently large as to make the job of any attacker (Eve) computationally difficult. General wisdom suggests that these values should have several hundred digits. This means that a simple approach to computing g^a cannot be used - there would simply be too many CPU cycles wasted in an approach such as:

unsigned long long val = g;

for (unsigned long long i = 0; i < a; ++i) {
    val += g;
}

val = val % p;

There has got to be a simpler, and less computationally expensive way!

Luckily there is: Successive Squares Method

What this means is that we can significantly reduce the number of computations we need to carry out in order to calculate the necessary values. The way this is done is as follows:

g^a mod p, where g=5, a=423, and p=765

We need to expand a as a sum of powers of 2 - this is known as the binary expansion of a. The largest power of 2 which is less than 423 is 256, so

a = 423 = 256 + 167

We repeat this step on the subsequent values until we get to 0. So:

a = 423 = 256 + 128 + 32 + 4 + 2 + 1

Meaning we can rewrite our original expression as:

5^423 mod 765

= 5^(256 + 128 + 32 + 4 + 2 + 1) mod 765

= 5^256 * 5^128 * 5^32 * 5^4 * 5^2 * 5^1 mod 765

There is still a problem in that the numbers needed to be calculated are still quite significant meaning that we will likely hit some kind of overflow situation quite quickly if we are not careful. We can limit the exposure to ths issue by taking advantage of the following properties:

5^1   = 5     =   5    mod 765
5^2   = 5^2   =  25    mod 765
5^4   = 25^2  = 625    mod 765
5^8   = 625^2 = 475    mod 765
5^16  = 475^2 = 715    mod 765
...

In other words we can use the square of the modulus of the previous exponent. I’m not sure exactly why - I should probably find out - but this means we can deal with much smaller numbers with a reduced risk of overflow issues. The largest number we would ever need to square would be the modulus value minus one.

From here we can use a simple solution to the equation to reduce the need to deal with large numbers. We can take the first two numbers and calculate the modulus, then repeat this using the third value plus the result, and so on.

 (iteration #1)
5^1 = 5 = 5 mod 765 = 5
5^2 = 5^2  = 5^2 = 5^2  = 25 mod 765 = 5
5^4 = 25^2  = 5^4 = 25^2  = 625 mod 765 = 25
5^8 = 625^2  = 5^8 = 625^2  = 390625 mod 765 = 625
5^16 = 475^2  = 5^16 = 475^2  = 225625 mod 765 = 475
5^32 = 715^2  = 5^32 = 715^2  = 511225 mod 765 = 715
5^64 = 205^2  = 5^64 = 205^2  = 42025 mod 765 = 205
5^128 = 715^2  = 5^128 = 715^2  = 511225 mod 765 = 715
5^256 = 205^2  = 5^256 = 205^2  = 42025 mod 765 = 205
 Result = 715

 (iteration #2)
5^1 = 5 = 5 mod 765 = 5
5^2 = 5^2  = 5^2 = 5^2  = 25 mod 765 = 5
5^4 = 25^2  = 5^4 = 25^2  = 625 mod 765 = 25
5^8 = 625^2  = 5^8 = 625^2  = 390625 mod 765 = 625
5^16 = 475^2  = 5^16 = 475^2  = 225625 mod 765 = 475
5^32 = 715^2  = 5^32 = 715^2  = 511225 mod 765 = 715
5^64 = 205^2  = 5^64 = 205^2  = 42025 mod 765 = 205
5^128 = 715^2  = 5^128 = 715^2  = 511225 mod 765 = 715
 # (715 * 205) mod 765
 Result = 460

 (iteration #3)
5^1 = 5 = 5 mod 765 = 5
5^2 = 5^2  = 5^2 = 5^2  = 25 mod 765 = 5
5^4 = 25^2  = 5^4 = 25^2  = 625 mod 765 = 25
5^8 = 625^2  = 5^8 = 625^2  = 390625 mod 765 = 625
5^16 = 475^2  = 5^16 = 475^2  = 225625 mod 765 = 475
5^32 = 715^2  = 5^32 = 715^2  = 511225 mod 765 = 715
 # (460 * 205) mod 765
 Result = 205

 (iteration #4)
5^1 = 5 = 5 mod 765 = 5
5^2 = 5^2  = 5^2 = 5^2  = 25 mod 765 = 5
5^4 = 25^2  = 5^4 = 25^2  = 625 mod 765 = 25
 # (205 * 625) mod 765
 Result = 370

 (iteration #5)
5^1 = 5 = 5 mod 765 = 5
5^2 = 5^2  = 5^2 = 5^2  = 25 mod 765 = 5
 # (370 * 25) mod 765
 Result = 70

 (iteration #6)
5^1 = 5 = 5 mod 765 = 5
 # (70 * 5) mod 765
 Result = 350

Phew!

Related Links

• Method of Successive Squares
• Square root using Newton’s method of successive approximations
• Handling big numbers in C
• Fast prime generator (C++ recipe)
• Prime Generator Algorithm
• Power of Successive Squares
• Diffie Helman, Successive Square, Modulo Arithmetic