Shamir의 비밀 공유 작동 방식

2 days ago 4

Shamir 비밀 공유는 비밀을 여러 조각으로 나누고, 임계값 이상이 모일 때만 복구되며 그보다 적으면 아무 정보도 드러나지 않음
회사 마스터 키, 가족 계정 복구, 팀 백업처럼 한 사람에게 전체 비밀을 맡기기 어렵고 일부 조각 손실에도 복구가 필요할 때 유용함
핵심 모델은 비밀을 다항식의 0 지점 값으로 숨기고, 각 조각을 곡선 위의 점 하나로 나눠 주는 방식임
임계값 k에는 차수 k - 1의 다항식을 쓰며, 두 조각은 직선, 세 조각은 포물선, 네 조각은 3차 곡선에 해당함
Ente Legacy Kit는 이 방식을 한 계층으로 사용해 카드가 영구 복구 키가 되지 않게 하고, 발급된 카드를 폐기 가능하게 만듦

비밀을 점과 다항식으로 나누는 방식

Adi Shamir가 1979년에 발표한 방식이며, 핵심은 단순히 “깨기 어렵다”가 아니라 필요한 조각 수가 부족하면 정보가 전혀 드러나지 않는다는 데 있음
서로 다른 두 점은 정확히 하나의 직선을 결정하지만, 한 점만 있으면 그 점을 지나는 직선은 무한히 많고 각 직선은 세로축과 다른 위치에서 만남
비밀이 숫자 7이라면, 직선이 세로축과 만나는 위치에 이 값을 숨길 수 있음
기울기는 비밀 자체가 아니라 비밀을 숨기기 위한 무작위성 역할을 함
각 사람에게 직선 위의 점 하나를 나눠주면, 한 사람의 점 하나만으로는 가능한 직선이 무한히 많아 서로 다른 비밀과 모두 호환됨
두 점을 합치면 직선이 고정되고, 그 직선이 0에서 갖는 값을 읽어 비밀을 복구할 수 있음
이 구조는 2-of-n 비밀 공유 방식이며, 점은 원하는 만큼 만들 수 있지만 임의의 두 점이면 직선을 복구할 수 있음
임계값이 커지면 더 높은 차수의 곡선을 사용함
- 포물선은 세 점이 있어야 결정되므로, 비밀을 포물선이 세로축과 만나는 위치에 숨기면 임의의 세 조각으로 복구 가능하고 두 조각으로는 복구할 수 없음
- 일반적으로 임계값 k에는 차수 k - 1의 다항식을 사용함
- 2개 조각은 직선, 3개 조각은 포물선, 4개 조각은 3차 곡선에 해당함
- 실제 구현은 그래프 종이가 아니라 유한체 산술을 사용하지만, 비밀은 0에서의 값이고 무작위 계수들이 이를 숨기며 각 조각은 다항식 위의 한 점이라는 구조는 같음
- 조각이 부족하면 비밀 계산이 어려운 정도가 아니라, 모든 가능한 비밀이 여전히 가능한 상태로 남는다는 점이 중요함