TLS/암호 알고리즘 쉽게 이해하기(6) - 이산 대수

키 합의, 비대칭키는 역연산이 실제적으로 불가능한 수학적 이론을 기반으로 만들어진 알고리즘이기 때문에, 이의 기본 동작을 이해하기 위해서는 수학적인 지식이 어느정도 필요하다.

여기에서는 이들 알고리즘의 동작 원리에 필요한 최소한의 수학을 정리해본다.

타원알고리즘을 제외하고, 키합의와 비대칭키 알고리즘을 이해하기 위해서는 다음과 같은 것을 알아야 한다.

• 소인수 분해
• 유클리드 호제법을 이용하여 두 수의 최대 공약 수 찾기
• 확장 유클리드 호제법으로 소수 모듈로 연산에서 곱하기 역원 찾기
• 페르마 소정리를 이용하여 소수 모듈로의 지수 연산 역원 찾기
• 오일러 정리를 이용하여 일반 모듈로에서 지수 역원 찾기

소인수 분해

임의의 정수를 소인수 분해하는 데에는 효과적인 방법이 없다. 기본적으로 2부터 정수의 1/2에 해당하는 수까지 하나씩 나누어 보면서 나머지가 있는지를 확인해 보는 수 밖에 없다.

1과 정수 자신 이외에는 다른 수로 나누어지지 않는 정수를 소수라고 하는데, 소인수분해가 어렵다는 의미는 소수인지를 판별하는 것도 어렵다는 말이다.

다만 소수인지를 판별하는 방법은 위키피디아 소수판별법과 같이 정확하지는 않지만 그래도 판별법은 있고, OpenSSL 과 같은 암호 라이브러리에서도 이들을 이용하여 임의의 소수를 선정하는데 사용한다.

그럼 여기서 말하는 큰 수란 어느정도의 수를 말하는 것일까? RSA 2048의 경우 2048bit에 가까운 수의 소인수 분해를 찾는 문제를 사용한다.
2048 bit는 십진수로 표현하면 0 이 600개 가량 붙는 아주 아주 큰 수이다.

$$ 2^{2048} = 3.23 \times 10^{616} $$

만일 $2^{1024}$ 가량의 큰 두 소수를 곱한 결과를, 소인수 분해하여 찾아 보라면 경우의 수는 얼마일까? 물론 어느 정도 횟수를 줄이는 방법은 있겠지만 단순하게 하나씩 찾는다면 거의 $2^{1024}$ 에 가까운 나누기를 해 보아야 한다.

정리를 해보면 암호화 용도로는 다음을 이용한다.

• 임의의 수가 소수인지는 소수판별법으로 100% 확신은 못하지만 판별할 수 있다.
• 아주 커다란 소수 두 개(p 와 q)를 곱하는 것은 컴퓨터로는 크게 어렵지 않다.
• 이 곱한 결과값을 소인수분해하여 다시 p 와 q 를 찾아내는 것은 불가능하다.

RSA에서는 이 역 연산인 소인수분해의 어려움을 이용한다.

최대 공약수 찾기

최대 공약수는 임의의 두 수에 대해서 공통으로 나누어 지는 최대 값을 말한다. 이 최대 공약수를 찾는 것은 의외로 단순하다.

두 수 A, B 가 있다고 하자. 둘 중 A가 더 큰 수이다. 이 두 수의 최대 공약수가 g 라고 한다면 각각의 두 수는 g 의 배수라는 말이다. 즉, 다음과 같은 수가 된다.

$$ A = g \times x, B = g \times y $$

위 두 수를 뺀 결과는 다음과 같다.

$$ A - B = g \times (x - y) $$

이 의미는 A, B 두 수의 최대 공약 수가 g 라면 A-B 도 A나 B와의 최대 공약수가 g 라는 말이다.

그러면 B와 A-B 의 최대 공약수는 어떨까? 둘다 각각 $g \times y$, $g \times (x-y)$ 이므로 B와 A-B 를 뺀 결과도 마찬가지로 최대공약수가 된다. 이와 같은 연산을 반복하면 마지막으로 남는 수가 최대 공약수가 된다. 컴퓨터 프로그램이라면 이 연산은 아무리 커다란 빅넘버라고 해도 그리 어렵지 않게 구할 수 있다.

예를 들어 973 과 301 의 최대 공약수 찾기는 다음과 같이 된다. 아래에서는 첫번째 식은 973 에서 301을 세번 빼준 셈이다. 즉, 301보다 작을때까지 빼주면 나머지 70 이 되고, 이 70도 973, 301과 같은 최대공약수를 가진다. 이를 반복하는 연산이다.

$$ \begin{align*} \textcolor{blue}{\mathbf{973}} &= 3 \cdot \textcolor{blue}{\mathbf{301}} + 70 \\ \textcolor{blue}{\mathbf{301}} &= 4 \cdot \textcolor{blue}{\mathbf{70}} + 21 \\ \textcolor{blue}{\mathbf{70}} &= 3 \cdot \textcolor{blue}{\mathbf{21}} + 7 \\ \textcolor{blue}{\mathbf{21}} &= 3 \cdot \textcolor{red}{\mathbf{7}} + 0 \end{align*} $$

위와 같이 나머지가 0일 때까지 해보면 이 때의 값인 7이 최대 공약수가 된다.

이와같이 최대 공약수를 찾는 방법이 유클리드 호제법이다.

암호에서는 이 최대 공약수 찾기가 아니라, 이를 확장한 확장 유클리드 호제법으로 모듈로 연산의 곱하기 역원을 찾는 용도로 이용한다. 우선 이 설명에 앞서 모듈로 연산(이산 대수)의 특징을 먼저 보기로 하자.

모듈로 연산

일반 프로그램에서도 모듈로 연산을 자주 사용한다.

이런 모듈로 연산 중 나누는 몫이 소수인 경우 재미있는 특징이 있다. 소수란 2,3,5,7,11,… 과 같이 1과 그수 자신 이외의 다른 자연수로 나누어 지지 않는 수를 말한다.

예를 들어 소수 11 모듈로 연산을 생각해 보자. 이 모듈로 11 연산으로 가능한 수는 0,1,…,9,10 까지 11개의 숫자이다.

이 모듈로 연산은 잠깐 생각해 보면 더하기, 빼기가 가능하다. 예를들어 각 수에서 +3 을 더하고, -3 을 빼며 이전 값을 얻을 수 있다.

-3을 더하는 것은 더 복잡해 보이지만, 쉽게 생각해서 +8을 더하는 것과 같은 결과이다.

중학교때 배운 덧셈의 성질을 생각해 보면 모듈로 연산은 더하기, 빼기에 대해서 역원이 존재하고(3과 8), 항등원(0, 더해도 값이 변하지 않는 수)이 존재한다. 결합법칙, 교환법칙도 성립한다. +3 이 아닌 어떤 수를 더해도, 이에 대한 역원이 존재를 한다.

곱하기, 나누기는 어떨까? 이 연산은 특별히 모듈로 몫이 소수인 경우에만 성립한다. 아럐는 모듈로 11(소수)의 곱하기 연산표이다. 항상 곱해도 0이 되는 0은 제외하였다.

위의 표를 자세히 보면 모든 열이나 행에는 중복되는 수 없이 1부터 10까지의 수가 있다. 정리해 보면 다음과 같은 특징이 있다.

• 모든 수에 대해서 임의의 수를 곱한 결과는 중복되지 않는다.

  • 예를 들어 1~10의 모든 수에 대해서 7을 곱한 결과는 1~10 사이의 수가 되고 중복 되지 않는다 (1→7, 2→3, 3→10, 4→6, 5→2, 6→4, 7→1, 8→9, 9→6, 10→3).

• 임의의 수를 계속 곱해 보아도(지수연산) 중복되지 않는 수가 나온다.

  • 예를 들어 7의 지수연산은 $6^1 → 6$, $6^2 → 3$, $6^3 → 7$, $6^4 → 9$, $6^5 → 10$, $6^6 → 5$, $6^7 → 8$, $6^8 → 4$, $6^9 → 2$, $6^{10} → 1$ 와 같이 된다.

위 두개의 특성 모두 암호 용도로 쓸만한 속성이다.

첫번째 속성은 곱의 결과를 다시 나누기를 하면 원래의 값으로 돌아갈 수 있다는 의미 이기도 하다.

예를 들어 모듈로 11 내의 임의의 수에 6을 곱한 결과는 반대로 6을 나누면 다시 원래 값이 된다는 말이다. 위 모듈로 더하기와 비슷하게 굳이 나눌 필요는 없다. 위의 표에서 찾아보면 곱하기 6의 역원은 곱하기 2이다.

정리해 보면 곱하기 6의 역원은 곱하기 2이고, 항등원은 1이다. 결과적으로 나누는 몫이 소수인 모듈로 연산은 사칙연산이 성립하고, 교환법칙, 결합법칙, 분배법칙 등이 성립한다. 결과적으로 소수의 모듈로는 사칙연산이 가능하다(닫혀 있다고도 표기한다).

두번째 속성은 더 재미있는 특성을 가지고 있다.

$6^{10}$ 을 해보면(모듈로 11보다 1작은 10) 이는 ${6^0}$ 과 같은 1이 된다. $6^{11}$ 이면 $6^1$ 과 같다는 말이다.

이는 이렇게도 확인할 수 있다.

모듈로 11에서 0을 제외한 모든 원소는 1부터 10까지의 수이다. 이를 모두 곱한 모듈로 11 결과를 A라고 해보자.

다시 임의의 수를 하나 고른다. 예를 들어 8을 골라보자. 모든 원소인 1부터 10까지에 이 8을 각각 곱하고, 나온 값들을 모두 곱한 모듈로 11 결과를 B라고 하면 A와 B의 관계는 어떻게 될까? 위 모듈로 곱하기 연산표를 보면 알 수 있다. 8에 1~10까지 각각을 곱한 결과를 보면 다시 1 부터 10까지 중복되지 않은 수이다. 결과적으로 1부터 10까지 곱한 값과 동일한 값이 된다.

이를 수식으로 표현해보면 다음과 같다.

$$(1 \times 8)(2 \times 8) … (10 \times 8) \equiv 1 \times 2 \times … \times 10 \mod 11$$

왼쪽의 수식에 8을 모아보면,

$$ (1 \times 2 \times … \times 10) \times 8^{10} \equiv 1 \times 2 \times … \times 10 \mod 11$$

양쪽의 공통 부분을 제거해 보면 결론은 다음과 같다. 8은 그냥 선정한 임의의 수로 1~10 사이의 어는 수이어도 상관없다.

$$ 8^{10} \equiv 1 \mod 11 $$

이것이 “페르마의 작은 정리” 로 정리해 보면 다음과 같다.

페르마의 작은 정리

임의의 소수 $p$ 의 모듈로에서 $p$ 보다 작은 양수 $k$ 에 대해서 다음 식이 항상 성립한다.

$$ k^{p-1} \equiv 1 \mod p$$

다시 모듈로 11로 바꾸어서 보면, 아래와 같다. $$ 8^{11} \equiv 8^1 \mod 11 $$

이것은 임의의 수에 제곱승의 결과를 다시 원래 값으로 돌릴 수 있는 방법을 찾을 수 있다는 의미이다.

아래와 같이 임의의 수에 7제곱승을 곱한 결과에 다시 3제곱승을 한 것은 결과적으로 임의의 수가 된다.

$$ {(8^{7})}^3 = 8^{(7 \cdot 3)} = 8^{21} = 8^{10} \cdot 8^{10} \cdot 8^1 = 8^1 \mod 11 $$

지수 연산의 지수 부분만 자세히 보면 특성이 모듈로 10 연산과 비슷하다 (모듈로 11이 아니라). 아래 부분에 다시 설명하겠지만 7과 3처럼 지수 부분의 곱하는 수 각각이 10과 서로소 인 경우에만 가능하다.

위의 패턴을 보면 예를 들어 7과 3을 비대칭 키의 한 예라고 볼수 있다. 모듈로 11의 경우 11보다 작은 임의의 수를 7제곱한 경우, 이를 다시 3제곱해주면 원본이 된다. 반대도 성립한다. 임의의 수를 3제곱 해준 것을 7제곱 해주면 원본이 된다.

모듈로 곱하기의 역원 찾기

위의 첫번째 특성에서 모듈로 11에서 곱하기 6의 역원은 곱하기 2이다. 만일 아주 큰 모듈로 연산의 곱하기 역원은 어떻게 찾을 수 있을까? 이는 위에서 설명한 최대 공약수를 찾은 유클리드 호제법의 변형인 확장 유클리드 호제법을 이용하여 찾을 수 있다.

확장 유클리드 호제법이란 다음과 같이 정의 된다.

확장 유클리드 호제법

두수 $r_0$, $r_1$ 의 최대 공약수를 $\gcd(r_0, r_1)$ 로 표기하면 다음을 만족하는 임의의 정수 s, t가 있다.

$$ \gcd(r_0, r_1) = s \cdot r_0 + t \cdot r_1 $$

말이 복잡해서 그렇지 확장 유클리드 호제법 연산과 비교해 보면 다음과 같이 된다.

모듈로 곱하기 역원 찾는 것만을 집중하여 설명하면 다음과 같다.

예를 들어 소수 983 으로 모듈로 연산을 한다고 하자. 이 모듈로 연산 중 곱하기 30의 역원을 구해보자.

983 과 30의 최대 공약수를 유클리드 호제법으로 구해 보자. 983 이 소수이기 때문에 계산해보지 않아도 1밖에 없다.

$$ \begin{align*} \textcolor{blue}{\mathbf{983}} &= 32 \cdot \textcolor{blue}{\mathbf{30}} + 23 \\ \textcolor{blue}{\mathbf{30}} &= 1 \cdot \textcolor{blue}{\mathbf{23}} + 7 \\ \textcolor{blue}{\mathbf{23}} &= 3 \cdot \textcolor{blue}{\mathbf{7}} + 2 \\ \textcolor{blue}{\mathbf{7}} &= 3 \cdot \textcolor{blue}{\mathbf{2}} + \textcolor{red}{\mathbf{1}} \\ \end{align*} $$

예상대로 1이 남는다.

위 식을 거꾸로 엮어 나가면 다음과 같이 된다.

• 4번째 식을 다시 쓰면 다음과 같다.

  $1 = \textcolor{blue}{\mathbf{7}} - 3 \cdot \textcolor{blue}{\mathbf{2}}$

• 수 2를 세번째 식으로 대체하면 다음과 같다.

  $1 = \textcolor{blue}{\mathbf{7}} - 3 \cdot (\textcolor{blue}{\mathbf{23}} - 3 \cdot \textcolor{blue}{\mathbf{7}}) = - 3 \cdot \textcolor{blue}{\mathbf{23}} + 10 \cdot \textcolor{blue}{\mathbf{7}}$

• 다시 수 7을 두번째 식으로 대체하면 다음과 같다.

  $1 = - 3 \cdot \textcolor{blue}{\mathbf{23}} + 10 \cdot (\textcolor{blue}{\mathbf{30}} - 1 \cdot \textcolor{blue}{\mathbf{23}}) = 10 \cdot \textcolor{blue}{\mathbf{30}} - 13 \cdot \textcolor{blue}{\mathbf{23}}$

• 다시 수 23을 첫번째 식으로 대체하면 다음과 같다.

  $1 = 10 \cdot \textcolor{blue}{\mathbf{30}} - 13 \cdot (\textcolor{blue}{\mathbf{983}} - 32 \cdot \textcolor{blue}{\mathbf{30}}) = -13 \cdot \textcolor{blue}{\mathbf{983}} + 426 \cdot \textcolor{blue}{\mathbf{30}} $

이렇게 해서 최종적으로 다음 식을 얻었다.

$$ 1 = -13 \cdot \textcolor{blue}{\mathbf{983}} + 426 \cdot \textcolor{blue}{\mathbf{30}} $$

모듈로 983 연산에서 위 식은 곱하기 30의 역원이 426 이라는 것을 말한다. 이유는 앞의 $-13 \cdot 983$ 은 모듈로 983에서는 0이기 때문에 30에 426을 곱하면 항등원 1이 된다는 말이다.

임의수 777 을 가지고, 30을 곱하면 다음과 같다.

$$ 777 \cdot 30 \mod{983} = 701 $$

다시 이 수에 426을 곱해보자.

$$ 701 \cdot 426 \mod{983} = 777 $$

정상적으로 777 이 나온다. 빅 넘버의 경우라도 위와 같은 반복 루프를 돌리면 모듈로 소수 연산의 임의의 수에 대한 곱하기 역원을 구할 수 있게 된다.

모듈로 지수 연산의 의미

정수에서 지수 연산은 값이 크다 뿐이지 역연산을 구하는 것이 가능하다. 이 역연산이 로그 함수이다.

예를 들어 다음과 같이 x의 y 승인 z 가 있다고 하자.

$$ x ^ y = z $$

z를 다시 x 로 만들려면 다음과 같이 로그함수를 적용하면 된다.

$$ \log_x(z) = y $$

복잡해 보여도 컴퓨터에게 시키면 아무리 큰 수라도 그리 어렵지 않게 계산 할 수 있다.

지수 연산도 다음과 같이 연산 횟수를 줄일 수 있다. 예를 들어 $x^{1024}$ 은 $x$ 를 1024번을 곱하여 구할 수도 있지만 1024는 $2^{10}$ 으로 다음과 같이 표현된다.

$$ x ^ {1024} = {(x^{2})}^{10} $$

$x$를 1024번을 곱할 필요 없이 $x^2$을 10번 곱하면 된다. 이와 같이 10번 곱하는 것도 동일하게 더 줄일 수 있다.

동일한 연산을 소수 모듈로에서 하면 어떻게 될까?

일단 지수 연산 자체는 연산량이 거의 동일하다. 차이나는 것은 적절한 시점에 모듈로 연산을 해서 나머지만 찾으면 되고, 위와 같이 지수 연산 횟수를 줄일 수도 있다 (모듈로에서도 사칙연산이 성립하므로 지수연산도 일반 정수연산과 동일하게 줄일 수 있다).

그러면 반대 연산은 어떻게 될까? 위 모듈로 11에서 $7^n$ 연산을 예로 들면 다음과 같은 순서가 된다.

• 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, …

지수 연산을 하는 결과값이 한 방향으로 계속 커지는 것이 아니라 균등분포를 가진 난수처럼 되어 버린다.

이 경우 로그 연산은 불가능하여 “모듈로 11에서 9 는 7의 몇승일까요?” 라는 문제를 찾기 위하여는 처음부터 하나씩 7을 곱해보아야 한다. 모듈로 11과 같은 작은수가 아니라 아주 아주 큰 소수에 대해서 동일한 문제를 물어보면 찾는 것은 거의 불가능하게 된다.

이와 같이 소수 모듈로 연산의 특성을 이용한 것이 키 합의, 비대칭 암호화 알고리즘의 이산 대수 문제이다.

• 순방향 연산인 지수연산은 연산 횟수를 줄여서 계산이 가능하다.
• 반대 연산은 모듈로에서 로그연산이 불가능하여, brute force 방식으로 밖에는 구할 수 없어, 아주 큰 수라면 실제적으로 찾는 것이 불가능하다.

갈르와체와 확장

위와 같은 사칙연산에 닫혀 있는 소수 모듈로의 원소들을 갈르와체(Galois Field)라고 한다.

약간은 제한적이기는 하지만 소수 모듈로가 아닌 경우에도 제한적인 범위에서 사칙 연산이 가능한 경우도 있다. 우선 두 소수를 곱한 합성수 15 (소수 3과 5의 곱)의 모듈로 연산을 보자 (이것을 RSA에서 사용한다).

위 표를 보면 일단 x3 과 같은 연산은 3,6,9,12,0,3,6,9,12,0,3,6,9,12 로 이와 같은 연산을 하여 다시 복원하는 것은 불가능하다.

그래서 위 연산이 쓸모 없어 보이지만, 자세히 보면 모듈로 15와 서로소(최대공약수가 1인)인 수에 대해서는 연산이 가능하다. 서로소가 아닌 수는 3과 5의 배수로, 3,5,6,9,10,12 이다. 이 수를 제외하고 다시 표를 그려보면 다음과 같다.

위 연산을 보면 항상 1~14가 중복되지 않아, 예를 들어 임의의 수에 7을 곱한 것은 다시 7의 역원인 13을 곱하면 복원이 된다. 마찬 가지로 임의의 수에 대해서 $7^3$ (7을 3번 곱한 것) 와 같은 지수 연산도 역연산이 가능하다.

오일러의 정리

우선 위와 같이 모듈로 15에서 서로소인 수의 갯수는 어떻게 구할까?

오일러의 파이함수(Euler’s phi function) 이라는 공식이 있다. 다른 문서를 보면 복잡한 공식이 있는데, 이것은 필요없고, 위처럼 두 소수의 곱셈의 결과에서만 고민해 보자.

예를 들어 두 소수 $p$, $q$로 모듈로 $(p \cdot q)$ 연산이라면 $p$의 배수와 $q$의 배수를 뺀 나머지 이면 된다.

이렇게 되면 개수는 다음과 같은 공식이 된다.

$$ \Phi(m) = (p - 1) \cdot (q - 1) $$

위의 3과 5의 곱인 모듈로 15에서 0과 서로소를 제외한 개수를 세면 $(3 - 1) \cdot (5 - 1) = 8$ 로 위의 표와 같이 1,2,4,7,8,11,13,14 총 8개 이다.

이제 다시 위의 표를 찬찬히 보고, 앞에서 언급한 페르마의 소정리를 다시 고민해 보자.

페르마의 소정리에서는 소수 모듈로에 대해서 1~(n-1)까지 모든 수를 곱한 것과, 1~(n-1) 각각에 대해서 임의의 수를 곱한 결과를 다시 다 곱한 값이 같다는 것이었다.

하지만 15와 같은 합성수 모듈로에 대해서는 전체는 성립하지 않고, 서로소인 수에 대해서만 성립한다.

즉, 서로소인 1,2,4,7,8,11,13,14 을 모두 곱한 것과, 임의의 수에 1,2,4,7,8,11,13,14 을 각각 곱한 결과를 다시 곱한 것이 같다.

그래서 페르마의 소정리에서는 아래처럼 소수p 모듈로에 대해서 아래처럼 되지만,

$$ k^{p-1} \equiv 1 \mod p$$

합성수에 대해서는 p-1 이 아니라 서로소의 개수가 된다. 이 수는 오일러 $\Phi$ 이므로 정리하면 다음과 같다.

$$ k^{\Phi(m)} \equiv 1 \mod m$$

위의 소수 3과 5의 곱인 모듈로 15를 보면 다음과 같다.

$$ k^8 \equiv 1 \mod 15 $$

이때 k는 1~14까지의 어떤 수이어도 가능하다.

이제 암호원리로 소수 모듈러 처럼 가능한지를 조금 더 큰 소수로 확인해 보자.

소수 p=3, q=11 을 선택하면 곱은 33이 되어 모듈로 33이 된다. 이때 33과 서로소인 개수는 위 공식에 의해 $(3 - 1) \cdot (11 - 1) = 20$ 이 된다. 그러면 오일러 공식에 의하여 다음 관계가 성립된다.

$$ k^{20} \equiv 1 \mod 33 $$

위에서 지수 연산은 모듈로 20과 같은 특성이다. 즉, 모듈로 20에서 두 곱을 해서 1이 되는 수를 찾으면 된다. 먼저 20과 서로소인 3을 하나 골라보자. 그러면 위의 확장 유클리드 호제법으로 역원을 찾을 수 있다. 여기서는 간단하니까 그냥 7을 바로 찾을 수 있다.

$$3 \cdot 7 = 21 = 1 \mod 20$$

그러면 임의 수에 대해서 결과를 보면 다음과 같이 된다. 33과 서로소가 아닌 3과 11에 대해서도 문제없이 결과가 나온다.

이 방법이 RSA 에서 사용하는 암호화 방법이다.

정리

이상으로 수학을 증명 보다는 이해하기 쉽도록 예로 들어서 정리하였다.

Diffie-Hellman 키합의나 RSA 와 같은 비대칭 키 암호 방식은 모두 이산대수의 지수 연산의 역변환이 불가능하다는 것을 기반으로 만들어 진 것이라고 보면 된다.

정리해 보면 다음과 같다.

• 소수 모듈로 지수 연산의 연변환이 불가능하여 이를 이용한 Diffie-Hellman 키 합의 알고리즘이나, Elgamal 비대칭키 암호 등을 만든다.
• 두개의 소수곱이 소인수 분해의 어려움과, 이 합성수로 만들어진 모듈로 지수 연산의 역변환의 불가능을 이용하여 RSA 암호 방식을 만든다.

이들 각각에 대해서 이번 글에서 정리한 수학을 기반으로 차례대로 설명하기로 한다.