Sharmir’s Secret Sharing (SSS): Triple S에 숨겨진 암호학 살펴보기
김인근 | ingeun92@naver.com | CURG
옛날, 필자의 모든 시간을 만화책 보기에 쏟아붓게 한 만화가 있었다. 사실 이름만 들으면 누구나 알 수 있는 “드래곤볼” 이라는 만화이다. 이 만화에는 한 가지 큰 규칙이 존재하는데, 7개로 나뉘어진 드래곤볼을 모두 모으면 용신이 나타나 소원을 들어준다는 것이다. 결국 7개를 다 모으지 못하면 용신은 나타나지 않고 소원도 들어주지 않는다.(참고로, 이 같은 설정은 TV프로그램인 신서유기에서도 똑같이 차용하고 있다.)
그렇다면 만약 현대시대에 갑자기 용신이 찾아와 소원을 들어주는 드래곤볼을 만들어 달라고 하면 만들 수 있을까? 이 글에서는 이 물음에 대한 목표로 Sharmir’s Secret Sharing (이하 SSS)를 알아볼 예정이다.
SSS는 Shamir’s (k, n) Threshold scheme이라고도 하며 일종의 독점을 방지하기 위한 비밀 공유 방식으로 1979년에 발표된 알고리즘이다. SSS처럼 독점을 방지하고 비밀을 공유하기 위해서는 두 가지 조건을 가지고 있는데 그 조건은 아래와 같다.
- 하나의 Secret을 여러 조각으로 나누어 분산시켜 저장한다. (Shares)
- 원래의 Secret을 복원하기 위해서는 반드시 일정한 수 이상의 Share가 필요하다. (Threshold)
SSS는 “x축 좌표값이 서로 다른 t개의 점을 지나는 x의 t-1차 다항식은 유일하게 결정된다”는 사실을 이용하여 위의 조건을 만족하면서 시간과 공간의 소모를 줄이는 획기적인 방식을 제시했다.
위의 말을 이해하기 위해 사전 지식을 짚고 넘어가보자. 정확히 중학교 2학년 수학시간으로 돌아가면 된다. 우리는 저 당시 연립방정식이라는 것을 배운다. 연립방정식은 방정식의 일종으로 2개 이상의 미지수를 포함하는 방정식이다. 이 연립방정식에서 미지수의 값을 구하는 방법은 소거법을 통해 식을 간편화하여 해를 구하게 된다. 그러나 해를 구하는 방법인 소거법을 배우기 전에 우리는 자칫 넘어갈 수 있는 중요한 개념을 하나 먼저 배운다. 그것은 구해야 할 미지수의 개수가 n개일 경우 연립방정식의 개수가 n개 이상이어야 한다는 것이다.
이것을 좀 더 확장해보자. 그렇다면 2차 다항식 f(x) = ax²+bx+c의 계수와 상수를 모두 구해서 원래의 2차 다항식을 찾으려면 어떤 것들이 필요할까? 여기서는 구해야 할 계수와 상수가 a, b, c로 3개이기 때문에 연립방정식이 3개가 필요하다. 따라서, 연립방정식을 3개 만들기 위해서 f(x)에 대응하는 최소 3개의 점인 (x_1, f(x_1)), (x_2, f(x_2)), (x_3, f(x_3))이 필요하다.
마지막으로 이것을 일반화 시키게 되면 “n차 다항식의 계수와 상수를 모두 알아내려면 n+1개의 점이 필요하다” 가 된다.
SSS에서는 이 특징을 이용해서 Shares와 Threshold 조건을 만족한다. 우선 이 조건들을 만족하기 위해서는 “Secret S를 n개의 share로 나누고 k개의 share가 모이면 S를 알아낼 수 있다”를 만족해야 한다. 이것을 변형하면 “S를 n개의 ‘점’으로 나누고 k개의 ‘점’을 이용하면 S를 알아낼 수 있다”로 변형할 수 있다. 이것은 다시금 “상수항을 S로 가지는 임의의 k-1차 다항식을 생성하게 되면 k개의 점을 이용해서 상수 S를 구할 수 있다”로 바뀔 수 있다.
이제부터 SSS가 어떻게 동작하는지 살펴보도록 하자.
- Secret S를 n개의 share로 나눈다.
상수항을 S로 가지는 임의의 k-1차 다항식을 생성하게 되면 k개의 점을 이용해서 상수 S를 구할 수 있다는 전제를 이용해 k-1차 다항식을 생성한다. 그 다음, k-1개의 계수 {a_1, a_2, … ,a_(k-1)} 를 무작위로 선택한다. 이 다항식의 상수항은 Secret인 S이다. 따라서, 원래의 다항식이 제대로 복구된다면 f(0) = S를 이용해 Secret을 다시 찾을 수 있다. 그리고 이 k-1차 다항식의 점을 n개 선택한다. k-1차 다항식을 다시 복구하기 위해서는 최소 k개의 점이 필요하기 때문에 n ≥ k 이어야 한다.
- k개의 share를 모아서 Secret S를 복원한다.
선택한 n개의 share 중에서 k개 이상이 모였을 때 복구가 되야한다. share의 집합에서 k개의 share를 {(x_0, y_0), (x_1, y_1), … ,(x_(k-1), y_(k-1))}이라고 하자. 구하고자 하는 다항식은 아래와 같고 여기에 k개의 share 점을 대입한 k개의 방정식들로 연립방정식을 구성하여 g(x)를 구하고 g(0)을 통해 S를 복원한다. g(x)를 구할 때는 라그랑주 보간법(Lagrange interpolation)을 이용한다.(여기 글에서는 라그랑주 보간법까지 설명하기엔 글이 너무 길어질 것 같아 이에 대해 설명하지 않고 설명에 대한 링크를 남겨놓는다.)
간단한 예시를 들어보자.
S = 777이고 n=4이며 k=3일 때 S의 복원이 가능하도록 SSS를 만드는 방식은 아래와 같다.
- k-1개(=2개)의 숫자 {a_1, a_2}를 무작위로 선택한다.
- k-1차(=2차) 다항식을 생성한다.
- 다항식 f(x)로부터 n=4개의 점(share)을 선택한다. ((0, 777)은 S이므로 제외)
- n=4개의 share 중 k=3개의 share를 가지고 g(x)의 계수와 상수를 유추하고 g(0)을 통해 S를 복원한다.
여기까지 SSS의 원리와 작동 방식에 대해 알아보았다. 그렇다면 이제 이 글의 처음에 나왔던 물음에 답을 할 차례이다. 눈치가 빠른 분들은 아시겠지만, SSS를 통해 우리는 드래곤볼을 만들 수 있다.
Secret S가 용신이 소원을 들어주는 티켓 넘버라고 하고 드래곤볼의 원래 설정과 같게 7개의 드래곤볼이 모여야 소원을 빌 수 있다고 한다면, n=7 & k=7인 SSS를 만들면 드래곤볼을 만들 수 있다. 더 자세히 보면 6차 다항식 f(x)를 생성하고 이 다항식에서 7개의 점을 선택한 후 이 7개의 점의 정보로 라그랑주 보간법을 통해 g(x)를 생성한다. 마지막으로 g(0) = S로 Secret S를 복원하여 용신에게 S의 티켓 넘버를 넘기면 소원을 빌 수 있는 것이다. 결국, 드래곤볼 7개를 모두 모아야 소원을 빌 수 있는 현대판 드래곤볼 시스템을 완성할 수 있는 것이다.
이 같은 SSS의 특성은 블록체인 내에서도 여러 방면으로 사용이 가능하다.
private key를 잃어버리면 해당 계정의 모든 소유권이 사라지는 블록체인 환경에서 private key의 복구를 위해 복구키를 여러 개로 나누어 보관하고 복구 가능하도록 하는 key 관리 차원으로 사용이 가능하다. 또한, 하나의 계정에 대해 혹은 자금에 대해 공동의 책임을 부여하고 싶을 때에도 사용이 가능하다. 그리고 블록체인 내에서 민주적인 과정을 거쳐서 어떠한 하나의 프로토콜을 결정하거나 행동을 결정할 때에도 유권자의 수만큼 share를 나누고 과반수나 정해진 수의 유권자가 모였을 때 비로소 유효성이 발현되는 식으로 SSS를 사용할 수도 있다.
이번 글에서는 SSS에 대해 알아보았는데, 필자도 글을 쓰면서 이 방식을 적절히 사용할 수 있는 여러가지 응용이 계속해서 떠오르는 굉장히 좋은 알고리즘이라고 생각한다. 특히, 민주적인 의사결정 단계에서 충분히 사용할 수 있다는 점에서 우리 사회의 의사결정 속도를 높여주고 갈등을 줄여줄 수 있는 수학적인 방법이 될 수 있지 않을까 라는 생각을 하며 이 글을 마치도록 하겠다.
참고 문헌
[1] How to share a secret | Adi Shamir | Communication of the ACM | 1979. 11. | https://dl.acm.org/doi/10.1145/359168.359176
[2] https://medium.com/codechain-kr/secret-sharing-비밀-공유하기-356fd756323a
[3] https://owljoa.postype.com/post/1546184
