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:481초 미만인 사실을 주의 하세요.
-
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:07589와 나누어지는 수를 찾을 때 까지
-
1:07 - 1:11어느만큼의 시행착오가 필요합니다.
-
1:11 - 1:12조금 헤매다 보면 소인수분해의
-
1:12 - 1:1719 곱하기 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:20300자리가 넘는
-
2:20 - 2:23N이란 수를 얻습니다.
-
2:23 - 2:27이 곱하기 단계는 1초도 안걸리고
-
2:27 - 2:30인터넷으로도 할 수 있습니다.
-
2:30 - 2:32그다음 앨리스는 N의 소인수분해인
-
2:32 - 2:35p1과 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
Next Nhn edited Korean subtitles for RSA Encryption step 3 | ||
steven song edited Korean subtitles for RSA Encryption step 3 |