The DataGenetics Blog has posted Sharing Secrets and Distributing Passwords, an excellent break down of Shamir’s Algorithm, an algorithm implementing several ideal properties for distributing a secret as a number of parts:
- Knowledge of any non-complete combination of sub-passwords gives an attacker no additional information on how to solve the problem. Even if you have knowledge of
n-1passwords, there are still an infinite number of curves that fit through these points, and thus an infinite number of possible intercepts.
- As we can clearly see, it’s very easy to generate new sub-passwords as needed. If we need to generate and distribute a new sub-password, we simply pull off another coordinate from the curve and give that out! None of the existing passwords need to change.
- If some of the sub-passwords are compromised (and you know which ones) and you want to regenerate new ones, but keep the uncompromised ones the same, you can generate a new curve that passes through the points you wish to keep. [Edit - Only if the the number of uncompromised points is two (or more) less than the minimum number needed to reconstruct the secret. Thanks for the correction @N1DQ]
- To weight passwords (such as giving The President a nuclear launch password with three times the power of a regular password), we simply give out multiple coordinates to that person. Thus, for the nuclear launch example requiring requiring five votes, we generate an order-4 polynomial, give The President three coordinates from the curve, The Secretary of Defence two coordinates off the curve, and the rest of the troops one coordinate each.