Return to Video

RSA Encryption step 3

  • 0:00 - 0:02
    - [Voiceover] Over 2,000
    years ago, Euclid showed
  • 0:02 - 0:06
    every number has exactly
    one prime factorization,
  • 0:06 - 0:09
    which we can think of as a secret key.
  • 0:09 - 0:11
    It turns out that prime factorization
  • 0:11 - 0:14
    is a fundamentally hard problem.
  • 0:14 - 0:18
    Let's clarify what we
    mean by "easy" and "hard",
  • 0:18 - 0:21
    by introducing what's
    called "time complexity".
  • 0:21 - 0:23
    We have all multiplied numbers before,
  • 0:23 - 0:26
    and each of us our own rules for doing so,
  • 0:26 - 0:28
    in order to speed things up.
  • 0:28 - 0:30
    If we program a computer
    to multiply numbers,
  • 0:30 - 0:33
    it can do so much faster
    than any human can.
  • 0:33 - 0:36
    Here is a graph that
    shows the time required
  • 0:36 - 0:39
    for a computer to multiply two numbers.
  • 0:39 - 0:41
    And, of course, the time
    required to find the answer
  • 0:41 - 0:44
    increases as the numbers get larger.
  • 0:44 - 0:46
    Notice that the computation time
  • 0:46 - 0:48
    stays well under one second,
  • 0:48 - 0:51
    even with fairly large numbers.
  • 0:51 - 0:53
    Therefore, it is "easy" to perform.
  • 0:53 - 0:56
    Now, compare this to prime factorization.
  • 0:56 - 1:00
    If someone told you to find
    the prime factorization of 589,
  • 1:00 - 1:03
    you will notice the problem feels harder.
  • 1:03 - 1:05
    No matter what your strategy,
  • 1:05 - 1:07
    it will require some trial and error
  • 1:07 - 1:11
    until you find a number
    which evenly divides 589.
  • 1:11 - 1:12
    After some struggle, you will find
  • 1:12 - 1:17
    19 times 31 is the prime factorization.
  • 1:17 - 1:19
    If you were told to find
    the prime factorization
  • 1:19 - 1:24
    of 437, 231, you'd probably give up
  • 1:24 - 1:26
    and get a computer to help you.
  • 1:26 - 1:28
    This works fine for small numbers,
  • 1:28 - 1:30
    though if we try to get a computer
  • 1:30 - 1:32
    to factor larger and larger numbers,
  • 1:32 - 1:35
    there is a runaway effect.
  • 1:35 - 1:37
    The time needed to
    perform the calculations
  • 1:37 - 1:41
    increases rapidly, as there
    are more steps involved.
  • 1:41 - 1:44
    As the numbers grow, the
    computer needs minutes,
  • 1:44 - 1:46
    then hours, and eventually it will require
  • 1:46 - 1:50
    hundreds, or thousands of
    years to factor huge numbers.
  • 1:50 - 1:54
    We therefore say it is a "hard" problem
  • 1:54 - 1:58
    due to this growth rate of
    time needed to solve it.
  • 1:58 - 2:00
    So factorization is what Cocks used
  • 2:00 - 2:02
    to build the trapdoor solution.
  • 2:02 - 2:05
    Step one, imagine Alice randomly generated
  • 2:05 - 2:08
    a prime number over 150 digits long;
  • 2:08 - 2:10
    call this "p one".
  • 2:10 - 2:12
    Then, a second randon prime number
  • 2:12 - 2:15
    roughly the same size; call this "p two".
  • 2:15 - 2:18
    She then multiplies
    these two primes together
  • 2:18 - 2:20
    to get a composite number, N,
  • 2:20 - 2:23
    which is over 300 digits long.
  • 2:23 - 2:27
    This multiplication step
    would take less than second;
  • 2:27 - 2:30
    we could even do it in a web browser.
  • 2:30 - 2:32
    Then, she takes the factorization of N,
  • 2:32 - 2:35
    p one times p two, and hides it.
  • 2:35 - 2:38
    Now, if she gave N to anyone else,
  • 2:38 - 2:40
    they would have to have a computer running
  • 2:40 - 2:42
    for years to find the solution.
  • 2:43 - 2:46
    Step two, Cocks needed to find a function
  • 2:46 - 2:50
    which depends on knowing
    the factorization of N.
  • 2:50 - 2:53
    For this, he looked back
    to work done in 1760
  • 2:53 - 2:57
    by Swiss mathematician, Leonhard Euler.
Τίτλος:
RSA Encryption step 3
Video Language:
English
Duration:
02:57

English subtitles

Αναθεωρήσεις