공개 키 암호 방식
위키백과 ― 우리 모두의 백과사전.
공개 키 암호 방식(公開 - 暗號 方式)는 암호의 한 종류로 사전에 비밀 키를 나눠가지지 않은 사용자들이 안전하게 통신할 수 있도록 해준다. 일반적으로 공개 키는 잠그는 기능을 하고 개인 키는 잠근 것을 여는 기능을 한다. 개인 키는 각 사용자가 안전하게 보관하지만 공개 키는 외부에 공개한다. 그렇기 때문에 공개 키로부터 개인 키를 알아내는 것이 어려워야 한다. 이 두 키는 서로 수학적으로 연관되어 있지만 별개의 키이므로, 이런 암호방식을 비대칭 암호(非對稱暗號)라고 부르기도 한다.
공개 키 암호 방식은 크게 두 가지 종류로 나눌 수 있다.
- 공개 키 암호 — 특정한 비밀 키를 가지고 있는 사용자만 내용을 열어볼 수 있음.
- 공개 키 서명 — 특정한 비밀 키로 만들었다는 것을 누구나 확인할 수 있음.
공개 키 암호 방식은 열쇠로 잠겨 있고 좁은 투입구가 있는 편지함에 비유할 수 있다. 이런 편지함은 위치(공개 키)만 알면 투입구를 통해 누구나 편지를 넣을 수 있지만 열쇠(개인 키)를 가진 사람만이 편지함을 열어 내용을 확인할 수 있다.
공개 키 서명은 인장으로 편지봉투를 봉하는 것에 비유할 수 있다. 이렇게 봉한 편지는 누구나 열어볼 수 있지만 인장을 통해 인장의 주인이 편지를 보냈음을 증명할 수 있다.
일반적으로, 공개 키 암호 방식은 비밀 키 암호보다 계산이 복잡한 단점이 있기 때문에, 효율을 위해 비밀 키 암호(혹은 대칭 암호)와 함께 사용된다. 메시지를 임의로 만들어진 비밀 키를 이용해 암호화한 다음 이 비밀 키를 다시 수신자의 공개 키로 암호화하여 메시지와 함께 전송하는 것이다. 이렇게 하면 공개 키 암호 기술로는 짧은 비밀 키만을 암호화하고 보다 효율적인 비밀 키 암호 기술로 전체 메시지를 암호화하므로 양쪽의 장점을 취할 수 있다.
[편집] 원리
공개 키 암호 방식에는 여러 가지 종류가 있지만 이들은 대부분 동일한 특징을 공유한다.
공개 키 암호 방식은 출제자만이 알고 있는 특정한 종류의 정보 없이는 매우 풀기 어려운 수학적 문제를 바탕으로 만들어진다. 키를 만드는 사람은 이 문제(공개 키)를 일반에 공개하고 특정한 정보(비밀 키)는 자신만이 알수 있도록 숨긴다. 그러면 어떤 사람이건 이 문제를 이용해 메시지를 암호화하면 키를 만든 사람만이 이 문제를 풀어 원래 메시지를 해독할 수 있다.
RSA 암호와 같은 초기 암호들은 두 개의 큰 소수를 곱한 숫자를 문제로 사용하였다. 사용자는 임의의 큰 소수를 두 개 골라 비밀 키로 삼고 그 곱한 값을 공개 키로 공개한다. 큰 수의 소인수분해는 대단히 풀기 어려운 문제에 속하기 때문에 다른 사람들은 비밀 키를 알 수 없을 것이라는 사실이 보장된다. 그러나 최근 이 분야의 연구가 크게 진전되어 RSA의 안전성을 보장하기 위해서는 수천비트 이상의 큰 소수를 키로 사용해야 한다.
또 다른 종류의 문제로는 a와 c가 알려진 상태에서 방정식 ab = c의 해 b를 구하는 문제가 있다. 실수나 복소수에 대해서는 로그 함수를 이용해 이 문제를 쉽게 풀 수 있다. 그러나 유한군에서는 이런 문제를 풀기가 어려운 것으로 알려져 있으며 이런 문제를 이산 로그 문제라 부른다. 타원곡선암호를 비롯한 여러 가지 공개 키 암호들이 이산 로그 문제를 바탕으로 만들어져 있다.
[편집] 역사
최근까지 암호를 사용하는 데 있어서, 암호 키를 미리 만들고 사용자들이 나누어가지는 방식을 주로 사용했다. 예를 들어서, 암호를 사용할 사람들이 미리 모여서 암호 키를 나누어가진다든지, 신뢰할 수 있는 전령을 시켜서 보내는 방식등이었다. 이러한 키 분배 방식에는 여러 문제가 있기 때문에 공개 키 암호 방식이 제안되었다. 공개 키 암호 방식을 이용하면, 사전에 미리 비밀값을 나누어가지지 않은 사용자들이라도 전령과 같은 안전한 채널이 없는 상황에서도 안전하게 통신할 수 있다.
공개 키 암호 방식은 1970년대 영국 GCHQ의 클리포드 콕스가 최초로 만들었으나. 이 사실은 1997년까지 비밀에 부쳐졌기 때문에 널리 알려지지는 않았다. 1976년에 휘트필드 디피와 마틴 헬만이 공개 키 암호 방식에 대한 최초의 논문을 썼으며, 이를 바탕으로 랄프 머클이 1978년에 지수승 연산을 이용하여 암호 키를 합의할 수 있는 암호 키 분배 방식을 제안했다. 이 방식은 디피-헬만 키 교환방식이라고 부르며, 안전하지 않은 채널에서 비밀 키를 나누어 가질 수 있는 최초의 방법이었다.
로널드 라이베스트, 아디 샤미르, 레너드 에이들먼 세 명은 MIT에서 콕스가 제안했던 것과 거의 같은 암호방식을 재발견하고 이것을 1978년에 논문으로 썼다. 이들은 자신들의 머리글자를 따서 이 암호방식을 RSA라고 이름 지었다. 두 개의 큰 소수를 곱한 값 n을 이용하여 모듈로 지수승연산한 것을 각각 암호화와 복호화에 이용하는 방식이었고, n을 소인수분해하는 효율적인 알고리즘이 없는 한 안전한 공개 키에서 비밀 키를 알아낼 수 없다고 가정하고 만들었다.
1970년대이후로 암호, 서명, 키 합의등과 관련된 수많은 기술이 개발되었다. 타헤르 엘가말은 이산로그문제의 어려움에 기반한 ElGamal 암호을 제안했고, 이것은 NSA와 NIST가 개발한 DSA도 이와 비슷한 개념을 적용했다. 닐 코블리츠와 빅터 밀러가 1980년대 중반에 타원곡선암호를 제안한 이후에는 이와 관련된 수많은 공개 키 알고리즘이 제안되었다. 특히 타원곡선을 이용하면 짧은 키를 사용해도 원래 이산로그문제와 비슷한 안전성을 제공할 수 있는 장점이 있다.
[편집] 같이보기
|
|
|
|---|---|
| 알고리즘 | Cramer-Shoup · DH · DSA · ECDH · ECDSA · EKE · ElGamal · GMR · MQV · NTRUEncrypt · NTRUSign · Paillier · 라빈 · Rabin-Williams · RSA · Schnorr · SPEKE · SRP · XTR |
| 이론 | 이산 로그 · 타원곡선 암호 · RSA 문제 |
| 표준 | ANS X9F1 · CRYPTREC · IEEE P1363 · NESSIE |
| 기타 | 전자 서명 · 공개 키 기반 구조(PKI) · Web of trust · 키 크기 |
