WEBVTT
00:00:00.000 --> 00:00:03.000
The next issue in implementing Diffie-Hellman I want to talk about
00:00:03.000 --> 00:00:05.000
is this problem of finding a large prime.
00:00:05.000 --> 00:00:08.000
The protocol assumes that we can start with this value Q,
00:00:08.000 --> 00:00:10.000
which is a large prime number.
00:00:10.000 --> 00:00:14.000
It doesn't have to be kept secret, but it should be different.
00:00:14.000 --> 00:00:16.000
And the reason we want it to be different is
00:00:16.000 --> 00:00:19.000
if there was only 1 large prime number, and everyone used the same one,
00:00:19.000 --> 00:00:23.000
then an attacker could do a lot of pre-computation based on that number
00:00:23.000 --> 00:00:28.000
and have a better chance of breaking a Diffie-Hellman protocol.
00:00:28.000 --> 00:00:31.000
So both protocols require a way to generate large prime numbers.
00:00:31.000 --> 00:00:33.000
For Diffie-Hellman you might think,
00:00:33.000 --> 00:00:37.000
well maybe we could have some large computing resource do that--
00:00:37.000 --> 00:00:40.000
not every participant needs to do this themselves.
00:00:40.000 --> 00:00:43.000
For RSA, which we'll talk about in the next unit,
00:00:43.000 --> 00:00:47.000
every participant needs to generate their own prime numbers to be able to generate their own key.
00:00:47.000 --> 00:00:49.000
So we'll talk now about how to do that.
00:00:49.000 --> 00:00:53.000
So both of these crypto systems depend on finding large prime numbers.
00:00:53.000 --> 00:00:56.000
The first question we should ask is are there enough prime numbers
00:00:56.000 --> 00:00:58.000
that we can always find a new one when we need one?
00:00:58.000 --> 00:01:02.000
The good news is that Euclid proved, over 2500 years ago,
00:01:02.000 --> 00:01:05.000
that there are infinitely many primes,
00:01:05.000 --> 00:01:07.000
and it's a very elegant and beautiful proof.
00:01:07.000 --> 00:01:09.000
So let's look at how Euclid proved this.
00:01:09.000 --> 00:01:12.000
We'll start by assuming that there are a limited number of primes.
00:01:12.000 --> 00:01:17.000
That would mean we could define a set consisting of all of the prime numbers
00:01:17.000 --> 00:01:20.000
and know that it's a finite set with N primes in it.
00:01:20.000 --> 00:01:24.000
The elements would be 2, 3, 5, and so forth
00:01:24.000 --> 00:01:28.000
and there would be some highest prime, which we don't know the value of.
00:01:28.000 --> 00:01:31.000
So then we'll compute the product of all those primes and add 1.
00:01:31.000 --> 00:01:32.000
So let's have a quiz.
00:01:32.000 --> 00:01:37.000
Is the value that we computed--is P a prime number?
00:01:37.000 --> 00:01:40.000
So the possible answers are: No, it's definitely not prime;
00:01:40.000 --> 00:01:43.000
maybe, we don't know enough to determine that;
00:01:43.000 --> 00:01:45.000
or yes it is definitely prime.