블록체인/레벨 I · 화폐/1.2 사이퍼펑크가 걸어온 길/수업 1
공개키 암호화: 디피-헬만과 RSA
만나지 않고도 공유된 비밀, 그리고 소유권을 증명하는 서명
준비물모듈러 산술을 처리할 수 있는 계산기나 스프레드시트디피-헬만 논문(1976년)
호기심
- 모두가 엿듣고 있는 상황에서 두 낯선 사람은 어떻게 비밀 키에 합의할 수 있을까?
- 두 개의 큰 소수를 곱하기는 쉬운데, 왜 그 곱에서 원래의 소수들을 찾아내기는 거의 불가능할까?
- 소유가 서명할 수 있는 능력으로 정의된다면, 무언가를 소유한다는 것은 무엇을 의미할까?
탐구
- 1976년 이전에는 안전한 통신을 하려면 신뢰할 수 있는 채널을 통해 교환한 공유 비밀이 필요했습니다. 도청자가 그 키를 가로채면 이후의 모든 통신 내용이 위태로워졌습니다. 휫필드 디피와 마틴 헬만은 ‘암호학의 새로운 방향(New Directions in Cryptography)’(IEEE Transactions on Information Theory, 1976년 11월)에서 해결책을 제시했습니다. 두 당사자는 모듈러 거듭제곱을 이용해 공개된 채널에서도 공유 비밀을 도출할 수 있었습니다. 이 수학은 일방향입니다. 정방향으로는 계산하기 쉽지만, 비공개 입력값 없이 역으로 계산하는 것은 계산상 불가능합니다.
- 랄프 머클은 1974년에서 1975년 사이에 비슷한 퍼즐을 고안해 1978년에 발표했습니다. 한쪽은 암호화된 작은 퍼즐을 다수 공개하고, 다른 쪽은 그중 하나를 무작위로 골라 풀어 그 내용을 키로 사용했습니다. 이 방식의 이점은 이차(제곱) 수준에 불과했습니다. 퍼즐이 n개라면 두 당사자는 약 n 단위의 작업을, 도청자는 약 n² 단위의 작업을 해야 했습니다. 디피-헬만의 격차는 키 크기에 따라 커지며, 세션마다 새로운 키 쌍을 사용하면 나중에 장기 키가 유출되더라도 과거의 통신 내용은 노출되지 않습니다.
- 1977년 MIT의 론 리베스트, 아디 샤미르, 레너드 애들먼이 RSA를 개발했습니다. 정식 논문이 Communications of the ACM(1978년 2월)에 실리기 전에, 마틴 가드너가 1977년 8월 사이언티픽 아메리칸 칼럼에서 이 시스템을 소개했습니다. RSA는 두 큰 소수의 곱을 원래의 소수로 분해하기 어렵다는 점에 기반합니다. RSA는 디지털 서명을 가능하게 했습니다. 개인 키로 데이터에 서명하면, 이에 대응하는 공개 키로 서명자의 비밀을 드러내지 않고도 그 서명을 검증할 수 있습니다.
- GCHQ의 제임스 엘리스는 1969년경 ‘비밀이 필요 없는 암호화(non-secret encryption)’를 고안하고 1970년에 이를 문서로 정리했습니다. 클리퍼드 콕스는 1973년에 RSA와 동등한 시스템을, 맬컴 윌리엄슨은 1974년에 디피-헬만과 동등한 방식을 도출했습니다. 이러한 발견은 1997년까지 기밀로 유지되었습니다. 이처럼 독립적으로 이루어진 병행 연구는 1970년대 초에 이미 수학적 기반이 성숙해 있었음을 보여 주지만, 실제 채택은 학계 연구자들이 공개적으로 발표한 뒤에야 이루어졌습니다. 비밀리에 진행된 연구는 공공 인프라를 만들지 못합니다.
- 리베스트, 샤미르, 애들먼은 2002년에, 디피와 헬만은 2015년에 튜링상을 받았습니다. 이는 비트코인에 중요한 의미가 있습니다. 소유권이 더 이상 물리적 보관이나 은행 기록에 묶이지 않고, 개인 키로 유효한 서명을 만들어 낼 수 있는 능력에 달려 있게 되었기 때문입니다. 비트코인은 RSA 대신 secp256k1 타원곡선 암호를 사용하지만, 핵심 구조는 그대로입니다. 사용자는 트랜잭션에 서명함으로써 자금에 대한 통제권을 증명하고, 네트워크는 개인 키를 전혀 보지 않고도 공개 키로 이를 검증합니다.
- 작은 숫자로 디피-헬만을 직접 계산해 봅시다. 먼저 소수 p = 23과 밑 g = 5를 공개적으로 합의합니다. 앨리스는 비밀 값 a = 6을 골라 5^6 mod 23 = 8을 보냅니다. 밥은 b = 15를 골라 5^15 mod 23 = 19를 보냅니다. 앨리스는 19^6 mod 23 = 2를, 밥은 8^15 mod 23 = 2를 계산합니다. 공개 채널로 오간 것은 23, 5, 8, 19뿐이지만, 이제 두 사람 모두 비밀 값 2를 갖게 되었습니다. 실제 시스템은 수백 자리에 이르는 숫자를 사용하므로, 공개된 값으로부터 a나 b를 알아내는 것은 계산상 불가능합니다.
핵심 사실
- 디피와 헬만은 1976년 11월에 자신들의 키 교환 프로토콜을 발표했습니다.
- RSA는 1977년 MIT에서 개발되어 1978년 2월에 Communications of the ACM에 발표되었습니다.
- GCHQ에서 제임스 엘리스, 클리퍼드 콕스, 맬컴 윌리엄슨은 1970년경부터 1974년 사이에, 이후의 미국 연구와는 독립적으로 공개키 방식을 개발했습니다.
- GCHQ의 공개키 암호화에 관한 연구는 1997년에 기밀이 해제되었습니다.
- RSA의 보안성은 두 개의 큰 소수의 곱을 인수분해하는 것이 어렵다는 점에 기반합니다.
- 비트코인 소유권은 개인 키로 서명할 수 있는 능력에 의해 결정됩니다.
연습 아홉, 여섯, 셋, 하나
9모으기1970년부터 2008년까지 등장한 암호 기본 요소(프리미티브) 또는 프로토콜 9가지를 나열하세요. 각각의 발명자, 연도, 핵심 수학적 특성을 적어 보세요.
6묶기9가지를 키 교환, 디지털 서명, 해싱, 대칭 암호화, 인증, 기타의 6가지 범주로 분류하세요.
3추리기6개 그룹을 비대칭 암호화가 탈중앙화 시스템을 가능하게 한 3가지 이유로 압축하세요.
1결정화개인 키가 무엇을 증명하는지, 그리고 그것이 왜 소유의 의미를 바꾸는지 한 문장으로 쓰세요.
팩트 체크
날짜, 수치 및 주장은 아래에 명시된 출처들을 통해 확인되었습니다.
- W. Diffie & M. Hellman, 'New Directions in Cryptography', IEEE Transactions on Information Theory (Nov 1976)
- R. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems', Communications of the ACM (Feb 1978)
- S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (1999)
- S. Levy, Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age (2001)