컴퓨터공학부: 암호학 / 현대암호학 개론

1. 과목에서 배울 수 있는 내용

암호는 정보를 다른 사람이 이해할 수 없도록 가공한 것을 말합니다. 암호학은 중요한 정보를 다른 사람으로부터 숨기기 위해, 주로 군사적인 목적으로 발전해 왔습니다. 현대의 암호학은 단순히 정보를 숨기는 것에서 더 나아가, 정보 전달이 이루어지는 의사소통 과정을 안전하고 신뢰할 수 있도록 설계하는 방법을 탐구합니다. 이를 통해 우리는 정보를 안전하게 숨기거나, 정보의 출처를 신뢰할 수 있는 방법으로 입증할 수 있습니다. 또한, 정보가 가공되지 않았음을 보장하거나, 정보 교환 과정에서 제3자 개입이 불가능하도록 안전성을 높일 수 있습니다.

컴퓨터공학의 발전으로 정보 교환이 기하급수적으로 늘어나고 있습니다. 정보 교환 과정을 어떻게 안전하게 만들지, 나아가 어떻게 더 빠르고 효율적으로 만들지에 대한 문제는 컴퓨터공학의 중요한 연구 주제 중 하나입니다. 암호학 수업에서는 이러한 과정에 대해 실제 물리적인 구현보다는 수학적, 이론적인 내용에 초점을 맞춰 배우게 됩니다. 이 수업을 듣는다고 해킹을 하거나 남의 비밀번호를 알아낼 수 있는 것은 아니지만 (ㅎㅎ) 그 저변에 깔려 있는 수학적인 원리에 대해 배울 수 있는 재미있는 과목입니다.

제가 수강한 22년 봄학기에는 ‘암호학’ 이라는 대학원 과목이었는데 이번 23년 가을학기부터는 ‘현대암호학 개론’ 이라는 학부 과목으로 개설된다고 합니다. 이 과목에서 공부하게 되는 몇 가지 기초적인 내용들을 알아봅시다.

1-1. 대칭 키 암호와 비대칭 키 암호

암호학에서 하는 가장 기본적인 일은 어떤 정보, 즉 문자열을 알아볼 수 없도록 암호화하고, 이를 다시 원래대로 복호화하는 것입니다. 암호화하기 전의 문자열을 평문(plaintext) 이라 하고, 암호화한 이후의 문자열을 암호문(ciphertext) 이라고 합니다. 암호문을 아무나 복호화할 수 있으면 안 되기 때문에, 암호화와 복호화 과정에서는 평문이나 암호문 이외에도 추가적인 정보를 알아야 합니다. 이를 나타낸 문자열을 키(key) 라고 합니다.

암호화와 복호화에 사용되는 키가 꼭 같을 필요는 없습니다. 두 키가 같은 암호를 대칭 키 암호, 다른 경우를 비대칭 키 암호라고 합니다. 두 종류 암호가 동작하는 과정을 그림을 통해 간단히 살펴봅시다. 참고로 암호학에서는 동작 과정을 설명하기 위해 국룰처럼 항상 사용되는 등장인물이 있는데, 바로 앨리스(Alice)와 밥(Bob)입니다.

먼저 몇 가지 기호가 필요합니다. 평문을 $m$, 암호문을 $c$ 라는 기호로 나타냅시다. 대칭 키 암호에서는 암호화와 복호화에 사용되는 키를 $k$ 라는 기호로 나타내겠습니다. 키 $k$를 이용해 평문 $m$을 암호문 $c$로 암호화하는 과정을 $c \leftarrow \mathrm{Enc}(k,m)$ 로 나타낼 수 있습니다. 반대로 키 $k$를 이용해 암호문 $c$를 평문 $m$으로 복호화하는 과정을 $m \leftarrow \mathrm{Dec}(k,c)$로 나타낼 수 있습니다.

그림 1. 대칭 키 암호의 동작 과정

 

비대칭 키 암호에서는 암호화에 사용되는 키를 $pk$, 복호화에 사용되는 키를 $sk$라는 기호로 나타내겠습니다. 이는 각각 공개 키 (secret key), 비밀 키 (public key)를 의미합니다. 메시지를 받는 사람(Bob)은 비밀 키를 자기 혼자만 알 수 있도록 숨기고, 공개 키를 누구나 볼 수 있게 공개합니다. 메세지를 보내는 사람(Alice)는 공개 키를 사용해 메시지를 암호화합니다. Alice가 Bob에게 보낸 암호문은 오직 비밀 키를 알고 있는 Bob만이 복호화할 수 있습니다.

그림 2. 비대칭 키 암호의 동작 과정

 

대칭 키 암호를 사용하려면 두 사람이 동일한 키를 공유해야 합니다. 그런데 만약 두 사람이 먼 거리에 떨어져 있다면 키를 안전하게 공유하는 것이 어려울 수도 있습니다. 반면, 비대칭 키 암호를 사용하면 비밀 키는 소유자만이 가지고 있고, 공개 키를 누구나 볼 수 있도록 할 수 있습니다, 따라서 키를 안전하게 공유하는 문제를 해결하고, 보안에 필요한 노력을 줄일 수 있습니다. 뿐만 아니라, 메시지를 수신하는 사람만이 암호문을 복호화할 수 있기 때문에 일대일이 아닌 일대다 형태로도 메시지를 주고받을 수도 있습니다.

그러나 비대칭 키 암호에도 단점이 있습니다. 일반적으로 비대칭 키 암호는 대칭 키 암호에 비해 번거롭고 계산 비용이 많이 듭니다. 따라서 비대칭 키 암호를 이용해 대칭 키 암호의 키를 안전하게 공유하고, 그 다음부터는 대칭 키 암호를 사용해 효율적으로 메시지를 주고받는 경우도 많습니다.

1-2. 어떤 암호가 ‘안전하다’ 라는 것은 무엇일까?

현대 암호학은 안전한 암호를 설계하기 위해 수학적인 도구를 사용합니다. 수학적으로 논리를 전개하기 위해서는 엄밀한 정의가 먼저 이루어져야 할 것입니다. 암호의 안전성을 어떻게 수학적으로 정의할 수 있을까요? 이상적으로 안전한 암호의 경우, 메시지를 보내는 사람과 받는 사람 외에는 누가 어떠한 방법을 쓰더라도 암호문의 정보를 알아낼 수 없어야 할 것입니다. 하지만 이러한 개념을 그대로 수학적인 정의로 옮기기는 어려운 일입니다.

암호학에서 안전성을 정의하는 방법은 맥락에 따라 아주 다양합니다. 그 중에서 “security game”이라고 불리는 일종의 상황극을 활용하는 방법이 있습니다. 대칭 키 암호의 안전성 중 하나인 “semantic security”를 security game을 이용해 설명하는 과정을 그림으로 살펴봅시다.

그림 3. Semantic Security의 Security Game

 

위 상황에서, 만약 Alice가 Bob이 보낸 암호문 $c$로부터 어떠한 유의미한 정보라도 알아낼 수 있다면, 이는 Alice가 답을 맞추는 데 도움이 될 수 있습니다. 이 Security Game을 충분히 많이 반복한다면, Alice는 50%보다 큰 확률로 답을 맞출 수 있을 것입니다.

그러나 반대로 Alice가 어떠한 정보도 알아낼 수 없다면, Alice의 최선의 전략은 답을 0 또는 1 중 하나로 랜덤하게 선택하는 것입니다. 이때 Alice는 50%의 확률로 답을 맞추게 될 것입니다.

이를 통해 우리는 암호의 안전성을 설명하는 데 확률을 사용할 수 있습니다. Alice가 $b = 0$인 경우와 $b = 1$인 경우를 구분할 수 없다면, 이 암호는 안전하다고 말할 수 있습니다. 조금 더 엄밀하게 말하면, Alice가 답을 맞출 확률이 50%보다 유의미하게 크도록 만들어주는 알고리즘이 존재하지 않는다면, 이 암호는 안전합니다.

이러한 정의에 따르면, 어떠한 암호가 안전하다는 것을 증명하기 위해서는 $b = 0$인 경우와 $b = 1$인 경우를 구분하는 알고리즘이 존재하지 않는다는 것을 보여야 합니다. 그런데 어떤 것이 존재하지 않는다는 것을 증명하는 것은 매우 어려운 일이며, 따라서 이 방법을 그대로 사용해 어떤 암호가 안전하다는 것을 정확하게 입증하는 것은 사실상 불가능합니다. 그렇다면 왜 이러한 정의를 사용할까요?

이러한 정의의 장점은 “암호 X가 안전하다면, 암호 Y도 안전하다"와 같은 논의를 쉽게 펼칠 수 있다는 점에 있습니다. 만약 어떤 암호를 만들 때 수학적으로 어려운 문제를 이용한다면, 암호의 안전성에 대한 믿음의 근거를 확보할 수 있습니다. 예를 들어, 다음과 같은 논의가 가능합니다.

“암호 Y가 안전하지 않다면, 이는 수학적으로 어려운 문제인 X를 해결하는 알고리즘이 존재한다는 뜻이다. 한편 X는 수학계의 난제로, 아직 X를 해결하는 효율적인 알고리즘이 발견되지 않았다. 따라서 X가 해결되지 않는 한, 암호 Y는 안전하다!”

1-3. 암호학의 최신 주제 - 다자간 계산과 영지식 증명, 동형 암호

과거의 암호학에서는 주로 정보를 알아볼 수 없도록 숨기는 암호화-복호화에 중점을 두었다면, 현대 암호학에서는 이러한 암호화-복호화를 활용하여 다양한 의사소통 방식을 안전하게 만드는 방법을 연구합니다. 얼핏 들으면 어렵거나 불가능해 보이는 일도 암호학의 힘을 빌어 가능하게 만들 수 있습니다. 몇 가지 예시를 살펴봅시다.

---

1-3-1. 다자간 계산

두 명의 백만장자가 둘 중 누구의 재산이 더 많은지 알고 싶어합니다. 그런데 둘 모두 자신의 정확한 재산을 본인 외의 다른 사람 누구에게도 공개하고 싶지 않습니다. 이 두 사람은 어떻게 서로의 재산을 비교할 수 있을까요?

이 문제는 암호학자 Andrew Yao가 제시한 ‘백만장자 문제’라는 유명한 문제입니다. 이 문제에 대한 Yao의 답은 안전한 다자간 계산(Secure Multiparty Computation)이라는 연구 분야의 출발점이 되었습니다. 이 분야에서는 여러 명의 사람들이 자신의 정보를 숨긴 채로 서로의 정보를 활용해 가치 있는 새로운 정보를 만들어내는 방법에 대해 연구합니다.

1-3-2. 영지식 증명

내가 알고 있는 정보의 내용을 공개하지 않은 상태에서, 상대방에게 ‘내가 정보를 알고 있다’ 라는 사실만을 논리적으로 증명할 수 있을까요? 이는 암호학에서 영지식 증명(Zero-knowledge Proof)라고 불리는 문제입니다. 이 문제는 말이 안 되는 것 같아 보이지만, 정확한 정보를 알고 있어야만 답할 수 있는 질문을 주고받는 방식으로 해결할 수 있습니다. 여기에서 문제는 상대방은 정보를 전혀 모르는 상태로 질문을 던질 수밖에 없고, 정보의 소유자는 질문에 답하는 과정에서 정보를 전혀 노출하고 싶지 않다는 점입니다. 영지식 증명은 이러한 과정을 체계화하여, 수학적인 논증을 통해 안전을 보장합니다. 암호학에서는 주로 풀기 매우 어려운 방정식 $F(\mathbf{x}) = 0$이 주어진 상태에서, 이 방정식의 해 $\mathbf{x}$를 알고 있다는 사실을 증명하는 방식으로 영지식 증명이 이루어집니다.

1-3-3. 동형 암호

암호화의 목적은 정보를 숨기는 것에 있기 때문에, 평문과 암호문 사이에는 어떠한 연관성도 드러나서는 안 됩니다. 따라서 일반적으로 암호화 과정은 평문의 연산 구조를 보존하지 않습니다. 예를 들어 1을 암호화한 결과와 2를 암호화한 결과를 더하더라도 3을 암호화한 결과가 나오지는 않습니다. 동형 암호는 암호화 과정에서 평문의 연산 구조를 보존하는 방법에 대해 연구하는 분야입니다. 정보를 숨기는 것과 연산 구조를 보존하는 것, 두 가지 목표를 동시에 이루어야 하기 때문에 매우 어렵습니다.

---

이렇게 현대 암호학에서 다루는 주제 중 세 가지를 간단히 살펴보았습니다. 이들은 자체로도 흥미로운 문제들이지만, 이를 통해 우리의 개인정보를 보호하는 방법을 향상시킬 수 있다는 점에서 매우 중요합니다.

우리는 인터넷에서 다양한 서비스를 사용하면서 습관적으로 많은 개인정보를 서비스 제공 업체에게 제공합니다. 서비스 제공 업체는 이러한 개인정보를 활용해 새로운 가치를 창출하고 이를 다시 우리에게 제공합니다. 우리는 서비스를 제공받기 위해 항상 위험을 감수하고 개인정보를 노출하고 있습니다.

암호학 기술이 더욱 발전한다면, 우리는 최소한의 개인정보만을 제공하고도 서비스를 제공받을 수 있을 것입니다. 예를 들어, 동형 암호를 사용하면 우리의 개인정보를 암호화한 상태로 업체에게 보내고, 업체는 암호화한 상태로 연산을 수행한 뒤 그 결과를 우리에게 돌려줄 수 있습니다. 이 과정에서 업체는 연산만 수행할 뿐, 우리의 개인정보를 알아낼 수 없습니다. 또한 영지식 증명을 활용하면 신원을 노출하지 않은 상태로 금융 거래를 수행하고, 거래에 정당하게 참여했다는 사실을 증명할 수 있습니다.

이렇듯 최신 암호학 기술들은 미래 우리의 개인정보 보호에 있어 매우 중요한 역할을 하게 될 것입니다. 소개한 세 가지 주제는 이미 해결 방법이 제시되었지만, 실행 속도가 느리거나 제한적인 상황에만 적용할 수 있는 등 한계점이 존재합니다. 더 효율적이고 더 다양한 상황에 적용 가능한 방법을 찾아내기 위해 지금도 많은 암호학자들이 연구하고 있습니다.

2. 선배의 조언

암호학이라는 분야 자체가 수학을 기본으로 하다 보니, 과목을 수강하기 전 수학에 겁을 내는 경우가 많은 것 같습니다. 하지만 의외로 수학적인 사전 지식은 많이 필요하지 않습니다. 정수론이나 대수학 지식이 조금 등장하지만 수업을 들으면서 충분히 따라갈 수 있는 정도입니다. 다만, 어떤 암호가 안전하다는 것을 설명하기 위해, 또 안전한 암호를 만들기 위해 암호학 특유의 수학적인 논리가 자주 사용됩니다. 여기에 익숙하지 않다면 어려움을 겪을 수 있습니다. 학기 초반부부터 증명이 자주 등장하는데, 전개 과정을 세심하게 따라가면서 왜 이런 방식으로 설명하는지, 또 어떤 아이디어가 핵심인지 이해할 수 있도록 노력해야 합니다.

학기 후반에는 팀을 이뤄 프로젝트를 수행하게 되는데, 이 강의를 통해 암호학을 처음 접했다면 다소 막막할 수 있습니다. 하지만 주제 선정이 논문 리뷰, 활용 아이디어 제안 등 매우 자유롭기 때문에 재미있는 주제가 많을 것이라 생각합니다. 영지식 증명이나 동형 암호처럼 최근 활발하게 연구되고 있는 분야들을 잘 살펴보면 흥미로운 논문들이 많습니다. 암호학 기술들이 어떻게 적용되고 있는지 알아보고 싶다면 가상화폐 분야를 찾아보는 것도 좋을 것 같습니다.

3. 진로 선택에 도움 되는 점

암호학은 빠르게 발전하고 있으며, 이론적인 분야에서도 연구 주제가 끊이지 않고 있습니다. 특히 1-3에서 소개한 최신 주제들은 아직 미지의 영역인 부분이 많습니다. 암호학의 중요성이 커짐에 따라 미래에 암호나 보안과 관련된 진로를 선택하는 사람이 많아질 것이라 생각하는데, 그런 분들에게 이 과목은 필수라고 생각합니다. 또한, 암호학 특유의 논리 전개 방식은 알고리즘 등 컴퓨터공학의 다른 분야를 이해하는 데도 도움이 된다고 생각합니다.

다른 분야에 활용할 수 있는 가능성도 무궁무진합니다. 컴퓨터공학에서 암호학이 가장 잘 활용될 수 있는 분야는 아마도 보안이나 네트워크 분야일 것입니다. 뿐만 아니라, 최근에는 머신 러닝이나 컴파일러 분야에서도 암호학을 접목하려는 시도가 늘어나고 있습니다. 특히, 머신 러닝에서는 실제 세계의 정보를 학습 데이터로 활용합니다. 따라서 학습 과정에서 개인 정보를 노출시키지 않기 위해, 또 보안을 유지한 채로 개인에게 맞춤화 서비스를 제공하기 위해 암호학이 필요합니다.

4. 맺음말

프로그래밍이 위주인 전공 수업과는 다른 매력을 느낄 수 있습니다. 컴퓨터공학의 이론적인 부분에 흥미를 느끼는 분들에게 이 수업을 강력하게 추천합니다.