Public Key(공개키) 암호화

📡 Public Key(공개 키) 암호화

대칭키 암호화에서는 송신자와 수신자가 같은 비밀키를 미리 안전하게 공유해야 한다는 점이 큰 제약이었다. 특히 원거리 네트워크 환경에서는 이 초기 키 분배 자체가 어려운 과제로 남아 있었다.

이 문제를 해결하기 위해 등장한 것이 공개키 암호화(Public Key Cryptography)다.

1970년대 디피-헬먼(Diffie–Hellman), RSA 알고리즘(Rivest–Shamir–Adleman) 등의 연구를 통해 제안된 이 방식은 하나는 공개키, 다른 하나는 비밀키로 구성된 쌍(pair) 형태의 키 구조를 사용한다. 공개키는 누구나 볼 수 있도록 열려 있고, 이 키로 암호화된 메시지는 오직 대응되는 비밀키로만 복호화할 수 있다.

이 구조에서는 수신자인 Bob이 두 개의 키를 갖는다. 하나는 공개키(${K_B}^+$)로 누구나 알 수 있으며, 다른 하나는 개인키(${K_B}⁻$)로 오직 Bob만 알고 있다. 송신자인 Alice가 Bob에게 메시지를 보내고 싶을 때는, Bob의 공개키(${K_B}⁺$)를 사용해 메시지 $m$을 암호화한다. 암호화된 메시지는 ${K_B}⁺(m)$의 형태로 표현된다.

Bob은 이 암호문을 받아, 자신의 개인키(${K_B}⁻$)로 복호화한다. 복호화는 아래 방식으로 수행된다.

$$m = {K_B}⁻({K_B}⁺(m))$$

이 식은 공개키로 암호화한 메시지를 해당 개인키로만 되돌릴 수 있다. 반대도 가능하다. 개인키로 서명하고, 공개키로 그 서명의 진위를 검증할 수 있다. 이 방식은 디지털 서명에 활용되어 송신자의 신원을 보장하는 역할을 한다.

공개키 암호는 오랜 시간 대칭키 방식에 의존하던 암호학의 패러다임을 바꿨다. 무엇보다 보안에서 가장 어려운 과제였던 비밀키의 안전한 분배 문제를 우아하게 해결했다는 점에서 큰 전환점이 되었다.

흥미로운 사실은 이 기술이 1970년대 후반, 미국(Diffie-Hellman, RSA)과 영국(GCHQ)에서 거의 동시에, 하지만 서로 독립적으로 발명되었다. 영국에서는 이 아이디어가 한동안 기밀로 분류되어 세상에 알려지지 않았지만, 나중에 공개되면서 두 기술 흐름이 하나로 이어지게 되었다.

공개키 암호화가 제대로 작동하려면, 몇 가지 수학적 조건을 만족해야 한다.

첫째, 암호화와 복호화가 정확히 짝을 이루어야 한다. 수신자인 Bob의 공개키 ${K_B}^+$와 개인키 ${K_B}⁻$가 있을 때, Alice가 ${K_B}^+$로 암호화한 메시지는 반드시 아래와 같이 복호화할 수 있어야 한다.

$$m = {K_B}⁻({K_B}^+(m))$$

공개키로 암호화한 결과는 개인키로 정확히 되돌릴 수 있어야 한다. 암호화와 복호화 함수가 수학적으로 정확히 맞물려 동작하지 않으면, 기밀성은 깨지고 통신은 무의미해진다.

둘째, 공개키로는 개인키를 유추할 수 없어야 한다. 공개키는 누구나 알 수 있지만, 거기서 개인키를 수학적으로 추론하거나 계산하는 것이 사실상 불가능해야 한다. 이 불가능성은 특정 수학적 문제의 계산 난이도에 기반해 정해진다. 대표적인 수학적 문제는 아래와 같다.

• 소인수 분해(Factoring): 두 개의 큰 소수를 곱해 만든 수에서, 원래 소수를 역으로 찾아내는 문제
• 이산 로그 문제(Discrete Logarithm Problem): 지수 연산 결과에서 지수를 찾아내는 문제

이 문제들은 현재의 알고리즘과 컴퓨팅 성능으로는 효율적으로 풀기 매우 어렵기 때문에, 공개키 암호의 기반이 될 수 있다.

이런 조건을 충족하는 대표적인 알고리즘이 바로 RSA다. 1978년, 로널드 리베스트(Rivest), 아디 샤미르(Shamir), 레너드 애들먼(Adleman)이 개발한 이 방식은 소인수 분해의 어려움을 기반으로 설계되었다. 기본 구조는 아래와 같다.

• 두 개의 큰 소수를 곱해 만든 수 $N = pq$를 기반으로, 공개키와 개인키를 생성한다.
• 공개키는 $N$과 특정 지수값으로 구성되며,
• 개인키는 $N$의 소인수인 $p, q$를 알고 있어야 계산할 수 있다.

RSA는 겉으로 드러난 공개키만으로는 개인키를 알 수 없어 현재 기준으로 매우 안전한 암호화 방식으로 사용되고 있다.

모듈러 연산과 RSA에서의 활용

모듈러 연산(modular arithmetic)은 어떤 정수 $x$를 양의 정수 $n$으로 나누었을 때 그 나머지를 반환하는 연산이다. 일반적으로 다음과 같이 표기한다.

$$x \mod n$$

예를 들어, $14 \mod 10 = 4$다.

모듈러 연산은 덧셈, 뺄셈, 곱셈과 같은 산술 연산과 잘 결합되고 아래와 같은 성질들을 가진다.

• $[(a \mod n) + (b \mod n)] \mod n = (a + b) \mod n$
• $[(a \mod n) - (b \mod n)] \mod n = (a - b) \mod n$
• $[(a \mod n) \cdot (b \mod n)] \mod n = (a \cdot b) \mod n$

즉, 연산 전에 모듈러를 취하든, 연산 후에 한 번만 모듈러를 취하든 결과는 동일하다. 이러한 성질 덕분에 암호 알고리즘에서는 중간 계산값이 커지더라도 결과의 일관성을 유지할 수 있다.

RSA에서는 이런 형태의 연산이 자주 등장한다.

$$a^d \mod n$$

이때 $a \mod n$을 먼저 구한 뒤 지수 연산을 수행해도 결과는 변하지 않는다. 즉, 아래와 같은 성질이 성립한다.

$$(a \mod n)^d \mod n = a^d \mod n$$

이것이 바로 모듈러 거듭제곱(modular exponentiation)의 핵심적인 성질이고 RSA 암호화·복호화의 기초가 된다.

RSA 암호화에서 메시지는 비트 패턴으로만 간주된다. 즉, 어떤 텍스트든 이미지든 간에, 그것은 결국 이진수 형태의 데이터이며, 이 비트열은 하나의 고유한 정수로 표현될 수 있다. 따라서 RSA에서는 메시지를 암호화한다는 것은 사실상 숫자를 암호화하는 것과 같다.

예를 들어, 비트 패턴 10010001이 있다고 하자. 이 비트열은 이진수로서 10진수 145에 해당한다. 다시 말해, 메시지 m = 10010001은 정수 145로 고유하게 표현된다. RSA 암호화에서는 이 정수 m을 암호화 함수에 입력하여 새로운 정수 c를 출력하는 방식으로 동작한다. 이 출력된 숫자 c가 암호문(ciphertext)이 되는 것이다.

RSA에서 공개키와 개인키를 생성하는 과정은 정수론의 원리를 기반으로 하며, 암호화와 복호화에 사용할 수 있는 수학적으로 짝을 이루는 키 쌍을 만드는 절차다.

첫째, 두 개의 매우 큰 소수 $p$와 $q$를 선택한다. 보안 강도를 위해 일반적으로 각 수는 1024비트 이상의 크기를 가진다. 이 두 소수는 비밀로 유지되어야 하며, RSA의 안전성은 이 값들이 충분히 크고 무작위라는 가정에 의존한다.

둘째, $n = pq$를 계산한다. 이 값은 공개키와 개인키 모두에 사용되며, 모듈러 연산의 기반이 된다. 또한 $z = (p-1)(q-1)$도 함께 계산하는데, 키 생성 과정에서 필요한 수로서 오일러 피 함수의 일종이다.

셋째, $z$와 서로소(relatively prime)인 정수 $e$를 선택한다. 즉, $\gcd(e, z) = 1$이어야 하며, $e$는 일반적으로 $n$보다 작고 계산 효율이 좋은 소수값이 선택된다. 자주 사용되는 값 중 하나는 $e = 65537$이다.

넷째, $d$를 계산한다. 이 값은 $ed \equiv 1 \mod z$를 만족하는 정수로, $e$의 모듈러 역원(modular inverse)이다. 즉, $d$는 $e$에 대해 모듈러 $z$ 위에서 곱했을 때 1이 되도록 만드는 수이다. 이 $d$가 바로 개인키의 핵심이다.

이 과정을 통해 두 개의 키가 생성된다.

• 공개키는 ($n, e$)이며, 누구나 알 수 있고 암호화 시 사용된다.
• 개인키는 ($n, d$)이며, 오직 수신자만 알고 있어야 하며 복호화에 사용된다.

정리하자면, 송신자는 수신자의 공개키를 사용해 메시지를 다음과 같이 암호화한다.

$$c = m^e \mod n$$

수신자는 자신의 개인키를 사용해 암호문을 복호화한다.

$$m = c^d \mod n$$

이 구조는 공개키로 암호화한 메시지를 오직 해당 개인키로만 복호화할 수 있도록 보장하며, RSA의 핵심 수학적 아이디어를 구성한다. 중요한 점은 $n$과 $e$가 알려져도, $p$와 $q$를 모르면 $d$를 역으로 계산하기가 매우 어렵다는 것이다. 이 계산 불가능성이 RSA의 보안성을 뒷받침하는 기반이 된다.

핵심은 공개키와 개인키가 서로 반대 연산을 수행하도록 구성되어 있다는 점이다. 이로 인해 누구나 암호화는 가능하지만, 오직 키를 가진 사람만 복호화가 가능하다.

먼저 공개키 ($n, e$)와 개인키 ($n, d$)가 주어졌다고 가정하자. 여기서 $n$은 두 개의 큰 소수 $p$와 $q$의 곱이고, $e$는 암호화에 사용되는 지수이며, $d$는 복호화에 사용되는 지수다. 이 둘은 오일러 피 함수 $(p-1)(q-1)$에 대해 서로 모듈러 역 관계를 가진다.

암호화는 다음과 같이 수행된다. 어떤 메시지 $m$이 있다고 하자. 이 메시지는 정수로 표현되고 $m < n$을 만족해야 한다. 암호문 $c$는 다음과 같이 계산된다.

$$c = m^e \mod n$$

이렇게 계산된 $c$는 암호화된 메시지로, 누구든 공개키 $(n, e)$를 알면 생성할 수 있다.

복호화는 수신자가 자신의 개인키 $(n, d)$를 사용해 암호문 $c$로부터 원래 메시지 $m$을 복원하는 과정이다:

$$m = c^d \mod n$$

이 연산이 정확하게 원래의 m으로 복원되는 이유는 RSA 구조상 다음 관계가 성립하기 때문이다.

$$m = (m^e)^d \mod n = m^{ed} \mod n$$

여기서 $ed \equiv 1 \mod (p-1)(q-1)$이라는 수학적 관계가 있기 때문에, 페르마의 소정리와 오일러 정리를 기반으로 이 등식이 성립하며, 정확한 복호화가 가능하다. 이것이 RSA의 “마법 같은” 부분이며, 평문을 공개된 방식으로 암호화하면서도 특정 개인만이 그 내용을 복원할 수 있게 만든다.

먼저 Bob이 다음과 같은 값을 선택했다고 가정하자

• 소수 $p = 5, q = 7$
• $n = p \times q = 35$
• $z = (p - 1)(q - 1) = 4 \times 6 = 24$

그다음 Bob은 공개 지수 $e = 5$를 선택했는데, 이는 $z = 24$와 서로소(relatively prime)이므로 적절한 선택이다. 이제 개인키 $d$는 $ed \equiv 1 \mod z$를 만족해야 한다. 여기서 $e = 5, d = 29$는 실제로 $5 \times 29 = 145 \equiv 1 \mod 24$ 이므로 조건을 만족한다.

따라서 Bob의 공개키는 $(n = 35, e = 5)$, 개인키는 $(n = 35, d = 29)$이다.

이제 암호화를 해보자. 메시지 비트열은 00001100으로, 이는 10진수로 $m = 12$이다.

암호화는 공개키를 사용하여 다음과 같이 수행된다.

$c = m^e \mod n = 12^5 \mod 35$

$12^5 = 24832,$ 그 다음 $24832 \mod 35 = 17$

즉, 암호문 $c = 17$

이제 복호화를 수행해보자. 암호문 $c = 17$을 개인키로 복호화한다.

$m = c^d \mod n = 17^{29} \mod 35$

이 값은 계산상 매우 크지만, 실제로 계산하면 $17^{29} \mod 35 = 12$가 된다. 이는 원래의 $m = 12$와 일치한다.

RSA가 작동하는 이유는 핵심적으로 수론, 특히 모듈러 산술(modular arithmetic)의 성질에 기반하고 있다. 우리는 암호화된 메시지 $c = m^e \mod n$를 다시 복호화하여 $m$을 얻을 수 있어야 하고 아래 식을 증명해야 한다.

$$c^d \mod n = m$$

이 과정을 이해하기 위해서는 $n = pq, z = (p - 1)(q - 1)$, $ed \equiv 1 \mod z$를 만족한다는 점이 중요하다. 즉, $ed = 1 + kz$ (어떤 정수 $k$에 대해)라는 관계가 성립한다.

RSA의 암호화와 복호화는 다음과 같이 이루어진다.

1. 암호화: $c = m^e \mod n$
2. 복호화: $c^d = (m^e)^d = m^{ed} \mod n$

이제 핵심은 $m^{ed} \mod n = m$이 항상 성립함을 보여야 하는 것이다.

이때 사용할 수 있는 중요한 수학적 사실은 다음과 같다.

$$m^{ed} \mod n = m^{(1 + kz)} \mod n = m \cdot (m^z)^k \mod n$$

여기서 $m^z \equiv 1 \mod p$ 및 $\mod q$가 되는 이유는 오일러의 정리(Euler’s theorem)에 따라, $m$이 $p$와 $q$의 배수가 아닌 한 $m^{p-1} \equiv 1 \mod p$, $m^{q-1} \equiv 1 \mod q$가 성립하며, $z = (p-1)(q-1)$이기 때문에 $m^z \equiv 1 \mod n$도 성립한다.

따라서,

$$m^{ed} \mod n = m \cdot 1^k \mod n = m \mod n$$

결국,

$$c^d \mod n = m$$

즉, 암호문을 개인키로 복호화하면 원래 메시지와 정확히 일치하게 된다. 이 구조가 가능한 이유는 $e$와 $d$가 $z = (p-1)(q-1)$에 대해 모듈러 역원 관계에 있기 때문이며, 이 수학적 성질이 RSA의 정확성과 보안성을 동시에 보장해준다.