확장 유클리드 알고리즘

m, n이 gcd(m,n) = 1인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.
출처 : 위키백과

확장 유클리드 알고리즘은 RSA를 만들기 위한 과정 중 복호키(또는 비밀키 라고도 부른다)를 구하기 위해 필요한 알고리즘이다.
일단 지금은 이 정도만 알고 넘어가도록 하자.

확장 유클리드 알고리즘은 정말 단순히 유클리드 알고리즘(gcd)연산을 거꾸로 한 것이다.
수식으로 설명을 들어보자,

a , b = 서로소인 두 정수(알기 쉽게 설명하기 위해서 서로소로 정했다\\ 원래는 어떤 수 라도 상관 없다.)
r(1),r(2),r(3)… = 나머지
q(1),q(2),q(3)… = 몫

라고 하면, 유클리드 알고리즘은

gcd(a,b)
=> a = b*q(1) + r(1)           >> gcd(b,r(1))
=> b = r(1)*q(2) + r(2)       >> gcd(r(1),r(2))
=> r(1) = r(2)*q(3) + r(3)   >> gcd(r(2),r(3))
……
=> r(n-1) = r(n)*q(n+1) + r(n+1)     >> gcd(r(n),r(n+1))
=> r(n) = r(n+1)*q(n+2) + 1             >> gcd(r(n+1),r(n+2))
=> r(n+1) = 1*r(n+1) + 0                  >> gcd(1,0)
∴ gcd(a,b) = 1

이렇게 진행 된다.

=====================================================

이제 확장된 유클리드 알고리즘 이용해 보자.
방법은 단순히 위에 연산을 거꾸로하고 대입하여 한 식으로 계산하면 된다, 아래를 참고하자.

[원래는 1 부터지만 거꾸로 계산했다는 것을 보여주기 위해 0부터 시작하겠다.]
0 = r(n+1) – 1*r(n+1) <=> r(n+1) = 1*r(n+1) + 0
1 = r(n) – r(n+1)*q(n+2) <=> r(n) = r(n+1)*q(n+2) + 1
r(n+1) = r(n-1) – r(n)*q(n+1) <=> r(n-1) = r(n)*q(n+1) + r(n+1)
……
r(3) = r(1) – r(2)*q(3) <=> r(1) = r(2)*q(3) + r(3)
r(2) = b – r(1)*q(2) <=> b = r(1)*q(2) + r(2)
r(1) = a – b*q(1)  <=> a = b*q(1) + r(1)

이제 거꾸로 구한 식을 한 식에 모두 대입하자. (복잡하니 n = 2 라고 두자)  (a, b, q(),r() 은 모두 상수 이다. )

[“0 = ~”은 양변이 모두 0 이므로 사용 할 수 없으니 “1 = ~”를 사용했다]
1 = r(2) – [r(1) – [b – [a – b*q(1)]*q(2)]*q(3)]*q(4)

이렇게 식을 만들고 정리 하면 1 = ☆×a + ★×b  이런 모양이 된다.

∴   1 ≡ ☆×a + ★×b (mod a) 라면, ★값이 역원(우리가 찾는 값) 이고
　  1 ≡ ☆×a + ★×b (mod b) 라면, ☆ 값이 역원 이다.

즉, mod a 라면 b에 곱해진 수가 역원 mod b라면 그 반대 라는 것이다.

(∵  A≡R (mod P) 이면. A = A*X + R 양변에 P를 더해 준다면 => A + P = P* (X + 1) + R이다.
따라서 나머지(다른)값은 변화가 없음으로, 위에서 mod a 일때, ☆×a 값을 무시 할 수 있다.)

자 이렇게 확장 유클리드 알고리즘에 대한 기본 설명은 끝났다.

이해가 잘 가지 않을 수도 있으니 간단한 예를 들어보자.

a = 576, b = 31

유클리드 알고리즘

576 = 31 × 18 + 18
31 = 18 × 1 + 13
18 = 13 × 1 + 5
13 = 5 × 2 + 3
5 = 3 × 1 + 2
3 = 2 × 1 + 1         ∴ gcd(576,31) = 1, 서로소 이다.

확장 유클리드 알고리즘(빠르게 계산 하기 위해 바로 “1 = ~”으로 시작하겠다.)

1 = 3 – 2 × 1
   = 3 – [5 – 3 × 1] × 1
   = 3 – [5 – [13 – 5 × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – 13 × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – 18 × 1] × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – [576 – 31 × 18] × 1] × 1] × 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 ≡ 1 (mod 576)
∴ 역원(우리가 찾는 값)은 223 이다.

 

위 알고리즘을 이용해 C언어로 코딩 하기전에 잠깐 생각해야 되는 부분이 있다.
우리가 필요한 값은 결과로 나오는 1 = ☆×a + ★×b 중에서 ☆or★이라는 점을 기억 해야 한다.

이제 한번 코딩해 보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

INT inverse(INT a, INT b) {
	long r1, r2, q, r, t, t1, t2;
	r1 = a;
	r2 = b;
	t1 = 0; t2 = 1;

	while (r1 != 1)
	{
		q = r2 / r1;
		r = r2 - r1*q;
		t = t1 - t2*q;
		r2 = r1;
		r1 = r;
		t1 = t2;
		t2 = t;
	}
	if (t2 < 0)
		t2 = t2 + b;
	return t2;
}

1 = ☆×a + ★×b 일때,

☆	t1 << 우리가 찾는 값
★	t2
a	r1
b	r2
t, q, r	임시 저장 공간(단, q는 몫을 임시 저장한다)

 

이렇게 정리 할 수 있다. 이번 글은 이해하기 어려웠다. 하지만 차근차근 하다 보면 이해 할 수 있을 것이다.

다음 글에선 이것 보다 간단한 고속 누승 알고리즘에 대해 알아보도록 하자.

 

부록 _ RSA에선 어떻게 쓸까?

e × d ≡ 1 (mod (N))에 이미 알고 있는
N [= p×q, 임의의 두 소수p, q] \\ (N)[= (p-1)(q-1)] \\ e (= gcd(e,(N)) = 1이 되는 e)의 값을 대입하여 확장 유클리드 알고리즘을 이용해 비밀키 d 값을 구한다.

 

참고 글 : 1, 2, 3