We rely on secrets such as safe combinations, PIN codes, computer passwords, etc.
Unfortunately, secrets can be lost: documents get destroyed, hard disks fail, people forget, people leave companies, people die...
The trouble and losses caused to others if one is not in a position to retrieve some secrets can be huge.
One way to avoid such problems is to share the secret by generating n "shares" (looking like "0303318D0E63BC8AB0D4B7") in such a way that the secret can only be retrieved if k of them are available. Individual shares give strictly no information at all about the secret. Even k-1 shares give strictly no information at all about the secret.
This approach is much more secure than storing the secret at multiple places or giving parts of it to several persons.
Such a method is called a (k, n) threshold scheme. One of them was proposed by Adi Shamir of the Massachusetts Institute of Technology in his paper How to Share a Secret.
Shamir gives the following example: "If we give the president of a company three shares, each vice-president two shares, and each executive one share, then a (3, n) threshold scheme enables checks to be signed either by any three executives, or by any two executives one of whom is a vice-president, or by the president alone."
In a family with two parents and three children, the secret combination of the personal burglary safe could be shared with a (6, n) threshold: 6 shares for each parent, 2 shares for each child, 1 share for 3 family friends. This would allow each parent to know the combination, or all 3 children together, or 2 children with 2 friends, etc.
More information can be found on
Here is a free implementation of Shamir's method, that can run
The robustness of programs using cryptography and the related fields must reside in the keys and the algorithms, not in unpublished implementation tricks. More, implementation glitches can ruin demonstrated algorithms. Therefore, here are the details of this implementation so that one can (in)validate its robustness.
At the present time, the program implements strictly the Shamir's method. Some authors have proposed improvements, in particular by using variations that allow to detect individual invalid shares. One of them is Martin Tompa in How to Share a Secret with Cheaters.
In order to maintain the compatibility of the shares generated with the current version of ShareSecret and future ones that may provide such improvements, this byte is used as a "flag".
Currently, its Least Significant Bit is set to 0, meaning "no cheaters detection". It will be set to 1 when/if such a detection is implemented and the corresponding option is selected. The others bits are random. This means that this value is currently a random even number.
Here is the Scilab prototype used to get the maths right.
Then you can install the AIR version of ShareSecret.