## Finding Large Primes - Applied Cryptography

• 0:00 - 0:03
The next issue in implementing Diffie-Hellman I want to talk about
• 0:03 - 0:05
is this problem of finding a large prime.
• 0:05 - 0:08
• 0:08 - 0:10
which is a large prime number.
• 0:10 - 0:14
It doesn't have to be kept secret, but it should be different.
• 0:14 - 0:16
And the reason we want it to be different is
• 0:16 - 0:19
if there was only 1 large prime number, and everyone used the same one,
• 0:19 - 0:23
then an attacker could do a lot of pre-computation based on that number
• 0:23 - 0:28
and have a better chance of breaking a Diffie-Hellman protocol.
• 0:28 - 0:31
So both protocols require a way to generate large prime numbers.
• 0:31 - 0:33
For Diffie-Hellman you might think,
• 0:33 - 0:37
well maybe we could have some large computing resource do that--
• 0:37 - 0:40
not every participant needs to do this themselves.
• 0:40 - 0:43
For RSA, which we'll talk about in the next unit,
• 0:43 - 0:47
every participant needs to generate their own prime numbers to be able to generate their own key.
• 0:47 - 0:49
So we'll talk now about how to do that.
• 0:49 - 0:53
So both of these crypto systems depend on finding large prime numbers.
• 0:53 - 0:56
The first question we should ask is are there enough prime numbers
• 0:56 - 0:58
that we can always find a new one when we need one?
• 0:58 - 1:02
The good news is that Euclid proved, over 2500 years ago,
• 1:02 - 1:05
that there are infinitely many primes,
• 1:05 - 1:07
and it's a very elegant and beautiful proof.
• 1:07 - 1:09
So let's look at how Euclid proved this.
• 1:09 - 1:12
We'll start by assuming that there are a limited number of primes.
• 1:12 - 1:17
That would mean we could define a set consisting of all of the prime numbers
• 1:17 - 1:20
and know that it's a finite set with N primes in it.
• 1:20 - 1:24
The elements would be 2, 3, 5, and so forth
• 1:24 - 1:28
and there would be some highest prime, which we don't know the value of.
• 1:28 - 1:31
So then we'll compute the product of all those primes and add 1.
• 1:31 - 1:32
So let's have a quiz.
• 1:32 - 1:37
Is the value that we computed--is P a prime number?
• 1:37 - 1:40
So the possible answers are: No, it's definitely not prime;
• 1:40 - 1:43
maybe, we don't know enough to determine that;
• 1:43 - 1:45
or yes it is definitely prime.
Title:
Finding Large Primes - Applied Cryptography
Video Language:
English
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
01:46
 Udacity Robot edited English subtitles for Finding Large Primes - Applied Cryptography Gundega added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• Gundega