공개키 암호화 방식

 

1. 개요
2. 역사
3. 용도
3.1. 기밀 내용의 전달
3.2. 발행자의 증명 및 문서의 변조 방지
4. 종류
5. 기타
6. 관련 문서


1. 개요

암호화와 복호화에 같은 키를 사용하는 비밀키 암호화 기법과 달리, 암호화[1]와 복호화[2]에 사용하는 키가 서로 다른 암호화 방식을 의미한다.
지금의 디지털 서명이나 인터넷에서의 암호화 통신을 가능하게 만든 1등 공신으로, 이 공개키 알고리즘이 개발되지 않았다면 우리는 지금처럼 인터넷으로 결제하는 등의 전자상거래 행위를 일체 하기 힘들었을 것이다.
참고로 띄어쓰기에 대해서는 "공개"와 "키"가 별도의 단어이므로 '''공개 키'''라고 쓰는 것이 더 적절하다. 다만 이 단어는 '''공개키'''라는 단어 자체도 전공자들 사이에서는 많이 쓰이기 때문에 이 문서의 제목이 '''공개키'''로 되어 있다.
비대칭키 암호화라고도 한다.

2. 역사

공개키라는 개념이 구상된 것은 생각보다 오래 되었다. 오래 전 대칭키 알고리즘만 존재했을 때에는 수신자와 송신자 사이에 동일한 암호화 키를 사용해야 했다. 또한, 송신자는 암호화된 메시지를 보내기 전에 무조건 수신자에게 어떤 방식으로든 그 암호화 키를 전달해야 하기 때문에 이는 보안상 큰 허점이 될 수 밖에 없었다. 중간에 통신을 감청하는 사람이 있다면 결국 암호화 키를 어떤 식으로든 전달할 때 이를 알아낼 수 있게 되었다. 따라서 학계에서는 70년대 이전부터 암호화와 복호화에 사용하는 키가 서로 다른 공개키의 개념을 구상해왔고, 이를 실제로 개발하기 위해 노력하였으나 실용적으로 사용할 수 있는 알고리즘은 쉽게 개발되지 않았다.
그러던 중 1976년에 디피와 헬만이 디피-헬만 키 교환 알고리즘을 학계에 발표하는데, 이는 학계에 최초로 발표된 (일종의) 공개키 암호화 방식이다. 항목을 보면 알겠지만 사실 엄밀히 말하면 이는 단순히 키 교환 알고리즘일 뿐이므로 암호화/복호화에 대한 내용은 없다. 그러나 어떤 식으로든 송신자와 수신자가 어떤 내용을 서로 전달하면, 그 내용을 제3자가 감청해도 알 수 없는(알기 힘든), 특정한 정수를 가질 수 있다는 것이므로 이 정수를 키로 사용하여 기존의 대칭키 알고리즘을 사용하면 되기 때문에 결과적으로 학계에서 염원하던 공개키 알고리즘이 실제로 개발된 것과 같았다.
그러나 키 교환 알고리즘은 단순히 데이터를 안전하게 암호화하는 데에는 사용할 수 있으나, 디지털 서명과 같은 곳에는 사용할 수가 없기 때문에 그 자체로는 모든 문제를 해결하기에는 한계가 있었고 결국 실질적인 진짜 공개키 암호화 알고리즘의 개발이 필요했다.
그리고 1978년에 세 수학자 Rivest, Shamir, Adleman이 엄밀한 의미에서 실제 공개키 "암호화" 알고리즘인 RSA를 개발하였고, 이것이 처음으로 발표된 진정한 의미에서의 실용적인 공개키 암호화 알고리즘이며, 현재 가장 널리 알려진 공개키 암호화 알고리즘이다.
이후 디피-헬만 키 교환 알고리즘의 핵심인 이산로그 문제에 기반한[3] 공개키 암호화인 ElGamal이나, 현재 많이 쓰이고 있는 타원 곡선 암호 등등이 개발되면서 알고리즘의 성능과 보안성에서 더욱 개량되고 있다.

3. 용도


3.1. 기밀 내용의 전달

A가 자신만 알고 있는 기밀을 B 에게 전달하고자 할 때 사용한다. B 를 제외한 타인은 이 내용을 알 수 없어야 한다.
  1. B 가 자신의 공개키를 공개한다.
  2. A 는 이 공개키로 문서를 암호화 한다.
  3. 암호화된 문서를 B 에게 전달한다.
  4. B 는 자신만이 가진 개인키로 이 문서를 해독한다.
타인이 전달과정에서 암호화된 문서를 가로채더라도 B의 개인키가 없으면 해독이 불가능하다
SSL/TLS에서 두 당사자가 사용할 '대칭키'를 전달하는 용도로 사용된다.

3.2. 발행자의 증명 및 문서의 변조 방지

어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 인장, 도장, 서명 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다.
  1. A 는 자신의 공개키를 공개한다.
  2. A 는 어떤 문서를 자신의 개인키로 암호화 한다.
  3. A 는 암호화된 문서를 일반에 공개하면서,이 문서를 자신이 만들었음을 선포한다.
  4. 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다.
타인은 A의 공개키로 복호 가능한 문서를 생성할 수 없으므로, 해당 문서는 A 만이 발행 할 수 있다는 강력한 증거가 된다.
추가로, 해당 문서가 '''변조되지 않았다'''라는 중요한 기능을 동시에 얻을 수 있다.
이는 공인인증서를 비롯한 전자서명에서 사용되는 방법이다.

4. 종류

  • 디피-헬만 키 교환
  • RSA 암호화
  • Rabin 암호[4]
  • ElGamal
  • DSA[5]
  • 타원 곡선 암호

5. 기타

일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. RSA의 예만 봐도, 일단 알고리즘의 특성상 큰 소수 
p
, 
q
를 먼저 랜덤하게 찾아야 하는데 현재 일반적으로 사용하는 소수가 1024비트를 넘어 2048비트나 그 이상의 크기까지 가고 있다는 점을 생각하면 이에 드는 연산(소수 판별)도 그렇게 작다고 볼 수 없다. 게다가 한 소수 
p
를 구해도, 거기에 단순히 숫자를 더하거나 빼면서 소수판별을 하는 식으로 하면 취약점이 생기므로[6] 그렇게 할 수는 없고 결국 두 번을 제대로 구해야 한다. 실제 암/복호화 과정의 핵심인 modular exponent[7]는 가장 빠른 알고리즘을 사용하면 별로 느리지 않다.[8] 물론 기본 연산 토대 뿐 아니라, 실용적으로 사용하기 위해 여러 보안적인 허점을 보완하는 데에는 다른 여러 연산들이 들어간다.
이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 대칭키 알고리즘에 사용되는 키만 암/복호화하여 서로 교환한 뒤 실제 평문을 암/복호화하는 것에만 대칭키 암호화를 이용하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[9]
위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 SSL/TLS.
비밀키 암호화 방식과 같이 컴활 1급 필기시험에서 단골문제로 나오는 주제중 하나이다.

6. 관련 문서


[1] 이것만 공개키이다.[2] 이건 비밀키이다.[3] RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다.[4] 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA 와 유사하지만 CRT를 응용한다.[5] 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다.[6] Fermat Factorization에 의해 
p*q
에서 
p
, 
q
를 비교적 빠르게 복원할 수 있다.[7] 어떤 수 $$a$$, $$b$$, $$c$$에 대해 $$a^b \; \mathrm{mod} \; c$$를 구하는 과정.[8] 게다가 보통 암호화에 쓰는 
e
는 보통 65537로 잡기 때문에 큰 수를 지수승하는 것도 아니다. 물론 복호화에 쓰는 
d
는 큰 수가 되지만.[9] 대표적으로 인텔의 AES-NI.

분류