The next issue in implementing Diffie-Hellman 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 pre-computation based on that number
and have a better chance of breaking a Diffie-Hellman protocol.
So both protocols require a way to generate large prime numbers.
For Diffie-Hellman 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 computed--is 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.