Shamir's Secret Sharing 이해하기: 신뢰의 수학

보안의 세계에서 우리는 종종 역설에 직면합니다. 어떤 비밀은 단 한 명의 개인에게 맡기기에는 너무나 중요하며, 동시에 그 사람이 부재할 경우를 대비해 잃어버려서는 안 될 만큼 중요합니다. 여러 관리자의 승인이 필요한 기업의 마스터 키든, 디지털 자산에 대한 가족 복구 계획이든, 기술 팀을 위한 분산 백업 시스템이든, "threshold-based" 신뢰 시스템의 필요성은 보편적입니다.

RSA 알고리즘의 설계자 중 한 명인 Adi Shamir는 1979년에 이 문제를 해결했습니다. 그는 비밀을 여러 조각(shares)으로 나누는 방법을 개발했는데, 이는 최소한의 개수가 모여야 비밀을 재구성할 수 있으며, 그 임계값(threshold) 미만의 개수로는 원래 데이터에 대해 그 어떤 것도 알 수 없도록 설계되었습니다.

기하학적 직관: 두 점은 하나의 직선을 결정한다

Shamir's Secret Sharing (SSS)이 어떻게 작동하는지 이해하기 위해, 기하학의 기본 원리인 "두 개의 서로 다른 점은 정확히 하나의 직선을 결정한다"는 원리에서 시작할 수 있습니다.

비밀이 예를 들어 숫자 7이라고 가정해 봅시다. 이 비밀을 숨기기 위해, 그래프의 세로축(y-intercept)에 이 숫자를 배치합니다. 그런 다음 그 점을 지나는 무작위 직선을 그립니다. 직선의 기울기는 무작위로 선택됩니다. 이 무작위성이 바로 비밀을 숨기는 역할을 합니다.

만약 이 직선 위의 한 점을 한 사람에게 준다면, 그 사람은 비밀을 알아낼 수 없습니다. 하나의 점만으로는 무수히 많은 직선이 그 점을 지날 수 있으며, 각 직선은 y축과 서로 다른 값에서 만납납니다. 단일 share를 보유한 사람에게는 모든 가능한 비밀이 똑같이 가능성이 높습니다.

하지만 두 사람이 그들의 점을 결합하는 순간, 직선은 고정됩니다. 두 점이 있으면 가능한 직선은 단 하나뿐이며, 비밀은 그 직선이 y축과 교차하는 지점에서 정확히 읽을 수 있습니다. 이것은 2-of-n 비밀 공유 방식입니다. 점을 원하는 만큼 배포할 수 있지만, 어떤 두 점만으로도 복구가 가능합니다.

임계값 확장하기: "곡선" 추가하기

복구에 필요한 share의 개수를 늘리려면, 단순히 곡선의 복잡성을 높이면 됩니다. 직선(1차 다항식)은 두 점을 필요로 하지만, parabola(2차 다항식)은 고유하게 결정되기 위해 세 점을 필요로 합니다.

일반적으로, $k$개의 share가 필요한 임계값은 $k-1$차 다항식을 필요로 합니다:

2 shares: 직선 (1차)
3 shares: parabola (2차)
4 shares: cubic curve (3차)

실제 구현에서는 이러한 것들을 그래프 용지에 그리는 것이 아니라 finite-field arithmetic을 사용하여 계산합니다. 이는 share들이 정수 상태를 유지하도록 보장하며, 공격자가 근사치나 반올림을 사용하여 비밀을 추측하는 것을 방지합니다. 핵심 속성은 동일합니다: 임계값 $k$에 도달하지 못하면, 비밀은 단순히 "찾기 어려운" 것이 아니라 수학적으로 보이지 않는 상태가 됩니다.

실무 적용 및 구현

Shamir's Secret Sharing은 단순한 이론적 호기심을 넘어, 단일 장애점(single points of failure)을 제거하기 위해 높은 이해관계가 걸린 환경에서 사용됩니다.

분산 키 관리

private key를 위해 3-of-5 스키마를 사용하는 Bitcoin 커뮤니티부터, 보조 비밀 저장소의 passphrase를 배포하는 팀들까지, SSS는 접근에 대한 "민주적이고 안전한" 접근 방식을 가능하게 합니다. 커뮤니티의 실무자들에 따르면, 이 기술은 조직이 특정 개인에게 전체 키를 "진정으로" 넘겨주지 않고도 접근 권한을 부여할 수 있게 해줍니다.

강화된 복구 흐름

Ente는 자신들의 "Legacy Kit" 내에서 SSS를 활용합니다. share들을 영구적인 복구 키로 사용하는 대신, 이들은 SSS를 더 큰 흐름의 한 단계로 사용합니다. share들은 로컬에서 별도의 비밀을 재구성합니다. 그 후 이 비밀은 서버 매개 복구 프로세스에 참여합니다. 이 아키텍처를 통해 발급된 카드를 취소할 수 있어, 분실된 share가 영구적인 보안 위협이 될 수 없도록 보장합니다.

기술적 고려 사항 및 트레이드오프

SSS는 강력하지만, 대규모로 구현할 때 특정 기술적 과제제가 따릅니다:

대규모 비밀 처리

비밀이 다항식의 단일 좌표로 쓰기에 너무 크다면, 먼저 페이로드를 암호화하는 것이 일반적인 관례입니다. 그 결과로 나온 암호화 키를 SSS를 사용하여 나누고, 그 키의 share들을 암호된 페이로드와 함께 배포합니다.

SSS vs. Erasure Coding

일부 개발자들은 SSS를 Reed-Solomon이나 PAR2와 같은 시스템과 비교합니다. 둘 다 데이터를 나누는 것을 포함하지만, 보안 측면에서 결정적인 차점이 있습니다. Reed-Solomon은 주로 중복성(erasure coding)을을 위한 것이며, SSS는 information-theoretic security를 제공합니다. 한 커뮤니티 기여자가 다음과 같이 지적했습니다:

"Shamir의 방식은 [Reed-Solomon과 달리] information-theoretic security를 잃게 된다는 점이 다릅니다... 페이로드는 또한 all-or-nothing-transform (AONT)을 거쳐야 합니다. 왜냐하면 Reed-Solomon은 조각각이 정보를 누설할 수 있는 병리적 사례가 존재하기 때문입니다."

양자 위협

양자 컴퓨팅이 발전함에 따라, share size와 share의 장기적 생안성(viability)에 대한 질문이 다음과 같이 제합니다기. SSS는 RSA와 같이 큰 소수의 인수분해의 어려움에 기반하기보다는 다항식 보간법(polynomial interpolation)에나 기반히기 때문에, finite field의 선택과 키 길이 대비 share의 크기는 미래 지향적인 암호화 시스템을 구축하는 데 있어 중요한 고려 사항입니다.

요약

Shamir's Secret Sharing이 어떻게 다항식 보간법을 사용하여 비밀을 share로 나누는지, 그리고 특정 임계값 이상의 참여자만이 원래 데이터를 복구할 수 있도록 보장하는지에 대한 탐구입니다.