| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
암호화와 복호화에 같은 키를 사용하는 비밀키 암호화 기법과 달리, 암호화와 복호화에 사용하는 키[1]가 서로 다른 암호화 방식을 의미한다.지금의 전자서명이나 인터넷에서의 암호화 통신을 가능하게 만든 1등 공신으로, 이 공개키 알고리즘이 개발되지 않았다면 우리는 지금처럼 인터넷으로 결제하는 등의 전자상거래 행위를 일체 하기 힘들었을 것이다.
비대칭키 암호화라고도 한다.
2. 역사
공개키라는 개념이 구상된 것은 생각보다 오래 되었다. 오래 전 대칭키 알고리즘만 존재했을 때에는 수신자와 송신자 사이에 동일한 암호화 키를 사용해야 했다. 또한, 송신자는 암호화된 메시지를 보내기 전에 무조건 수신자에게 어떤 방식으로든 그 암호화 키를 전달해야 하기 때문에 이는 보안상 큰 허점이 될 수 밖에 없었다. 중간에 통신을 감청하는 사람이 있다면 결국 암호화 키를 어떤 식으로든 전달할 때 이를 알아낼 수 있게 되었다. 따라서 학계에서는 70년대 이전부터 암호화와 복호화에 사용하는 키가 서로 다른 공개키의 개념을 구상해왔고, 이를 실제로 개발하기 위해 노력하였으나 실용적으로 사용할 수 있는 알고리즘은 쉽게 개발되지 않았다.그러던 중 1976년에 미국의 암호학자 베일리 휫필드 디피(Bailey Whitfield Diffie, 1944 ~ )와 미국 수학자 마틴 에드워드 헬만(Martin Edward Hellman, 1945 ~ )이 협동으로 만든 디피-헬만 키 교환 알고리즘을 학계에 발표하는데, 이는 학계에 최초로 발표된 (일종의) 공개키 암호화 방식이다. 문서를 보면 알겠지만 사실 엄밀히 말하면 이는 단순히 키 교환 알고리즘일 뿐이므로 암호화/복호화에 대한 내용은 없다. 그러나 어떤 식으로든 송신자와 수신자가 어떤 내용을 서로 전달하면, 그 내용을 제3자가 감청해도 알 수 없는(알기 힘든), 특정한 정수를 가질 수 있다는 것이므로 이 정수를 키로 사용하여 기존의 대칭키 알고리즘을 사용하면 되기 때문에 결과적으로 학계에서 염원하던 공개키 알고리즘이 실제로 개발된 것과 같았다.
그러나 키 교환 알고리즘은 단순히 데이터를 안전하게 암호화하는 데에는 사용할 수 있으나, 디지털 서명과 같은 곳에는 사용할 수가 없기 때문에 그 자체로는 모든 문제를 해결하기에는 한계가 있었고 결국 실질적인 진짜 공개키 암호화 알고리즘의 개발이 필요했다.
그리고 1978년에 미국 암호학자 로널드 로린 리베스트(Ronald Lorin Rivest,1947 ~), 이스라엘의 암호학자, 컴퓨터과학자 아디 샤미르(1952 ~ , עֲדִי שָמִיר), 미국 컴퓨터 과학자 레너드 애들먼(Leonard Adleman, 1945 ~ )이 엄밀한 의미에서 실제 공개키 "암호화" 알고리즘인 RSA를 개발하였고, 이것이 처음으로 발표된 진정한 의미에서의 실용적인 공개키 암호화 알고리즘이며, 현재 가장 널리 알려진 공개키 암호화 알고리즘이다.
이후 디피-헬만 키 교환 알고리즘의 핵심인 이산로그 문제에 기반한[2] 공개키 암호화인 ElGamal이나, 현재 많이 쓰이고 있는 타원 곡선 암호 등등이 개발되면서 알고리즘의 성능과 보안성에서 더욱 개량되고 있다.
3. 약점 및 해결 방법
현재 널리 사용되는 공개키 암호화 방식들은 공개키가 잘 전달되었다는 가정 하에 현실적인 시간 및 자원으로 깰 수 없는 (즉, 공개키만 가지고 개인키를 얻어낸다든가 복호화를 한다든가 할 수 없는) 방식들이다.[3] 그 무엇으로부터 안전해 보이는 이 강력한 공개키 암호화 방식은 아이러니하게도 이 문서의 상단에 언급된 암호화 키 전달 문제에서 완전히 자유롭지 않다. 즉, 공개키를 전달하는 과정에서 중간자 공격 문제가 생길 수 있다는 것이다.이 문제를 설명하기 위해 앨리스(Alice)와 밥(Bob)이 암호화된 통신을 한다고 하고, 이들이 사용하는 채널을 말로이(Malloy)가 도청 및 위조를 할 수 있다고 치자. 즉, 말로이는 앨리스 혹은 밥이 보내는 메세지를 읽을 수 있을 뿐만 아니라 자기 맘대로 변형시킬 수 있다고 하자.[4] 통신이 이루어지기 전에 말로이는 앨리스와 밥이 사용하게 될 공개키 암호화 방식이 무엇인지 (물론 프로토콜이 무엇인지도) 파악한 다음, 자신의 공개키 및 개인키를 준비한다. 이제 앨리스는 자신의 공개키를 밥한테 보내줄텐데, 말로이는 이때 앨리스의 이 메세지를 가로챈 다음, 그 메세지에 담긴 앨리스의 공개키를 자신(말로이)의 공개키로 바꿔서 밥한테 보낸다. 즉, 밥은 앨리스의 공개키를 받았다고 생각하겠지만 실제로 받은 키는 말로이의 공개키이다. 밥은 자신의 메세지를 이 공개키로 암호화해서 앨리스에게 전송할 것인데, 말로이는 이 메세지를 가로챈 다음, 자신의 개인키로 이 메세지를 복호화하고, 그 원문을 앨리스의 공개키로 암호화하여 앨리스에게 보낸다. 이런 식으로 말로이는 밥의 메세지를 읽을 수 있게 되는 것이다. 특히 이 과정에서 앨리스와 밥이 대칭키를 교환하게 된다면 말로이는 이 대칭키를 가로챌 수 있을 것이다. 게다가 이 과정에서 앨리스와 밥은 도청당하고 있다는 사실도 알 수 없다.[5]
이를 막기 위해 밥이 앨리스의 키를 제대로 받았는지 검증할 필요가 있는데, 여기서 전자서명이 사용된다. 아래에 소개된 용도들 중 "발행자의 증명"을 활용한 것이 전자서명인데, 이를 구현하기 위해 먼저 앨리스와 밥이 사전에 어떤 공개키 K를 가지고 있다고 가정하자. (둘 다 이 공개키의 개인키를 가지고 있을 필요는 없다.) 이제 앨리스는 K의 개인키를 소유한 사람에게 가서 앨리스 자신의 공개키와 앨리스의 몇몇 공개된 고유 정보, 특히 앨리스가 사용하는 기기의 주소를 가지고 전자서명을 제작한다. 그리고 앨리스는 밥과 통신을 하면서 자신의 공개키를 보낼 때 전자서명도 같이 보낸다. 밥은 앨리스가 보내준 공개키와 앨리스의 정보들을 가지고 전자서명과 비교할 수 있는데, 이는 밥이 K를 가지고 있기 때문에 수행할 수 있는 작업이다. 이 비교 과정에서 전자서명의 내용과 앨리스의 정보가 잘 일치하면 밥은 통신을 이어가고, 그렇지 않으면 통신을 끊는다.
이때 말로이가 할 수 있는 것은 아무 것도 없다는 것을 알 수 있다. 이제 말로이는 앨리스의 공개키 뿐만 아니라 이 공개키의 전자서명도 바꿔야 한다. 말로이가 자신의 공개키+앨리스의 정보를 가지고 K로 해독되는 전자서명을 만들지 않는 한, 말로이의 공개키는 밥의 검증 과정을 통과하지 못할 것이다. 이런 식으로 앨리스와 밥은 중간자 공격을 방어할 수 있을 것이다.
이제 문제는 제2의 키 K가 앨리스와 밥에게 어떻게 공유될 것인가 하는 문제일 것이다. 결국 제자리 걸음 같아 보이겠지만, 보통의 경우 이 K는 훨씬 더 낮은 레벨에서 공유된다. 예를 들어, K가 인증기관(Certificate Authority, CA)의 공개키이고, 모든 인증기관들의 공개키가 운영체제나 브라우저에 내장되어 있다면[6], 앨리스와 밥은 운영체제 혹은 브라우저를 (올바르게) 설치하는 순간 K를 보유하는 셈이 되는 것이다. 전자서명도 해당 K를 보유한 인증기관한테 앨리스가 신청해서 받을 수 있을 것이다. 물론 제대로 된 인증기관이라면 말로이의 공개키+앨리스의 정보를 가지고 전자서명을 발행하는 짓은 안 할 것이다. 다만, 운영체제나 브라우저를 신뢰할 수 없는 방식으로 (예컨대, 불법복제물을 사용한다든가 하는 방식으로) 설치하면, 변조된 프로그램을 까는 셈이 될 수 있으며, 특히 인증기관의 키 목록에 어떤 변조가 이루어진 채 통신을 수행하는 셈이 될 수도 있다. 이 정도만 조심하면 공개키 암호화 방식을 활용한 암호화 통신은 충분히 안전할 것이다.
위 방식을 활용한 통신 규약으로 TLS가 있다.
4. 용도
4.1. 기밀 내용의 전달
A가 자신만 알고 있는 기밀을 B에게 전달하고자 할 때 사용한다. B를 제외한 타인은 이 내용을 알 수 없어야 한다.- B가 자신의 공개키를 공개한다.
- A는 이 공개키로 문서를 암호화 한다.
- 암호화된 문서를 B에게 전달한다.
- B는 자신만이 가진 개인키로 이 문서를 해독한다.
다만, 공개키 암호화 방식은 처리 속도가 매우 느리고 대용량 파일에는 적용이 불가능하다는 큰 단점이 있다.[7] 그래서, 데이터의 암호화는 '대칭 열쇠 암호'를 사용해서 암호화 하여 전달하고, 이때 사용하는 '대칭키' 자체를 전달하는 용도로 공개키/개인키를 이용해서 암호화 하여 전달한다. 예를 들어 TLS에서는 이 방식을 이용한다.
4.2. 발행자의 증명 및 문서의 변조 방지
어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 인장, 도장, 서명 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다.- A는 자신의 공개키를 공개한다.
- A는 어떤 문서 혹은 해당 문서의 해시 정보[8]를 자신의 개인키로 암호화 한다.
- A는 암호화된 문서를 일반에 공개하면서, 이 문서를 자신이 만들었음을 선포한다.
- 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다.
추가로, 해당 문서가 변조되지 않았다라는 중요한 기능을 동시에 얻을 수 있다.
이는 공인인증서를 비롯한 전자서명에서 사용되는 방법이다.
4.3. 부인 방지
B가 가지고 있는 어떤 문서에 A의 서명 (또는 도장)이 있는데, 정작 A는 이 서명이 자신의 것이 아니라고 부인할 수 있다. 예를 들어 A가 B에게 돈을 빌린 후 '차용증'에 서명했는데, 후에 A는 돈을 빌리지 않았으며 차용증 역시 자신의 서명이 아니라고 부인 하는 경우를 생각해 볼 수 있다. 이 때, B는 문서에 있는 서명이 A의 것이 맞다는 것을 확인하는 것이 '부인 방지'이다. 공개키 암호화 방식에서는 본질적으로 '발행자의 증명'과 동일한 절차로 이루어진다.- B는 A에게 개인키/공개키를 생성한 뒤 공개키를 공개하도록 요구한다. 이 절차는 공인인증서같은 것으로 대체할 수 있다.
- B는 A에게 '문서'를 개인키로 암호화할 것으로 요구한다.
- B는 이 '암호화된 문서'를 수령한다.
- B는 '암호화된 문서'를 A의 공개키로 해독하여, 이 문서가 A의 개인키로 제대로 암호화 되었음을 검증할 수 있다.[9]
5. 종류
- 디피-헬만 키 교환 - 다만, 이는 약간 다른데, A가 가진 정보가 B에게 전달되는 것이 아니라, A와 B가 어떤 랜덤한 수를 동시에 얻게 되는 결과를 만들어 낸다.
- RSA 암호화
- Rabin 암호 - 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA와 유사하지만 중국인의 나머지 정리(CRT)를 응용한다.
- ElGamal
- DSA (Digital Signature Algorithm) - 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다.
- 타원 곡선 암호 - ECC(Elliptic curve cryptography)로 불린다. 같은 공개키 암호 방식인 RSA 암호화에 비해 짧은 키(Key)값을 가지면서도 안정성은 동일하며 속도 또한 빠르다. 다만 어려운 수학적 배경이론과 소프트웨어적 구현의 어려움 때문에 개발은 더딘 편. 그래도 RSA와 비교하여 동일 키값을 가질 시 안정성은 더욱 높기 때문에 일부 산업용에서 종종 쓰이는 편이다. RSA가 140자리 이상의 큰 두개의 소수를 이용하는 반면 ECC는 알려진 특정한 점에 대한 무작위 타원곡선의 이산 로그를 이용한다.
6. 기타
일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. RSA의 예만 봐도, 일단 알고리즘의 특성상 큰 소수p, q를 먼저 랜덤하게 찾아야 하는데 현재 일반적으로 사용하는 소수가 1024비트를 넘어 2048비트나 그 이상의 크기까지 가고 있다는 점을 생각하면 이에 드는 연산(소수 판별)도 그렇게 작다고 볼 수 없다. 게다가 한 소수 p를 구해도, 거기에 단순히 숫자를 더하거나 빼면서 소수판별을 하는 식으로 하면 취약점이 생기므로[10] 그렇게 할 수는 없고 결국 두 번을 제대로 구해야 한다. 그나마 실제 암/복호화 과정의 핵심인 modular exponent[11]는 가장 빠른 알고리즘을 사용하면 별로 느리지 않지만[12] 대칭키 암호화에 비하면 여전히 높은 연산량을 요구하기에 통신되는 모든 데이터를 암복호화하기에는 많이 부담스러울 것이다. 물론 기본 연산 토대 뿐 아니라, 실용적으로 사용하기 위해 여러 보안적인 허점을 보완하는 데에는 다른 여러 연산들이 들어가기 때문에 대칭키 암호화에 비해 더더욱 연산량이 늘어날 것이다.[13]이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 실제 평문을 암/복호화하는 데에는 대칭키 암호화를 이용하고 대칭키 알고리즘에 사용되는 키만 공개키 방식으로 암/복호화하여 서로 교환하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[14]
위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 SSL/TLS.
비밀키 암호화 방식과 같이 컴활 1급 필기시험에서 단골문제로 나오는 주제중 하나이다.
7. 관련 문서
[1] 원칙적으로는 암호화는 공개키, 복호화는 비밀키를 사용한다. 다만, 경우에 따라 반대로 사용할 수도 있다.[2] RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다.[3] 양자 컴퓨터의 발전이 이를 뒤집을 수 있다고는 하나, 여기서는 이 문제를 다루지 않겠다.[4] 혹시나 해서 강조하건대, 만약 앨리스와 밥이 무사히 키 교환을 마친 다음 암호화된 통신을 하게 되면 말로이는 현실적인 방법으로 이 암호화된 통신의 원문을 읽을 수도 없고, 자기 입맛대로 변형시킬 수도 없다.[5] 최소한 교환된 공개키가 잘 일치하는지 다른 채널로 확인하기 전에는 알 수 없을 것이다. 하지만 다른 채널이 안전하다는 보장도 없는데다가 안전해질 수록 비용이 더 들어갈 것이다.[6] 물론 운영체제나 브라우저의 개발자들이 어떤 인증기관를 신뢰하느냐에 따라 그 보유 목록이 상이해질 수는 있다.[7] 대칭키 암호화는 블록 모드가 존재하여 데이터를 블록 단위로 쪼개서 병렬적으로 처리하기에 패딩 과정만 잘 거치면 용량 제약을 받지 않는다. 그러나 공개키 암호화 방식은 블록화가 불가능하여 암호화 비트수를 넘어가는 대부분의 데이터에 대해서는 아예 처리 자체가 불가능하다.[8] 문서 용량이 큰 경우 처리 속도가 느린 공개키 암호화로 해당 문서를 통째로 암호화하기에는 비효율적이기 때문이다.[9] 만약 해독되지 않는다면, 개인키-공개키 쌍이 맞지 않음을 의미한다. 공개한 공개키가 잘못되었거나, 다른 개인키로 암호화 했음을 뜻한다.[10] Fermat Factorization에 의해
p*q에서 p, q를 비교적 빠르게 복원할 수 있다.[11] 어떤 수 [math(a)], [math(b)], [math(c)]에 대해 [math(a^b \; \mathrm{mod} \; c)]를 구하는 과정.[12] 게다가 보통 암호화에 쓰는 e는 보통 65537로 잡기 때문에 큰 수를 지수승하는 것도 아니다. 물론 복호화에 쓰는 d는 큰 수가 되지만.[13] 클라이언트 입장에서도 부담스러울 수 있겠지만, 서버에게는 연산량 증가가 더 심각한 문제로 다가온다. 서버는 보통 동시에 여러 클라이언트들을 상대해야 함을 상기하자. 저전력을 요구하는 시스템의 경우, 클라이언트에게도 연산량 증가는 민감한 문제가 될 것이다.[14] 대표적으로 인텔의 AES-NI. 사실 인텔 계열 칩 뿐만 아니라 ARM도 포함하여 요즘 쓰이는 웬만한 고성능 프로세서들은 (스마트폰의 메인 프로세서도 포함해서) AES의 하드웨어 구현 모듈을 기본으로 탑재하고 있다.