[RSA 이해를 위한 몸부림 - 1] 유클리드 알고리즘과 확장된 유클리드 알고리즘

1. 유클리드 알고리즘

유클리드 알고리즘은 최대 공약수의 두 가지 성질에 기반한 두 수의 최대공약수 추출 알고리즘이다.

1. gcd(a,0) = a
   두 수 중에서 한 쪽이 0이라면 두 수의 최대공약수는 다른 한 쪽 수이다.

2. gcd(a,b) = gcd(b,r) ( ※ r은 a를 b로 나눈 나머지이다. )

위와 같은 성질을 통해 나온 유클리드 알고리즘은 다음과 같다.

gcd(a,b) = gcd(b,r) = ... = gcd(r,0) = r

이에 대한 것은 예제로 알아보자.

ex) gcd(48,15) = gcd(15,3) = gcd(3,0) = 3

이런 식으로 48과 15의 최대공약수를 구할 수 있다.

파이썬으로 유클리드 알고리즘을 짜보자.

def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)

if __name__=="__main__":
    v1,v2=map(int,input().split())
    res=gcd(v1,v2)
    print(str(res))

간단하다.

2. 확장된 유클리드 알고리즘

다음은 유클리드 알고리즘에서 약간의 추가 요소가 생긴 확장된 유클리드 알고리즘을 알아보자.

확장된 유클리드 알고리즘은 유클리드 알고리즘에서의 최대공약수 도출을 넘어, 두 수의 정수곱의 합으로 최대공약수를 표현할 수 있음을 보이는 것이다.

설명이 조금 난해하다면 식으로 한 번 이해해보자.

gcd(a,b) = as + bt

a와 b의 최대공약수를 a의 x배수, b의 y배수의 합으로 나타낼 수 있음을 보여주고있다.

예제를 한 번 들어보자.

161과 28의 최대공약수를 구하는 상황이다.

위 식에 따르면 gcd(161, 28) = 161s + 28t 가 되어야하는 상황이다.

이를 도출하기 위해서는 유클리드 알고리즘에서 약간의 변형을 거쳐야한다.

161 = 28 * 5 + 21 에서 나머지를 기준으로 식을 정리하자.

그러면 21 = 161*1 + 28*(-5) 라는 식이 나올 것이다. 이 식을 기억하자.

그 다음은 위에 이어서, 유클리드 알고리즘에 따라

28 = 21*1 + 7 이라는 식이 도출 된다. 또 다시 나머지를 기준으로 식을 정리하면,

7 = 28*1 + 21*(-1) 로 식이 정리된다.

이 때, 21은 위 식에서 다른 꼴로 가져올 수 있다. 다시 정리하면

7 = 28*1 + {161*1 + 28*(-5)}(-1)
7 = 161*(-1) + 28*6 

이다.

이런 식으로 유클리드 알고리즘에서 나머지가 0이 나올 때까지 실행하면...

21 = 7*3 + 0

7은 최대공약수임을 알 수 있고, 확장된 유클리드 알고리즘에 대한 배수는

7= 161*(-1) + 28*6 에서 s=-1, t=6임을 알 수 있다.

이는 RSA에서 모듈러 역(modular inverse)를 구할 때 유용하게 사용되는 원리이다.

이것을 일반화 하기 위해 몇 가지 기호를 사용해보자.

최대공약수를 구할 두 정수를 나타내는 r1과 r2, 몫을 표현하는 q, 그리고 두 수를 나눈 나머지를 표현할 r, 그리고 초기 두 수의 배수가 되어줄(도움이 되어줄) s1, s0, s, t1, t0, t 까지.

이를 모두 이용하여 표로 161과 28의 최대공약수와 확장된 유클리드 알고리즘에서 정수배의 합으로 최대공약수를 표현해보자.

q	r1	r2	r	s1	s2	s	t1	t2	t
5	161	28	21	1	0	1	0	1	-5
1	28	21	7	0	1	-1	1	-5	6
3	21	7	0	1	-1	4	-5	6	-23
X	7	0	X	-1	4	X	6	-23	X

여기서 s = s1 - s2*q 이고 t = t1 - t2*q 이다.

r = r1 - q*r2 = r1%r2 이며 r1=r2 r2=r 로 업데이트 할 수 있다.

그리고 r2가 0, 그러니까 이전 나머지가 0이 나오고 다음 순간의 s1=s , t1=t로

161과 28의 최대공약수는 7이고 7 = (161 * -1) + (28 * 6) 으로 최대공약수 7을 표현할 수 있음을 알 수 있다.

조금 더 보충설명이 되길 바라며 확장된 유클리드 알고리즘의 파이썬 코드를 첨부한다.

def extended_euclid(r1,r2,s1=1,s2=0,t1=0,t2=1):
    #처음 시작 시 s1 ~ t2 초기값 설정
    q=r1//r2 # 두 수의 몫
    s=s1-s2*q # 첫 번째 항의 곱
    t=t1-t2*q # 두 번째 항의 곱
    r=r1-r2*q # 두 수의 나머지와 같다.
    if(r==0):
        res={'gcd':r2,'s':s2,'t':t2}
        return res
    else:
        return extended_euclid(r2,r,s2,s,t2,t)
        # 나머지가 0이 아니라면 다음 회차에 인자들 전달

if __name__=="__main__":
    a,b=map(int,input().split())
    res=extended_euclid(a,b)
    print("┌---------------------------------")
    print("|gcd : {0}\n|equation : {3}*({1}) + {4}*({2}) = {0}".format(res['gcd'],res['s'],res['t'],a,b))
    print("└---------------------------------")

[실행결과 ]

암호학에서 주로 쓰이는 유클리드 알고리즘과 확장된 유클리드 알고리즘에 대해 알아보았다.

정확한 증명은 있지만 깊게 파지않았고, 정확히 어떻게 도출되는지 정도 알 수 있기를 바란다.

다음은 모듈러(modular) 연산에 대해 알아보려고 한다.

.
.
.
.
contact : a42873410@gmail.com