2010년 3월 11일 목요일

05. 확장된 유클리드 알고리즘(Extended euclidean algorithm)

활용
- 공개키 암호화 알고리즘에서 비밀키를 알아내기 위해 사용.
- 공개키 암호화 알고리즘의 가장 어려운 부분은 큰 두 소수의 곱을 가지고, 두개의 소수를 유추해 내는 것이다.
- 즉, p*q=N 일 때, p와 q의 값을 알 때, N은 쉽게 구할 수 있다. 하지만, N을 값 만으론 p와 q를 유추해 내기 어렵다.

RSA 공개키/비밀키 생성방법 요약
① 두 개의 서로 다른 소수 p, q 선택.
② p * q를 공용키로 선택
③ (p - 1)(q - 1)의 값과 서로 소인 임의의 정수 e를 선택해서 공개키로 사용.
④ e와 서로소인 d를 선택해서 비밀키로 사용. ed≡1 (mod (p-1)*(q-1))
∵ 확장된 유클리드 알고리즘을 사용해서 비밀키를 생성 할 수 있다.

정의
- ap + bq = GCD(p, q) 식에서 a와 b를 구 할 수 있다.

예제
① 두 개의 서로 다른 소수 p, q 선택. p = 17, q = 37
② (p - 1)(q - 1)과 서로소인 임의의 정수 e를 선택. e = 31
③ GCD((p - 1)(q - 1), 31) => GCD(576, 31)
GCD(576, 31) => 576 = 31 * 18 + 18
GCD(31, 18) => 31 = 18 * 1 + 13
GCD(18, 13) => 18 = 13 * 1 + 5
GCD(13, 5) => 13 = 5 * 2 + 3
GCD(5, 3) => 5 = 3 * 1 + 2
GCD(3, 2) => 3 = 2 * 1 + 1
=>
① 1 = 3 - 2
= 3 - (5 - 3) => 2 * 3 - 5
= 2 * ( 13 - 5 * 2 ) - 5 => 2 * ( 13 ) - 5 * 5
= 2 * 13 - 5 * ( 18 - 13 ) => -5 * ( 18 ) + 7 * 13
= -5 * 18 + 7 * ( 31 - 18 ) => 7 * 31 - 12 * ( 18 )
= 7 * 31 - 12 * ( ( 576 - (31 * 18) ) ) => -12 * 576 + 223 * 31
② -12 * 576 + 223 * 31에서 사고를 확장해 보았을 때, 223 * 31≡1(mod 576)을 알 수 있다. 576은 (p-1)(q-1)의 값.
※ 증명
ⓐ a≡r (mod p) 이면. a = p*x + r 양변에 p를 더해 준다면 => a + p = p* (x + 1) + r 로 나머지 값은 변화가 없음을 알 수 있다.
ⓑ -12 * 576은 무시할 수 있다.
③ 이제 비밀키 선택 알고리즘에서 ed≡1 (mod (p-1)*(q-1)) d의 값을 구할 수 있다. 223 * 31≡1(mod 576)
∵ 비밀키는 223

댓글 1개: