
The next issue in implementing DiffieHellman I want to talk about

is this problem of finding a large prime.

The protocol assumes that we can start with this value Q,

which is a large prime number.

It doesn't have to be kept secret, but it should be different.

And the reason we want it to be different is

if there was only 1 large prime number, and everyone used the same one,

then an attacker could do a lot of precomputation based on that number

and have a better chance of breaking a DiffieHellman protocol.

So both protocols require a way to generate large prime numbers.

For DiffieHellman you might think,

well maybe we could have some large computing resource do that

not every participant needs to do this themselves.

For RSA, which we'll talk about in the next unit,

every participant needs to generate their own prime numbers to be able to generate their own key.

So we'll talk now about how to do that.

So both of these crypto systems depend on finding large prime numbers.

The first question we should ask is are there enough prime numbers

that we can always find a new one when we need one?

The good news is that Euclid proved, over 2500 years ago,

that there are infinitely many primes,

and it's a very elegant and beautiful proof.

So let's look at how Euclid proved this.

We'll start by assuming that there are a limited number of primes.

That would mean we could define a set consisting of all of the prime numbers

and know that it's a finite set with N primes in it.

The elements would be 2, 3, 5, and so forth

and there would be some highest prime, which we don't know the value of.

So then we'll compute the product of all those primes and add 1.

So let's have a quiz.

Is the value that we computedis P a prime number?

So the possible answers are: No, it's definitely not prime;

maybe, we don't know enough to determine that;

or yes it is definitely prime.