[암호학] 1. 암호학에서 사용되는 수학(2)

1. 나누어떨어짐(Divisibility)

암호학에서 관심 있는 수의 범위는 오로지 정수이기 때문에, 나눗셈에 있어서도 나누어떨어짐(Divisibility)에 제일 관심이 많다.

간단히, 나누어떨어짐 이라는 것은 나머지(remainder)가 0인 것이다. r=0 이므로 앞선 나눗셈의 관계는 다음과 같이 나타낼 수 있게 된다.

이렇게 나타낼 수 있을 때, b가 a로 나누어떨어지는 경우 a|b로 나타내며, b가 a로 나눠어떨어지지 않는 경우 a∤b로 나타낸다.

1) 성질

① if a|1, then a = ±1

② if a|b and b|a, then a = ±b

③ if a|b and b|c, then a|c

④ if a|b and a|c, then a|(mXb+nXc), where m,n are arbitrary integers.

2. 약수(All Divisiors)

나누어떨어짐으로부터 생각해 볼 수 있는 부분이다. 어떤 수의 약수는 어떤 수를 나누어떨어지게 할 수 있다. 예를 들어 12의 약수는 1,2,3,4,6,12가 되는 것이다. 이런 약수에 관한 두 가지 사실이 있다.

① 정수 1은 1개의 약수만을 가진다. 1 자기자신이다.

② 1을 제외한 나머지 정수들은 적어도 2개의 약수를 가진다. 1과 자기자신이다.

3. 최대공약수(Great Common Divisor)

두 개의 정수에 대해서 공통되는 약수를 공약수라고 말한다. 그 공약수들 중에서도 최대의 값을 최대공약수(Great Common Divisor, GCD)라고 부른다. 간단히, 18과 24의 최대 공약수를 생각해보면 6이라는 결과를 얻을 수 있다.

1) 유클리드 알고리즘(Euclidean Algorithm)

두 개의 정수에 대해 최대공약수를 쉽게 찾을 수 있는 방법 중 하나이다. 유클리드 알고리즘은 최대공약수의 두개의 성질에 기반을 하고 있다.

① gcd(a,0) = a

② gcd(a,b) = gcd(b,r), where r is remainder of a/b

다음과 같이 위의 성질을 반복적으로 사용하면 최대공약수를 구할 수 있다. 

마지막에 r1에 저장된 값이 a와 b의 최대공약수가 될 것이다.

ex) 48, 15 의 최대공약수를 구해보자.

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

즉, 48, 15의 최대공약수는 3이다.

ex2) 2740, 1760의 최대공약수를 구해보자.

즉, 최대공약수는 20이다.

※ gcd(a,b)가 1인 경우, a와 b의 관계를 서로소(relatively prime)이라고 한다.

2) 확장 유클리드 알고리즘(The Extended Euclidean Algorithm)

확장 유클리드 알고리즘은 유클리드 알고리즘의 a와 b의 최대공약수를 구함과 동시에 a와 b에 특정한 정수 s와 t를 곱해 그 값의 합이 gcd(a,b)와 동일하게 만드는 알고리즘이다. 이를 식으로 나타내면 아래와 같다.

유클리드 알고리즘과 마찬가지로 a를 b로 나누며, r2가 0 이 될 때까지 진행한다. 그러면서 s1=1, s2=0 이라는 조건과 t1=0, t2=1 이라는 조건을 추가해 s와 t의 값을 찾을 수 있다.

위의 과정대로 s = s1 - q X s2, t = t1 - q X t2 를 이용해 진행시키면, 마지막에 남는 결과로부터 s = s1, t = t1를 통해 s와 t를 찾을 수 있다.

ex) 161, 28의 최대공약수와 s, t의 값을 찾아보자.

따라서, (-1) X 161 + 6 X 28 = 7 임을 알 수 있다.

3) 디오판토스 방정식(Linear Diophantine Equation)

확장 유클리드 알고리즘을 적용할 수 있는 방정식이다. 디오판토스 방정식은 흔히 다음과 같은 방정식을 말한다.

이 식을 만족하는 x와 y를 찾고자 할 때, 확장 유클리드 알고리즘을 이용할 수 있다.

d=gcd(a,b)라고 할 때, 일반적으로 디오판토스 방정식에서 해가 존재하는 경우는, d|c인 경우이며 해가 존재하지 않을 때는 d∤c가 성립한다.

① Particular Solution

해가 존재하는 경우(d|c인 경우) 디오판토스 방정식을 만족하는 부분해를 찾는 방법이다.

1) ax + by = c의 모든 항을 d로 나눈다. 나누어 

꼴로 만든다.

2) 를 만족하는 s와 t를 확장 유클리드 알고리즘을 이용해 찾는다.

3) s와 t를 찾았다면, 그에 대한 부분해는 다음과 같다.

   

② General Solution

부분해를 찾았다면, 그로부터 일반해를 유추할 수 있다.

  

이 떄의 k는 정수이다.