공개키 암호화 방식

''' 이론 컴퓨터 과학 {{{#!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=#aa3366> 이론
기본 대상	수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
	오토마타 이론	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. 개요2. 역사3. 용도

3.1. 기밀 내용의 전달3.2. 발행자의 증명 및 문서의 변조 방지3.3. 부인 방지

4. 종류5. 기타6. 관련 문서

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 는 자신만이 가진 개인키로 이 문서를 해독한다.

타인이 전달과정에서 암호화된 문서를 가로채더라도 B의 개인키가 없으면 해독이 불가능하다

SSL/TLS에서 두 당사자가 사용할 '대칭키'를 전달하는 용도로 사용된다.

다만 공개키 암호화는 처리 속도가 매우 느리므로 공개키 암호화는 TLS의 키 교환 같이 간단한 데이터를 전달하는 용도로만 사용된다. 그렇다면 처리 속도가 빨라야 할 경우는 어떡할까? 대칭 열쇠 암호가 있다.

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

어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 인장, 도장, 서명 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다.

A 는 자신의 공개키를 공개한다.
A 는 어떤 문서 혹은 해당 문서의 해시 정보[3]를 자신의 개인키로 암호화 한다.
A 는 암호화된 문서를 일반에 공개하면서,이 문서를 자신이 만들었음을 선포한다.
타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다.

타인은 A의 공개키로 복호 가능한 문서를 생성할 수 없으므로, 해당 문서는 A 만이 발행 할 수 있다는 강력한 증거가 된다.

추가로, 해당 문서가 변조되지 않았다라는 중요한 기능을 동시에 얻을 수 있다.

이는 공인인증서를 비롯한 전자서명에서 사용되는 방법이다.

3.3. 부인 방지

B가 가지고 있는 어떤 문서에 A 의 서명 (또는 도장)이 있는데, 정작 A 는 이 서명이 자신의 것이 아니라고 부인할 수 있다. 예를 들어 A 가 B 에게 돈을 빌린 후 '차용증'에 서명했는데, 후에 A 는 돈을 빌리지 않았으며 차용증 역시 자신의 서명이 아니라고 부인 하는 경우를 생각해 볼 수 있다. 이 때, B 는 문서에 있는 서명이 A 의 것이 맞다는 것을 확인하는 것이 '부인 방지'이다. 공개키 암호화 방식에서는 본질적으로 '발행자의 증명'과 동일한 절차로 이루어진다.

B 는 A 에게 개인키/공개키를 생성한 뒤 공개키를 공개하도록 요구한다. 이 절차는 공인인증서같은 것으로 대체할 수 있다.
B 는 A 에게 '문서'를 개인키로 암호화할 것으로 요구한다.
B 는 이 '암호화된 문서'를 수령한다.
B 는 '암호화된 문서'를 A 의 공개키로 해독하여, 이 문서가 A 의 개인키로 제대로 암호화 되었음을 검증할 수 있다. [4]

이 '암호화된 문서'는 A 의 공개키로만 해독이 가능하므로, 이 '암호화된 문서'는 A 만이 발행할 수 있다는 증거가 된다. 또한, 변조되지 않았음도 동시에 증명할 수 있다.

4. 종류

디피-헬만 키 교환
RSA 암호화
Rabin 암호 - 이 역시 큰 수의 소인수분해의 어려움에 기반하는 알고리즘이고 RSA 와 유사하지만 중국인의 나머지 정리(CRT)를 응용한다.
ElGamal
DSA - 이는 사실 특별히 디지털 서명을 위한 알고리즘이지만, 기존의 디지털 서명이 RSA 등의 다른 공개키 알고리즘에 기반하고 있는 반면 이는 독자적인 공개키 알고리즘으로 디지털 서명을 하는 것이기 때문에, 공개키 암호 부분만 생각하면 이 종류에 넣어도 무방하다.
타원 곡선 암호 - ECC(Elliptic curve cryptography)로 불린다. 같은 공개키 암호 방식인 RSA에 비해 짧은 키(Key)값을 가지면서도 안정성은 동일하며 속도 또한 빠르다. 다만 어려운 수학적 배경이론과 소프트웨어적 구현의 어려움 때문에 개발은 더딘 편. 그래도 RSA와 비교하여 동일 키값을 가질 시 안정성은 더욱 높기 때문에 일부 산업용에서 종종 쓰이는 편이다. RSA가 140자리 이상의 큰 두개의 소수를 이용하는 반면 ECC는 알려진 특정한 점에 대한 무작위 타원 곡선의 이산 로그를 이용한다.

5. 기타

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

이 때문에 실제로 공개키 암호화를 이용해서 평문을 암호화하는 경우는 실용적인 용도로는 거의 찾아볼 수 없고, 실제 평문을 암/복호화하는 데에는 대칭키 암호화를 이용하고 대칭키 알고리즘에 사용되는 키만 공개키 방식으로 암/복호화하여 서로 교환하는 경우가 대부분이다. 보통 대칭키 알고리즘들은 특정한 몇몇 부분을 빼면 분기도 별로 없을 정도로 단순 연산의 반복이기 때문에, 속도도 빠를뿐더러 아예 하드웨어적으로 구현된 경우도 많다.[8]

위에서 언급한 대로 암호화를 이용하는 대표적인 경우가 바로 SSL/TLS.

비밀키 암호화 방식과 같이 컴활 1급 필기시험에서 단골문제로 나오는 주제중 하나이다.

6. 관련 문서

[1] 원칙적으로는 암호화는 공개키, 복호화는 비밀키를 사용한다. 다만, 경우에 따라 반대로 사용할 수도 있다. [2] RSA는 큰 수의 소인수분해의 어려움에 기반하고 있다. [3] 문서 용량이 큰 경우 처리 속도가 느린 공개키 암호화로 해당 문서를 통째로 암호화하기에는 비효율적이기 때문이다. [4] 만약 해독되지 않는다면, 개인키-공개키 쌍이 맞지 않음을 의미한다. 공개한 공개키가 잘못되었거나, 다른 개인키로 암호화 했음을 뜻한다. [5] Fermat Factorization에 의해 p*q에서 p, q를 비교적 빠르게 복원할 수 있다. [6] 어떤 수 [math(a)], [math(b)], [math(c)]에 대해 [math(a^b \; \mathrm{mod} \; c)]를 구하는 과정. [7] 게다가 보통 암호화에 쓰는 e는 보통 65537로 잡기 때문에 큰 수를 지수승하는 것도 아니다. 물론 복호화에 쓰는 d는 큰 수가 되지만. [8] 대표적으로 인텔의 AES-NI.