CRT, Modulo Operation

***************** INDEX *****************

 

👾 모드연산

🤖 Chinese Remainder Theorem

 

********************************************

 

모드연산

암호학에서 빠질 수 없는 모드연산을 기본으로 암호학에서 사용하는 수학적인 기법들을 알아보고자 합니다.

이 포스팅은 모드연산을 기본적으로 알고 있다는 가정하에 작성하겠지만, 

그래도 모드연산을 가볍게 훑고만 가겠습니다.

 

모드연산? 

나눗셈을 해서 나머지를 구하는 연산. 바늘이 하나밖에 없는 시계연산

$A \bmod B = C$

 

모드연산에서 기본적으로 $B$가 동일하면 합산 가능합니다.

ex) $(2 \bmod 5) + (4 \bmod 5) = (2+4) \bmod 5 = 1$

 

 

✔️ 모드의 거듭제곱

모드 연산의 거듭제곱을 계산할 때에는 아주 중요한 특징을 언급할 수 있는데요.

계산 도중에 mod를 취해도 같은 결과가 나온다는 굉장히 편리한 특징이 있습니다.

 

예시를 통해 이해를 도와볼게요.

$\small 6^4 \bmod 11 = (6 \times 6 \bmod 11) \times (6 \times 6 \bmod 11) = (36 \bmod 11) \times (36 \bmod 11) = (3 \times 3) \bmod 11 = 9$

 

예시를 보니 이해가 쉽게 가시나요? (이해 강요하는 것 같네요,,ㅎㅎ,ㅎㅎ,,,)

제곱을 나눠 계산하기 편하게 쪼개놓은 다음 작은 수를 다루는 방법입니다.

예시로는 $6^4$이라는 작은 수지만, $6^{243}$이라는 수를 계산할 때에는 굉장히 유용하겠죠?

 

 

✔️  모드의 곱셈의 역원

이번 포스팅의 마지막 섹션인 CRT(중국인의 나머지 정리)를 정리할 때 필수로 알아야하는 개념입니다.

먼저, 곱셈의 역원이라고 하면 어떤 수를 곱했을 때 1이 되는 수죠.

($x$가 $3$일 때, $x$의 곱셈의 역원은 $\frac{1}{3}$이죠.)

 

모드계산에서 곱셈의 역원은 어떻게 찾을까요?

모드 12 상에서 7의 곱셈의 역원 $x$를 구할 때의 식은 $(7 \times x) \bmod 12 = 1$ 으로 정의할 수 있습니다.

 

 

암호학 - 수학적 문제

이산대수문제

$Y=X^n$ 라는 식에서 $X$값이 주어질 때 $Y$값은 쉽게 구할 수 있지만(단시간에 가능),

$Y$ 값이 주어질 때 $X$값은 구하기 어렵다(굉장히 긴 시간이 필요)는 원리입니다.

 

모드 상에서 제곱근을 구하는 문제로 다양한 암호화 방식의 기초가 되는 아주 중요한 개념입니다.

모드로 사용되는 숫자가 매우 크면 이산대수 계산이 매우 어렵고 시간이 대단히 많이 걸리기 때문에 해결하기 어렵습니다.

이런 특징을 이용하여 Diffie-Hellman은 공개키 안호 알고리즘을 설계했습니다.

 

 

소인수 분해 문제

Integer factorization Problem.

매우 큰 정수를 소인수해야하는 문제입니다.

두 수를 곱하는 연산은 쉽지만, 곱해진 수를 두 수로 쪼개는 건 어렵습니다.

 

 

 

Chinese Remainder Theorem

✔️ 중국인의 나머지 정리 (CRT)

중국인의 나머지 정리에 대해 알아보도록 하겠습니다.

CRT의 정의는 아래와 같습니다.

$K$개의 서로소: $m_{1}, m_{2}, m_{3}, ···, m_{k}$ (즉, $gcd(m_{i}, m_{j}) = 1, i \neq j \space$)와
정수 $a_{1}, a_{2}, a_{3}, ···, a_{k}$에 대해
다음 연립 방정식을 만족하는 $x$는 $mod (m_{1} \times m_{2} \times ··· \times m_{k})$에 대해 유일한 해를 가진다.

$\begin{cases}x &\equiv a_{1} (\bmod m_{1}) \\x &\equiv a_{2} (\bmod m_{2}) \\&\vdots \\x &\equiv a_{k} (\bmod m_{k}) 
\end{cases}$

 

위의 연립 방정식에서 하나의 해가 나온다는 것이 CRT핵심입니다.

 

뭔가 풀어 설명하는 버릇이 있는데, 이 포스팅은 설명을 할 게 없네요 ... 

최대한 수식이라도,,ㅎㅎ 잘 써보도록 하겠습니다.

 

단일 해 $x$를 구하는 과정은 아래와 같습니다.

1.  $M = m_{1} \times m_{2} \times m_{3} \times ··· \times m_{k}$

2.  $M_{1} = \frac{M}{m_{1}}, M_{2} = \frac{M}{m_{2}} , ···, M_{k} = \frac{M}{m_{k}}$

3.  $M_1^{-1} = M_1^{-1} (\bmod m_{2}),\space M_2^{-1} = M_2^{-1} (\bmod m_{2}),···, M_k^{-1} = M_k^{-1} (\bmod m_{k})$

4.  $x = (a_{1} \times M_{1} \times M_1^{-1} + a_{2} \times M_{2} \times M_2^{-1} + ··· +a_{k} \times M_{k} \times M_k^{-1}) \bmod M$

 

 

계산식이 굉장히 복잡해보이죠. 풀어보니까 실제로도 복잡한 것 같아요...ㅎㅎㅎ.,..

그래도 몇 번 해보면 익숙해지겠죠?

 

 

 

예시를 같이 풀면서 이해를 돕도록 해봅시다.

ex ) $x \equiv 2 \space (\bmod 5), \space x \equiv 3 \space (\bmod 5), \space x \equiv 2 \space (\bmod 7)$ 를 모두 만족하는 $x$? 

 

 

1. 모든 서로소를 곱하여 $M$ 구하기

$\small M = m_{1} \times m_{2} \times m_{3} \times ··· \times m_{k}$    👉🏻   $M=3 \times 5 \times 7 =105$

 

 

2. $M_{1}, M_{2}, M_{3}$  계산하기

$\small M_{1} = \frac{M}{m_{1}}, M_{2} = \frac{M}{m_{2}} , ···, M_{k} = \frac{M}{m_{k}}$    👉🏻   $M_{1}=5 \times 7, \space M_{2}=3 \times 7, \space M_{3}=3 \times 5$

 

 

3. $M_{k}^{-1}$  곱셈의 역원 구하기 

$\small M_1^{-1} = M_1^{-1} (\bmod m_{2}),\space M_2^{-1} = M_2^{-1} (\bmod m_{2}),···, M_k^{-1} = M_k^{-1} (\bmod m_{k})$   

모드 연산의 곱셈의 역원의 정의 $\small M_1 \times M_1^{-1} (\bmod m) = 1$ 를 이용하여 위의 수식을 풀 수 있습니다.

 

👉🏻   $\begin{cases}x &\equiv a_{1} (\bmod m_{1}) \space ··· \space 35^{-1} ( \bmod 3) = 1 , \space x=2 \\x &\equiv a_{2} (\bmod m_{2}) \space ··· \space 21^{-1} ( \bmod 5) = 1 , \space x=1 \\x &\equiv a_{3} (\bmod m_{3}) \space ··· \space 15^{-1} ( \bmod 7) = 1 , \space x=1 \end{cases}$

 

모드연산의 곱셈의 역원을 구하는 것이 어색할 수 있으니, 하나만 같이 풀어봅시다 ~!

$\small 35^{-1} ( \bmod 3) = 1$

$\small 35 \times M^{-1} \space (\bmod 3) \equiv 2 \times M^{-1} \space (\bmod 3) = 1, M^{-1} \in \{2, 5, 8, ···\}$

$\small \therefore M^{-1} = 2$

 

여기까지 잘 따라오고 계신가요 .. 

자, 이제 마지막입니다.

 

 

4.  $x$값 찾기

$\small x = (a_{1} \times M_{1} \times M_1^{-1} + a_{2} \times M_{2} \times M_2^{-1} + ··· +a_{k} \times M_{k} \times M_k^{-1}) \bmod M$ 를 만족하는 $x$값 찾아봅시다.

 

$x = ((2 \times 35 \times 35^{-1} \bmod 3) + (3 \times 21 \times 21^{-1} \bmod 5) + (2 \times 15 \times 15^{-1} \bmod 7)) \bmod 105$

$= ((2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1)) \bmod 105$

$= 23$

 

추가적으로, 4번과 같은 결론이 나오는 이유는 $x$값을 찾을 때 전체 수식에 $\bmod m_{1}$을 하게 되면

첫 번째 곱셈을 제외한 나머지는 $m_{1}$을 포함하고 있기 때문에 (2번째 단계 참조) 0으로 처리됩니다.

따라서 연립방정식의 첫 번째에 동일한 식이 나오게 되죠.