Return to Video

RSA Encryption step 3

  • 0:00 - 0:02
    유클리드는 2000년 전에
  • 0:02 - 0:06
    모든 숫자는 하나의 소인수분해
    밖에 없다고 증명했고
  • 0:06 - 0:09
    우리는 이가 비밀의 "열쇠"라고
    생각할 수 있습니다.
  • 0:09 - 0:11
    소인수분해는 사실
  • 0:11 - 0:14
    어려운 문제입니다.
  • 0:14 - 0:18
    일단 쉬운것과 어려운것을
  • 0:18 - 0:21
    "시간의 복잡성"을 통해 정의 해 봅시다.
  • 0:21 - 0:23
    우린 모두 수를 곱한 적이 있고
  • 0:23 - 0:26
    계산을 빨리 하기 위해 나름의
  • 0:26 - 0:28
    규칙을 쓰기도 하죠.
  • 0:28 - 0:30
    반면에 컴퓨터를 수를 곱하기 위해
    프로그래밍을 하면
  • 0:30 - 0:33
    인간보다 월등히 빨리 계산할 수 있게
    됩니다.
  • 0:33 - 0:36
    이는 컴퓨터가 두 수를 곱하기 위해
    필요한 시간을
  • 0:36 - 0:39
    표시하는 그래프입니다.
  • 0:39 - 0:41
    그리고 당연히 수가 커질수록
  • 0:41 - 0:44
    계산하는 시간도 늘겠죠.
  • 0:44 - 0:46
    여기서 계산하는 시간이
  • 0:46 - 0:48
    1초 미만인 사실을 주의 하세요.
  • 0:48 - 0:51
    아무리 수가 커져도 마찬가지입니다.
  • 0:51 - 0:53
    그래서 이 문제는 "쉬울"겁니다.
  • 0:53 - 0:56
    이제 소인수분해의 문제와 비교해
    봅시다.
  • 0:56 - 1:00
    누군가가 589란 숫자를 소인수분해
    하라고 시키면
  • 1:00 - 1:03
    훨씬 어려운 문제로 느낄겁니다.
  • 1:03 - 1:05
    어떤 전략을 써도라도
  • 1:05 - 1:07
    589와 나누어지는 수를 찾을 때 까지
  • 1:07 - 1:11
    어느만큼의 시행착오가 필요합니다.
  • 1:11 - 1:12
    조금 헤매다 보면 소인수분해의
  • 1:12 - 1:17
    19 곱하기 39가 나올겁니다.
  • 1:17 - 1:19
    이제 다시 437,231란 숫자를
    소인수분해하라고
  • 1:19 - 1:24
    시키면 아마도 포기하고
  • 1:24 - 1:26
    컴퓨터를 사용할 겁니다.
  • 1:26 - 1:28
    작은 숫자에겐 괜찮지만
  • 1:28 - 1:30
    더욱 큰 수를 컴퓨터에게
  • 1:30 - 1:32
    소인수분해하라고 하면
  • 1:32 - 1:35
    "달아나는"현상이 나타납니다.
  • 1:35 - 1:37
    이 계산을 하기 위해 필요한 시간은
  • 1:37 - 1:41
    수에 따라 급격히 증가합니다.
  • 1:41 - 1:44
    수가 증가하는 만큼 컴퓨터는
    몇분,
  • 1:44 - 1:46
    몇 시간, 그리고 결국엔
  • 1:46 - 1:50
    백, 또는 천년이 소인수분해하기 위해
    필요합니다.
  • 1:50 - 1:54
    따라서 이런 문제는 "어렵"다고 말하죠.
  • 1:54 - 1:58
    왜냐하면 이러한 시간의 상승률이 있기
    때문입니다.
  • 1:58 - 2:00
    그래서 콕스는 트랩도어의의
    해결책을
  • 2:00 - 2:02
    소인수분해를 사용해 썼습니다.
  • 2:02 - 2:05
    첫째, 알리스가 150자리의
    소수를
  • 2:05 - 2:08
    무작위로 생산하고
  • 2:08 - 2:10
    이를 p1이라고 부릅니다.
  • 2:10 - 2:12
    그리고 크기가 비슷한
  • 2:12 - 2:15
    둘째의 소수 p2를 생산합니다.
  • 2:15 - 2:18
    그리고 이 두 소수를 곱해서
  • 2:18 - 2:20
    300자리가 넘는
  • 2:20 - 2:23
    N이란 수를 얻습니다.
  • 2:23 - 2:27
    이 곱하기 단계는 1초도 안걸리고
  • 2:27 - 2:30
    인터넷으로도 할 수 있습니다.
  • 2:30 - 2:32
    그다음 앨리스는 N의 소인수분해인
  • 2:32 - 2:35
    p1과 p2를 숨깁니다.
  • 2:35 - 2:38
    그리고 N을 누구한테도 줘도
  • 2:38 - 2:40
    그들은 소인수분해를 찾기위해
  • 2:40 - 2:42
    몇년간 컴퓨터를 돌려야 됩니다.
  • 2:43 - 2:46
    둘째, 콕스는 N의 소인수분해에
  • 2:46 - 2:50
    의존하는 함수가 필요했습니다.
  • 2:50 - 2:53
    그리고 이를 위해 콕스는
    1760년대 스위스 수학자
  • 2:53 - 2:57
    레온하르트 오일러의 정의를 찾아보았습니다
Title:
RSA Encryption step 3
Video Language:
English
Duration:
02:57

Korean subtitles

Revisions

Our website uses cookies for analysis purposes.