[암호학] 1. RSA

이전 글에서는 보안의 기본 개념과 대표적인 암호 시스템에 대해 간략하게 설명했습니다.
비대칭 암호에서 어려운 문제란 무엇이고 그것이 어떻게 사용되는지 알아보겠습니다. 자세한 내용보다는 개념 위주로 서술하겠습니다.

RSA 암호

RSA 암호는 IFP (Integer Factorization Problem) 문제를 사용합니다. IFP 문제는 간단히 소인수분해라고 생각하면 됩니다.

$pq = n$일 때, $p$와 $q$를 이용해 $n$을 구하는 것은 쉽지만 $n$으로 $p$와 $q$를 구하는 것은 어렵습니다.

Number Theory

소수

먼저 소수(prime number)가 무엇인지에 대해 알아보겠습니다.

소수 $p$는 $1$보다 크며, $\pm1, \pm p$만을 약수로 가집니다.

또한 이 소수들의 곱을 이용하면 모든 수를 표현할 수 있습니다.

1보다 큰 모든 정수 $a$에 대하여, $a = p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdots p_{t}^{\alpha_{t}} (p_{1} < p_{2} \cdots < p_{t},\ p_{i}\ \text{is prime number})$ 로 표현할 수 있는 단 하나의 방법이 존재합니다.

서로소

최대공약수에 대한 설명은 생략하겠습니다. 두 수 $a$, $b$에 대해서 $c = \gcd(a, b)$를 $a$, $b$의 최대공약수라고 합니다.
만약 $\gcd(a, b) = 1$이라면 $a$와 $b$는 서로소입니다.

모듈러 연산

어떤 정수 $a$와 양의 정수 $n$이 있을 때, $a$를 $n$으로 나누면 다음과 같은 관계가 성립합니다.

$a = q \cdot n + r,\ 0 \leq r \leq n\ \text{and}\ q = \lfloor a / n\rfloor$. $q$는 몫, $r$은 나머지입니다.
여기서 $a\mod\ n$은 $r$, 즉 나머지가 됩니다.

만약 $a\mod n = b\mod n$이라면 $a \equiv b\mod n$이라고 쓰며, $\text{mod}\ n$에 대해 합동이라고 합니다.

Euler's Totient Function

오일러의 토션트 함수 또는 오일러의 파이 함수라고 부르는 함수가 있습니다.
이 함수는 양의 정수 $n$에 대해 $n$보다 작은 정수 중 1을 포함한 서로소의 개수를 나타냅니다.
표기는 다음과 같습니다.

$\phi (n)$

오일러 토션트 함수는 다음과 같은 성질이 있습니다.

어떤 양의 정수에 $n$에서 다른 소수 $p$, $q$에 대해, $n = p \times q$일 때, $\phi (n)$은 다음과 같이 정해집니다.
$\phi (n) = \phi (pq) = \phi (p)\phi (q) = (p-1)(q-1)$

페르마의 소정리

페르마의 소정리는 다음과 같습니다.

$p$가 소수이고 $a$가 $p$로 나눠지지 않을 때 $a^{p-1} \equiv 1\mod p$가 성립합니다.

증명은 생략하겠습니다.

오일러의 정리

오일러의 정리는 페르마의 소정리의 일반화를 통해 얻어집니다.

모든 서로소인 $a$와 $n$에 대해 $a^{\phi (n)} \equiv 1\mod n$이 성립합니다.

오일러 토션트 함수의 성질을 이용해 다음과 같은 따름정리가 나오게 됩니다.

두 개의 소수 $p$와 $q$에 대해 정수 $m$과 $n$이 $n = pq$이고 $0<m<n$일 때,
$m^{\phi (n) + 1} = m^{(p-1)(q-1) + 1}\equiv m\mod n$

RSA 암호의 구현

이제 위와 같은 정리들을 이용해 만들어진 RSA 암호를 살펴보겠습니다.

키 생성

1. 두 개의 소수 $p$와 $q$를 정합니다.
2. $pq = n$과 $(p-1)(q-1) = \phi (n)$을 구합니다.
3. $\phi (n)$과 서로소인 정수 $e$를 고릅니다.
4. $1\mod \phi (n) = ed$가 되도록 $d$를 찾습니다.

여기서 $n$과 $e$가 공개키, $d$가 개인키가 됩니다. 왜 그럴까요?
그 이유를 설명하기 위해서 암호화 과정과 복호화 과정을 설명하겠습니다.

암호화와 복호화

• 암호화
  $C = M^e \mod n\ for\ 0 < M < N$ (여기서 $M$은 평문, $C$는 암호문입니다.)
• 복호화
  $M = C^d \mod n$

복호화가 왜 성립하는지 증명하겠습니다.

$C^d = M^{ed}$까지는 암호화의 과정을 적용시키면 쉽게 계산할 수 있습니다.
키 생성 과정의 4번에서 모듈러의 정의를 적용시키면 $ed = k\phi (n) + 1$이 나오고,
$M^{\phi (n)}$에 오일러 정리를 적용하면 1이 됩니다.

암호화 과정과 복호화 과정을 함수로 나타내면 다음과 같습니다.

이전 글에서 비밀통로 일방향 함수는 특정한 정보를 알고 있다면 역함수를 구하기 쉽다고 설명했습니다.
여기서 $d$를 알고 있다면 역함수를 구하기 쉬울 것입니다.
암호문을 보내는 사람이 공개키로만 암호를 만들면 개인키를 가지고 있는 수신자는 다시 암호를 평문으로 변환할 수 있게 됩니다.

다음 글에서는 또 다른 어려운 문제인 DLP와 그 어려움을 이용한 ElGamal에 대해서 설명하겠습니다.