[암호학] 2. 기초 정수론(2)

[암호학] 2. 기초 정수론(2)  

오일러 정리에 따르면 양의 정수 $n$과 $\text{gcd}(a,\,n)=1$인 정수 $a$에 대하여 $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다. 

양의 정수 $n$과 $\text{gcd}(a,\,n)=1$인 정수 $a$에 대하여 다음을 만족하는 최소의 정수 $r$을 법 $n$에 대한 $a$의 위수(order)라고 한다. $$a^{r}\equiv1\,(\text{mod}\,n)$$ 이때 다음이 성립한다.

(a) 양의 정수 $k$에 대하여 $a^{k}\equiv1\,(\text{mod}\,n)$이면, $r|k$이다.  

(b) $r|\phi(n)$

(c) 양의 정수 $i,\,j$에 대해 다음이 성립한다. $$a^{i}\equiv a^{j}\,(\text{mod}\,n)\,\Leftrightarrow\,r|(i-j)\,\Leftrightarrow\,i\equiv j\,(\text{mod}\,n)$$ (d) 음이 아닌 정수 $k$에 대하여 $a^{k}$의 위수는 $\displaystyle\frac{r}{\text{gcd}(k,\,r)}$이다. 

(e) 음이 아닌 정수 $k$에 대하여 $a^{k}$의 위수가 $r$일 필요충분조건은 $\Leftrightarrow$ $\text{gcd}(k,\,r)=1$이다.

양의 정수 $n$에 대해 $\text{gcd}(a,\,n)=1$, $a$의 법 $n$에 대한 위수가 $\phi(n)$이면, $a$를 $n$의 원시근(primitive root)이라고 한다. 

양의 정수 $n$이 $2,\,4,\,p^{k},\,2p^{k}$($p$는 홀수 소수이고 $k\geq1$)일 필요충분조건은 법 $n$에 대한 원시근이 존재한다.

양의 정수 $n$에 대해 정수집합 $R=\{r_{1},\,...,\,r_{\phi(n)}\}$이 다음의 두 조건을 만족하면

(i) 모든 $r_{i}\in R$에 대하여 $\text{gcd}(r_{i},\,n)=1$ 이다. 

(ii) $\text{gcd}(a,\,n)=1$인 임의의 정수 $a$에 대하여 $r_{i}\in R$가 존재해서 $a\equiv r_{i}\,(\text{mod}\,n)$이다. 

$R$을 법 $n$에 대한 기약잉여계라고 한다.

$r$을 $n$의 원시근이라 하자. $\text{gcd}(a,\,n)=1$이면, $a\equiv r^{k}\,(\text{mod}\,n)$를 만족하는 최소의 정수 $k$를 $r$을 밑으로 갖는 $a$의 이산로그(discrete logarithm) 또는 지표(index)라고 하고 이것을 $\text{ind}_{r}a$로 나타낸다. 즉 $k=\text{ind}_{r}a$. 분명히 $1\leq\text{ind}_{r}a\leq\phi(n)$이고 다음이 성립한다. $$r^{\text{ind}_{r}a}\equiv a\,(\text{mod}\,n)$$ $n$이 원시근 $r$을 갖고 $\text{gcd}(a,\,n)=1$이면, 다음이 성립한다. 

(a) $\text{ind}_{r}(ab)\equiv\text{ind}_{r}a+\text{ind}_{r}b\,(\text{mod}\,\phi(n))$ 

(b) $k>0$에 대하여 $\text{ind}_{r}a\equiv k\,(\text{mod}\,\phi(n))$ 

(c) $\text{ind}_{r}1\equiv0\,(\text{mod}\,\phi(n))$, $\text{ind}_{r}r\equiv1\,(\text{mod}\,\phi(n))$      

홀수인 소수 $p$에 대해 법 $p$에 대한 원시근 $a$가 존재한다. 이때 임의의 양의 정수 $k$에 대하여 $$a^{k}\equiv b\,(\text{mod}\,p),\,1\leq b\leq p-1$$ 인 $b$를 구하는 것은 쉬우나 $p$가 상당히 크면 $\text{gcd}(b,\,p)=1$인 정수 $b$에 대하여 $k=\text{ind}_{a}b$, 즉 $a^{k}\equiv b\,(\text{mod}\,p),\,0\leq i\leq p-2$인 정수 $k$를 구하는 것은 어렵다.   

다음은 이산로그를 계산하는 알고리즘이다.

홀수인 소수 $p$와 법 $p$에 대한 원시근 $a$를 알 때 $\text{gcd}(b,\,n)$인 정수 $b$에 대하여 $k=\text{ind}_{a}b$를 구하는 알고리즘이다. 

1단계: 적당한 $t$개의 소수로 이루어진 집합 $P=\{p_{1},\,p_{2},\,...,\,p_{t}\}$를 고른다.

2단계: 양의 정수 $j$에 대하여 $$c_{j}\equiv a^{j}\,(\text{mod}\,p),\,1\leq c_{j}\leq p-1$$ 인 정수 $c_{j}$가 $$c_{j}=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}\,(e_{1}\geq0,\,\cdots,\,e_{t}\geq0)$$ 의 형태로 나타나는지 확인하고, 이렇게 표현되는 $c_{j}$들 중 $p_{1},\,p_{2},\,...,\,p_{t}$가 적어도 한 번 나타나도록 $t$개의 $b_{j}$를 택한다. 

3단계: 2단계에서 얻은 식으로부터 $$\begin{align*}&e_{1}\text{ind}_{a}p_{1}+e_{2}\text{ind}_{a}p_{2}+\cdots+e_{t}\text{int}_{a}p_{t}\\&\equiv\text{ind}_{a}c_{j}\equiv j\,(\text{mod}\,p-1)\end{align*}$$ 과 같은 형태의 $t$개의 합동식들로 이루어진 연립합동방정식의 해를 구한다. $$\text{ind}_{a}p_{1},\,\text{ind}_{a}p_{2},\,...,\,\text{ind}_{a}p_{t}$$ 4. 양의 정수 $i$에 대하여 $$d_{k}\equiv ba^{i}\,(\text{mod}\,p),\,1\leq d_{k}\leq p-1$$ 인 정수 $d_{k}$가 $$d_{k}=p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots p_{t}^{f_{t}}\,(f_{1}\geq0,\,f_{2}\geq0,\,\cdots,\,f_{t}\geq0)$$ 의 형태로 나타나는지 확인하고, 이렇게 표현되는 $d_{j}$를 선택한다.

5단계: 4단계에서 얻은 $d_{k}$에 대하여 $$\begin{align*}&\text{ind}_{a}d_{k}\equiv\text{ind}ba^{i}\equiv\text{ind}_{a}b+i\,(\text{mod}\,p-1)\\&\text{ind}_{a}d_{k}\equiv f_{1}\text{ind}_{a}p_{1}+f_{2}\text{ind}_{a}p_{2}+\cdots+f_{t}\text{ind}_{a}p_{t}\,(\text{mod}\,p-1)\end{align*}$$ 임을 이용하여 $k=\text{ind}_{a}b$를 구한다. 

소수 $p=47$에 대하여 $a=10$은 법 $p$에 대한 원시근이다. 앞에서의 알고리즘을 이용하여 $\text{ind}_{10}17$을 구하자. 

1단계: 세 개의 소수로 이루어진 집합 $P=\{2,\,3,\,5\}$를 고른다. 

2단계: 양의 정수 $j$에 대하여 $$c_{j}\equiv a^{j}\equiv10^{j}\,(\text{mod}\,47),\,1\leq c_{j}\leq46$$ 이라 할 때 다음이 성립한다. $$\begin{align*}b_{2}&\equiv10^{2}\equiv6\,(\text{mod}\,47),\,6=2\cdot3\\b_{7}&\equiv10^{7}\equiv45\,(\text{mod}\,47),\,45=3^{2}\cdot5\\b_{15}&\equiv10^{15}\equiv40\,(\text{mod}\,47),\,40=2^{3}\cdot5\end{align*}$$ 3단계: 위의 2단계에서 얻은 결과로부터 연립합동식 $$\begin{matrix}\text{ind}_{a}2&+\text{ind}_{a}3&&\equiv2\,(\text{mod}\,46)\\&2\text{ind}_{a}3&+\text{ind}_{a}5&\equiv7\,(\text{mod}\,46)\\3\text{ind}_{a}2&&+\text{ind}_{a}5&\equiv15\,(\text{mod}\,46)\end{matrix}$$ 을 얻고 이 연립합동식의 해는 다음과 같다. $$\text{ind}_{a}2=30,\,\text{ind}_{a}3=18,\,\text{ind}_{a}5=17$$ 4단계: 양의 정수 $i$에 대하여 $$d_{k}\equiv ba^{i}\equiv17\cdot10^{i}\,(\text{mod}\,47)\,1\leq d_{k}\leq p-1$$ 라고 할 때 $$d_{12}\equiv17\cdot10^{12}\equiv27\,(\text{mod}\,47),\,27=3^{3}$$ 이므로 다음이 성립하고 $$\begin{align*}&\text{ind}_{10}17+12\equiv3\text{ind}_{10}3\,(\text{mod}\,46)\\&\text{ind}_{10}17\equiv3\cdot18-12\equiv42\,(\text{mod}\,46)\end{align*}$$ 따라서 $\text{ind}_{10}17=42$이다.     

고정된 정수 $b(\geq2)$에 대하여 모든 양의 정수 $n$은 유일한 방법으로 다음과 같이 나타낼 수 있고 $$m=a_{m}b^{m}+a_{m-1}b^{m-1}+\cdots+a_{2}b^{2}+a_{1}b+a_{0}$$ 이때 $m\geq0$, $1\leq a_{i}\leq b-1\,(0\leq i\leq m)$이다. 

위의 $n$을 $n$의 $b$진법(base $b$)에 대한 전개식이라고 하고, $$n=(a_{m}a_{m-1}\cdots a_{2}a_{1}a_{0})_{b}$$ 로 나타낸다.  

양의 정수 $a$에 대하여 $$b^{m}\leq a<b^{m+1}$$ 즉 $[\log_{b}a]=m$일 때 $a$를 $b$진법으로 나타낼 때의 자리수는 $m+1$이고, $a$를 2진법으로 나타낼 때의 자리의 수를 비트(bit, binary digit)라고 한다. 

전자계산기에서 정수를 나타낼 때 2진법, 8진법, 16진법으로 나타낸다. 정수를 16진법으로 나타낼 때 16개의 기호 0, 1, 2,..., 9, A, B, C, D, E, F를 사용하는데 A, B, C, D, E, F는 각각 10, 11, 12, 13, 14, 15를 뜻하고, 2진법에서 16진수는 각각 다음과 같다.

2진수	16진수
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

16진수 $2FB3_{16}$은 2진수 $10111110110011_{2}$와 같고, 16진수 $A0B2F_{16}$은 다음과 같이 10진수로 나타낼 수 있다. $$10\cdot16^{4}+0\cdot16^{3}+11\cdot16^{2}+2\cdot16+15=68399$$ 참고자료:

암호학과 부호이론, 박승안, 경문사

Elementary Number Theory 7th edition, Burton, McGraw-Hill