베루의 보안공부

정수론의 기본 바탕인 나눗셈 관계식,  자주 쓰일 유클리드 알고리즘에 대해 다뤄보고자 한다.

 나눗셈 관계식이란 피제수(dividend), 제수(divisor), 몫(quotient)으로 되어있는 관계식이다.

그림으로 이러한 형태로 나오며, 이는 차 후 합동식에서 나머지와 최대공약수를 구하기 위해 자주 쓰인다.

이 식을 가로형태로 만들면 a = q x b + r  이고 0  ≤  r  <  b의 조건을 성립해야한다.

암호학에서 사용하는 나눗셈 관계식은 2개의 제약이 존재한다.

1. 재수는 양의 정수 (b > 0)이다.
2. 나머지는 음이 아닌 정수(r  ≥ 0) 이여야 한다.

유클리드 알고리즘 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다

유클리드 알고리즘은 아래 2개를 기반하고 있다.

1. gcd(a, b) = a이며 0은 모든 정수의 배수이고 모든 정수는 0의 약수이다.
2. gcd(a, b) = gcd(b, r)이다, 이 때 r은 a을 b로 나눈 나머지다.

계산을 할 때는 알고리즘 표를 작성을 해야 계산하기 유리하다. 

위와 같은 형태가 유클리드 알고리즘을 계산할 때 쓰이는 "표" 이다.

유클리드 알고리즘은 사용은 하나 한계가 있기에 이름하여 "확장된 유클리드 알고리즘" 을 사용한다.

확장된 유클리드 알고리즘이며 r = r1 - (q x r2), s = s1 - (q x s2), t = t1 - (q x t2) , s1  =  1,  s2  =  0,  t1  =  0,  t2 = 1은 해당 알고리즘에 고정된 값이며, 주로 사용되는 공식은 디피헬먼, RSA, 역원,  원시근등이 존재한다. 

확장된 유클리드 알고리즘의 공식은 (a x s)  + (b x t) = d , d는 최대공약수 1이다. 

양수가 아닌 음수가 존재 할 때 

• a  >  0, b  <  0 인 경우
• a  <  0, b  >  0 인 경우 

즉, r1 = 음의 정수(피제수),  r2 = 양의 정수(제수) 로 계산을 시작해야한다.