[암호학] 법 연산? 모듈러 연산? (합동식부터 잉여계, 오일러 피함수, 피함수로 구하는 곱셈암호 키)

1. 모듈러 연산, 법 연산 정의 
2. 합동식이란?
3. 법 m에 관한 잉여계
4. 오일러의 피($\phi $)함수
5. 곱셈 암호 키 (역원 존재 조건)

 

 

모듈러 연산, 법 연산

 

모듈러 연산은 나머지 연산을 뜻한다. 

 

예를들어, 7 mod 3 을 계산할 때

 

7을 3으로 나눈 몫은 2이고 나머지는 1이므로

 

7 mod 3 = 1 이라고 한다.

 

법 연산은 모듈러 연산을 한국어로 바꾼 거라 생각하면 된다.

 

(법을 영어로 하면 modulus 이다.)

 

 

합동식

 

예전에 도형을 배울 때 합동이란 말을 들어봤을 것이다.

 

두 도형이 합동이라 하면 두 도형은 완전히 같다는 것이고

 

두 도형이 닮음이라 하면 두 도형의 각은 모두 같고 변의 비율은 일정한 것이라고 배웠다.

 

 

법 (modulus) 연산에서도 합동이 있는데, 정의는 도형의 합동에서의 합동과 비슷하다.

 

만약 a ≡ b (mod m) 이렇게 있다면, mod m를 했을 때의 결과가 서로 같으면 된다. 

 

38 ≡ 14 (mod 12) 일 경우를 보면

 

38 (mod 12) 와 14 (mod 12) 가 같은지 보면 된다.

 

38 (mod 12) 는 2 이고, 14 (mod 12) 도 2이기 때문에 

 

두 수는 법 12에 대해 합동이라고 할 수 있다.

 

이를  38 | 14 로 표기할 수 있으며 모듈러 연산에 대해 동일한 나머지를 가지고 있다는 의미이다. 

 

 

여기까지만 이해해도 관련 문제를 푸는데에는 큰 어려움이 없을 것이다.

 

하지만 아래 내용을 추가로 이해하면 문제 풀이 시간을 줄일 수 있다.

 

두 정수 a, b에 대하여 a-b가 m의 배수일 때, 

a와 b는 법 (modulus) m에 관하여 합동이다. 

 

처음 보기에는 이게 무슨 말인가 싶지만 사실 당연한 말이다. 

 

a 와 b가 m에 대해 합동이 되기 위해서는

 

a와 b 모두 m * n + s  (s = 나머지) 꼴이 되어야 한다. 

 

위의 예시에서도 수를 m * n + s  (s = 나머지)  꼴로 정리해보면

 

38 = 12 * 3 + 2 (s=2) , 14 = 12* 1 +2 (s=2) 이렇게 되고, 

 

둘 다 나머지 (s) 값이 2 로 같으므로 합동이다.

 

그럼 합동인 두 수를 뺀다면 m* n + s 에서 s 값은 당연히 사라질 것이고

 

m의 배수만 남게된다. 

 

이걸 말로 정리한 게  "a-b 가 m 의 배수라면 두 수가 합동이다" 인 것이다. 

 

 

여기까지 이해했다면,  a ≡ b (mod m) 가 참인지 묻는 문제에서

 

a mod m 과 b mod m을 각각 구할 필요없이

 

두 수를 뺀 뒤 mod m의 배수가 나오는지 확인하고 넘어가면 된다.

 

 

 

법 m에 관한 잉여계

 

1. 완전 잉여계 $Z_{m}$
2. 기약 잉여계 ${Z_{m}}^{*}$

 

법 m에 관한 완전 잉여계 (complete resudue system)

 

완전 잉여계 $Z_{m}$ 는,

 

어떤 수를 m으로 나누었을 때 나올 수 있는 나머지들을 전부 나열한 것이다.

 

$Z_{9}$  를 구하라고 한다면, mod 9를 해서 나올 수 있는 값을 모두 적어주면 되므로

 

$Z_{9}$  = {0,1,2,3,4,5,6,7,8} 이라 해주면 된다. (나누어 떨어지면 나머지는 0이므로 0도 포함)

 

따라서  $Z_{m}$ 이 가질 수 있는 값은 0 ~ m-1 까지 총 m개이다.

 

법 m에 관한 기약 잉여계 (reduced resudue system)

 

기약 잉여계 ${Z_{9}}^{*}$  는,

 

완전 잉여계의 원소 중에서 m과 서로소인 원소 전체의 집합이라고 나와있는데

 

쉽게 말해 완전 잉여계에서 1을 제외한 m의 약수의 배수와 0을 뺀다는 뜻이다.  

 

서로소: 두 수 사이의 최대 공약수가 1인 경우 

 

0은 자신을 제외한 모든 수와 최대 공약수가 0이기 때문에 서로소가 아님

1은 모든 수와 최대 공약수가 1이기 때문에 모든 수와 서로소임

 

∴ 0은 모든 수와 서로소가 아니고, 1은 모든 수와 서로소이다. 

 

${Z_{9}}^{*}$  를 구하라고 한다면, $Z_{9}$  = {0, 1, 2, 3, 4, 5, 6, 7, 8} 에서

 

1을 제외한 9의 약수는 3, 9이므로 3의 배수인 3, 6 을 빼주고, 0도 뺴주면 된다. 

 

${Z_{9}}^{*}$   = {0, 1, 2, 3, 4, 5, 6, 7, 8} 

 

 

오일러의 피 ($\phi$)함수

 

m이 양의 정수일 때$\phi (m)$은 m보다 크지 않으면서 m의 서로소인 정수의 개수라고 한다.

 

그냥 기약 잉여계의 개수라고 생각해도 된다. 

 

${Z_{9}}^{*}$ = {1, 2, 4, 5, 7, 8} 이므로 기약 잉여계는 총 6개

 

$\phi (9)$는 6이라고 할 수 있다. 

 

 

하지만, 만약 $\phi (252)$같은 걸 구하라고 한다면 기약 잉여계를 구하기 너무 오래 걸린다.

 

그래서 오일러 피함수를 쉽게 구하기 위해 아래 공식을 외워주어야 한다.

$\phi (m) = (p^{\alpha }-p^{\alpha -1})(q^{\beta}-q^{\beta -1})(r^{\gamma }-r^{\gamma -1})$

 

 

식만 보니 외우기 어려워 보일지도 모른다. 

 

하지만 하나 구하고 나면 외우기 쉬울 것이니 위에 말했던 $\phi (252)$를 함께 구해보자.

 

 

먼저 , 252를 소인수분해(=표준분해) 해주어야 한다.

 

$252 = 2^{2} * 3^{2} * 7^{1}$ 

 

그리고 위의 식에 대입해주면

 

$\phi (252) = (2^{2}-2^{1}) * (3^{2}-3^{1}) * (7^{1}-7^{0})$

 

$\therefore \phi (252) = 72$이다.

 

 

원리를 이해하고 싶으면 아래를 확인해봐도 좋을 것 같다.

완전 잉여계 $Z_{m}$는 0에서 m-1 까지를 나열한 것이고,

 

완전 잉여계에서 m과 서로소인 원소만 적은 것이  기약 잉여계 ${Z_{m}}^{*}$이다.

(편의를 위해 1을 제외한 m의 약수의 배수와 0을 뺀다고 설명했었다.)

 

완전 잉여계에서 m과 서로소인 원소만 적었다는 것은

 

완전 잉여계에서 m과 서로소가 아닌 원소들을 빼면 기약 잉여계라는 말과 같다.

 

오일러의 피 ($\phi$)함수는 기약 잉여계 원소의 개수와 같으므로

 

$\phi (p^{e})$를 구할 때 (p는 소수)

 

우리는 0~ $p^{e}-1$ 의 정수 중 p과 서로소가 아닌 것을 빼야한다. 

 

서로소가 아니라는 것은 p로 나누어진다는 뜻이므로

 

p의 배수를 빼주면 된다. 

 

0~ $p^{e}-1$ 사이의 p의 배수는 1*p부터  $p^{e-1}*p$까지 있을 것이므로

 

총 $p^{e-1}$개다.

 

그럼  0~ $p^{e}-1$  의 정수 중 p과 서로소가 아닌 것을 빼야한다는 말로 돌아가서

 

계산을 해주면 된다.

 

0~ $p^{e}-1$  의 정수는 총 $p^{e}$개 ,  p과 서로소가 아닌 것의 개수는 총 $p^{e-1}$ 개,

 

따라서  $\phi (p^{e}) = p^{e}-p^{e-1}$ 임을 알 수 있다.

 

 

그럼 $\phi (252)$를 다시 구해보자. 

 

$\phi(252) = \phi (2^{2}*3^{2}*7^{1})$

 

$= \phi (2^{2})*\phi (3^{2})*\phi (7^{1})$

 

$= (2^{2}-2^{1})*(3^{2}-3^{1})*(7^{1}-7^{0})$

 

이렇게 소인수분해 한 뒤 각각을 피함수로 씌워주고 계산할 수 있다.

 

피함수와 곱셈 암호 키

 

이러한 피 ($\phi$)함수를 통해 곱셈 암호 키의 개수를 구할 수 있다. 

 

곱셈 암호의 키가 되기 위해서는 단 하나의 역원이 보장되어야하는데,

 

이 조건을 충족시키기 위해서는 두 수 (키와 평문)의 최대 공약수가 1이어야 한다.

 

두 수의 최대 공약수가 1이라는 건 두 수가 서로소여야 한다는 말과 같고

 

그렇다면 $ \phi (26)$를 통해 나오는 수는 모두 곱셈 암호의 키가 될 수 있다는 뜻이다. 

 

곱셈 암호 키의 개수 : $ \phi (26)= 12$
곱셈 암호 키 : ${Z_{26}}^{*}={1,3,5,7,9,11,15,17,19,21,23,25}$