Return to Video

RSA Encryption step 3

  • 0:00 - 0:04
    Ponad 2000 lat temu Euklides wykazał,
    że każda liczba
  • 0:04 - 0:09
    ma dokładnie jeden rozkład na czynniki
    pierwsze. Uznajmy go za tajny klucz.
  • 0:09 - 0:14
    Okazuje się, że rozkład na czynniki
    pierwsze to trudny problem.
  • 0:15 - 0:18
    Wyjaśnijmy, co rozumiemy
    przez „łatwy” i „trudny”,
  • 0:18 - 0:21
    wprowadzając pojęcie
    tzw. złożoności czasowej.
  • 0:21 - 0:23
    Każdy z nas mnożył liczby
  • 0:23 - 0:27
    i ma własne sposoby,
    żeby to przyspieszyć.
  • 0:28 - 0:30
    Odpowiednio zaprogramowany komputer
  • 0:30 - 0:33
    będzie mnożył liczby
    znacznie szybciej niż człowiek.
  • 0:33 - 0:37
    Na wykresie przedstawiono
    czas potrzebny komputerowi
  • 0:37 - 0:39
    do pomnożenia dwu liczb.
  • 0:39 - 0:42
    Czas potrzebny
    do znalezienia odpowiedzi
  • 0:42 - 0:45
    wydłuża się wraz ze wzrostem liczb.
  • 0:45 - 0:47
    Zauważcie, że czas obliczeniowy
  • 0:47 - 0:51
    jest znacznie krótszy od sekundy
    nawet przy dużych liczbach.
  • 0:51 - 0:53
    Dlatego wykonanie jest „łatwe”.
  • 0:53 - 0:56
    Porównajmy to z rozkładem
    na czynniki pierwsze.
  • 0:56 - 1:00
    Gdyby ktoś kazał wam
    rozłożyć liczbę 589,
  • 1:00 - 1:03
    od razu byście wiedzieli,
    że będzie trudno.
  • 1:03 - 1:05
    Niezależnie od obranej strategii,
  • 1:05 - 1:08
    metodą prób i błędów
    będziecie szukać liczby,
  • 1:08 - 1:11
    przez którą
    bez reszty dzieli się 589.
  • 1:11 - 1:16
    Pomęczycie się trochę i ustalicie,
    że ten rozkład to 19 razy 31.
  • 1:17 - 1:23
    Gdyby kazano wam rozłożyć
    na czynniki pierwsze liczbę 437231,
  • 1:23 - 1:26
    zapewne poddalibyście się
    i zaprzęgli do pomocy komputer.
  • 1:27 - 1:29
    Uda się to przy małych wartościach,
  • 1:29 - 1:33
    ale gdy każemy komputerowi
    rozkładać coraz większe liczby,
  • 1:33 - 1:34
    wystąpi efekt lawiny.
  • 1:35 - 1:37
    Czas potrzebny do wykonania obliczeń
  • 1:37 - 1:41
    będzie rósł bardzo szybko,
    bo jest więcej etapów.
  • 1:41 - 1:46
    W miarę wzrostu liczb, komputer
    będzie potrzebował minut, godzin…
  • 1:46 - 1:48
    aż wreszcie - setek lub tysięcy lat,
  • 1:48 - 1:50
    by przeprowadzić
    rozkład ogromnych liczb.
  • 1:51 - 1:53
    Dlatego zadanie nazwiemy trudnym,
  • 1:54 - 1:57
    z powodu czasu potrzebnego
    na znalezienie rozwiązania.
  • 1:57 - 2:02
    Rozkładu na czynniki pierwsze
    użył Cocks w rozwiązaniu zapadkowym.
  • 2:02 - 2:06
    Krok pierwszy: że Alicja losowo
    wygenerowała liczbę pierwszą
  • 2:06 - 2:10
    o długości ponad 150 cyfr.
    Nazwijmy ją P1.
  • 2:10 - 2:15
    Wygenerowała kolejną liczbę pierwszą,
    podobnej wielkości; nazwiemy ją P2.
  • 2:15 - 2:18
    Teraz mnoży te liczby pierwsze
  • 2:18 - 2:21
    i uzyskuje liczbę złożoną N,
  • 2:21 - 2:23
    mającą ponad 300 cyfr.
  • 2:24 - 2:27
    Mnożenie potrwa mniej niż sekundę;
  • 2:27 - 2:30
    poradzi sobie z nim
    nawet przeglądarka internetowa.
  • 2:30 - 2:32
    Potem Alicja
    bierze czynniki pierwsze N,
  • 2:32 - 2:35
    czyli P1 razy P2, i ukrywa je.
  • 2:36 - 2:38
    Gdyby podała komuś N,
  • 2:38 - 2:42
    przez wiele lat
    komputerowo szukałby rozwiązania.
  • 2:43 - 2:46
    Krok drugi:
    Cocks musiał znaleźć funkcję,
  • 2:46 - 2:50
    która zależy od tego, czy znamy
    rozkład N na czynniki pierwsze.
  • 2:50 - 2:53
    Sięgnął więc do opublikowanej
    w 1760 roku pracy
  • 2:53 - 2:57
    szwajcarskiego matematyka
    Leonharda Eulera.
Title:
RSA Encryption step 3
Video Language:
English
Duration:
02:57
Lech Mankiewicz edited Polish subtitles for RSA Encryption step 3

Polish subtitles

Revisions

Our website uses cookies for analysis purposes.