[목차] == 개요 == [[암호화]]와 [[복호화]]에 같은 키를 사용하는 [[대칭 열쇠 암호|비밀키 암호화 기법]]과 달리, __암호화와 복호화에 사용하는 키가 서로 다른__ 암호화 방식을 의미한다. 지금의 디지털 서명이나 인터넷에서의 암호화 통신을 가능하게 만든 1등 공신으로, 이 공개키 알고리즘이 개발되지 않았다면 우리는 지금처럼 인터넷으로 결제하는 등의 전자상거래 행위를 일체 하기 힘들었을 것이다. [[비대칭키 암호화]]라고도 한다. == 역사 == 공개키라는 개념이 구상된 것은 생각보다 오래 되었다. 오래 전 대칭키 알고리즘만 존재했을 때에는 수신자와 송신자 사이에 동일한 암호화 키를 사용해야 했다. 또한, 송신자는 암호화된 메시지를 보내기 전에 무조건 수신자에게 어떤 방식으로든 그 암호화 키를 전달해야 하기 때문에 이는 보안상 큰 허점이 될 수 밖에 없었다. 중간에 통신을 감청하는 사람이 있다면 결국 암호화 키를 어떤 식으로든 전달할 때 이를 알아낼 수 있게 되었다. 따라서 학계에서는 70년대 이전부터 암호화와 복호화에 사용하는 키가 서로 다른 공개키의 개념을 구상해왔고, 이를 실제로 개발하기 위해 노력하였으나 실용적으로 사용할 수 있는 알고리즘은 쉽게 개발되지 않았다. 그러던 중 1976년에 미국의 암호학자 베일리 휫필드 디피(Bailey Whitfield Diffie, 1944 ~ )와 미국 수학자 마틴 에드워드 헬만(Martin Edward Hellman, 1945 ~ )이 협동으로 만든 [[디피-헬만 키 교환]] 알고리즘을 학계에 발표하는데, 이는 학계에 최초로 발표된 (일종의) 공개키 암호화 방식이다. 항목을 보면 알겠지만 사실 엄밀히 말하면 이는 단순히 키 교환 알고리즘일 뿐이므로 암호화/복호화에 대한 내용은 없다. 그러나 어떤 식으로든 송신자와 수신자가 어떤 내용을 서로 전달하면, 그 내용을 제3자가 감청해도 알 수 없는(알기 힘든), 특정한 정수를 가질 수 있다는 것이므로 이 정수를 키로 사용하여 기존의 대칭키 알고리즘을 사용하면 되기 때문에 결과적으로 학계에서 염원하던 공개키 알고리즘이 실제로 개발된 것과 같았다. 그러나 키 교환 알고리즘은 단순히 데이터를 안전하게 암호화하는 데에는 사용할 수 있으나, 디지털 서명과 같은 곳에는 사용할 수가 없기 때문에 그 자체로는 모든 문제를 해결하기에는 한계가 있었고 결국 실질적인 진짜 공개키 암호화 알고리즘의 개발이 필요했다. 그리고 1978년에 미국 암호학자 로널드 로린 리베스트(Ronald Lorin Rivest,1947 ~), 이스라엘의 암호학자, 컴퓨터과학자 아디 샤미르(1952 ~ , עֲדִי שָמִיר), 미국 컴퓨터 과학자 레너드 애들먼(Leonard Adleman, 1945 ~ )이 엄밀한 의미에서 실제 공개키 "암호화" 알고리즘인 [[RSA 암호화|RSA]]를 개발하였고, 이것이 처음으로 발표된 진정한 의미에서의 실용적인 공개키 암호화 알고리즘이며, 현재 가장 널리 알려진 공개키 암호화 알고리즘이다. 이후 [[디피-헬만 키 교환]] 알고리즘의 핵심인 이산로그 문제에 기반한[* RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다.] 공개키 암호화인 ElGamal이나, 현재 많이 쓰이고 있는 타원 곡선 암호 등등이 개발되면서 알고리즘의 성능과 보안성에서 더욱 개량되고 있다. == 용도 == === 기밀 내용의 전달 === A가 자신만 알고 있는 기밀을 B 에게 전달하고자 할 때 사용한다. B 를 제외한 타인은 이 내용을 알 수 없어야 한다. 1. B 가 자신의 공개키를 공개한다. 1. A 는 이 공개키로 문서를 암호화 한다. 1. 암호화된 문서를 B 에게 전달한다. 1. B 는 자신만이 가진 개인키로 이 문서를 해독한다. 타인이 전달과정에서 암호화된 문서를 가로채더라도 B의 개인키가 없으면 해독이 불가능하다 [[TLS|SSL/TLS]]에서 두 당사자가 사용할 '대칭키'를 전달하는 용도로 사용된다. 다만 공개키 암호화는 처리 속도가 매우 느리므로 공개키 암호화는 TLS의 키 교환 같이 간단한 데이터를 전달하는 용도로만 사용된다. 그렇다면 처리 속도가 빨라야 할 경우는 어떡할까? [[대칭 열쇠 암호]]가 있다. === 발행자의 증명 및 문서의 변조 방지 === 어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 [[인장]], [[도장(도구)|도장]], [[서명]] 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다. 1. A 는 자신의 공개키를 공개한다. 1. A 는 어떤 문서 혹은 해당 문서의 [[해시]] 정보[* 문서 용량이 큰 경우 처리 속도가 느린 공개키 암호화로 해당 문서를 통째로 암호화하기에는 비효율적이기 때문이다.]를 자신의 개인키로 암호화 한다. 1. A 는 암호화된 문서를 일반에 공개하면서,이 문서를 자신이 만들었음을 선포한다. 1. 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다. 타인은 A의 공개키로 복호 가능한 문서를 생성할 수 없으므로, 해당 문서는 A 만이 발행 할 수 있다는 강력한 증거가 된다. 추가로, 해당 문서가 '''변조되지 않았다'''라는 중요한 기능을 동시에 얻을 수 있다. 이는 [[공인인증서]]를 비롯한 [[전자서명]]에서 사용되는 방법이다. === 부인 방지 === B가 가지고 있는 어떤 문서에 A 의 서명 (또는 도장)이 있는데, 정작 A 는 이 서명이 자신의 것이 아니라고 부인할 수 있다. 예를 들어 A 가 B 에게 돈을 빌린 후 '차용증'에 서명했는데, 후에 A 는 돈을 빌리지 않았으며 차용증 역시 자신의 서명이 아니라고 부인 하는 경우를 생각해 볼 수 있다. 이 때, B 는 문서에 있는 서명이 A 의 것이 맞다는 것을 확인하는 것이 '부인 방지'이다. 공개키 암호화 방식에서는 본질적으로 '발행자의 증명'과 동일한 절차로 이루어진다. 1. B 는 A 에게 개인키/공개키를 생성한 뒤 공개키를 공개하도록 요구한다. 이 절차는 [[공인인증서]]같은 것으로 대체할 수 있다. 1. B 는 A 에게 '문서'를 개인키로 암호화할 것으로 요구한다. 1. B 는 이 '암호화된 문서'를 수령한다. 1. B 는 '암호화된 문서'를 A 의 공개키로 해독하여, 이 문서가 A 의 개인키로 제대로 암호화 되었음을 검증할 수 있다. [* 만약 해독되지 않는다면, 개인키-공개키 쌍이 맞지 않음을 의미한다. 공개한 공개키가 잘못되었거나, 다른 개인키로 암호화 했음을 뜻한다.] 이 '암호화된 문서'는 A 의 공개키로만 해독이 가능하므로, 이 '암호화된 문서'는 A 만이 발행할 수 있다는 증거가 된다. 또한, 변조되지 않았음도 동시에 증명할 수 있다. == 종류 == * [[디피-헬만 키 교환]] * [[RSA 암호화]] * Rabin 암호 - 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA 와 유사하지만 [[중국인의 나머지 정리]](CRT)를 응용한다. * ElGamal * [[DSA]] - 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다. * 타원 곡선 암호 - ECC(Elliptic curve cryptography)로 불린다. 같은 공개키 암호 방식인 [[RSA]]에 비해 짧은 키(Key)값을 가지면서도 안정성은 동일하며 속도 또한 빠르다. 다만 어려운 수학적 배경이론과 소프트웨어적 구현의 어려움 때문에 개발은 더딘 편. 그래도 RSA와 비교하여 동일 키값을 가질 시 안정성은 더욱 높기 때문에 일부 산업용에서 종종 쓰이는 편이다. RSA가 140자리 이상의 큰 두개의 소수를 이용하는 반면 ECC는 알려진 특정한 점에 대한 무작위 [[타원 곡선]]의 [[이산 로그]]를 이용한다. == 기타 == 일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. [[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]] [[분류:암호학]][[분류:컴퓨터 보안]][[분류:알고리즘]]