# Exploring Diffie-Hellman Encryption

Communicating "in the clear", Alice and Bob select two numbers, q and n. Alice then selects the secret number xa. Bob selects the secret number xb. From the two public numbers, q and n, and her secret number xa, Alice calculates ya and sends the number to Bob. Using the same two public numbers, q and n, and his secret number xb, Bob calculates yb and sends the number to Alice. Alice and Bob have completed step one of the Diffie-Hellman process.

The program crypto.bc shows how Alice calculates ya using the formula

**ya = (n ^ xa) % q**

This says, multiply n by itself xa times, then divide the product by q and save only the remainder.

Alice sends the number ya to Bob. In the meantime, Bob applies the same formula to the numbers n, xb and q to calculate the number yb:

**yb = (n ^ xb) % q**

Bob sends the number yb to Alice. They are ready for step two.

Using the number yb received from Bob, Alice calculates

**ka = (yb ^ xa) % q**

Again, this means multiply yb by itself xa times, and then save the remainder after dividing the product by q. When Bob receives Alice's number ya he calculates:

**kb = (ya ^ xb) % q**

Alice and Bob have completed the Diffie-Hellman encryption process.

Alice applied her secret number xa to Bob's value yb and calculated ka. Bob applied his secret number xb to Alice's value ya and calculated kb. Presto: it turns out that ka = kb, a number now known to Alice and Bob, but to no one else. Even though Eve, the eavesdropper, may have been monitoring their communications studiously, Eve cannot discover the number ka easily.

The following program, written for the bc compiler, was adapted from Simson Garfinkel's book on Phil Zimmerman's Pretty Good Privacy. Where large numbers would be used in practice, we use small numbers for clarity. The operation x % y returns x modulo y, that is, the remainder obtained when x is divided by y. The operation n ^ xa multiplies the number n times itself xa times. In programs designed to handle really large numbers, we can speed up the calculation of (n ^ xa) % q by applying the modulo operation after each multiply. While using relatively small numbers, illustration is made simpler with the naïve literal method used below:

/* crypto.bc - From Simson Garfinkel: PGP, appendix F * the mathematics of Diffie-Hellman encryption. */ q = 563 /* Alice and Bob select a large prime */ a = 5 /* ...and another random number */ xa = 9 /* Alice picks the random number 9 */ xb = 14 /* Bob picks the random number 14 */ ya = a ^ xa /* Alice */ ya = ya % q print "_nAlice sends ya = ", ya," to Bob_n"; yb = a ^ xb /* Bob */ yb = yb % q print "Bob sends yb = ", yb," to Alice_n"; ka = yb ^ xa print "_n from yb^xa = ";ka; ka = ka % q print " Alice calculates ka = ",ka,"_n" kb = ya ^ xb print " from ya^xb = "; kb; kb = kb % q print " Bob calculates kb = ",kb,"_n"; print "_nThey can now use ",kb," to encrypt messages._n"; quit

When executed with the command **bc
crypto.bc**, this program writes the following output to
stdout:

Alice sends ya = 78 to Bob Bob sends yb = 534 to Alice from yb^xa = 3530785328217308860798464 Alice calculates ka = 117 from ya^xb = 308549209196654470906527744 Bob calculates kb = 117 They can now use 117 to encrypt messages.

Operating entirely in the clear, Alice and Bob have passed the number 117 between them without disclosing it to anyone else. Eve, who may have been monitoring their communications or recording them for analysis, may have difficulty discovering the number ka = 117.

Eve knows the numbers n, q, ya and yb, so she could write the equation

**ya = ( n ^ xa) % q**

and try all possible values of xa until she finds one that generates the known value of ya. Using that value of xa in the equation

**ka = (yb ^ xa) % q**

Eve could calculate the value of ka. This "brute force" method of attack, however, is practical only if Alice and Bob use small numbers. By using large numbers, preferably large prime numbers, Alice and Bob can make Eve's brute force attack impractical.

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Sponsored by Red Hat

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Sponsored by ActiveState

## Trending Topics

August 2014 Issue of Linux Journal: Programming | Aug 01, 2014 |

August 2014 Video Preview | Aug 01, 2014 |

Open-Source Space | Jul 31, 2014 |

Silicon Mechanics Gives Back | Jul 30, 2014 |

Reglue: Opening Up the World to Deserving Kids, One Linux Computer at a Time | Jul 29, 2014 |

diff -u: What's New in Kernel Development | Jul 23, 2014 |

- Open-Source Space
- Numerical Python
- Silicon Mechanics Gives Back
- August 2014 Issue of Linux Journal: Programming
- Reglue: Opening Up the World to Deserving Kids, One Linux Computer at a Time
- New Storage Solution is Music to the Ears of Fast-Growing Digital Music Company
- Linux Systems Administrator
- Download "Linux Management with Red Hat Satellite: Measuring Business Impact and ROI"
- Senior Perl Developer
- Technical Support Rep

## Comments

## prime(q) => prime((q-1)/2) ???

This is in the part "How to Select q and n":

prime(q) => prime((q-1)/2)

q=13 (q-1)/2 == 6

Have I missed something?

## doubt in diffie-hellman

I saw your article about diffie-hellman. I understood all the things from your article. But after getting the private key, public key and shared secret key then How to encrypt a text and decrypt the text. Please explain. I am eagerly waing your reply.

My email ID - tvmalaigopal@yahoo.com

## Re: doubt in diffie-hellman

Thanks; I had the same reaction when first

looking into Diffie-Hellman encryption. The

method simply communicates a secret number

between Alice and Bob. They know that

number but no one else does, even though

their communications were entirely in the

clear. From the number, called the "result,"

they calculate a key. One simple way would

be to give the result number to rand() as

the seed value and take from rand a stream

of pseudo-random bytes to be used as their

key. To encrypt a message Alice takes the

exclusive-or of each message byte with

successive pseudo-random bytes. To

decrypt the message, Bob does exactly

the same. Since they both used the same

seed, their pseudo-random streams of

bytes will be identical. But no one else

knows the seed.

Diffie-Hellman itself does not encrypt;

it's just a method of "exchanging" keys.

It is a secure method, and convenient,

and that's why it is used.

jdennon@seasurf.com

## Re: doubt in diffie-hellman

How can I calculate the public value lengths for different prime number and exponent/generator sizes ?

## Re: prime(q) => prime((q-1)/2) ???

Okay, I should have read bjb's reply

first. I thought you were quoting some

program text. For the full story on why

we want both q and (q-1)/2 to be prime

numbers, find a copy of the paper by

S. C. Pohlig and M. E. Hellman:

"An Improved Algorithm for Computing

Logarithms in GF(p) and Its

Cryptographic Significance," IEEE

Transactions on Information Theory,

v.24, n.1, Jan 1978, pp. 106-111.

When (q-1)/2 is prime, Eve's job is

a little tougher.

jdennon@seasurf.com

## Re: prime(q) => prime((q-1)/2) ???

I have only a few minutes to look at this

right now and cannot tell where the text

you give was found. If you are running

from text found in the published article,

then by all means download the tar

file from my web page and try again

using the original programs. Thanks

for your comment.

jdennon@seasurf.com

## Re: prime(q) => prime((q-1)/2) ???

It doesn't work for 13. That's the point of the test: to find numbers it does work for.

Try 23.

bjg