샤미르 비밀 분산 계산기

차수가 k−1인 다항식은 점 k개로 정확히 하나 정해진다는 성질을 씁니다. 비밀을 상수항에 두고 나머지 계수를 아무렇게나 뽑아 다항식을 만든 뒤, (1, f(1)), (2, f(2)) …를 조각으로 나눠 줍니다. k개가 모이면 라그랑주 보간으로 다항식을 되살려 f(0)을 읽으면 그것이 비밀입니다.

아무것도 알 수 없습니다. 절반쯤 풀리거나 후보가 좁혀지는 것이 아닙니다. 비밀 후보를 아무거나 잡아도 그 후보를 설명하는 다항식이 정확히 하나 있으므로 모든 후보가 똑같이 그럴듯합니다. 조각을 하나도 못 가진 사람과 정확히 같은 처지입니다.

계산이 어려워서 못 푸는 것이 아니라 정보가 아예 없어서 못 푼다는 뜻입니다. RSA는 큰 수를 소인수분해하기 어렵다는 가정 위에 서 있어서 계산력이 충분히 늘면 뚫리지만, 샤미르 비밀 분산은 k−1개로는 어떤 계산으로도 비밀을 좁힐 수 없습니다. 대신 k개가 모이는 순간 완전히 풀리므로 「절반쯤 아는」 상태가 없습니다.

실수로 보간하면 두 가지가 무너지기 때문입니다. 첫째로 부동소수점 오차 때문에 답이 정확히 떨어지지 않고, 둘째로 더 나쁘게는 정보가 샙니다 — 실수 위에서는 조각 몇 개만 봐도 다항식이 대충 어느 근방인지 알 수 있어 비밀의 범위가 좁혀집니다. 나머지만 다루면 값이 0부터 p−1까지 고르게 흩어져 그런 실마리가 남지 않습니다.

비밀보다 커야 합니다. 작으면 비밀이 소수로 나눈 나머지로 접혀 원래 값을 잃습니다. 한 바이트를 나눌 때는 257, 두 바이트면 65537을 흔히 쓰고, 실제 구현은 훨씬 큰 소수나 GF(2^8) 같은 이진 체를 씁니다. 조각의 크기가 비밀과 비슷해지므로 소수를 필요 이상으로 크게 잡을 이유는 없습니다.

쓰지 마십시오. 이 계산기는 난수를 씨앗값으로 뽑아 같은 결과를 다시 낼 수 있게 해 두었는데, 계산기로서는 필요하지만 암호로서는 치명적입니다 — 씨앗을 아는 사람은 조각 하나만으로 전부 풀 수 있습니다. 무엇이 일어나는지 눈으로 보려는 데모이며, 실제로는 검증된 구현을 쓰십시오.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.