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

## ← RSA Encryption step 3

• 1 Οπαδός
• 63 Γραμμήs

### Πάρτε τον Κωδικό ενσωμάτωσης x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=cJvoi0LuutQ" data-team="null"></div> ``` 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
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
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.