Shamir Secret Sharing

지갑은 비트코인을 받고 보내는 앱이나 기기입니다. 안나는 기록 일부를 잃어도 복구할 수 있는 백업을 원합니다. 다섯 개 중 세 개를 선택하면 서로 다른 조각 다섯 개가 생성되고, 같은 묶음의 유효한 조각 세 개만 있으면 어떤 조합이든 비밀을 복원합니다. 두 개는 잃어도 되지만 세 개는 안 됩니다. 필요한 개수를 임계값이라고 합니다. 일반적으로 n개 중 k개가 필요하다면 n−k개를 잃어도 됩니다. 그러나 임계값은 안나의 동의를 확인하지 않습니다. 다른 사람이 세 개를 확보하거나 보관자들이 협력해도 같은 비밀을 복구합니다. 임계값을 낮추면 복구는 쉬워지지만 안나 없이 복구할 수 있는 집단도 작아집니다. [1] [6]

다섯 파일을 하나의 클라우드 계정에 저장하면 효과가 크지 않습니다. 그 계정을 잃거나 탈취당하면 모두가 한꺼번에 영향을 받습니다. 백업에는 적절한 분산 보관, 사용한 방식과 매개변수 기록, 신뢰할 수 있는 기기에서의 복구 확인이 필요합니다. 상속인도 이용할 계획이라면 무엇을 찾아 어떻게 안전하게 다뤄야 하는지 알아야 합니다. 같은 비밀 S를 새로운 난수로 다시 나누면 새 묶음이 생기며, 이전 조각과 새 조각을 섞지 않습니다. 하지만 충분한 이전 조각도 여전히 S를 복원합니다. 다시 나누는 것만으로 이미 유출된 유효한 백업을 무효화하거나 비밀 자체를 바꾸지는 못합니다. [1] [4]

일반적인 복구에서는 비밀 전체가 한 기기에 다시 모입니다. 기기가 침해되었다면 공격자는 바로 그때 비밀을 얻을 수 있습니다. 비밀이 Private Key, 즉 자금 지출을 승인하는 디지털 서명을 만드는 비밀 숫자 값이라면, 이를 얻은 사람은 이후 조각을 다시 모으지 않고 서명할 수 있습니다. 반면 Multisig는 해당 지출 조건에 따라 여러 서명을 요구합니다. 임계값 서명도 있습니다. 여러 참여자가 안전하게 함께 계산하는 추가 MPC 프로토콜을 사용하면, 전체 키를 조립하지 않고도 조각으로 서명을 만들 수 있습니다. NIST는 이런 경우를 구분합니다. 샤미르 조각 하나만으로 이러한 서명 프로토콜까지 갖추어지는 것은 아닙니다. [3] [5] [6]

이름에 Shamir가 들어가는 두 프로그램이 서로의 조각을 읽을 수 있다는 보장은 없습니다. 수학 연산, 값의 인코딩, 조각 식별자와 묶음 소속이 맞아야 합니다. SLIP-39는 이 방법을 기반으로 만든 구체적인 표준입니다. 조각을 기록할 단어 목록, 보조 정보인 메타데이터, 그룹, 암호화와 오류 검사를 추가합니다. 따라서 일반 원리는 기존 Seed Phrase를 손으로 나누라는 지침이 아닙니다. 지갑을 그 백업에 맡기기 전에 지원 형식을 알고, 계획한 절차로 실제로 복구되는지 확인해야 합니다. [2]

다섯 개 중 세 개 방식에서 두 개를 잃으면 어떻게 되는지는 분명합니다. 하지만 손상되거나 위조된 조각은 기본 계산이 개수 부족을 알리는 대신 다른 비밀을 반환하게 할 수 있습니다. 방법 자체는 조각의 출처나 만든 사람의 정직성을 증명하지 않습니다. 오류 검출과 수정, 그리고 분산 과정이 올바른지 확인하는 verifiable secret sharing은 각자의 전제가 있는 추가 장치입니다. 예를 들어 SLIP-39는 체크섬과 digest라는 검증값을 추가합니다. 모든 Shamir Secret Sharing 앱이 같은 검사를 제공한다는 뜻은 아니며, 체크섬이 맞는다고 백업의 출처가 믿을 만하다는 증거도 되지 않습니다. [2] [5]

이상적인 방식에서는 완전한 조각이 k개보다 적으면, 계산 능력이 무한해도 공격자가 S에 관한 새 정보를 얻지 못합니다. 각 조각에서 원래 단어의 삼분의 일을 그대로 읽을 수 있는 것은 아닙니다. 다만 분산에 쓰는 수를 독립적이고 동일한 확률로 뽑는 올바른 무작위성이 필요합니다. 예측 가능한 수, 수의 재사용, 기기 메모리 유출이 있으면 상황이 달라집니다. SLIP-39의 digest 같은 추가 검증 데이터도 따로 평가해야 합니다. 그리고 원래 비밀번호가 약하다면, 백업을 나눴다고 다른 방법으로 추측할 가능성까지 사라지지는 않습니다. [1] [2]

작은 비밀 S=5와 규칙 f(x)=5+3*x mod 17을 생각해 봅시다. mod 17은 17로 나눈 나머지를 취한다는 뜻입니다. 조각 세 개는 (1,8), (2,11), (3,14)입니다. 첫 수는 위치, 둘째 수는 계산한 값입니다. 앞의 두 점에서 증가량 3을 얻고, 원래 비밀을 8−3=5로 구할 수 있습니다. 가능한 세 쌍 중 어느 것을 골라도 같은 비밀을 복원합니다. 반면 점 (1,8) 하나만으로는 증가량을 a=8−S mod 17로 정하면 0부터 16까지 모든 S가 가능합니다. 작은 수를 쓴 이 계산은 설명용이며 실제 지갑의 백업 설계가 아닙니다. [1]

일반식은 f(x)=S+a1*x+…+a(k−1)*x^(k−1)입니다. 이런 식을 다항식이라고 합니다. S는 비밀이고 나머지 계수는 유한체에서 독립적이고 균등하게 무작위로 고른 원소입니다. 유한체는 덧셈과 곱셈 규칙이 정확히 정해진 수학적 환경입니다. 조각은 (x,f(x))이며 각 x는 서로 다르고 영이 아니어야 합니다. x=0이면 S가 바로 드러나기 때문입니다. k개 점에서 라그랑주 보간으로 비밀인 f(0)을 계산합니다. 같은 점을 두 번 복사해도 정보가 늘지는 않습니다. 소체 GF(p)에서는 보통의 나눗셈 대신, 제수와 곱하면 1이 되는 모듈러 역원을 곱합니다. 또한 GF(256) 연산은 단순히 256으로 나눈 나머지를 구하는 것과 다릅니다. 두 연산을 혼동하면 안 됩니다. [1]