[목차] == 개요 == [[암호화]]와 [[복호화]]에 같은 키를 사용하는 [[대칭 열쇠 암호|비밀키 암호화 기법]]과 달리, __암호화[* 이것만 공개키이다.]와 복호화[* 이건 비밀키이다.]에 사용하는 키가 서로 다른__ 암호화 방식을 의미한다. 지금의 디지털 서명이나 인터넷에서의 암호화 통신을 가능하게 만든 1등 공신으로, 이 공개키 알고리즘이 개발되지 않았다면 우리는 지금처럼 인터넷으로 결제하는 등의 전자상거래 행위를 일체 하기 힘들었을 것이다. 참고로 [[띄어쓰기]]에 대해서는 "공개"와 "키"가 별도의 단어이므로 '''공개 키'''라고 쓰는 것이 더 적절하다. 다만 이 단어는 '''공개키'''라는 단어 자체도 전공자들 사이에서는 많이 쓰이기 때문에 이 문서의 제목이 '''공개키'''로 되어 있다. [[비대칭키 암호화]]라고도 한다. == 역사 == 공개키라는 개념이 구상된 것은 생각보다 오래 되었다. 오래 전 대칭키 알고리즘만 존재했을 때에는 수신자와 송신자 사이에 동일한 암호화 키를 사용해야 했다. 또한, 송신자는 암호화된 메시지를 보내기 전에 무조건 수신자에게 어떤 방식으로든 그 암호화 키를 전달해야 하기 때문에 이는 보안상 큰 허점이 될 수 밖에 없었다. 중간에 통신을 감청하는 사람이 있다면 결국 암호화 키를 어떤 식으로든 전달할 때 이를 알아낼 수 있게 되었다. 따라서 학계에서는 70년대 이전부터 암호화와 복호화에 사용하는 키가 서로 다른 공개키의 개념을 구상해왔고, 이를 실제로 개발하기 위해 노력하였으나 실용적으로 사용할 수 있는 알고리즘은 쉽게 개발되지 않았다. 그러던 중 1976년에 디피와 헬만이 [[디피-헬만 키 교환]] 알고리즘을 학계에 발표하는데, 이는 학계에 최초로 발표된 (일종의) 공개키 암호화 방식이다. 항목을 보면 알겠지만 사실 엄밀히 말하면 이는 단순히 키 교환 알고리즘일 뿐이므로 암호화/복호화에 대한 내용은 없다. 그러나 어떤 식으로든 송신자와 수신자가 어떤 내용을 서로 전달하면, 그 내용을 제3자가 감청해도 알 수 없는(알기 힘든), 특정한 정수를 가질 수 있다는 것이므로 이 정수를 키로 사용하여 기존의 대칭키 알고리즘을 사용하면 되기 때문에 결과적으로 학계에서 염원하던 공개키 알고리즘이 실제로 개발된 것과 같았다. 그러나 키 교환 알고리즘은 단순히 데이터를 안전하게 암호화하는 데에는 사용할 수 있으나, 디지털 서명과 같은 곳에는 사용할 수가 없기 때문에 그 자체로는 모든 문제를 해결하기에는 한계가 있었고 결국 실질적인 진짜 공개키 암호화 알고리즘의 개발이 필요했다. 그리고 1978년에 세 수학자 Rivest, Shamir, Adleman이 엄밀한 의미에서 실제 공개키 "암호화" 알고리즘인 [[RSA 암호화|RSA]]를 개발하였고, 이것이 처음으로 발표된 진정한 의미에서의 실용적인 공개키 암호화 알고리즘이며, 현재 가장 널리 알려진 공개키 암호화 알고리즘이다. 이후 [[디피-헬만 키 교환]] 알고리즘의 핵심인 이산로그 문제에 기반한[* RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다.] 공개키 암호화인 ElGamal이나, 현재 많이 쓰이고 있는 타원 곡선 암호 등등이 개발되면서 알고리즘의 성능과 보안성에서 더욱 개량되고 있다. == 용도 == === 기밀 내용의 전달 === A가 자신만 알고 있는 기밀을 B 에게 전달하고자 할 때 사용한다. B 를 제외한 타인은 이 내용을 알 수 없어야 한다. 1. B 가 자신의 공개키를 공개한다. 1. A 는 이 공개키로 문서를 암호화 한다. 1. 암호화된 문서를 B 에게 전달한다. 1. B 는 자신만이 가진 개인키로 이 문서를 해독한다. 타인이 전달과정에서 암호화된 문서를 가로채더라도 B의 개인키가 없으면 해독이 불가능하다 [[TLS|SSL/TLS]]에서 두 당사자가 사용할 '대칭키'를 전달하는 용도로 사용된다. === 발행자의 증명 및 문서의 변조 방지 === 어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 [[인장]], [[도장]], [[서명]] 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다. 1. A 는 자신의 공개키를 공개한다. 1. A 는 어떤 문서를 자신의 개인키로 암호화 한다. 1. A 는 암호화된 문서를 일반에 공개하면서,이 문서를 자신이 만들었음을 선포한다. 1. 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다. 타인은 A의 공개키로 복호 가능한 문서를 생성할 수 없으므로, 해당 문서는 A 만이 발행 할 수 있다는 강력한 증거가 된다. 추가로, 해당 문서가 '''변조되지 않았다'''라는 중요한 기능을 동시에 얻을 수 있다. 이는 [[공인인증서]]를 비롯한 [[전자서명]]에서 사용되는 방법이다. == 종류 == * [[디피-헬만 키 교환]] * [[RSA 암호화]] * Rabin 암호[* 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA 와 유사하지만 [[중국인의 나머지 정리|CRT]]를 응용한다.] * ElGamal * DSA[* 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다.] * 타원 곡선 암호 == 기타 == 일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. [[RSA 암호화|RSA]]의 예만 봐도, 일단 알고리즘의 특성상 큰 소수 {{{p}}}, {{{q}}}를 먼저 랜덤하게 찾아야 하는데 현재 일반적으로 사용하는 소수가 1024비트를 넘어 2048비트나 그 이상의 크기까지 가고 있다는 점을 생각하면 이에 드는 연산(소수 판별)도 그렇게 작다고 볼 수 없다. 게다가 한 소수 {{{p}}}를 구해도, 거기에 단순히 숫자를 더하거나 빼면서 소수판별을 하는 식으로 하면 취약점이 생기므로[* [[https://en.wikipedia.org/wiki/Fermat%27s_factorization_method|Fermat Factorization]]에 의해 {{{p*q}}}에서 {{{p}}}, {{{q}}}를 비교적 빠르게 복원할 수 있다.] 그렇게 할 수는 없고 결국 두 번을 제대로 구해야 한다. 실제 암/복호화 과정의 핵심인 [[https://en.wikipedia.org/wiki/Modular_exponentiation|modular exponent]][* 어떤 수 [math(a)], [math(b)], [math(c)]에 대해 [math(a^b \; \mathrm{mod} \; c)]를 구하는 과정.]는 가장 빠른 알고리즘을 사용하면 별로 느리지 않다.[* 게다가 보통 암호화에 쓰는 {{{e}}}는 보통 65537로 잡기 때문에 큰 수를 지수승하는 것도 아니다. 물론 복호화에 쓰는 {{{d}}}는 큰 수가 되지만.] 물론 기본 연산 토대 뿐 아니라, 실용적으로 사용하기 위해 여러 보안적인 허점을 보완하는 데에는 다른 여러 연산들이 들어간다. 이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 대칭키 알고리즘에 사용되는 키만 암/복호화하여 서로 교환한 뒤 실제 평문을 암/복호화하는 것에만 대칭키 암호화를 이용하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[* 대표적으로 인텔의 AES-NI.] 위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 [[TLS|SSL/TLS]]. 비밀키 암호화 방식과 같이 [[컴활 1급]] 필기시험에서 단골문제로 나오는 주제중 하나이다. == 관련 문서 == * [[암호 알고리즘]] * [[대칭 열쇠 암호]] * [[복호화]] * [[비트코인]]: [[SHA]]-256 사용 * [[TrueCrypt]]: SHA-512 사용 * [[gpg4usb]] [[분류:암호학]][[분류:컴퓨터 보안]][[분류:알고리즘]]