YouTube

Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

English υπότιτλους

← RSA Encryption step 3

Πάρτε τον Κωδικό ενσωμάτωσης
8 Γλώσσες

Showing Revision 1 created 05/24/2015 by Report Bot.

  1. - [Voiceover] Over 2,000
    years ago, Euclid showed

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