공개키 암호화 방식
최근 수정 시각:
상위 문서 : 수학 관련 정보
1. 개요[편집]
암호화와 복호화에 같은 키를 사용하는 대칭키 암호화 방식과 달리, 암호화와 복호화에 사용하는 키가 서로 다른 암호화 방식을 의미한다.
지금의 디지털 서명이나 인터넷에서의 암호화 통신을 가능하게 만든 1등 공신으로, 이 공개키 알고리즘이 개발되지 않았다면 우리는 지금처럼 인터넷으로 결제하는 등의 전자상거래 행위를 일체 하기 힘들었을 것이다.
참고로 띄어쓰기에 대해서는 "공개"와 "키"가 별도의 단어이므로 공개 키라고 쓰는 것이 더 적절하다. 다만 이 단어는 공개키라는 단어 자체도 전공자들 사이에서는 많이 쓰이기 때문에 이 문서의 제목이 공개키로 되어 있다.
비대칭키 암호화라고도 한다.
2. 역사[편집]
공개키라는 개념이 구상된 것은 생각보다 오래 되었다. 오래 전 대칭키 알고리즘만 존재했을 때는, 수신자와 송신자 사이에 동일한 암호화 키를 사용해야 하고, 또한 송신자는 암호화된 메시지를 보내기 전에 무조건 수신자에게 어떤 방식으로든 그 암호화 키를 전달해야 하기 때문에 이는 보안상 큰 허점이 될 수 밖에 없었다. 중간에 통신을 감청하는 사람이 있다면 결국 암호화 키를 어떤 식으로든 전달할 때 이를 알아낼 수 있게 된다. 따라서 학계에서는 70년대 이전부터 암호화와 복호화에 사용하는 키가 서로 다른 공개키의 개념을 구상해왔고, 이를 실제로 개발하기 위해 노력하였으나 실용적으로 사용할 수 있는 알고리즘은 쉽게 개발되지 않았다.
그러던 중 1976년에 디피와 헬만이 디피-헬만 키 교환 알고리즘을 학계에 발표하는데, 이는 학계에 최초로 발표된 (일종의) 공개키 암호화 방식이다. 항목을 보면 알겠지만 사실 엄밀히 말하면 이는 단순히 키 교환 알고리즘일 뿐이므로 암호화/복호화에 대한 내용은 없다. 그러나 어떤 식으로든 송신자와 수신자가 어떤 내용을 서로 전달하면, 그 내용을 제 3자가 감청해도 알 수 없는(알기 힘든), 특정한 정수를 가질 수 있다는 것이므로 이 정수를 키로 사용하여 기존의 대칭키 알고리즘을 사용하면 되기 때문에 결과적으로 학계에서 염원하던 공개키 알고리즘이 실제로 개발된 것과 같았다.
그리고 1978년에 Rivest, Shamir, Adleman 의 세 수학자가 엄밀한 의미에서 실제 공개키 "암호화" 알고리즘인 RSA 를 개발하였고, 이것이 처음으로 발표된 진정한 의미에서의 실용적인 공개키 암호화 알고리즘이며, 현재 가장 널리 알려진 공개키 암호화 알고리즘이다.
이후 디피-헬만 키 교환 알고리즘의 핵심인 이산로그 문제에 기반한[1] 공개키 암호화인 ElGamal 이나, 현재 많이 쓰이고 있는 타원 곡선 암호 등이 개발되면서 알고리즘의 성능과 보안성에서 더욱 개량되고 있다.
3. 종류[편집]
디피-헬만 키 교환
RSA 암호
Rabin 암호[2]
ElGamal
DSA[3]
타원 곡선 암호
4. 기타[편집]
일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. RSA 의 예만 봐도, 일단 알고리즘의 특성상 큰 소수 p, q를 먼저 랜덤하게 찾아야하는데 현재 일반적으로 사용하는 소수가 1024bit 를 넘어 2048bit, 그 이상의 크기까지 가고 있다는 점을 생각하면 이에 드는 연산(소수판별)도 그렇게 작다고 볼 수 없다. 게다가 한 소수 p 를 구해도, 거기에 단순히 숫자를 더하거나 빼면서 소수판별을 하는 식으로 하면 취약점이 생기므로[4] 그렇게 할 수는 없고 결국 두 번을 제대로 구해야 한다. 실제 암/복호화 과정의 핵심인 modular exponent 는 가장 빠른 알고리즘을 사용하면 별로 느리지 않다.[5] 물론 기본 연산 토대 뿐 아니라, 실용적으로 사용하기 위해 여러 보안적인 허점을 보완하는 데에는 다른 여러 연산들이 들어간다.
이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 대칭키 알고리즘에 사용되는 키만 암/복호화하여 서로 교환한 뒤 실제 평문을 암/복호화하는 것은 대칭키 암호화를 이용하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를 뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[6]
위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 SSL/TLS.