So, Bob sends over to Alice g to the b and of

course I should remind you that both g to the a and

g to the b are just elements in this group G. Now,

they can derive the shared secret, If you remember,

the shared secret is g to the ab, and these equalities

here shows that both sides can actually compute

the shared secret given the values at their disposal.

So, Alice for example, has B and she has a, and

so raising B to the power of a, gives her the shared

secret. The attacker, of course, the poor attacker

he gets to see A and B and his goal is now,

of course, he also gets to see the generated g, and

his goal now is to compute g to the ab. But, we said that

this is believed to be a hard problem. Given g, g to the a,

and g to the b, in a group like Zp<i>, computing g to </i>

the ab is difficult. So, now let's see how to convert to

the Diffie-Hellman protocol into an actual public key

system. As I said, this was a brilliant idea due to

Taher ElGamal. So, as before, we are going to fix our

cyclic group G and a generator g inside of G.

Now, here I wrote the Diffie-Hellman protocol again,

except now we are going to assume that these guys

are separated in time. These two steps do not have

to occur simultaneously; they could actually take place

at quite different times. The first step of the Diffie-Hellman

protocol is what we are going to view as key

generation. That is the public key is going to be

this capital A and the secret key is simply going to

be the little a. So, you notice of course that

extracting the secret key from the public key,

namely extracting the little a from capital A is a

discrete log problem. So, that recovering a secret

key is actually difficult. Ok, now this gives us our public key.

So, now at a later time Bob wants to encrypt a

message to Alice, encrypted using her public key.

So how does Bob encrypt? Well, what he is going to do is

he's going to compute his contribution to the Diffie-Hellman

protocol. Namely, he is going to send over g to the

little b. Of course, he is going to choose this little b

at random and now he is going to compute by

himself the shared secret. So, he is going to

compute by himself g to the ab. From this g to the ab

he is going to derive a symmetric key for a

symmetric encryption system and then he is going to

encrypt the message m using this symmetric key

that he just derived. And that is the pair he is going to

send. So, he is going to send over his contribution

to the Diffie-Hellman protocol plus the symmetric

encryption of the message m that he wants to send

over to Alice. Ok, so you can see basically, we are

doing the exact same thing as we would do in the Diffie-Hellman

protocol except now we, Bob directly immediately is using

his Diffie-Hellman secret to encrypt the message that he

wants to send over to Alice.

Now, what does Alice do to decrypt?

Basically, she is going also to compute the

Diffie-Hellman secret. Remember, that now she just

received Bob's contribution to the Diffie-Hellman

protocol and she has her secret key a. So, she can

compute also the Diffie-Hellman secret, namely

g to the ab, from which she is going to derive the

symmetric encryption key k. And then, she is going

to decrypt the message to recover the actual

plaintext. Ok, so that is the intuition for how we

convert the Diffie-Hellman protocol into a public key

system. By the way, this was kind of an interesting

development at the time that it came out, partially

because, you notice this is a randomized encryption scheme.

So, every time Bob encrypts a message, it is

required that he choose a new random b and

encrypt the message using this new random b.

So, let's see the ElGamal system, actually in more

detail. So, now actually let's view it as an actual

public key encryption system. Namely, algorithm Gen,

algorithm E and algorithm D.

So, as usual, we are going to fix our finite cyclic

group of order n. Another ingredient that we are going

to need is a symmetric encryption system. So, I am

going to refer to it as E sub s, and D sub s. These are the

encryption and decryption algorithms of a symmetric

encryption system that happens to provide

authenticated encryption. And, the key space for

this system is capital K. And, then we are also going

to need a hash function that maps pairs of elements

in the group, namely elements in G squared into

the key space. Now, here is how the public key

encryption system works. So, I have to describe

three algorithms. Algorithm that generates the

public key and the secret key, and then the encryption

and decryption algorithms. So, the key generation

algorithm works as follows: All we do is basically,

build up Alice's contribution to the Diffie-Hellman

protocol. What we are going to do is going to choose a

random generator g in G and then we are going to

choose a random exponent a. The secret key is

going to be a and then the public key is going to be

the generator g and Alice's contribution to the

Diffie-Hellman protocol. The reason, by the way,

we don't use a fix generator, is because it

allows us to somewhat use a weaker assumption,

improving security. And, so it is actually better to

choose a random generator every time. It is easy

enough to choose a random generator. All we do, is we

take the generator that we started with and then we

raise it to some power that is relatively prime to n.

That will give us another generator. A random

generator of the group capital G. Ok. So, you can

see here that again the public key is simply Alice's

contribution to the Diffie-Hellman protocol. And, the

secret key is the random a that she chose. Now, how

do we encrypt and decrypt? Well, when Bob wants

to encrypt the message, he is going to use the

public key. Remember, it consists of g and h.

Here, he wants to encrypt a message m.

So, here is what he is going to do. So, he is going

to choose his contribution to the Diffie-Hellman protocol.

So, this is the secret b that he would normally

choose in Diffie-Hellman. And, now he is going to

compute g to the b, which is actually his message,

that gets send to Alice in the Diffie-Hellman protocol.

He is going to compute the Diffie-Hellman secret,

that's h to the b. If you remember, h was g to the a,

therefore, this value here is really g to the ab.

That's the Diffie-Hellman secret. That is the one thing that

the attacker doesn't actually know. Next, he is going

to compute a symmetric key by basically hashing

this pair u comma v. So, u, of course, is something

that the attacker is going to know because that is

going to be sent as part of the ciphertext. But v, the

attacker isn't going to know. Again, for the proof of

security, actually it helps to hash both u and v. So, we

hash both of them together. Although, strictly speaking

we just needed to hash v, because v is the only value

that the attacker doesn't know. The attacker

already knows u, because that's going to be part of the data

that's sent on the network. So, anyhow, so Bob derives

this symmetric key k, by hashing u and v. Then, he

goes ahead and encrypts the message using the

symmetric key k and finally he outputs his

contribution to the Diffie-Hellman protocol.

The value u and then the symmetric ciphertext that

directly encrypts the message m.

That's it. So, the ciphertext consists of these two

parts and that is the thing that gets sent over the

network. Let's see, how does Alice decrypt now.

So, she is going to use her secret key a to decrypt

and she receives here, Bob's contribution to the

Diffie-Hellman protocol plus the symmetric

encryption of the message that Bob sent.

What she will do is she'll compute herself the Diffie-Hellman

secret. If you remember, u to the a is simply g to the b

to the a. Which is g to the ab. So, here Alice

computed the Diffie-Hellman secret. And, now let me

ask you, how does she derive the symmetric key k

given the Diffie-Hellman secret, g to the ab and the

ciphertext that she was given?