RSA - 확장 유클리드 호제법 (Extended GCD)

정수 m, n 의 GCD(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때,

 

확장된 유클리드 호제법을 이용하여, ax + by = gcd(a,b)의 해가 되는 정수 x, y 짝을 찾아낼 수 있다.

 

특히, x, y이 서로소(gcd(x,y) = 1)인 경우 유용한데, 그럼 위의 식은 ax + by = 1이 되고,

 

여기서 a는 모듈로 연산의 곱의 역원 (modular multiplicative inverse) 이 되기 때문이다.

 

extended gcd 와 뒤에 포스팅할 CRT (중국인의 나머지 정리) 둘 다 RSA를 위한 기반이 되므로 잘 알아두자.

 

우선 extended gcd 를 설명하고, python 코드로 구현하는 시연을 하겠다.

 

 

확장 유클리드 호제법

위의 소리가 이해가 가지 않아도 아직 상관없다.

 

ax + by = gcd(a,b)의 해가 되는 정수 x, y 짝을 찾아서 도대체 뭘 하느냐?

 

의문이 들테지만 일단 찾아보자. 찾는 방법은 다음과 같다.

 

초기 조건을 x0, x1, y0, y1 = 1, 0, 0, 1 으로 세팅한다.

 

적당한 예시로 15x+6y=3 를 만족시키는 x,y를 찾아보자.

	xi	yi	ri	qi
i=0	1	0	a=15
i=1	0	1	b=6	⌊ 15 / 6⌋=2
i=2	1−0∗2=1	0−1∗2=−2	15 mod 6=3
i=3

위 표에서 우린 다음 q2와 r3을 얻을 수 있다. 이걸로 다시 또 x3,y3를 찾을 수 있고 계속 반복한다.

	xi	yi	ri	qi
i=0	1	0	a=15
i=1	0	1	b=6	22
i=2	1	−2	3	⌊ 6 / 3 ⌋=2
i=3			6 mod 3=0

 

r이 0 이 되는 순간 그 위의 x , y 가 15x+6y=3 를 만족시키는 x, y 이다.

 

즉 1과 -2 가 방정식의 해 인데, 15x+6y = 15⋅1+6⋅(−2) = 15−12 = 3 으로 방정식을 만족시킨다.

 

곱셈의 역원을 구하기 위해서는

 

if gcd(a,p)=1,  a⋅s≡1 (mod p)        ∴  a⋅s+p⋅t=1     이다.

 

a와 p는 주어진 숫자이고, 그렇다면 확장 유클리드 알고리즘으로 s를 구할 수 있다.

 

(s는 음수가 될수 있고 t는 필요없기도 한것 같다.)

 

 

이제 파이썬 코드로 보자.

def extended_gcd(a, b):
    
    x0, x1, y0, y1 = 1, 0, 0, 1
    
    while b != 0:
        n, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - n * x1
        y0, y1 = y1, y0 - n * y1
        
    return x0, y0

위의 표를 사용하면 코드를 짜는 것은 쉽다.