나무모에 미러 (일반/어두운 화면)
최근 수정 시각 : 2024-04-13 18:55:55

공개키 암호화 방식

'''이론 컴퓨터 과학
{{{#!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 를 제외한 타인은 이 내용을 알 수 없어야 한다.
  1. B 가 자신의 공개키를 공개한다.
  2. A 는 이 공개키로 문서를 암호화 한다.
  3. 암호화된 문서를 B 에게 전달한다.
  4. B 는 자신만이 가진 개인키로 이 문서를 해독한다.

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

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

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

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

어떤 문서를 '자신이 작성했음'을 증명하는 용도로도 사용될 수 있다. 오래전부터 발행자의 증명은 인장, 도장, 서명 등의 방법이 사용되었으나, 이는 모두 위조가 가능하다. 게다가, 문서의 변조를 막을 수도 없다.
  1. A 는 자신의 공개키를 공개한다.
  2. A 는 어떤 문서 혹은 해당 문서의 해시 정보[3]를 자신의 개인키로 암호화 한다.
  3. A 는 암호화된 문서를 일반에 공개하면서,이 문서를 자신이 만들었음을 선포한다.
  4. 타인은 공개된 공개키로 해당 문서를 해독하여 내용을 볼 수 있다.

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

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

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

3.3. 부인 방지

B가 가지고 있는 어떤 문서에 A 의 서명 (또는 도장)이 있는데, 정작 A 는 이 서명이 자신의 것이 아니라고 부인할 수 있다. 예를 들어 A 가 B 에게 돈을 빌린 후 '차용증'에 서명했는데, 후에 A 는 돈을 빌리지 않았으며 차용증 역시 자신의 서명이 아니라고 부인 하는 경우를 생각해 볼 수 있다. 이 때, B 는 문서에 있는 서명이 A 의 것이 맞다는 것을 확인하는 것이 '부인 방지'이다. 공개키 암호화 방식에서는 본질적으로 '발행자의 증명'과 동일한 절차로 이루어진다.
  1. B 는 A 에게 개인키/공개키를 생성한 뒤 공개키를 공개하도록 요구한다. 이 절차는 공인인증서같은 것으로 대체할 수 있다.
  2. B 는 A 에게 '문서'를 개인키로 암호화할 것으로 요구한다.
  3. B 는 이 '암호화된 문서'를 수령한다.
  4. B 는 '암호화된 문서'를 A 의 공개키로 해독하여, 이 문서가 A 의 개인키로 제대로 암호화 되었음을 검증할 수 있다. [4]

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

4. 종류

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.

분류