[정보보안] 비대칭키 암복호화, 전자서명

1. 비대칭키 암호의 필요성

전통적인 대칭키 암호 방식에서는 송신자와 수신자가 동일한 키를 공유해서 가지고 있어야한다. 여기에서 같은 키를 어떻게 안전하게 상대에게 전달할 수 있는지 문제가 있다. 키를 상대에게 보내는 것 자체가 중간에 탈취될 우려도 있고 보안 취약점이다. 또한, n명의 사용자가 서로 통신을 하기 위해 암호 키를 공유해야한다면 $n(n-1)/2$개의 키가 필요하게 된다. 이는 관리 복잡성을 기하급수적으로 늘어난다는 문제가 있다.

 

이러한 대칭키의 한계를 극복하기 위해 비대칭 키(Asymmetric Key)라는 것이 생겼다.

• 공개키(Public Key): 누구나 알 수 있으며, 암호화나 서명 검증에 사용된다.
• 개인키(Private Key): 소유자만 알고 있어야 하며, 복호화나 서명 생성에 사용된다.

이 방식은 비밀 키 공유를 위한 신뢰할 수 있는 센터(Key Distribution Center) 없이도 안전한 통신을 가능하게해 키분배 문제를 해결했다. 또한, 메시지의 무결성을 확인하는 전자서명(Digital Signature) 기능을 제공할 수도 있다. 

 

비대칭키 암호는 1.암복호화 2.인증(전자서명) 3.키교환 세가지 정도로 활용된다. 비대칭키 암호 알고리즘 중 Diffie-Hellman은 키 교환에만 사용되고, DSS는 전자서명에만 특화되어있다. 각 알고리즘의 특징은 나중에 다시 살펴볼 것이다.

---

2. 비대칭키 암호의 수학적 기반: Trapdoor One-way Function

비대칭키 암호는 Trapdooor One-way Function이라는 아이디어에 기반한다. trapdoor는 비밀통로, 은밀한 탈출구 등을 의미한다. 

 

One-Way Function (OWF)

1. $f$는 계산하기 쉬워야한다.
2. $f^{-1}$는 계산하기 어려워야한다.

Trapdoor One-Way Function (TOWF)

• Trapdoor라는 추가 정보가 주어지면 역산($f^{-1}$ 계산)이 쉬워지는 단방향 함수이다.

비대칭키 암호는 여기서 아이디어를 얻었다. private key(개인키)가 trapdoor 역할을 해서 개인키를 가지고 있는 사람만 쉽게 역산을 통해 원래 문장으로 복호화 할 수 있게 하고 개인키가 없는 사람은 복호화가 매우 어렵게 되는 것이다.

 

[예시]

• 소인수분해 문제: 두 큰 소수 $p, q$의 곱 $n$을 구하기는 쉽지만, $n$으로부터 $p, q$를 찾는 것은 매우 어렵다.
• 이산 대수 문제: $y = x^k \pmod n$ 연산에서 $x, k, n$으로 $y$를 구하기는 쉽지만, $y, k, n$으로 $x$를 구하기는 어렵다. 하지만 $k \times k' \equiv 1 \pmod{\phi(n)}$을 만족하는 trapdoor $k'$을 알면 복호화가 가능하다.

이런 수학적 이론들은 실제 비대칭키 암호 알고리즘에서 사용된다.

---

3. 비대칭키 암호화 / 복호화

비대칭키의 암복호화는 아래 과정으로 이뤄진다.

1. 키 쌍 생성: 수신자 B는 자신의 공개키(PubB)와 개인키(PrivB) 쌍을 생성한다.
2. 암호화 (Src A): 송신자 A는 공개된 채널을 통해 얻은 수신자 B의 공개키(PubB)를 사용하여 평문 메시지 $M$을 암호화 알고리즘에 입력한다. 그 결과로 암호문 $C$가 생성된다.
3. 전송: 암호문 $C$는 안전하지 않은 채널을 통해 전송된다. 이때 도청자(Cryptanalyst)는 $C$와 PubB를 가로챌 수 있지만, 메시지 $M$의 내용을 알아내거나 개인키를 유도하는 것은 계산적으로 불가능하다.
4. 복호화 (Dst B): 수신자 B는 자신만이 보유한 개인키(PrivB)를 사용하여 암호문 $C$를 복호화 알고리즘에 입력하고 원래의 평문 $M$을 복구한다. 즉, 개인키를 아는 사람(B!)만이 이를 해독할 수 있다.

 

한마디로 요약하면 수신자의 공개키로 암호화해서 수신자가 자신의 개인키로 복호화하는 구조이다. 공개키는 누구나 봐도 상관없고 메시지 암호화에 사용된다. 개인키만 털리지 않으면 되기 때문에 공개키를 송신자에게 공유해줄 때 쉽게 전달이 가능하다는 엄청난 장점이 있다. 중간에 공격자가 메시지를 탈취해도 공개키로는 복호화가 불가능하고 개인키로만 복호화가 가능하기 때문에 수신자만 메시지를 확인할 수 있는 안전한 구조가 된다.

---

4. 전자서명 (Digital Signature)

 

전자서명은 송신자가 메시지를 보냈음을 다수의 수신자가 확인할 수 있게 하는 시스템이다. 

1. 서명 생성 (Src A): 송신자 A는 메시지 $M$에 대해 자신의 개인키(PrivA)를 사용하여 서명 알고리즘을 적용한다. 결과물은 메시지와 서명이 결합된 형태 $(M, \text{Sign}(M))$이거나 별도의 서명 값 $\text{Sign}(M)$이 된다.
2. 전송: 메시지와 서명이 수신자 B에게 전달된다. 도청자는 이를 가로챌 수 있지만, A의 개인키 없이는 동일한 서명을 위조할 수 없다.
3. 서명 검증 (Dst B): 수신자 B는 송신자 A의 공개키(PubA)를 사용하여 전달받은 서명을 검증 알고리즘에 입력한다.
4. 결과: 검증 과정에서 서명이 유효하다고 판단되면, 이 메시지는 반드시 A가 작성한 것이며 전송 도중 내용이 바뀌지 않았음이 수학적으로 증명된다. 즉 A의 서명에 대한 검증은 A의 공개키로 이뤄진다.

 

한마디로 요약하면 송신자가 자신의 개인키로 암호화하고 다수의 수신자들이 공개키로 복호화가 가능한 것을 통해 이 메시지가 송신자가 개인키로 암호화해서 보낸 것이 맞구나 하고 증명되는 구조이다. 공격자가 송신자인척 위장하고 싶어도 송신자의 개인키를 알아야 하기 때문에 불가능하게 된다.