베루의 보안공부

원시근을 하기에 앞서 먼저 배워야 할 것은 위수(order)이다.

(a, m) = 1이 성립되고  a^r ≡ 1 (mod m)을 만족하는 정수 중에서 가장 작은 양의 정수 r(나머지)을 법 m, p에 관한 a의 위수이다.

예시로 들자면 법 7에 관한 2의 위수를 구하여라

2^r ≡ 1(mod 7)을 만족하는 가장 작은 양의 정수 r을 구할 때 2^1 ≡ 1(mod 7), 2^2 ≡ 4 (mod 7),  2^3 ≡  1(mod 7)

법 7에 관한 2의 위수는 3 ≤ ∂(7) = 6이다. 즉 ord_7 2 = 3이다. 

법 7에 관한 3의 위수에서 3^r ≡ 1(mod 7)일 때 3^1 ≡  3 (mod 7), 3^2 ≡  2 (mod 7), 3^3 ≡  6 (mod 7), 3^4 ≡  4 (mod 7), 3^5 ≡  5 (mod 7), 3^6 ≡  1 (mod 7)이며 법 7에 관한 3의 위수는 r = 6이다.  

위수:ord_7 3 = 6인 것이다.

※계산할 때 오일러 피 함수로 모듈러 m, p를 먼저 구하고 나온 값 만큼 거듭제곱을 해야한다. (1 ~ m-1 까지)

n | ∂(m) 은 약수배수 관계이다. 또한 ∂(m)은 원소의 개수와 같다.

원시근과 위수는 꽤나 비슷하다. ord_m a =  ∂(m) 동일한 값이 나오면 원시근, ord_m a 일 때 위수인 것이다.

원시근은 2, 4, p^k, 2p^k만 존재하고 그 이상에 합성수는 존재하지 않는다. 

값이 있더라도 그 값은 해가 될 수 없다.

존재하는 경우는 집합 Z^* p인 기약잉여계 즉 소수일 때만 존재한다.

암호학에서 키, 키쌍은 모두 정수의 형태를 가지고 있고 "소수"를 기반하고 있다.

그 이유는 144자리 이상에 소수를 나누라고 하면 어느 값을 기준으로 그 값을 만들었는지 모르기 때문이다. 

크게 3가지로 본다면 "소수로 이뤄진 합성수", "합성수", "소수"로 분류하며 어느 게 좋다 물어보면 서로 상황에 맞게 쓰이기 때문에 판단하기 어렵다.

위 표와같이 나타낼 수 있고 소수가 왜 중요한지는 합동식을 들어갈 때 설명을 하도록 하겠다.

다음 설명으로 소인수 분해는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법이다.

위 그림과 같이 이진트리 형식으로 나타낼 수 있고 식으로 나타내면 864 = (2^5) x (3^3) 으로 보일 수 있다. 

소인수 분해 또한 소수와 동일하게 합동식에서 중요한 역할을 수행한다. 소수를 나눌 때 소인수 분해를 사용한다 하지만 키 값을 가져갔다 했을 때 무슨 수로 나눌건지 정확히 알 수 없기에 중요 포인트중 하나라고 생각해두면 편하다.

다음 글에선 본격적으로 암호 수학의 시작인 합동식을 알아보도록 하겠다.