<< PasswordMaker | index | Calibration images >>

Shamir's "How to share a Secret"

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

Type your secret and click 'Calculate':

View the "lean" version of this page with details removed

How do I use ShareSecret ?

To share your secret

  1. Determine how many shares will be required to recover your secret ('Quorum', or k))
  2. Determine how many shares you need in total (n)
  3. Go to http://www.christophedavid.org/w/c/w.php/Calculators/ShamirSecretSharing, or use the stand-alone version
  4. Select the tab 'Generate Shares'
  5. Select the number of shares
  6. Select the Quorum (k)
  7. Type you secret
  8. Click 'Calculate'
  9. Each line in the 'shares' box is one share
  10. Copy/Paste the shares to distribute them. Make sure they are stored in safe places.

To recover your secret

  1. Obtain k shares
  2. Go to http://www.christophedavid.org/w/c/w.php/Calculators/ShamirSecretSharing, or use the stand-alone version
  3. Select the tab 'Calculate Secret from Shares'
  4. Type the shares, one per line
  5. Click 'Calculate'
  6. Read the secret

Implementation details

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.

  • The program is written using Adobe Flex.
    • All calculations are performed locally on the user computer by the Adobe Flash Player
    • Strictly no information about the secret or the shares is transmitted over the internet
  • The random bytes used are produced using the following method
    1. The internal random generator provided by the framework is used to generate a real number, which is converted to a string
    2. This string is concatenated with a string representation of the current time
    3. The SHA256 digest of this string is calculated
    4. All bytes of this digest are XORed
    5. The resulting value is used as the random byte
  • The symbols used below refer to the ones in How to Share a Secret
    • n must be more than 1 and less than 256
    • k must be more than 1 and less than n + 1
    • p = 257
  • These choices imply that all resulting values are from 0 to 256
  • The shares are the concatenation of the hexadecimal representation of these values (two characters per value), with one exception for 256, which is represented as 'G0'.
  • All calculations are based on the ASCII value of the secret bytes
  • Each byte of the secret is processed totally independently from the others, with different random values for a0, a1, a2, ...
  • Only printable characters having an ASCII code less than 128 are allowed in order to avoid any characters sets related issues

Shares structure:

  • The first value is x, which can also be considered as the share number
    • 01033ED38FFE2E2F57CDE8BB
    • 0203B095FF8FC8FEB41FF694
    • 03030494C8D51FD0796A8FG0
    • 040316D0EBCF35A6A7ADB4FE
    • 05038848677D09803DE8648E
  • The second value is k (the quorum)
    • 01033ED38FFE2E2F57CDE8BB
    • 0203B095FF8FC8FEB41FF694
    • 03030494C8D51FD0796A8FG0
    • 040316D0EBCF35A6A7ADB4FE
    • 05038848677D09803DE8648E
  • The third value is reserved. See below.
    • 01033ED38FFE2E2F57CDE8BB
    • 0203B095FF8FC8FEB41FF694
    • 03030494C8D51FD0796A8FG0
    • 040316D0EBCF35A6A7ADB4FE
    • 05038848677D09803DE8648E
  • The remaining values are the Di, one value (two characters) for each character of the secret
    • 01033ED38FFE2E2F57CDE8BB
    • 0203B095FF8FC8FEB41FF694
    • 03030494C8D51FD0796A8FG0
    • 040316D0EBCF35A6A7ADB4FE
    • 05038848677D09803DE8648E

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.

Availability:

  • It is my intention to keep allowing free usage of ShareSecret on this website.
  • However, should this website not be available for any reason, you will still be able to recover your secret using the stand-alone version (which you should definitely download while the site is still there...)
  • ShareSecret is freeware, provided as-is, and as such comes with no guarantees or support.

Stand-alone version:

  • Here is a cross-operating system version using Adobe AIR, available for Windows, Mac OS X and Linux. You need to install the Adobe AIR runtime.

Then you can install the AIR version of ShareSecret.

Known issues:

  • None

Road map:

  • Cheaters detection option
printer friendly view
PDF 

   

      

             
             Google
          
          
             
             
             
          
      

      

          
         
            

               

                  
                     
                     Web
                  
                  
                     
                     www.christophedavid.org