YouTube

Got a YouTube account?

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

Czech υπότιτλους

← RSA Encryption step 3

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

Showing Revision 2 created 12/10/2017 by dhbot.

  1. Před 2000 lety Eukleides dokázal,

  2. že každé číslo má jedinečný
    prvočíselný rozklad,
  3. který si můžeme představit
    jako tajný klíč.
  4. Ukazuje se, že prvočíselný rozklad
    je složitý problém.
  5. Vyjasníme si, co myslíme pojmy
    "snadný" a "složitý"
  6. pomocí tzv. časové složitosti algoritmu.
  7. Všichni umíme násobit čísla
  8. a každý z nás pro urychlení
    používá svůj vlastní postup.
  9. Pokud naprogramujeme počítač,
    aby násobil čísla,
  10. tak to může provádět
    mnohem rychleji než člověk.
  11. Zde je graf, který ukazuje kolik času potřebuje
    počítač, aby vypočetl násobek dvou čísel.
  12. Potřebný čas pro získání výsledku
    se zvyšuje s rostoucími čísly.
  13. Všimněte si, že čas pro výpočet se drží
    pod 1s i s poměrně vysokými čísly.
  14. Proto je snadné provádět násobení.
  15. Teď to porovnejte
    s prvočíselným rozkladem.
  16. Pokud by vám někdo řekl,
    abyste našli prvočíselný rozklad čísla 589,
  17. tak si hned všimnete,
    že se příklad zdá být těžší.
  18. Bez ohledu na vaši strategii to bude
    vyžadovat použití metody pokus-omyl,
  19. dokud nenajdete číslo,
    kterým lze 589 dělit.
  20. Až s tím dozápasíte, tak zjistíte,
    že prvočíselný rozklad je (19 krát 31).
  21. Pokud byste měli najít
    prvočíselný rozklad čísla 437231,
  22. tak byste to pravděpodobně
    vzdali a vzali si na pomoc počítač.
  23. Tohle funguje dobře pro malá čísla,
  24. ale pokud zkusíme rozkládat větší čísla,
    tak výsledek nebude spočítán "v rozumném čase".
  25. Čas potřebný k výpočtu rapidně
    roste s přírůstkem potřebných kroků.
  26. A jak čísla rostou, tak počítač
    potřebuje minuty a pak i hodiny.
  27. Nakonec bude potřebovat stovky nebo tisíce let
    pro prvočíselný rozklad obrovských čísel.
  28. Proto říkáme, že je to těžký problém.
    Kvůli nárůstu času potřebného k řešení.
  29. Takže prvočíselný rozklad je to, co Cocks použil
    pro vytvoření řešení se zadními vrátky.
  30. Krok 1:
  31. Alice náhodně vygeneruje prvočíslo
    přes 150 číslic dlouhé. Nazveme ho P1.
  32. Potom vygeneruje druhé náhodné prvočíslo
    o zhruba stejné velikosti. Říkejme mu P2.
  33. Pak vynásobí tyto dvě prvočísla,
  34. aby dostala složené číslo N,
    které má více než 300 číslic.
  35. Tento krok s násobením
    zabere méně než sekundu.
  36. Zvládli byste to provést dokonce
    i ve svém webovém prohlížeči.
  37. Potom vezme prvočíselný rozklad N,
    (P1 krát P2), a schová ho.
  38. I kdyby se teď N dostalo
    ke komukoliv jinému,
  39. tak by mu trvalo roky, než by na počítači
    nalezl prvočíslený rozklad N.
  40. Krok 2:
  41. Cocks potřeboval nalézt funkci, která závisí
    na znalosti prvočíselného rozkladu N.
  42. Kvůli tomu se podíval
    do práce z roku 1760,
  43. jejímž autorem byl švýcarský
    matematik Leonhard Euler.