공개 키 암호 방식

파일:Public key encryption.svg

공개 키 암호 방식(公開 - 暗號 方式, public-key cryptography)은 암호 방식의 한 종류로 비밀 키 암호 방식과 달리 암호화와 복호화에 이용하는 키가 다른 방식을 말한다. 공개 키 암호를 구성하는 알고리즘은 대칭 키 암호 방식과 비교하여 비대칭 암호(非對稱暗號)라고 부르기도 한다.

공개 키 암호 방식은 크게 두 가지 종류로 나눌 수 있다.

• 공개 키 암호 — 특정한 비밀 키를 가지고 있는 사용자만 내용을 열어볼 수 있음.
• 공개 키 서명 — 특정한 비밀 키로 만들었다는 것을 누구나 확인할 수 있음.

공개 키 암호 방식은 열쇠로 잠겨 있고 좁은 투입구가 있는 편지함에 비유할 수 있다. 이런 편지함은 위치(공개 키)만 알면 투입구를 통해 누구나 편지를 넣을 수 있지만 열쇠(개인 키)를 가진 사람만이 편지함을 열어 내용을 확인할 수 있다.

공개 키 서명은 인장으로 편지봉투를 봉하는 것에 비유할 수 있다. 이렇게 봉인한 편지는 누구나 열어볼 수는 있지만 인장 확인을 통해 인장을 소유한 발신자가 이 편지를 보냈음을 증명할 수 있다.

일반적으로, 공개 키 암호 방식은 대칭 키 암호보다 계산이 복잡한 단점이 있기 때문에, 효율을 위해 비밀 키 암호(혹은 대칭 암호)와 함께 사용된다. 메시지를 임의로 만들어진 비밀 키를 이용해 암호화한 다음 이 비밀 키를 다시 수신자의 공개 키로 암호화하여 메시지와 함께 전송하는 것이다. 이렇게 하면 공개 키 암호 기술로는 짧은 비밀 키만을 암호화하고 보다 효율적인 비밀 키 암호 기술로 전체 메시지를 암호화하므로 양쪽의 장점을 취할 수 있다.

원리

공개 키 암호 방식은 출제자만이 알고 있는 특정한 종류의 정보(비밀 키) 없이는 매우 풀기 어려운 수학적 문제(공개 키)를 바탕으로 만들어진다. 키를 만드는 사람은 이 문제(공개 키)를 일반에 공개하고 특정한 정보(비밀 키)는 자신만이 알 수 있도록 숨긴다. 그러면 어떤 사람이건 이 문제를 이용해 메시지를 암호화하면 키를 만든 사람만이 이 문제를 풀어 원래 메시지를 해독할 수 있다.

RSA 암호와 같은 초기 암호들은 두 개의 큰 소수를 곱한 숫자를 문제로 사용하였다. 사용자는 임의의 큰 소수를 두 개 골라 비밀 키로 삼고 그 곱한 값을 공개 키로 공개한다. 큰 수의 소인수 분해는 대단히 풀기 어려운 문제에 속하기 때문에 다른 사람들은 비밀 키를 알 수 없을 것이라는 사실이 보장된다. 그러나 최근 이 분야의 연구가 크게 진전되어 RSA의 안전성을 보장하기 위해서는 수천비트 이상의 큰 소수를 키로 사용해야 한다.

또 다른 종류의 문제로는 a와 c가 알려진 상태에서 방정식 a^b = c의 해 b를 구하는 문제가 있다. 실수나 복소수에 대해서는 로그 함수를 이용해 이 문제를 쉽게 풀 수 있다. 그러나 유한군에서는 이런 문제를 풀기가 어려운 것으로 알려져 있으며 이런 문제를 이산 로그 문제라 부른다. 타원곡선 암호를 비롯한 여러 가지 공개 키 암호들이 이산 로그 문제를 바탕으로 만들어져 있다.

역사

암호화 역사 초기에는 안전하기는 하지만 암호화되지는 않은 키를 사용했다. 예를 들어서, 암호를 사용할 사람들이 미리 모여서 암호 키를 나누어가진다든지, 신뢰할 수 있는 전령을 시켜서 보내는 방식등이었다. 이 키는 양쪽에서 완벽하게 보안을 유지하고 교환되는 메시지를 암호화하는데 사용되었지만, 이러한 키 분배 방식에는 실용적으로 많은 어려운 문제가 따랐다. 공개 키 암호 방식은 이러한 문제를 해결하고, 사용자들이 사전에 미리 공유 키를 교환하지 않더라도 공개 채널 상에서 안전하게 통신할 수 있도록 해준다.

1874년 윌리엄 스탠리 제본스는 자신의 책에서 단방향 함수와 암호화의 관계에 대해 설명하고 이어 RSA 시스템 내 트랩도어 함수 생성에 사용된 인수 분해 문제를 거론했다.

1997년, 비대칭 키 알고리즘이 영국 정부통신본부 (GCHQ)에서 제임스 일리스, 클리포드 콕스, 그리고 말콤 윌리암슨에 의해 1973년에 개발된 것이라는 발표가 있었다. 이들은 디피-헬먼 키 교환 방식과 RSA의 특별한 경우를 독립적으로 개발하였다. GCHQ의 암호학자들은 자신의 기법을 "비-보안 암호화"로 불렀으며 2010년에 IEEE 마일스톤에 등록되었다.

1976년에 휫필드 디피와 마틴 헬만이 랄프 머클의 공개 키 분배에 대한 연구를 참고하여 새로운 비대칭 키 암호체계를 발표했는데, 이 키 교환 방식이 디피-헬먼 키 교환방식이다. 이 방식은 인증된 (그러나 공개된) 통신 채널 상에서 미리 키를 공유하지 않으면서도 공유 보안 키를 설정할 수 있는 최초의 실용적인 방법이었다. 머클의 공개 키 교환 기법은 머클의 퍼즐이라 부르는데 1974년에 고안되어 1978년에 발표되었다.

로널드 라이베스트, 아디 샤미르, 레너드 애들먼 세 명은 MIT에서 콕스가 제안했던 것과 거의 같은 암호방식을 재발견하고 이것을 1978년에 논문으로 썼다. 이들은 자신들의 머리글자를 따서 이 암호방식을 RSA라고 이름 지었다. RSA는 두 개의 큰 소수를 곱한 값 n을 이용하여 모듈로 지수승 연산한 것을 각각 암호화와 복호화에 이용하여 공개 키 암호와 공개 키 서명을 수행하는 방식이며, 이 방식을 사용할 경우 보안 수준은 큰 정수의 인수 분해처럼 극도로 어려워 일반적인 기법 중에는 알려진 효과적인 (실용적으로 빠른) 방법이 없다고 가정했다. 1979년, 미하엘 라빈이 공개 키의 인수 분해가 어려울 경우 보안이 검증된 라빈 암호체계를 발표했는데 RSA의 보안 수준도 동등한 것으로 간주되고 있다.

1970년대 이후로 공개 키 암호 분야에서 암호, 서명, 키 합의, 및 다른 기법과 관련된 수많은 기술이 개발되었다. 타헤르 엘가말이 고안한 엘가말 암호는 이산 로그문제의 어려움에 기반하고 있으며, 미국 국가안보국 (NSA)가 개발하고 미국 국립표준기술연구소 (NIST)가 발표한 디지털 서명 알고리즘 (DSA)도 이와 비슷한 개념을 적용했다. 1980년대 중반에는 닐 코블리츠와 빅터 밀러가 각자 독자적으로 타원곡선 암호를 제안했는데, 이는 이산 알고리즘 문제에 기반한 새로운 공개 키 알고리즘을 구축하였다. 타원곡선이 수학적으로는 더 복잡하지만 동등한 수준의 보안을 위해 더 작은 키를 사용하면서도 연산 속도는 빠르다는 장점이 있다.

같이 보기

• 키 합의
• GNU 프라이버시 가드
• PGP (소프트웨어)
• 전송 계층 보안 (SSL/TLS)
• 시큐어 셸
• 양자 암호
• 공개 키 기반 구조(PKI).