
Title:
Key Exchange  Applied Cryptography

Description:

Here's the idea of the protocol.

First they agree on 2 shared values.

The first is q, some large prime number,

and the second is g, and g is a primitive root of q.

What it means to be a primitive root is that for all numbers

in the group Zq, that is the numbers 1, 2, through q1,

we can generate all those numbers by raising g to some integer power.

If q is prime, it must have a primitive root,

and there are ways to find these primitive roots.

We could think of a brute force way of trying numbers until we find one.

That would be very expensive for a large prime number,

but there are more efficient ways to find them, which we won't talk about.

That's what they start with, those 2 things.

And then here's how the protocol works.

Alice will select a large random number, and Bob will also select

his own large random number.

This is like selecting the secret paint colors.

Then Alice will compute a value we'll call yA,

and she'll compute that by raising g to the xA power

and doing this modulo q.

Bob will do the same thing but with his secret power xB.

He'll raise g to the xB power modulo q.

They'll exchange these values.

Alice sends yA to Bob.

Bob sends yB to Alice.

And then Alice will compute a key that will be shared between Alice and Bob,

and she'll compute that by raising the yB value that she received from Bob

to the xA power and do that all modulo q.

If this is a good key distribution protocol,

then there should be a way for Bob to compute the same key.

I'll see if you can figure that out yourself by making that a quiz.

These are the possible choices.

Which one of these should Bob compute to obtain the same key as Alice did here?