[RSA] 유클리드 알고리즘, 확장 유클리드 알고리즘 (C언어 구현)

유클리드 알고리즘 (Euclidean algorithm)

두 정수 사이의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.

 

유클리드 알고리즘의 동작

유클리드 알고리즘의 프로세스와 수도코드

두 정수 a, b가 있을 때 r은 a ÷ b의 나머지로 정의한다. 즉, r = a % b이다. (a > b로 가정)

위 프로세스와 같이 나머지가 0이 될 때까지 두 번째 인자 값을 첫 번째 인자 값에 넣고, 나머지를 두 번째 인자 값에 넣는다.

 

예시

Q1. 2740과 1760의 최대공약수 계산

유클리드 알고리즘 예시1

2740과 1760의 최대 공약수는 20이다.

 

 

Q2. 25와 60의 최대공약수 계산

유클리드 알고리즘 예시2

25와 60의 최대공약수는 5이다.

위 예제에서는 r1과 r2 중 어느 쪽이 커도 상관 없다는 것을 보여준다.

 

구현

gcd = lambda a, b : a if not b else gcd(b, a % b)

위 소스는 python에서 gcd를 계산하는 한줄짜리 코드를 가져와봤다. (코드가 짧다고 해서 무조건 좋은 코드는 아니다. 이렇게도 짤 수 있구나를 보여주기 위해서 가져와봤다.)

위의 프로세스 동작과 비교하면서 보면 더 이해하기 쉬울 것이다.

b가 0(false)가 될 때까지 gcd라는 임시 함수(lambda를 이용한)를 재귀적으로 호출해서 수의 크기를 줄여나간다.

 

#include <stdio.h>

int euclidean(int a, int b) {
	int r1 = a, r2 = b, r;
	while (r2) {
		r = r1 % r2;
		r1 = r2;
		r2 = r;
	}
	return r1;
}

int main() {
	int gcd;
	
	gcd = euclidean(180, 120);
	printf("%d", gcd);
}

 

gcd(a, b) = 1 이면, a와 b는 서로소(relatively prime)이다.

 

확장 유클리드 알고리즘 (EEA, Extended Euclidean Algorithm)

두 정수 a, b가 주어졌을 때

2변수 일차 디오판투스 방정식

gcd(a, b)를 계산할 수 있을 뿐만 아니라, 동시에 s와 t값을 계산할 수 있는 알고리즘이다.

 

 

확장 유클리드 알고리즘의 동작

 

확장 유클리드 알고리즘의 프로세스

확장 유클리드 알고리즘의 수도 코드

기본적인 매커니즘은 유클리드 알고리즘과 비슷하다.

s와 t를 구하기 위해서는 초기값을 설정해주는데,

s를 구하기 위해서는 s1 = 1, s2 = 0을 설정해 유클리드 알고리즘을 수행하고,

t를 구하기 위해서는 t1 = 0, t2 = 1을 설정해 유클리드 알고리즘을 수행한다.

그리고, s와 t의 계산에서는 r1 ÷ r2의 몫인 q를 사용한다.

s = s1 - q x s2, t = t1 - q x t2로 계산해 나간다.

횟수는 a, b의 최대 공약수가 나오면 멈추면 된다. 예시를 통해 자세히 알아보자.

 

 

예시

Q. a = 161, b = 28 일때, gcd(a, b)와 s, t 값 계산

확장 유클리드 알고리즘 예시

gcd(a, b)가 계산되기까지 3번의 계산이 필요했다.

s와 t에 초기값을 설정하고, 똑같이 3번의 계산을 했을 때 s1은 -1, t1은 6이 나왔다. -1과 6이 우리가 찾던 s와 t의 값이다.

s = s1 - q x s2이다. 첫 번째 계산에서 q는 5이므로, s = 1 - 5 x 0 = 1

t = t1 - q x t2이다. 첫 번째 계산에서 q는 5이므로, t = 0 - 1 x 5 = -5이다. 이처럼 계산해 나가면 된다.

세 번의 계산이 끝나면 r2의 값이 0이 되면서 계산이 종료되고, r1, s1, t1의 값이 gcd(a, b), s, t의 값이 된다.

 

답은 gcd(161, 28) = 7이고, s = -1, t = 6이다.

∴ ( 161 x ( -1 ) + 28 x 6 = 7 )

 

 

구현

#include <stdio.h>

void EEA(int a, int b) {
	int r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
	int r, s, t, q;
	while (r2) {
		q = r1 / r2;
		// gcd 계산
		r = r1 % r2;
		r1 = r2, r2 = r;

		// s 계산
		s = s1 - q * s2;
		s1 = s2, s2 = s;

		// t 계산
		t = t1 - q * t2;
		t1 = t2, t2 = t;
	}
	s = s1, t = t1;
	printf("gcd(%d, %d) = %d, s = %d, t = %d \n", a, b, r1, s, t);
	printf("%d x %d + %d x %d = %d \n", a, s, b, t, r1);
}

int main() {
	EEA(161, 28);
}

 

 

RSA에서의 활용 (역원 구하기)

우리는 RSA에서 키 생성 알고리즘 중 개인키인 d를 계산하는 과정에서 확장된 유클리드 알고리즘을 사용하게 될 것이다. ( de ≡ 1 mod φ(N) )

 

※ RSA에서의 키 생성 알고리즘이 궁금하다면 여기로!!

 

확장된 유클리드 알고리즘을 사용하면 곱셈에 대한 역원을 쉽게 구할 수 있다.

 

위의 식에서 a, b가 서로소라면 gcd(a, b)가 1일 것이다.

a, b가 서로소일 때 b의 곱셈에 대한 역원을 구할 수 있다.

b의 곱셈에 대한 역원을 구하고 싶다면 t를 구하면 되는데 이때 t의 초기값으로 t1 = 0, t2= 1을 넣어서 b의 곱셈에 대한 역원 t를 구할 수 있다.

 

예시

Q1. a = 26, b = 11

일 때, 11의 곱셈에 대한 역원 계산

역원 계산 예시1

26과 11은 서로소이므로 gcd(26, 11)은 1이다.

t1 = 0, t2 = 1로 초기값을 설정하고 계산 결과 t는 -7이 나왔다.

 

정답: 11의 역원은 -7 이거나 19이다.

 

 

Q2. a = 100, b = 23일 때, 23의 곱셈에 대한 역원 계산

역원 계산 예시2

gcd(100, 23) = 1이므로, 두 수는 서로소이다.

t1 = 0, t2 = 1로 초기값을 설정하고 계산 결과 t = -13이 나왔다.

 

정답: 23의 역원은 -13 이거나 87이다.

 

 

Q3. a = 26, b = 12일 때, 12의 곱셈에 대한 역원 계산

역원 계산 예시3

gcd(26, 12) 는 2이다.

 

정답: 역원은 존재하지 않는다.

 

 

구현

#include <stdio.h>

int EEA(int a, int b) {
	int r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
	int r, s, t, q;
	while (r2) {
		q = r1 / r2;
		// gcd 계산
		r = r1 % r2;
		r1 = r2, r2 = r;

		// s 계산
		s = s1 - q * s2;
		s1 = s2, s2 = s;

		// t 계산
		t = t1 - q * t2;
		t1 = t2, t2 = t;
	}
	r = r1, s = s1, t = t1;
	printf("gcd(%d, %d) = %d, s = %d, t = %d \n", a, b, r, s, t);
	printf("%d x %d + %d x %d = %d \n", a, s, b, t, r);

	if (r == 1) {
		if (t < 0) {
			t += a;
		}
		return t;
	}
	else return NULL;
}

int main() {
	int inverse;
	inverse = EEA(26, 11);
	if (inverse != NULL){
		printf("역원: %d \n", inverse);
	}
}

gcd(a, b)가 1이면 역원이 존재한다.

역원으로 나온 t가 음수일 경우 a를 더해줘서 양수의 역원을 구하고 return 한다. a, b가 서로소가 아니어서 역원이 존재하지 않는다면, NULL을 return 한다.

 

main() 함수에서 역원이 존재한다면 역원을 출력해준다.