이 글은 HTTPS의 동작 원리를 이해하기 위해 알아두어야 할 암호화 지식들을 다룬다.
처음 HTTPS에 대해 공부하면서 어렵지 않게 이해했다고 생각했고, 누가 물어보면 잘 답변할 수 있을 것이라고 생각했는데 막상 닥쳐보니 그렇지 않았다.
HTTPS의 동작 과정은 나에게 일종의 암기처럼 느껴져서, 공부한 직후에는 이해가 되지만 시간이 지나면 까먹는 존재였다. 그리고 그 원인은 “암호화에 대해서 제대로 이해하지 못해서” 라는 생각이 들었다. 그래서 HTTPS를 다루기 전, 먼저 암호화에 대해 궁금했던 점들을 정리해보려고 한다.
이 포스팅을 통해 해결하고자 하는 궁금증은 다음과 같다.
암호화는 암호화 알고리즘과 암호화 키를 이용해서 데이터를 남들이 해석할 수 없도록 만드는 것이다. 암호화 알고리즘은 공개되어 있다. 따라서 암호화에서는 사용되는 키를 어떻게 생성하고 관리하느냐가 핵심이라고 볼 수 있다.
암호화 기법에는 크게 대칭키 방식과 공개키(비대칭키) 방식이 있다.
대칭키 방식은 암호화 키와 복호화 키가 같은 방식을 말한다.
암호화와 복호화 키가 같기 때문에, 복호화 하는 쪽에 비밀리에 키를 전달해줘야 한다.
이때 키를 보내지 않으면 복호화를 할 수 없고, 키를 보내면 도중에 탈취될 가능성이 있는데 이를 키 배송 문제(key distribution problem)라고 한다.
키 배송 문제는 다음과 같은 방법으로 해결할 수 있다.
자세한 동작 방식은 이 글에서 확인할 수 있다.
암호화에 사용할 비밀 키를 공개키 방식의 개념을 참고하여, 수학적 연산을 통해 생성해서 사용하는 방식이다.
송신자와 수신자 사이의 비밀 키가 이미 정해져서 이를 전달하는 방식이 아니라, 공개된 변수와 각자가 가지고 있는 비밀 변수들의 연산으로 만들어진 값을 비밀 키로 사용하는 방식이다. Diffie-Hellman key agreement(키 합의)라고도 한다.
이산 로그 문제(DLP, Discrete Logarithm Problem)가 해결하기 어렵다는 사실을 기반으로 한다.
간단하게 동작하는 방식을 그려보면 다음과 같다.
Diffie-Hellman 키 교환에서는 p가 충분히 크다면, 비밀 키인 a, b 값을 모르는 이상 A와 B값을 가지고 s를 구할 수 없다.
문제점
공개키 방식은 (공개키, 개인키)가 하나의 묶음으로 동작한다. 즉, 공개키로 암호화를 하면 개인키로만 복호화할 수 있고, 개인키로 암호화하면 공개키로만 복호화할 수 있다.
어떤 키로 암호화 하느냐에 따라 크게 공개키 암호화와 전자 서명(인증)으로 구분한다.
공개키 암호화는 말 그대로 공개키로 암호화하고, 복호화는 개인키로만 가능한 방법이다. 복호화가 개인키로만 가능하기 때문에, 데이터가 보호되어야 할 때 사용된다.
전자 서명은 반대로 개인키로 암호화하는 방식이다. 따라서 공개키로 복호화가 가능하다. 즉, 나의 개인키에 대한 공개키를 알고 있는 사람이라면 누구나 복호화할 수 있다. 당연히 보안이 중요한 데이터는 이 방법으로 암호화하면 안된다. 대신 이 데이터를 보낸 사람이 나라는 것을 증명(인증)할 수 있다. 공개키와 개인키는 쌍으로 동작하기 때문에, 특정 공개키로 복호화 가능하다는 것은 해당 공개키의 쌍인 개인키로 암호화되었다는 것을 의미한다. 이 특성을 이용해 사용자를 인증하는 데 사용할 수 있다.
RSA 알고리즘에 대한 자세한 설명은 이 글에서 확인할 수 있다.
RSA는 공개키 방식에서 대표적으로 사용되는 알고리즘 중 하나이다. RSA는 복잡한 수학적 연산을 통해 사용 가능한 (공개키, 개인키) 묶음을 만들어주는 알고리즘이라고 생각하면 편하다. RSA 암호는 2개의 큰 소수를 곱하는 것은 쉽지만, 곱해진 결과가 어떤 두 소수의 곱 인지 알아내는 것은 어렵다는 성질을 이용한다.
RSA에서 키를 만드는 방법은 다음과 같다.
이런 식으로 만든 공개키 e로 암호화하면, 개인키 d를 사용해 복호화하여 원래 문장을 찾을 수 있다. 암호화 키와 복호화 키가 달라도 되는 이유는 e*d(modN)이 1인 성질을 가지기 때문이다.
N과 e를 공개해도 되는 이유에 대해 생각해보자. 복호화 키 d를 구하기 위해서는 N을 구성하는 소수 p, q를 알아야 한다. 그래야 p-1, q-1과 서로소인 e를 통해 d를 구할 수 있기 때문이다. N이 작을 경우 p, q를 구하는 소인수분해 과정은 어렵지 않다. 가장 쉬운 방식으로 루트 n보다 작은 값들을 일일이 나눠서 구하는 방식이 있다. 하지만 우리가 암호화에 사용하는 소수 p, q는 굉장히 큰 수이다. 이를 소인수분해하여 p, q를 구하는 것은 물리적, 시간적으로 어렵다. 따라서 현실적으로 개인키인 e를 구할 수 없다고 판단한다.
예를 들어 30자리 수를 소인수분해하기 위해 10^15보다 작은 수로 나누어보면 되는데, 1초에 100만 번 연산을 수행하는 슈퍼컴퓨터라 할지라도 계산하는 데 10^9초가 소요되므로 약 30년이 걸린다.
마지막으로 우리가 암호화, 복호화에서 사용한 연산의 시간 복잡도에 대해서 생각해보자. 지수 연산에서는 밑의 수를 n번 만큼 곱해주면 되기 때문에, 시간 복잡도는 으로 볼 수 있다. 이전에 구한 값을 저장해두고 어느 수의 제곱을 구할 때 이를 사용한다면, 시간 복잡도를 까지 줄일 수 있다. 하지만 RSA에서 사용되는 키 값은 매우 크기 때문에, 지수 연산을 하는데도 상당한 시간이 소요된다고 한다. 그래서 RSA 만으로 모든 암호화를 하지는 못하고, 다른 암호화 방식이랑 연동하여 쓰는 것이 보통이라고 한다.
결론부터 말하자면, 암호화한 공개키를 공개해도 복호화를 위한 개인키를 구하는 데 시간이 너무 오래 걸려 현실적으로 찾을 수 없다고 판단하기 때문이다. RSA 알고리즘에서 간단하게 살펴봤듯이, 매우 큰 숫자를 소인수분해해서 그 중에 키 값을 도출하는데 사용하는 값을 알아내는 것은 어렵다.
공개된 정보로 개인키를 찾기 위해서는 대체로 NP(Non-deterministic Polynomia)와 같이 여러가지 가능성을 동시에 고려해야 해서 연산이 어려운 문제를 해결해야 한다.
이것도 RSA 알고리즘에서 살펴본 내용을 참고하면 이해하기 수월해진다. 공개키 방식은 개인키를 제3자가 구할 수 없게 하기 위해 키 값을 매우 크게 사용하는 것이 보통이다. 그리고 암호화, 복호화 알고리즘에서 이 키를 가지고 연산하기 때문에 그만큼 연산량이 많다. 즉, 공개키는 키로 사용되는 값이 매우 커서 이를 가지고 암호화, 복호화 연산을 하는데 시간이 많이 소요된다.
그에 비해 대칭키는 키를 비밀로 관리하기 때문에, 키 배송 문제만 없다면 공개키 방식만큼 키 값이 클 필요가 없다.
흔히 암호화를 공부하다보면 위와 같은 표를 볼 수 있다. 앞선 내용들을 다루고 보니, 이런 특징들이 더 잘 이해가 되는 것 같다. 마지막으로 궁금증에 대한 요약 정리로 포스팅을 마치도록 하겠다.