엔지니어링 철학: 아디 샤미르(Adi Shamir)

핵심 요점

• 그는 최초의 실용적 공개키 암호 시스템인 RSA의 ‘S’입니다. 아디 샤미르는 1977년 MIT에서 론 리베스트(Ron Rivest), 레너드 애들먼(Leonard Adleman)과 함께 RSA를 공동 발명했습니다. 그해에 공개적으로 기술되었고 1978년 2월 Communications of the ACM에 발표되었습니다. 이 방식은 사전에 비밀을 공유하지 않고도 누군가에게 암호화해 보내고 그 사람의 서명을 검증할 수 있게 했으며, 그 안전성은 큰 수를 소인수분해하기가 어렵다는 사실에 기반합니다. 이 업적으로 세 사람은 2002년 ACM 튜링상을 받았습니다.¹²
• 그는 하나의 다항식을 완벽한 비밀로 바꿨습니다. 1979년 샤미르는 “How to Share a Secret”를 발표했습니다. 이는 비밀을 n명에게 나누어, 그중 임의의 k명이 모이면 복원할 수 있지만 k-1명은 아무것도 — 힌트조차, 범위를 좁힐 단서조차 — 알 수 없게 하는 임계값 방식입니다. 이 모든 것이 오직 다항식 위의 점들만으로 만들어집니다.³
• 그는 뛰어난 암호 해독가입니다. 그는 방어하기 위해 공격합니다. 1980년대 후반 샤미르는 엘리 비함(Eli Biham)과 함께 블록 암호를 깨는 일반적 기법인 차분 분석법(differential cryptanalysis)을 공개적으로 발견했으며, 그보다 앞서 머클-헬먼(Merkle-Hellman) 배낭 암호 시스템을 깬 바 있습니다. RSA를 만든 바로 그 두뇌가 수십 년에 걸쳐 무언가를 깨는 법을 익혔습니다. 암호학에서는 그것이 시스템이 강하다는 것을 알 수 있는 유일하게 정직한 방법이기 때문입니다.⁴⁵
• 그는 깔끔한 수학을 실용적 메커니즘으로 바꾸는 일을 계속해 왔습니다. RSA와 비밀 공유를 넘어 샤미르는 피아트-샤미르 휴리스틱(Fiat-Shamir heuristic) — 해시 함수를 사용해 대화형 증명을 비대화형 서명으로 바꾸는 방법 — 을 공동 발명했고, ID 기반 암호와 시각 암호 방식도 만들었습니다. 1980년부터 바이츠만 연구소(Weizmann Institute) 교수로 재직 중인 그의 경력은, 깊은 정수론이 박물관의 유물이 아니라 하나의 도구 모음이라는 긴 논증입니다.¹⁶

원칙

“훗날 차분 분석법은 IBM과 미국 국가안보국(NSA) 양쪽 모두가 이미 알고 있었고 비밀로 유지해 왔던 것으로 드러났습니다.” — 비함과 샤미르가 공개적으로 재발견한 그 기법에 관하여, 역사적 기록을 풀어 옮김⁴⁵

대부분의 엔지니어링은 시연(demo)을 향해 나아갑니다. 무언가를 작성하고, 실행해 보고, 작동하면, 그 작동 자체가 증명이 됩니다. 암호학은 그런 안락함을 거부합니다. 올바르게 암호화하고 복호화하는 암호는 그것이 안전한지에 대해 아무것도 입증하지 못합니다. 깨진 암호와 깰 수 없는 암호는 누군가가 공격하기 전까지는 똑같이 동작하기 때문입니다. 그래서 이 분야는 다른 종류의 진리 기준을 만들어 내야 했습니다. 시스템은 실행될 때가 아니라, 진지한 사람들이 깨뜨리려 열심히 시도했으나 실패했을 때 비로소 신뢰할 만한 것이 됩니다. 샤미르의 경력 전체가 바로 그 기준의 구현입니다. 시스템을 안전하게 만들려면 시스템을 깨는 법을 익혀야 합니다. 방어하기 위해 공격하는 것입니다.⁴

가장 분명한 표현은, 그가 두 절반을 모두 직접 해낸다는 점입니다. 그는 공개키 암호의 초석인 RSA를 만들었고, 증명 가능한 정보이론적 안전성을 갖춘 방식인 샤미르 비밀 공유(Shamir’s Secret Sharing)도 만들었습니다.¹³ 하지만 그는 안전해 보였으나 그렇지 않았던 경쟁 공개키 방식인 머클-헬먼 배낭 암호 시스템을 깨뜨렸고, 데이터 암호화 표준(DES) 자체를 위협할 만큼 일반적인 기법인 차분 분석법을 공동 발견하기도 했습니다.⁴⁵ 이것은 두 개의 경력이 아닙니다. 하나의 분과 학문입니다. 구축 작업은 무엇이 가능한지를 알려 주고, 파괴 작업은 무엇이 진짜인지를 알려 줍니다. 만들기만 하는 암호학자는 추측하고 있는 것이며, 이에 대한 가장 섬뜩한 증거는 훗날 드러났습니다. IBM과 NSA가 1970년대 중반부터 차분 분석법을 알고 있었으면서도 기밀로 유지했다는 사실이 밝혀진 것입니다. 다시 말해, 공개 학계는 적들이 이미 손에 쥐고 있던 공격을 보지 못한 채 암호를 만들어 오고 있었던 셈입니다.⁴⁵

이 원칙에는 두 번째 절반이 있습니다. 더 조용하지만 그에 못지않게 핵심을 떠받치는 것 — 깔끔한 수학적 발상을 실용적 메커니즘으로 바꾸는 힘입니다. 비밀 공유는 그저 다항식 보간일 뿐입니다. 두 점이 직선 하나를 정하고 세 점이 포물선 하나를 정한다는, 누구나 대수학에서 배우는 사실입니다. 샤미르는 같은 사실을 거꾸로 읽으면 그것이 안전성 원시 요소가 된다는 것을 보았습니다. 점들을 나누어 주면, 충분한 점이 모일 때까지 곡선은 숨겨진 채로 남습니다.³ RSA는 그저 모듈러 거듭제곱과 소인수분해의 어려움입니다.² 피아트-샤미르 휴리스틱은 그저 검증자의 동전 던지기를 해시로 대체하는 것입니다.⁶ 깔끔한 수학적 구조를 찾아, 그것을 메커니즘으로 읽어 내십시오. 천재성은 새로운 수학에 있는 경우가 드뭅니다. 그것은 오래된 수학을 올바른 각도에서 바라보면 이미 당신이 만들어야 할 바로 그것임을 알아보는 데 있습니다.

배경

아디 샤미르는 1952년 7월 6일 이스라엘 텔아비브에서 태어났습니다.¹ 1973년 텔아비브 대학교에서 수학 학사 학위를 받은 뒤 바이츠만 과학 연구소로 옮겨 대학원 과정을 밟았고, 1975년에 컴퓨터과학 석사, 1977년에 박사 학위를 받았습니다.¹ 그의 시기는, 이 분야와 마찬가지로 막 전환점을 맞으려 하고 있었습니다. 1977년은 공개키 암호가 매혹적인 발상에서 작동하는 시스템으로 넘어간 해였습니다.

박사 학위를 받은 뒤 그는 영국 워릭 대학교(University of Warwick)에서 박사후 연구원으로 1년을 보냈고, 이어 매사추세츠 공과대학교(MIT)로 가서 1977년부터 1980년까지 연구원으로 일했습니다.¹ RSA가 탄생한 곳이 바로 MIT입니다. 암호학자 론 리베스트는 두 당사자가 공유된 비밀 없이도 비밀을 확립할 수 있다는 디피-헬먼(Diffie-Hellman)의 발상에서 영감을 받아 공개키 방식을 좇고 있었습니다. 샤미르와 애들먼은 그의 협력자이자, 결정적으로 그의 적수였습니다. 리베스트가 방식을 제안하면 샤미르와 애들먼이 그것을 깨뜨리기를 거듭했고, 마침내 하나가 살아남았습니다. 살아남은 그것이 RSA였고, 세 사람의 이름을 따서 명명되어 1977년에 공개되고 1978년 Communications of the ACM에 발표되었습니다.² (그들이 모르는 사이, 영국 수학자 클리퍼드 콕스(Clifford Cocks)가 GCHQ에서 1973년 기밀 문서에 동등한 시스템을 기술해 두었고, 이는 1997년까지 비밀로 남아 있었습니다. 정보기관이 지켜보는 가운데 학계가 어둠 속에서 무언가를 만들고 있던 또 하나의 사례입니다.)²

1980년 샤미르는 바이츠만 연구소로 돌아왔고, 그 이후 줄곧 컴퓨터과학·응용수학과 교수로 재직해 왔으며, 훗날 파리 고등사범학교(École Normale Supérieure)의 초빙 교수직도 맡았습니다.¹ 그를 규정하는 거의 모든 것 — 비밀 공유, 배낭 암호에 대한 공격, 제자 엘리 비함과 함께한 차분 분석법, 피아트-샤미르 휴리스틱, 모니 나오르(Moni Naor)와의 시각 암호, 큐브 공격, TWIRL과 TWINKLE 소인수분해 장치 — 이 모두가 바이츠만에서 나왔습니다. 2002년 미국 컴퓨터 학회(ACM)는 공개키 암호에 대한 공헌을 인정하여 리베스트, 샤미르, 애들먼에게 컴퓨팅 분야 최고의 영예인 튜링상을 수여했습니다.¹²

업적

샤미르 비밀 공유: 비밀을 지키는 포물선

여기서 시작합시다. 그 원칙이 가장 순수하고 아름다운 형태로 담겨 있기 때문입니다. 비밀 — 마스터 키, 발사 코드, 금고의 비밀번호 — 이 있고, 이것을 다섯 명의 수탁자에게 나누어, 그중 임의의 세 명이 함께하면 복원할 수 있되 두 명만으로는 아무것도 알 수 없게 하고 싶다고 합시다. 키를 물리적으로 조각낼 수도 있겠지만, 그러면 정보가 새어 나갑니다. 각 조각이 추측 범위를 좁히기 때문입니다. “How to Share a Secret”에 담긴 1979년 샤미르의 통찰은, 다항식이 이미 이 문제를 정확히 풀어 준다는 것이었습니다.³

그 비결은 초등학교 수준의 사실을 거꾸로 읽는 것입니다. 두 점은 유일한 직선 하나를 정하고, 세 점은 유일한 포물선 하나를 정하며, 일반적으로 k개의 점은 차수가 k-1인 유일한 다항식 하나를 정합니다. 그러므로 비밀을 임계값 k로 n명에게 나누려면, 임의로 정한 차수 (k-1) 다항식의 상수항 — 즉 x = 0에서의 곡선 값 — 에 비밀을 숨기고, 각 사람에게 그 곡선 위의 점 하나씩을 나누어 줍니다.³ 그중 임의의 k명은 자신들의 점을 지나는 유일한 곡선을 보간하여 0에서의 값을 읽어 낼 수 있습니다. 하지만 놀라운 부분은 그 안전성입니다. k-1개의 점만으로는 곡선을 단지 찾기 어려운 것이 아니라, 진정으로 결정되지 않은 채로 남습니다. 가능한 모든 비밀 값 각각에 대해, 그들의 점을 지나면서 0에서 바로 그 값을 갖는, 올바른 차수의 곡선이 정확히 하나씩 존재하기 때문입니다. 샤미르의 방식이 보장하듯, “임의의 k-1개 이하의 몫에 대한 지식만으로는 S가 완전히 결정되지 않은 채로 남습니다.”³ 임계값보다 적으면 아무것도 드러나지 않고, 임계값에 이르면 모든 것이 드러납니다. 그 깔끔한 전부-아니면-전무의 경계가 이를 정보이론적으로 안전하게 만듭니다. 깨는 것이 계산적으로 어려워서가 아니라, 정보 자체가 거기에 존재하지 않기 때문에 안전한 것입니다.³

이것이 엔지니어링으로서 중요한 이유는, 이 방식이 수학을 메커니즘으로 읽어 낸 샤미르의 전형적인 사례이기 때문입니다. 그는 다항식 보간을 발명하지 않았습니다. 그것은 수백 년 된 것입니다. 그는 그것의 실패 양상 — 너무 적은 점으로는 곡선을 복원할 수 없다는 것 — 이 바로 안전성 속성이며, 그것의 성공 양상 — 충분한 점이 곡선을 정확히 확정한다는 것 — 이 바로 복원 속성임을 보았습니다. 같은 사실이 양방향으로 쓰여, 오늘날 하드웨어 보안 모듈, 암호화폐 보관, 인증 기관 내부에서 작동하는 암호 원시 요소가 됩니다. 깔끔한 수학을 도구로 읽어 낸 것입니다.³

RSA: 낯선 이에게 암호화하기

RSA는 거의 역설처럼 보였던 물음에 답했습니다. 한 번도 만난 적 없고, 적이 엿듣고 있는 회선으로만 소통하는 두 사람이 어떻게 비밀을 주고받을 수 있는가? 고전 암호학은 사전에 확립된 공유 키를 요구했습니다. 그러나 바로 그 보호하려는 채널 위로 키를 공유할 수는 없는 노릇입니다. 리베스트, 샤미르, 애들먼이 1977년에 작동하는 시스템으로 만들어 낸 돌파구는 트랩도어 일방향 함수였습니다. 정방향으로 계산하기는 쉽지만, 비밀 정보 한 조각을 쥐고 있지 않으면 거꾸로 되돌리기가 사실상 불가능한 연산입니다.²

RSA의 트랩도어는 소인수분해입니다. 큰 소수 두 개를 골라 곱해 법(modulus) n을 만듭니다. n과 공개 지수가 당신의 공개키가 되며, 이는 온 세상에 공개해도 됩니다. 누구나 그것을 사용해 모듈러 거듭제곱을 통해 당신에게 메시지를 암호화해 보낼 수 있습니다. 하지만 복호화하려면 개인키가 필요한데, 이는 원래의 두 소수에서만 유도할 수 있습니다. 그리고 그 곱으로부터 소수들을 복원하는 것은 매우 큰 수를 소인수분해한다는 뜻이며, 이는 알려진 효율적 해법이 없는 문제입니다.² 그 정식화된 표현에 따르면, 키를 만드는 것은 실용적이지만 “e와 n만 주어졌을 때 법 n에 대한 e제곱근을 계산하는 것은 사실상 불가능합니다.”² 당신은 자물쇠를 공개하고, 열쇠는 당신만 쥐고 있으며, 그 둘 사이의 간극이 바로 소인수분해의 어려움입니다.

샤미르의 구체적인 역할은 분명히 짚어 둘 가치가 있습니다. 그것이 다시금 그 원칙이기 때문입니다. 그는 애들먼과 함께 세 사람 중 암호 해독가였습니다. RSA 발명의 이야기는 깨뜨리는 이야기입니다. 리베스트가 후보 방식들을 제안하면 샤미르와 애들먼이 그것을 공격했고, 단 하나만이 그 공세를 견뎌 냈습니다. 살아남은 그 방식이 강했던 것은 바로, 그것을 깨뜨리려 작정한 두 사람의 공격을 견뎌 냈기 때문입니다. RSA는 안전하도록 설계한 뒤 안전하기를 바란 시스템이 아닙니다. 그것은 자신을 만든 사람들의 공격을 견뎌 냄으로써 그 주장을 얻어 낸 시스템입니다.²

방어하기 위해 공격하기: 배낭 암호 깨뜨리기와 차분 분석법

RSA가 만드는 샤미르를 보여 준다면, 다음 일련의 업적은 이 분야가 그보다 훨씬 더 필요로 하는 일을 하는 그를 보여 줍니다. 바로 깨뜨리는 것입니다. 1970년대 후반, 머클-헬먼 배낭 암호 시스템은 RSA의 유력한 경쟁자였습니다. 그 안전성은 NP-완전이어서 만만찮게 어려워 보였던 “부분집합 합” 문제에 기반하고 있었습니다. 샤미르는 그것을 깼습니다. 그는 머클-헬먼이 사용한 특정한 배낭들이 어려운 일반적 경우가 아니라, 효율적으로 풀 수 있는 특수하고 구조화된 경우임을 보여 주어, 많은 이가 신뢰하던 방식을 무너뜨렸습니다.¹ 그 교훈은 암호학이 거듭 다시 배우는 것입니다. 어떤 문제가 일반적으로 어렵다고 해서, 당신의 암호가 실제로 사용하는 사례들이 어렵다는 뜻은 아닙니다. 오직 공격만이 그 차이를 드러냅니다.

그의 가장 영향력 있는 암호 해독 업적은 1980년대 후반 제자 엘리 비함과 함께 나왔습니다. 1990년 무렵에 발표된 차분 분석법입니다.⁴⁵ 이는 암호에 입력되는 한 쌍의 차이가 어떻게 출력의 차이로 전파되는지를 연구하는 일반적 기법입니다. 특정한 입력 차이가 무작위가 아닌 확률로 특정한 출력 차이로 이어진다면, 그 통계적 편향이 균열 — 키에 관한 정보의 누설 — 이 됩니다. 비함과 샤미르는 이를 다양한 블록 암호에 대한 공격으로, 그중에는 당시 세계에서 가장 중요한 암호였던 데이터 암호화 표준(DES)의 이론적 약점까지 포함한 공격으로 바꿔 냈습니다.⁴⁵

그러고 나서 이 분야는 겸허해지는 사실을 알게 되었습니다. 1994년, 돈 코퍼스미스(Don Coppersmith)는 1970년대에 DES를 설계한 IBM이 차분 분석법을 “이미 1974년에” 알고 있었고, 그것을 방어하는 것이 DES의 명시적 설계 목표였으며, NSA가 이 기법을 기밀로 유지하도록 압박했음을 밝혔습니다. “설계 고려 사항이 공개되면 차분 분석법이라는 기법이 드러날 것이고, 그것은 많은 암호에 사용될 수 있는 강력한 기법”이기 때문이었습니다.⁴⁵ 오랫동안 백도어를 숨기고 있는 것으로 의심받던 DES의 알 수 없는 내부 상수들은, 알고 보니 공개 학계가 존재조차 모르던 공격에 대한 방어를 숨기고 있었던 것입니다. 이 사건은 샤미르의 원칙을 뒷받침하는 가장 강력한 논거입니다. 20년 동안 공개 공동체는 적들이 이미 쥐고 있던 근본적인 공격을 보지 못한 채 암호를 만들고 신뢰해 왔습니다. 비함과 샤미르의 공개적 재발견은 암호학을 약화시킨 것이 아니라, 그 공격을 모두가 대비해 설계할 수 있는 밝은 곳으로 끌어냄으로써 암호학을 강화했습니다. 방어하기 위한 공격을, 한 분야 전체의 규모에서 행한 것입니다.⁴⁵

피아트-샤미르와 도구 모음의 폭

같은 본능 — 깔끔한 구조를 찾아 그것을 메커니즘으로 읽어 내는 것 — 이 샤미르의 다른 발명들을 관통합니다. 1980년대 중반 아모스 피아트(Amos Fiat)와 함께 만든 피아트-샤미르 휴리스틱은 지식의 대화형 증명이 안고 있던 실용적 문제를 풀었습니다. 그런 증명은 검증자가 무작위 도전 값을 보내고 증명자가 응답하는, 살아 있는 주고받음을 요구합니다. 피아트와 샤미르는 검증자의 유일한 역할이 예측 불가능한 무작위성을 공급하는 것뿐이며, 증명자 자신의 메시지에 암호 해시 함수를 적용하면 그 무작위성을 똑같이 잘 공급할 수 있음을 보았습니다. 이로써 대화는 단 하나의 자기 완결적인 비대화형 증명, 곧 디지털 서명으로 바뀝니다.⁶ 그 단 하나의 변환이 현대 서명 방식과 영지식 시스템의 상당 부분을 떠받칩니다. 그는 또한 (사람의 신원을 공개키로 사용하는) ID 기반 암호를 제안했고, 모니 나오르와 함께 시각 암호 — 이미지를 여러 투명 필름으로 나누어 겹쳐 쌓을 때만 비밀이 드러나게 하는, 눈으로 볼 수 있는 비밀 공유 — 를 공동 발명했으며, 훗날 큐브 공격과 TWIRL·TWINKLE 소인수분해 장치를 개발했습니다.¹ 그 모든 것에 걸쳐 같은 패턴이 유지됩니다. 알려진 수학 한 조각을 올바른 방향으로 돌려 놓으면, 그것이 도구가 됩니다.

방법

RSA, 비밀 공유, 깨진 배낭 암호, 차분 분석법, 피아트-샤미르를 두루 읽어 보면, 같은 신념들이 거듭 나타납니다. 샤미르의 방법은 구호라기보다는 일관되게 유지되는 일련의 습관에 가깝습니다.

같은 손으로 만들고 깨뜨리기. 그를 규정하는 행동은, 시스템을 구축하는 이와 공격하는 이 사이의 분업을 거부하는 것입니다. 샤미르는 RSA를 공동 발명하면서 머클-헬먼 배낭 암호를 깼고, 비밀 공유의 안전성을 증명하면서 차분 분석법을 공동 발견했습니다. 이 교훈은 암호학을 훌쩍 넘어서까지 적용됩니다. 자신이 만든 것을 진심으로 무너뜨리려 시도해 보기 전까지는, 무엇을 만들었는지 이해하지 못합니다. 이것은 증거의 관문을 삶의 방식으로까지 끌어올린 것입니다. “작동한다”는 것은 안전성의 증거가 아니며, “진지한 사람들이 깨뜨리려 시도했으나 그러지 못했다”는 것이 증거입니다.²⁴

공격을 견뎌 낸 것만 신뢰하기. 그저 신중하게 설계된 암호는 하나의 희망일 뿐이고, 집중적인 암호 해독을 견뎌 낸 암호는 하나의 사실입니다. 그 규율은 자신의 시스템을 공격받기 전까지는 유죄로 다루는 것 — 적이 균열을 대신 찾아 주기를 기다리는 대신, 균열이 있다고 가정하고 직접 찾아 나서는 것입니다. 이것은 톰슨의 “신뢰를 신뢰하는 것에 관한 성찰”의 암호학적 형태입니다. 적대적으로 검토해 보지 않은 것은 신뢰할 수 없다는 근본 통찰, 즉 당신을 무너뜨리는 것은 당신이 볼 수 없는 위협이라는 것 — 차분 분석법의 기밀 역사가 증명했듯 말입니다.⁴⁵

수학을 메커니즘으로 읽기. 가장 강력한 원시 요소는 새로운 수학인 경우가 드뭅니다. 그것은 새로운 각도에서 바라본 오래된 수학입니다. 다항식 보간이 비밀 공유가 되고, 소인수분해의 어려움이 트랩도어가 되며, 해시 함수가 대화형 검증자의 대역이 됩니다. 그 습관은 깔끔한 구조를 바라보며 “이것은 무엇인가?”가 아니라 “이것은 무엇을 할 수 있는가?”를 묻는 것입니다. 가장 강력한 원시 요소를 동시에 가장 단순하게 만드는 그 수단의 절약 — 최소한의 가치 있는 제품의 정신과 같은 것입니다.³⁶

얻을 수 있는 곳에서는 증명 가능한 안전성을, 그 밖의 모든 곳에서는 얻어 낸 안전성을 선호하기. 비밀 공유는 정보이론적으로 안전합니다. 아무리 강력한 컴퓨터라도 너무 적은 몫에서 비밀을 추출할 수 없습니다. 정보 자체가 거기에 없기 때문입니다.³ RSA는 계산적으로 안전합니다. 소인수분해가 어려운 채로 남아 있는 한에서만 안전한 것입니다. 샤미르는 두 수준 모두에서 일하며, 자신이 어느 쪽을 쥐고 있는지에 대해 정확합니다. 그 규율은 자신의 안전성 주장이 정확히 무엇에 기반하는지를 알고, “아직 아무도 깨지 못했다”를 결코 “깰 수 없다”와 혼동하지 않는 것입니다. 이것은 신뢰에 적용된 품질이 유일한 변수입니다. 중요한 것은 오직 그 보장이 진짜인가 하는 것뿐입니다.²³

일반적 경우 속에 숨은 특수한 경우를 의심하기. 머클-헬먼을 깨뜨린 일은, 어떤 문제가 일반적으로 NP-완전이라는 사실이 암호가 실제로 사용하는 특정 사례들에 대해서는 아무것도 말해 주지 않는다는 것을 이 분야에 가르쳐 주었습니다.¹ 그 일관된 습관은, 어려운 문제의 편리하고 구조화된 형태 — 시스템을 만들기에 충분히 쉬운 그 형태 — 가 바로 깨기에도 쉬운 형태일지 모른다고 의심하는 것입니다. 레슬리 램포트(Leslie Lamport)가 분산 시스템에 가져온 것과 같은 회의주의입니다. 당신이 가정한 속성을 신뢰하지 말고, 그것이 실제로 성립하는 정확한 조건을 찾아내십시오.

영향의 사슬

그를 빚어낸 이들

디피, 헬먼, 그리고 공개키라는 발상. RSA는 사전 공유 키 없이도 비밀을 확립할 수 있다는 휫필드 디피(Whitfield Diffie)와 마틴 헬먼(Martin Hellman)의 1976년 제안에 대한 직접적인 응답이었습니다. 디피-헬먼은 물음을 던졌고 — 공개키 암호 시스템이 존재해야 한다 — 리베스트, 샤미르, 애들먼이 최초의 실용적 답을 만들었습니다.² (직접적 영향)

론 리베스트와 레너드 애들먼. RSA 협업은 진정으로 세 손이 함께한 것이었습니다. 끊임없이 제안하는 리베스트, 끊임없이 깨뜨리는 샤미르와 애들먼. 제안하고 공격하고 되풀이하는 그 동반 관계의 적대적 구조가, 구축과 암호 해독이 하나의 분과 학문이라는 샤미르의 평생에 걸친 신념을 빚어냈습니다.² (형성적 영향)

정수론의 전통. 고전 수학을 암호학적 메커니즘으로 읽어 내는 샤미르의 전형적 행동은, 정수론과 소인수분해의 어려움, 유한체의 대수를 계산과 잇는 긴 전통에서 비롯됩니다. 그의 천재성은 그 수학의 발명이 아니라 응용에 있었습니다. (형성적 영향)

그가 빚어낸 이들

엘리 비함과 현대 암호 해독. 제자 비함과 함께 개발한 차분 분석법은, 이제 모든 진지한 블록 암호 설계자가 반드시 대비해야 하는 표준 도구가 되었습니다. 고급 암호화 표준(AES)의 설계 기준을 포함해, 암호가 만들어지는 방식 자체를 다시 빚어냈습니다.⁴⁵

공개키 생태계 전체. RSA는 수십 년간의 안전한 통신, 디지털 서명, 키 교환을 떠받쳤습니다. 브라우저가 안전한 연결을 확립하거나 인증서를 검증할 때마다, 그것은 샤미르가 놓는 데 일조한 공개키의 토대 위에 서 있습니다.²

영지식과 서명 방식. 피아트-샤미르 휴리스틱은 현대의 광범위한 디지털 서명과 영지식 증명 시스템 아래에서 일하는 일꾼이며, 여기에는 오늘날 프라이버시 보호와 블록체인 암호의 핵심이 된 것들도 포함됩니다.⁶

관통하는 줄기

샤미르는 이 시리즈의 보안 종석(keystone)입니다. 나머지 스택을 신뢰할 만하게 만드는 인물입니다. 팀 버너스리(Tim Berners-Lee)는 모두를 위한 웹을 만들었지만, 그 위에서 쇼핑하고 은행 업무를 보고 자유롭게 말할 수 있는 웹은 TLS 연결과 서명된 인증서를 위해 공개키 암호에 전적으로 의존합니다. 다시 말해, 그것은 RSA와, 샤미르가 세우는 데 일조한 분야에 의존합니다. 톰슨과 리치(Thompson and Ritchie)는 우리가 그 위에서 작동하는 시스템을 주었고, “신뢰를 신뢰하는 것에 관한 성찰”에서는 적대적으로 검토해 보지 않은 것은 신뢰할 수 없다는 근본 경고를 주었습니다. 샤미르가 한 경력을 쌓아 올린 바로 그 본능입니다. 그리고 레슬리 램포트는 분산 시스템에, 임의로 행동하는 비잔틴 적들에 맞서 정확성을 엄밀히 정의하고 증명하는 규율을 주었습니다. 샤미르의 비밀 공유는 바로 그 같은 충동의 암호학적 형태로, 희망이 아니라 증명을 갖춘 원시 요소입니다. 버너스리가 이것은 모두를 위한 것이다라고 말하고 톰슨이 당신이 만들지 않은 것은 아무것도 신뢰하지 말라고 말하는 곳에서, 샤미르는 이렇게 말합니다. 나는 당신에게 안전한 무언가를 만들어 주고, 그런 다음 평생을 그것을 깨뜨리려 애쓰며 보낼 것이다 — 그것이 우리 둘 다 그것이 진짜임을 알게 될 유일한 방법이기 때문이다. (시리즈 교량)

내가 여기서 얻는 것

샤미르에게서 내가 계속 간직하는 교훈은 공격을 견뎌 낸 것만 신뢰하라입니다. 대부분의 만드는 이들이 그렇듯, 나의 본능도 작동하는 코드를 증명으로 다루는 것입니다 — 테스트가 통과하고, 데모가 돌아가니, 내보내자. 암호학은 그런 안락함을 금합니다. 깨진 시스템과 건전한 시스템은 누군가가 공격하기 전까지는 똑같아 보이기 때문이며, 샤미르의 답은 먼저 그 누군가가 되는 것입니다. 그는 배낭 암호를 깼고, 애들먼과 함께 RSA가 살아남을 때까지 리베스트의 후보 방식들을 깼으며, 비함과 함께 DES를 정보기관이 20년간 숨겨 온 것을 폭로할 만큼 심하게 깼습니다. 그래서 이제 나는 무언가를 만들 때 — 인증 흐름, 권한 경계, 데이터 파이프라인을 — 공격자가 그러기 전에 먼저 공격자의 모자를 써 보려 합니다. 균열이 있다고 가정하고 사냥에 나서며, 누가 알려 주기를 기다리지 않습니다. 중요한 자신감은 “이것이 어떻게 깨지는지 나는 알 수 없다”가 아니라, “나는 이것을 깨뜨리려 열심히 시도했으나 그러지 못했다”입니다.

두 번째 교훈은 가장 강력한 메커니즘은 올바른 방식으로 읽어 낸 깔끔한 수학이다입니다. 처음 비밀 공유를 이해했을 때 나는 조금 무너졌습니다 — 그것은 점들이 다항식을 정한다는 그저 교과서적 사실일 뿐인데, 증명 가능하고 정보이론적으로 안전한 비밀을 내놓습니다. 샤미르는 더 어려운 수학을 발명한 것이 아닙니다. 그는 이미 자기 손에 있던 수학이, 한 각도에서 보면 바로 안전성 원시 요소임을 보았습니다. 그것이 내 앞에 이미 놓여 있는 구조들을 바라보는 방식을 바꿔 놓았습니다. 조회에 쓰는 해시는 하나의 약속(commitment)이 될 수 있고, 신뢰성을 위해 더한 중복은 임계값 방식이 될 수 있으며, 골칫거리로 여기던 제약은 자물쇠가 될 수 있습니다. 기술은 늘 새로운 무언가를 발명하는 데 있는 것이 아닙니다 — 이미 이해하고 있는 그 깔끔한 것이, 올바른 방식으로 돌려 놓으면, 당신에게 필요했던 바로 그 메커니즘임을 알아보는 데 있습니다.

자주 묻는 질문

아디 샤미르는 무엇으로 유명한가요?

아디 샤미르는 이스라엘의 암호학자이자 바이츠만 과학 연구소 교수로, RSA의 ‘S’로 가장 잘 알려져 있습니다. RSA는 그가 1977년 MIT에서 론 리베스트, 레너드 애들먼과 함께 공동 발명한 최초의 실용적 공개키 암호 시스템입니다. 세 사람은 그 업적으로 2002년 ACM 튜링상을 공동 수상했습니다. 그는 또한 샤미르 비밀 공유(1979)를 발명했고, 엘리 비함과 함께 차분 분석법을 공동 발견했으며, 피아트-샤미르 휴리스틱을 공동 창안하는 등 암호학에 수많은 공헌을 했습니다.¹²

샤미르 비밀 공유란 무엇인가요?

이는 샤미르가 1979년 “How to Share a Secret”에서 발표한 방법으로, 비밀을 n명에게 나누어 그중 임의의 k명이 모이면 복원할 수 있지만 k-1명은 아무것도 알 수 없게 하는 것입니다. 비밀은 차수가 k-1인 임의의 다항식의 상수항에 숨겨지고, 각 사람은 그 곡선 위의 점 하나씩을 받습니다. k개의 점은 차수 (k-1) 다항식 하나를 유일하게 정하므로, 임의의 k개의 몫은 비밀을 복원합니다. 반면 k개보다 적으면 비밀은 “완전히 결정되지 않은 채로” 남아, 이 방식에 정보이론적 안전성을 부여합니다.³

RSA의 ‘S’는 무엇이며, RSA는 어떻게 작동하나요?

‘S’는 샤미르입니다. RSA는 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)을 뜻합니다. RSA는 공개키 암호 시스템입니다. 각 사용자는 누구나 자신에게 메시지를 암호화하거나 자신의 서명을 검증하는 데 쓸 수 있는 공개키와, 자신만 쥐고 있는 개인키를 가집니다. 그 안전성은 트랩도어에 기반합니다. 공개키는 두 개의 큰 소수의 곱으로 만들어지고, 개인키를 복원하려면 그 곱을 다시 소수들로 소인수분해해야 하는데, 충분히 큰 수에 대해서는 이것이 계산적으로 불가능합니다. RSA는 1978년 Communications of the ACM에 발표되었습니다.²

차분 분석법이란 무엇인가요?

차분 분석법은 1980년대 후반 엘리 비함과 아디 샤미르가 공개적으로 발견한 일반적 기법으로, 한 쌍의 입력 사이의 차이가 어떻게 출력의 차이로 전파되는지를 연구하여 블록 암호를 공격하는 방법입니다. 그 전파에서 나타나는 통계적 편향은 비밀 키에 관한 정보를 누설할 수 있으며, 비함과 샤미르는 이를 사용해 DES에서 이론적 약점을 찾아냈습니다. 훗날 IBM과 NSA가 1970년대 중반부터 이 기법을 알고 있었고, DES를 그것에 저항하도록 비밀리에 설계해 두었으면서도 기밀로 유지해 왔던 것으로 드러났습니다.⁴⁵

출처