| '''이론 컴퓨터 과학 {{{#!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.1. 기밀 내용의 전달
A가 자신만 알고 있는 기밀을 B에게 전달하고자 할 때 사용한다. B를 제외한 타인은 이 내용을 알 수 없어야 한다.- B가 자신의 공개키를 공개한다.
- A는 이 공개키로 문서를 암호화 한다.
- 암호화된 문서를 B에게 전달한다.
- B는 자신만이 가진 개인키로 이 문서를 해독한다.
다만, 공개키 암호화 방식은 처리 속도가 매우 느리고 대용량 파일에는 적용이 불가능하다는 큰 단점이 있다.[3] 그래서, 데이터의 암호화는 '대칭 열쇠 암호'를 사용해서 암호화 하여 전달하고, 이때 사용하는 '대칭키' 자체를 전달하는 용도로 공개키/개인키를 이용해서 암호화 하여 전달한다. 예를 들어 TLS에서는 이 방식을 이용한다.
3.2. 발행자의 증명 및 문서의 변조 방지
어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 인장, 도장, 서명 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다.- A는 자신의 공개키를 공개한다.
- A는 어떤 문서 혹은 해당 문서의 해시 정보[4]를 자신의 개인키로 암호화 한다.
- A는 암호화된 문서를 일반에 공개하면서, 이 문서를 자신이 만들었음을 선포한다.
- 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다.
추가로, 해당 문서가 변조되지 않았다라는 중요한 기능을 동시에 얻을 수 있다.
이는 공인인증서를 비롯한 전자서명에서 사용되는 방법이다.
3.3. 부인 방지
B가 가지고 있는 어떤 문서에 A의 서명 (또는 도장)이 있는데, 정작 A는 이 서명이 자신의 것이 아니라고 부인할 수 있다. 예를 들어 A가 B에게 돈을 빌린 후 '차용증'에 서명했는데, 후에 A는 돈을 빌리지 않았으며 차용증 역시 자신의 서명이 아니라고 부인 하는 경우를 생각해 볼 수 있다. 이 때, B는 문서에 있는 서명이 A의 것이 맞다는 것을 확인하는 것이 '부인 방지'이다. 공개키 암호화 방식에서는 본질적으로 '발행자의 증명'과 동일한 절차로 이루어진다.- B는 A에게 개인키/공개키를 생성한 뒤 공개키를 공개하도록 요구한다. 이 절차는 공인인증서같은 것으로 대체할 수 있다.
- B는 A에게 '문서'를 개인키로 암호화할 것으로 요구한다.
- B는 이 '암호화된 문서'를 수령한다.
- B는 '암호화된 문서'를 A의 공개키로 해독하여, 이 문서가 A의 개인키로 제대로 암호화 되었음을 검증할 수 있다.[5]
4. 종류
- 디피-헬만 키 교환 - 다만, 이는 약간 다른데, A가 가진 정보가 B에게 전달되는 것이 아니라, A와 B가 어떤 랜덤한 수를 동시에 얻게 되는 결과를 만들어 낸다.
- RSA 암호화
- Rabin 암호 - 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA와 유사하지만 중국인의 나머지 정리(CRT)를 응용한다.
- ElGamal
- DSA (Digital Signature Algorithm) - 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다.
- 타원 곡선 암호 - ECC(Elliptic curve cryptography)로 불린다. 같은 공개키 암호 방식인 RSA 암호화에 비해 짧은 키(Key)값을 가지면서도 안정성은 동일하며 속도 또한 빠르다. 다만 어려운 수학적 배경이론과 소프트웨어적 구현의 어려움 때문에 개발은 더딘 편. 그래도 RSA와 비교하여 동일 키값을 가질 시 안정성은 더욱 높기 때문에 일부 산업용에서 종종 쓰이는 편이다. RSA가 140자리 이상의 큰 두개의 소수를 이용하는 반면 ECC는 알려진 특정한 점에 대한 무작위 타원곡선의 이산 로그를 이용한다.
5. 기타
일반적으로 지금까지 발표된 모든 공개키 암호화는 기존의 대칭키 암호화들에 비해 연산량이 보통 훨씬 많다. RSA의 예만 봐도, 일단 알고리즘의 특성상 큰 소수p, q를 먼저 랜덤하게 찾아야 하는데 현재 일반적으로 사용하는 소수가 1024비트를 넘어 2048비트나 그 이상의 크기까지 가고 있다는 점을 생각하면 이에 드는 연산(소수 판별)도 그렇게 작다고 볼 수 없다. 게다가 한 소수 p를 구해도, 거기에 단순히 숫자를 더하거나 빼면서 소수판별을 하는 식으로 하면 취약점이 생기므로[6] 그렇게 할 수는 없고 결국 두 번을 제대로 구해야 한다. 그나마 실제 암/복호화 과정의 핵심인 modular exponent[7]는 가장 빠른 알고리즘을 사용하면 별로 느리지 않지만[8] 대칭키 암호화에 비하면 여전히 높은 연산량을 요구하기에 통신되는 모든 데이터를 암복호화하기에는 많이 부담스러울 것이다. 물론 기본 연산 토대 뿐 아니라, 실용적으로 사용하기 위해 여러 보안적인 허점을 보완하는 데에는 다른 여러 연산들이 들어가기 때문에 대칭키 암호화에 비해 더더욱 연산량이 늘어날 것이다.[9]이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 실제 평문을 암/복호화하는 데에는 대칭키 암호화를 이용하고 대칭키 알고리즘에 사용되는 키만 공개키 방식으로 암/복호화하여 서로 교환하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[10]
위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 SSL/TLS.
비밀키 암호화 방식과 같이 컴활 1급 필기시험에서 단골문제로 나오는 주제중 하나이다.
6. 관련 문서
[1] 원칙적으로는 암호화는 공개키, 복호화는 비밀키를 사용한다. 다만, 경우에 따라 반대로 사용할 수도 있다.[2] RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다.[3] 대칭키 암호화는 블록 모드가 존재하여 데이터를 블록 단위로 쪼개서 병렬적으로 처리하기에 패딩 과정만 잘 거치면 용량 제약을 받지 않는다. 그러나 공개키 암호화 방식은 블록화가 불가능하여 암호화 비트수를 넘어가는 대부분의 데이터에 대해서는 아예 처리 자체가 불가능하다.[4] 문서 용량이 큰 경우 처리 속도가 느린 공개키 암호화로 해당 문서를 통째로 암호화하기에는 비효율적이기 때문이다.[5] 만약 해독되지 않는다면, 개인키-공개키 쌍이 맞지 않음을 의미한다. 공개한 공개키가 잘못되었거나, 다른 개인키로 암호화 했음을 뜻한다.[6] Fermat Factorization에 의해
p*q에서 p, q를 비교적 빠르게 복원할 수 있다.[7] 어떤 수 [math(a)], [math(b)], [math(c)]에 대해 [math(a^b \; \mathrm{mod} \; c)]를 구하는 과정.[8] 게다가 보통 암호화에 쓰는 e는 보통 65537로 잡기 때문에 큰 수를 지수승하는 것도 아니다. 물론 복호화에 쓰는 d는 큰 수가 되지만.[9] 클라이언트 입장에서도 부담스러울 수 있겠지만, 서버에게는 연산량 증가가 더 심각한 문제로 다가온다. 서버는 보통 동시에 여러 클라이언트들을 상대해야 함을 상기하자. 저전력을 요구하는 시스템의 경우, 클라이언트에게도 연산량 증가는 민감한 문제가 될 것이다.[10] 대표적으로 인텔의 AES-NI. 사실 인텔 계열 칩 뿐만 아니라 ARM도 포함하여 요즘 쓰이는 웬만한 고성능 프로세서들은 (스마트폰의 메인 프로세서도 포함해서) AES의 하드웨어 구현 모듈을 기본으로 탑재하고 있다.