Return to Video

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
    The protocol assumes that we can start with this value Q,
  • 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