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

키 합의와 비대칭 키 암호는 역연산을 현실적인 시간 안에 수행하기 어렵다는 수학적 문제를 기반으로 하기 때문에, 기본 동작을 이해하려면 어느 정도 수학 지식이 필요하다.

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

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

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

소인수분해

큰 정수를 소인수분해하는 문제를 효율적으로 푸는 고전 알고리즘은 알려져 있지 않다. 가장 단순한 방법은 2부터 정수의 제곱근에 해당하는 수까지 하나씩 나누어 보면서 나머지가 있는지를 확인하는 것이다.

1과 정수 자신 이외에는 다른 자연수로 나누어지지 않는 1보다 큰 정수를 소수라고 한다. 소수 판별은 소인수분해와는 다른 문제이며, 소인수분해보다 훨씬 효율적인 알고리즘이 알려져 있다.

실제로는 위키피디아 소수판별법에 소개된 것과 같은 확률적 소수 판별법을 반복해 오류 확률을 충분히 낮출 수 있다. OpenSSL과 같은 암호 라이브러리에서도 이런 방법을 이용하여 큰 소수를 생성한다.

그럼 여기서 말하는 큰 수란 어느 정도의 수를 말하는 것일까? RSA-2048은 약 2048비트 크기의 합성수를 소인수분해하는 문제를 사용한다. 2048비트 수는 십진수로 약 617자리인 아주 큰 수이다.

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

만일 각각 약 1024비트인 큰 소수 두 개를 곱한 결과에서 원래의 소수들을 찾아보라면 경우의 수는 얼마일까? 물론 시행 횟수를 줄이는 방법은 있지만, 단순하게 하나씩 찾는다면 약 $2^{1024}$에 가까운 후보를 확인해야 한다.

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

• 임의의 수가 소수인지는 소수 판별법으로 매우 높은 신뢰도까지 빠르게 판별할 수 있다.
• 아주 큰 소수 두 개($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을 법으로 한 모듈로 연산을 생각해 보자. 이 연산에서 가능한 나머지는 0, 1, …, 9, 10까지 11개의 숫자이다.

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

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

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

곱하기, 나누기는 어떨까? 법이 소수이면 0을 제외한 모든 수가 곱셈의 역원을 가진다. 아래는 모듈로 11의 곱하기 연산표이다. 어떤 수를 곱해도 0이 되는 0은 제외하였다.

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

• 1 ~ 10의 모든 수에 같은 0이 아닌 수를 곱하면 그 결과는 중복되지 않는다.

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

• 선택한 수를 계속 곱해 보는 지수 연산에서도 주기적인 수열이 나온다. 특히 6처럼 원시근인 수는 1부터 10까지의 모든 수를 한 번씩 만든다.

  • 예를 들어 6의 지수 연산은 $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이다. 결과적으로 소수를 법으로 한 모듈로 연산에서는 0이 아닌 수로 나눌 수 있고, 교환법칙, 결합법칙, 분배법칙 등이 성립한다. 즉, 소수를 법으로 한 나머지 전체는 사칙연산이 가능한 체를 이룬다. 단, 일반적인 수 체계와 마찬가지로 0으로 나누는 연산은 정의되지 않는다.

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

$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 \equiv 8 \pmod{11} $$

지수 연산의 지수 부분만 자세히 보면 특성이 모듈로 10 연산과 비슷하다(모듈로 11이 아니다). 아래에서 다시 설명하겠지만 7과 3처럼 두 지수의 곱이 모듈로 10에서 1이 되어야 한다. 따라서 각 지수는 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은 소수이고 30의 배수가 아니므로 최대 공약수는 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이 남는다.

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

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

  $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이 나온다. 큰 정수의 경우라도 위와 같은 반복 연산을 하면 모듈로 연산의 곱셈 역원을 구할 수 있다. 단, 역원을 구하려는 수와 법의 최대 공약수가 1이어야 한다.

모듈로 지수 연산의 의미

일반적인 수의 지수 연산에는 로그 함수라는 역연산이 있다.

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

$$ x ^ y = z $$

밑이 x일 때 지수 y를 구하려면 다음과 같이 로그 함수를 적용하면 된다.

$$ \log_x(z) = y $$

일반적인 로그는 컴퓨터로 효율적으로 근삿값을 계산할 수 있다.

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

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

$x$를 1024번 곱할 필요 없이 $x$에서 시작해 제곱 연산을 10번 반복하면 된다. 이를 반복 제곱법이라고 한다.

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

지수 연산 방법은 거의 동일하다. 중간중간 모듈로 연산을 해서 나머지만 남기고, 위와 같이 반복 제곱법으로 연산 횟수를 줄일 수 있다.

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

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

지수 연산의 결과값이 한 방향으로 계속 커지는 것이 아니라 난수처럼 불규칙하게 나타난다.

이 경우 “모듈로 11에서 9는 7의 몇 승일까요?“처럼 지수를 찾는 문제를 이산 로그 문제라고 한다. 모듈로 11과 같은 작은 수라면 하나씩 7을 곱해서 답을 찾을 수 있지만, 암호에서 사용하는 아주 큰 소수에 대해서는 효율적인 고전 알고리즘이 알려져 있지 않아 현실적인 시간 안에 답을 찾기 어렵다.

이와 같은 소수 모듈로 연산의 특성과 이산 로그 문제의 어려움을 이용한 대표적인 알고리즘이 Diffie-Hellman 키 합의와 ElGamal 암호이다.

• 순방향 연산인 지수 연산은 연산 횟수를 줄여서 계산할 수 있다.
• 반대 연산인 이산 로그를 푸는 알고리즘도 있지만, 충분히 큰 수와 적절한 매개변수를 사용하면 현실적인 시간 안에 답을 찾기 어렵다.

갈루아 체와 확장

위와 같이 소수를 법으로 하여 사칙연산에 닫혀 있는 원소들의 집합을 갈루아 체(Galois field), 즉 유한체라고 한다.

법이 소수가 아니어도 그 법과 서로소인 원소끼리는 곱셈과 나눗셈이 가능하다. 우선 두 소수를 곱한 합성수 15(소수 3과 5의 곱)의 모듈로 연산을 보자. RSA에서는 이와 같이 두 소수의 곱을 법으로 사용한다.

위 표를 보면 일단 ×3과 같은 연산은 3, 6, 9, 12, 0, 3, 6, 9, 12, 0, 3, 6, 9, 12가 되어, 이와 같은 연산으로는 다시 복원할 수 없다.

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

위 연산을 보면 각 행에는 15와 서로소인 8개의 수가 중복 없이 나타난다. 예를 들어 15와 서로소인 임의의 수에 7을 곱한 것은 다시 7의 역원인 13을 곱하면 복원된다. 마찬가지로 15와 서로소인 수에 대한 지수 연산도 지수의 역원을 이용해 되돌릴 수 있다.

오일러의 정리

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

오일러의 파이 함수(Euler’s phi function)라는 공식이 있다. 일반적인 공식 대신 여기서는 서로 다른 두 소수의 곱인 경우만 고민해 보자.

예를 들어 서로 다른 두 소수 $p$, $q$에 대해 $m=p \cdot q$라면, 1부터 $m-1$까지의 수 중 $p$의 배수와 $q$의 배수를 제외하면 된다.

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

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

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

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

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

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

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

그래서 페르마의 소정리에서는 소수 $p$를 법으로 하여 아래처럼 되지만,

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

합성수 $m$을 법으로 할 때는 $p-1$ 대신 $m$과 서로소인 양의 정수의 개수를 사용한다. 이 개수를 나타내는 함수가 오일러 $\varphi(m)$이므로 정리하면 다음과 같다.

$$ k^{\varphi(m)} \equiv 1 \mod m \quad (\gcd(k,m)=1) $$

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

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

이때 k는 1~14 중 15와 서로소인 1, 2, 4, 7, 8, 11, 13, 14만 가능하다. 예를 들어 15와 서로소가 아닌 3을 대입하면 $3^8 \equiv 6 \pmod{15}$이므로 위 식이 성립하지 않는다.

이제 암호 원리로 이용할 수 있는지를 조금 더 큰 수로 확인해 보자.

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

$$ k^{20} \equiv 1 \mod 33 \quad (\gcd(k,33)=1) $$

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

$$3 \cdot 7 = 21 \equiv 1 \pmod{20}$$

그러면 임의의 수에 대해서 결과를 보면 다음과 같이 된다. 오일러 정리 자체는 33과 서로소인 수에만 적용되지만, 이 예에서는 $3 \cdot 7=21$이 2와 10을 법으로 하여 모두 1이므로 33과 서로소가 아닌 3과 11의 배수도 중국인의 나머지 정리에 따라 복원된다.

이 표는 RSA에서 사용하는 모듈로 지수 연산의 원리를 단순화한 예이다.

정리

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

Diffie-Hellman 키 합의와 ElGamal 암호는 이산 로그 문제의 어려움을 이용한다. RSA는 이와 달리 큰 합성수의 소인수분해가 어렵다는 점을 이용한다.

정리해 보면 다음과 같다.

• 소수 모듈로에서 순방향 지수 연산은 효율적이지만 이산 로그를 구하기는 어렵다. 이를 이용해 Diffie-Hellman 키 합의 알고리즘이나 ElGamal 비대칭 키 암호 등을 만든다.
• 두 개의 큰 소수는 쉽게 곱할 수 있지만, 그 곱을 다시 소인수분해하기는 어렵다. RSA 암호 방식은 이 어려움을 이용한다.

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