[Powered by Google Translate] [RSA]는
[롭 보덴] [토미 MacWilliam] [하버드 대학]
[이 CS50 수 있습니다.] [CS50.TV]
가 RSA, 데이터 암호화를위한 널리 사용되는 알고리즘을 살펴 보자.
시저와 Vigenère의 암호와 같은 암호화 알고리즘은 매우 안전하지 않습니다.
카이사르 암호문으로, 공격자는 25 서로 다른 키를 시도 할 필요가
메시지의 일반 텍스트를 할 수 있습니다.
Vigenère의 암호 시저 암호보다 안전하지만
때문에 키 큰 검색 공간을 한 번 공격자
, Vigenère의 암호로 키의 길이를 알고
어떤은 암호화 된 텍스트의 패턴의 분석을 통해 결정될 수
Vigenère의 암호가 훨씬 더 안전 카이사르 암호문보다하지 않습니다.
RSA는 반면에,이 같은 공격에 취약하지 않습니다.
카이사르 암호문과 Vigenère 암호 같은 키를 사용
암호화 및 해독 메시지가 모두 있습니다.
이 속성은이 암호 대칭 키 알고리즘을합니다.
대칭 키 알고리즘 근본적인 문제
그들은 메시지를 암호화하고 보내는 하나에 의존하고 있습니다
그리고 하나는 수신하고 메시지를 해독
이미 둘 다 사용 키에 선행을 동의합니다.
하지만 우리는 여기서 시작 문제가 좀 있습니다.
어떻게 의사 소통을하려면 2 대의 컴퓨터는 그들 사이의 비밀 키를 구축합니까?
키가 비밀해야하는 경우, 우리는 키를 암호화하고 암호를 해독 할 수있는 방법이 필요합니다.
우리가 모든 대칭 키 암호화하는 경우
다음에 우리가 같은 문제로 다시 왔어요.
RSA는 반면에, 키 쌍을 사용하여
해독을위한 암호화 및 다른 한.
하나는 공개 키라고, 다른 하나는 개인 키입니다.
공개 키는 메시지를 암호화하는 데 사용됩니다.
당신이 그 이름으로 추측 하듯이, 우리는과의 공개 키를 공유 할 수 있습니다
우리가 암호화 된 메시지의 보안을 손상시키지 않고 싶은 사람.
메시지는 공개 키를 사용하여 암호화
만 해당 개인 키를 해독 할 수 있습니다.
귀하의 공개 키를 공유 할 수 있지만, 당신은 항상 개인 키 비밀을 유지해야합니다.
만 개인 키를 해독 메시지에 사용할 수 있습니다
이 사용자는 RSA와 메시지 암호화 보내려면
앞뒤로 두 사용자는 자신의 공개 및 개인 키 쌍을 필요합니다.
사용자 1 사용자 2 메시지
전용 사용자 2 사용자 1 사용자 2의 키 쌍, 및 메시지를 사용
전용 사용자 1의 키 쌍을 사용합니다.
2 개의 암호화 키와 해독 메시지가 있다는 사실
RSA 비대칭 키 알고리즘합니다.
우리는 다른 컴퓨터에 메시지를 보내려면 공개 키를 암호화 할 필요가 없습니다
키는 어쨌든 대중 때문입니다.
이 RSA는 같은 시작 문제가없는 것을 의미합니다
대칭 키 알고리즘 있습니다.
나는 RSA 암호화를 사용하여 메시지를 보내하고 싶다면
롭, 처음 롭의 공개 키가 필요합니다.
키 쌍을 생성하려면, 롭은 2 개의 대형 소수의 숫자를 선택해야합니다.
이 번호는, 모두 공공 및 민간 키에 사용됩니다
하지만 공개 키는이 두 숫자의 제품을 사용합니다
아니라 숫자 자체.
일단 로브의 공개 키를 사용하여 메시지를 암호화 한
나는 롭 메시지를 보낼 수 있습니다.
컴퓨터를 들어, 율도 번호는 어려운 문제입니다.
공개 키는 기억이 소수의 제품을 사용했습니다.
이 제품은 다음 단 2 가지 요소가 있어야합니다
개인 키를 구성하는 숫자로 발생된다.
해독 메시지에 위해 RSA는 개인 키를 사용합니다
또는 번호는 공개 키를 만드는 과정에 함께 곱.
이 수를 고려해야 계산 힘들어서
개인 키에 사용되는 2 개의 숫자로 공개 키에 사용
공격자가 개인 키를 알아내는 것이 어렵습니다
해독에 메시지가 필요 할 것입니다.
이번에는 RSA의 일부 낮은 수준의 세부 정보로 가자.
자, 먼저 우리가 키 쌍을 생성 할 수있는 방법을 참조하십시오.
첫째, 우리는이 소수의 숫자가 필요합니다.
우리는이 두 숫자 P와 Q 전화 할게.
실제로 P와 Q를 선택하기 위해 우리는 pseudorandomly 발생합니다
그리고 많은 수의하고 결정하기위한 검사의 사용 여부와 관계없이
그 숫자는 아마 소수이다.
우리는 다시 이상 임의의 숫자를 생성 유지할 수
우리는 우리가 사용할 수있는 두 primes이 때까지.
여기가 P = 23 Q = 43 찍게하고.
실제로, 기억, P와 Q가 훨씬 더 큰 숫자 여야합니다.
우리가 아는 바와 같이, 숫자 큰, 더 그렇죠
암호화 된 메시지를 해독합니다.
그러나 또한 암호화 및 해독 메시지에 더 비싸요.
오늘은이 종종 P와 Q가 적어도 1024 비트 것을 권장하는 것은,
이는 300여 자릿수에 각 번호를 넣습니다.
그러나 우리는이 예에 대해 이러한 작은 숫자를 선택합니다.
지금 우리는 제 3 수를 함께 P와 Q를 곱합니다
우리는 N 부를된다.
우리의 경우, N = 23 1989 = * 43,.
우리는 = 1989 습니했습니다.
Q와 함께 1 - - 다음 우리는 P를 곱합니다 1
우리가 m 부를 네번째 숫자를. 구하는 방법
우리의 경우, m = 22 924를 = * 42.
우리는 m = 924이 있습니다.
이제 우리는 상대적으로 소수 숫자 전자가 필요합니다 m
그리고 m 이내 거리에 있습니다.
두 숫자는 상대적으로 소수 또는 coprime 아르
모두 균등을 분할하는 유일한 양의 정수는 1 인 경우.
E와 M의 즉, 최대 공약수
하나이어야합니다.
실제로, 그것은 소수 65,537 할 전자에 대한 일반적
만큼이 수치는 m의 요소로 발생하지 않습니다.
우리의 키를 들어, 우리는 갈 게요 E = 5
5부터 924 상대적으로 소수입니다.
마지막으로, 우리는 우리가 D 부를 한 곡 더 필요합니다.
D는 방정식을 만족하는 어떤 값이어야합니다 드 = 1 (MOD m).
이 모드에서 m은 우리가 모듈 산술이라는 것을 사용합니다 의미합니다.
모듈 산술에서 한 번에 숫자가 일부 상위 바운드보다 더 도착
는 0으로 주변을 다시 줄 바꿈됩니다.
시계가 예를 들어, 모듈 형 산술을 사용합니다.
1시 59분 후 잠시만 요, 예를 들어, 2 시야
1:60 없습니다.
분침은 0으로 주변에 포장했다
60 행 상부에 도달시.
그래서, 우리는 우리가 60 0 (MOD 60)와 동일합니다 말할 수
그리고 125이 65에 해당 것은 5 일 (MOD 60)와 동일합니다.
공개 키는 쌍 전자와 N 것입니다
이 경우 전자는 5이며, n은 989입니다.
우리 개인 키는 쌍 D와 N 것입니다
우리의 경우에 이것은 185과 989입니다.
오리지널 primes P와 Q가 표시되지 않는 것을 알
어디서든 우리의 비공개 또는 공개 키 인치
이제 키의 쌍을 가지고, 그럼 우리가 암호화 할 수있는 방법을 살펴 보자
및 해독 메시지가 나타납니다.
나는 롭에게 메시지를 보낼
그래서 그는이 키 쌍을 생성 할 수있는 하나가 될 것입니다.
그래서 내가 사용할 자신의 공개 키에 대한 롭를 요청할 것
그에게 보낼 메시지를 암호화합니다.
롭이 날 자신의 공개 키를 공유하는 기억, 너무 괜찮아요.
그러나 그의 개인 키를 공유 괜찮아 질 않습니다.
나는 그의 개인 키가 뭔지 짐작이 없습니다.
우리는 여러 그룹으로의 메시지 m을 깰 수
모든 다음에 n보다 작고 그 덩어리의 각을 암호화합니다.
우리는 4 그룹으로 헤어지고 할 수있는 문자열 CS50을, 암호화됩니다
문자 당 하나의.
내 메시지를 암호화하기 위해, 나는로 변환해야합니다
숫자 표현의 일종.
의 내 메시지의 문자를 ASCII 값을 연결하여 보자.
주어진 메시지 m을 암호화하기 위하여
나는 전자 (MOD N)에 C = m을 계산해야합니다.
그러나 m은 N보다 작아야합니다
그렇지 않으면 전체 메시지는 모듈로 n을 표현 할 수 없습니다.
우리는 N보다 작은 모든 필드는 여러 덩어리,에 m을 깰 수
그리고 그 덩어리의 각을 암호화합니다.
이 덩어리를 각각 암호화, 우리가받을 C1 5 = 67 (MOD 989)
있는 = 658.
두 번째 덩어리를 우리는 5 일 (모드 989)에 83이
어떤 = 15.
세 번째 덩어리를 우리는 5 일 (모드 989)에 53이
있는 = 799.
그리고 마지막으로, 우리의 마지막 덩어리를 우리는 5 일 (모드 989) 48이
이는 975을 =.
이제 우리는 롭 이러한 암호화 값을 통해 보낼 수 있습니다.
여기 롭 이동합니다.
우리의 메시지가 비행하는 동안의 또 다른 모습을 봅시다
방법에 대해 우리는 d의 그 가치가있다 구.
우리 번호를 d는 5 일 = 1 (MOD 924)을 만족해야했습니다.
이 D 5 모듈로 924의 multiplicative 역 수 있습니다.
두 정수, a와 b, 확장 유클리드 알고리즘을 감안할 때
이 두 정수의 최대 공약수를 찾는 데 사용하실 수 있습니다.
또한 우리에게이 다른 번호, x와 y를 제공합니다
그 a와 b의 = 최대 공약수하여 방정식 도끼 +를 만족.
어떻게 이런 일이 우리를 도와합니까?
음,에 대한 전자에 = 5를 연결해
와 B에 대한 m = 924
우리는 이미이 숫자가 coprime 않고 있다는 것도 알고있다.
이들의 최대 공약수는 1입니다.
이 + 924y = 1 우리에게 5 배를 제공합니다
또는 5 배 = 1 - 924y.
그러나 우리는 모든 모듈로 924을 배려한다면
924y - 그러면 우리는을 드롭 할 수 있습니다.
시계로 생각합니다.
분침은 1에 다음 정확히 10 시간, 통과하는 경우
우리는 분 손이 여전히 1 될 것입니다 알아요.
여기 우리는 1에서 시작하고 정확히 Y 시간을 주위에 포장
그래서 우리는 여전히 1에 있습니다.
우리는 = 1 (MOD 924)를 5 배 있습니다.
그리고 여기이 x는, 우리가 전에 찾고있는 D와 동일합니다
우리는 확장 유클리드 알고리즘을 사용하도록하는 경우
이 숫자 x를 얻으려면 우리가 우리의 D로 사용할 수 있습니다.
이제 한 = 5 확장 유클리드 알고리즘을 실행하게
및 b = 924.
우리는 테이블 방식이라는 방법을 사용합니다.
우리 테이블은 4 열, X, Y, D 및 K를해야합니다.
우리 테이블은 2 개의 행으로 시작합니다.
첫 번째 행에서 우리는 1, 0, 5 우리의 가치를,이
우리의 두 번째 행은 0, 1, 및 B에 대한 값이되는데,이 924입니다.
4 열, K,의 값은 결과입니다
D의 값과 함께 위의 행에 D의 값을 나누지
같은 행에.
우리는 924으로 나눈 5 일부 나머지 0이 있습니다.
우리가 = 0 K 있다는 것을 의미합니다.
지금 다른 모든 셀의 값은 위의 셀이 행의 값이 될것이다
그 배 K 위의 행의 마이너스 값입니다.
3 행에서 D로 시작하자.
우리는 5가 - 924 * 0 = 5.
0 1 * 0 - 우리는 0이 다음
그리고 1-0 * 0 어떤은 1입니다.
그리 나쁘지는 않아 그러니, 다음 행으로 이동하세요.
처음에 우리는 K의 가치가 필요합니다.
924, 어떤 나머지 5 개 = 184으로 나눈 값
그래서 K에 대한 값은 184입니다.
지금 924-5 * 184 = 4.
1-0 * 184은 1입니다 0 - 1 * 184는 -184입니다.
좋아, 다음 행을 해보자 구.
K 당사의 값은 1 때문에 수
5 일부 나머지 갖춘 4 = 1로 나눈 값입니다.
의가 다른 열을 입력 보자.
5-4 * 1 = 1.
0-1 * 1 = -1.
그리고 1-184 * 1 85이다.
K 우리의 다음 값이 될 알아 보자.
우리가 4 1으로 4 분할있는 것 같아.
우리가 1 분할하고이 경우에는 그 k는 같다
위의 행의 D의 값은 우리가 우리의 알고리즘을 완료 있다는 것을 의미합니다.
우리는 마지막 행에 X = 185와 y = -1 것으로 볼 수 있습니다.
의 지금의 원래 목표로 돌아와 보자.
우리는의 결과로 x의 값이 알고리즘을 실행했다
(MOD B)의 multiplicative 역이 될 것입니다.
그래서 185의 5 multiplicative 역 (MOD 924)을 의미합니다
그건 우리가 d의 185의 값을 가지고 있다는 것을 의미합니다.
사실 그 D = 1의 마지막 행에
그 전자가 m에 coprime되었습니다 확인합니다.
이 1 아니었다한다면 우리는 새로운 전자를 선택해야합니다.
지금 롭 내 메시지를받은 경우 보자.
누군가가 나에게 암호화 된 메시지를 보낼 때
그 동안 내 개인 키의 비밀을 유지 한대로
나는 메시지를 해독 할 수있는 유일한 사람이야.
해독 덩어리를 C 나는 원래 메시지를 계산할 수
D 전력 (모드 N)에 덩어리와 동일합니다.
d와 n은 내 개인 키에서 것을 기억하십시오.
우리 해독 각 덩어리의 덩어리에서 전체 메시지를 얻으려면
그 결과를 연결.
RSA는 정확히 어떻게 안전합니까?
사실, 우리는 몰라요.
보안은 메시지를 해독하기 위해 공격자가 얼마나 걸릴 기반으로
RSA로 암호화.
공격자가 사용자의 공개 키에 액세스 할 수있는 기억,
이는 전자와 N을 모두 포함하고 있습니다.
공격자는이 primes, P와 Q로 n을 반영하기 위해 관리하는 경우
그리고는 확장 유클리드 알고리즘을 사용하여 d를 계산 수 있습니다.
이 그녀에게 어떤 메시지를 해독하는 데 사용할 수있는 개인 키를 제공합니다.
그러나 얼마나 빨리 우리는 정수를 반영 할 수 있습니까?
다시 말하지만, 우리는 몰라요.
아무도 그 일을의 빠른 방법을 찾을 수 없었습니다
이는 주어진 것을 의미 충분히 큰 N
이 unrealistically 긴 공격자 걸릴거야
수를 반영합니다.
사람을 고려해 정수의 빠른 방법을 공개하는 경우
RSA가 고장됩니다.
그러나 경우에도 정수 인수 분해는 본질적으로 느립니다
RSA 알고리즘은 여전히​​ 일부 결함을 가질 수
그 메시지를 쉽게 해독 할 수 있습니다.
아무도 아직 이러한 결함을 발견하지 않고 밝혔다
하지만 그 사람이 존재하지 않는 것은 아닙니다.
이론적으로, 누군가가 RSA로 암호화 모든 데이터를 읽고 거기에있을 수 있습니다.
개인 정보 보호 문제의 또 다른 비트가 있습니다.
토미는 내 공개 키를 사용하여 일부 메시지를 암호화하는 경우
그리고 공격자는 공개 키를 사용하여 동일한 메시지를 암호화
공격자는 2 개의 메시지가 동일한 것을 볼 수 있습니다
그래서 토미가 암호화 알아.
이러한 문제를 방지하기 위해, 메시지는 일반적으로 임의의 비트와 함께 패드를 물렸다 아르
동일한 메시지가 암호화되도록 암호화되기 전에
메시지에 패딩이 다른이기 때문에 여러 번에 한해 다르게됩니다.
하지만 우리가 그룹으로 메시지를 분할해야하는 기억
각 청크가 N보다 작 있도록?
기억을 패딩은 우리가 일을 분할해야 할 수도 있습니다 것을 의미합니다
이후 더 많은 그룹으로 패딩 덩어리가 N보다 작아야합니다.
암호화 및 암호 해독, RSA와 상대적으로 비싸다
그렇게 많은 그룹으로 메시지를 헤어지게 할 필요 것은 매우 치명타가 될 수 있습니다.
데이터의 큰 볼륨을 암호화 할 필요가 및 복호화하는 경우
우리는 대칭 키 알고리즘의 장점을 결합 할 수 있습니다
RSA의 사람들과 보안과 효율성을 모두 가져옵니다.
우리는 여기로 이동하지 않습니다 만,
AES는 Vigenère와 카이사르 암호와 같은 대칭 키 알고리즘입니다
하지만 훨씬 더 구먼.
물론, 우리는 공유 비밀 키를 설정하지 않고 AES를 사용할 수 없습니다
2 시스템 사이에, 우리는 전에 그와 관련된 문제를 보았다.
하지만 지금 우리는 2 시스템 간의 공유 비밀 키를 구축하기 위해 RSA 사용할 수 있습니다.
우리는 데이터에게 보낸을 보내 컴퓨터를 전화 할게요
와 컴퓨터가 데이터에게 리시버를 수신.
수신기는 RSA 키 쌍을 보유하고 전송
보낸 사람의 공개 키.
보낸 사람은 AES 키를 생성
수신기의 RSA 공개 키와 함께 암호화
그리고 수신기에 AES 키를 보냅니다.
수신기는 RSA 개인 키와 메시지를 해독합니다.
발신자와 수신기 모두 지금 사이에 공유 AES 키가 있습니다.
RSA보다 암호화 및 해독에 훨씬 빠른 AES,
이제 데이터의 큰 볼륨을 암호화하고 수신자에게 보낼 수 있습니다,
해독은 동일한 키를 누가 사용하실 수 있습니다.
RSA보다 암호화 및 해독에 훨씬 빠른 AES,
이제 데이터의 큰 볼륨을 암호화하고 수신자에게 보낼 수 있습니다,
해독은 동일한 키를 누가 사용하실 수 있습니다.
우리는 공유 키를 전송하는 RSA 필요했습니다.
우리는 더 이상 전혀 RSA를 사용할 필요가 없습니다.
나는 메시지가 있어요 것 같습니다.
사람이 종이 비행기에 어떤 읽는 경우가 잡기 전에 그건 중요하지 않아요
나는 개인 키가있는 유일한 사람이야 때문입니다.
메시지에서 덩어리의 각 암호를 해독하자.
첫 번째 청크, 658, 우리는 185 D 파워로 인상
989이 모드 n은,,, 67와 동일합니다
ASCII의 문자 C가되는 것입니다.
이제 두 번째 청크로.
두 번째 덩어리가 가치 15가
우리는 1백85번째 전원을 모금, 그
MOD 1989이 83과 동일
ASCII에서 문자 S하는 것입니다.
지금 값이 799이 세 번째 청크에 대해, 우리는 185로 증가
MOD 1989이 53와 같다,
ASCII의 문자 (5)의 값은하는 것입니다.
이제 마지막 덩어리를, 즉, 가치 975이
우리는, 185에 MOD 989을 능가
이는 ASCII의 문자 0 값이 48와 동일합니다.
내 이름은 롭 보덴 있으며,이 CS50입니다.
[CS50.TV]
전혀 RSA.
전혀 RSA. [웃음]
천만에.