베루의 보안공부

일차합동식은 일차방정식과 같은 형태지만 합동식이 들어가 있어 일차합동식이라 부른다.

식으로 표현하자면 ax+ b ≡ 0 (mod ⁡m)에 형태이다.

일차방정식이 있듯이 이차방정식이 있고 당연히 이차합동식 또한 존재한다.

x^2 + 1 ≡ 0 (mod 5)일 때  , f(x) = x^2 + 1 ≡ 0 (mod 5)

f(0) = 1 ≡ 1 (mod 5) ,  f(1) = 2 ≡ 2 (mod 5), f(2) = 5 ≡ 0 (mod 5)

f(3) = 10 ≡ 0 (mod 5), f(4) = 17 ≡ 2 (mod 5)

그로 인해 해가 존재하는건  x ≡ 2 (mod 5), x ≡ 3 (mod 5)가 이차합동식의 해이다.

답을 작성할 때 해가 존재하는 경우 위와 같이 적어주고 해가 존재하지 않을 경우 해가 존재하지 않다. 라 작성하면 된다.

위 식에서 계산은 덧셈으로 하였을 때 항등원은 0이며, m = 5 이므로 5 = {0 ,1, 2, 3, 4}로 f(x)의 x값안에 차례대로 대입하여 계산한다.

반대로 

만약 식이 곱셉이였을 때 항등원은 1이며, m 또는 p로 0을 제외한 수로 대입하며 계산해야한다.

일차 합동식 ax ≡ b (mod m)이 해를 가지기 위해 필요충분조건 d = (a, m)과 d | b일 때 성립된다. 

d = (a, m) = gcd (a, m) 즉 최대공약수 1이 되야하며, d | b의 수가 약수, 배수 관계가 되면 가능하다.

위 식의 경우 곱셈으로 되어있는 일차합동식인데 (a x s) + (b x t) = 1이 성립이 되어야 하며, 식을 풀어 나갈 때 "확장된 유클리드 알고리즘"으로 계산 해야한다. 

r = r_1 - (q × r_2 ), S = S1 - (q × S2 ), t = t1 (q x t2 )

r = 나머지

역원이란 두 원소를 연산한 결과가 항등원일 때, 한 편에 대하여 다른 편을 이르는 말이다. 덧셈에서의 반수와 곱셈에서의 역수를 일반화한 개념이다.

곱셈의 항등원은 a x b ≡ 1 (mod m), 덧셈의 항등원은 a + b ≡ 0 (mod m)이다.

모듈러 연산에서 각각의 정수는 덧셈, 곱셈에 대한 역원을 갖는다. a * b, a + b의 합동은 1과 0이다.

위 연산이 자기자신도 물론 가능하다. 단 m값보다 작게 나와야 한다. 

a = 8, b = 6, m = 49으로 계산하면 a x b = 48 ≡ 1 (mod 49) 

※ mod 모듈러는 나눗셈이라 생각하면 편하다.

임의의 정수 a ∈ Zm 가 곱셈에 대한 필요충분조건은 gcd(a, m) = 1이 되어야 한다. 

위 조건은 무조건 성립해야한다. 

m의 값이 소수일 경우 곱셈이 역원이 존재, m의 값이 합성수일 때 존재하거나 존재하지 않는다. 

역원을 구할 때는 "확장된 유클리드 알고리즘"을 이용한다.

(m x s) + (b x t) = gcd(m, b) 

이때도 gcd(m, b) =1, 최대공약수 1이 꼭 되어야 한다. 

즉 (m x s) + (b x t)  = 1 ↔  b x t ≡ 1 (mod m)과 같다.   

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

 나눗셈 관계식이란 피제수(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 = 양의 정수(제수) 로 계산을 시작해야한다.