Return to Video

RSA Encryption step 3

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

Czech subtitles

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