Implementation of Shamir's method for sharing a secret

The two perl scripts shares.pl and reconstruct.pl implement Shamir's algorithm for key sharing described in
A. Shamir,
How to Share a Secret,
Comm. ACM 22, 612–613 (1979).
This is useful for encrypting backup tapes. The encryption key for the backup needs to be on the computer doing the backups. However it also needs to be stored in another location in case of a disk failure on that computer. However merely writing the key onto a floppy disk is dangerous in case the floppy disk falls into the wrong hands (or is lost!).

Shamir's method allow the key to be split into N pieces in such a way that any K piece suffice to reconstruct the key but knowledge of only K − 1 pieces yields no information on the key.

This implementation was written by Charles Karney in 2001 and is licensed under the GPL. For more information, see http://charles.karney.info/misc/secret.html.

In this implementation we require 0 < K ≤ N ≤ 256. Here's how this might work with (K,N) = (3,5)

  1. generate a printable secret key (in this example, 36 × 8 = 288 bits or 36 × 8/6 = 48 characters)
    cp /dev/null SECRET
    chmod 600 SECRET
    dd if=/dev/random bs=1 count=36 2>/dev/null | base64-encode >> SECRET
    base64-encode converts binary data to printable form. If it's not available use some other procedure for accomplishing this.
  2. Split the key up into N = 5 pieces
    cat SECRET | ./shares.pl 3 5
    This produces N lines of output which need to be written to N floppy disks together with N copies of reconstruct.pl. Store these disks in N separate secure locations.
  3. If the original SECRET gets destroyed, gather K = 3 or more of the floppy disks and feed the shared keys to reconstruct.pl, thus
    ./reconstruct.pl <<EOF
    share5
    share1
    share2
    EOF
    The output will be the original secret.
  4. If some number < K of floppy disks are stolen or mislaid, then immediately generate a new set of N floppy disks (see step 2), and destroy at least N − K + 1 of the remaining disks.
  5. If some number ≥ K of floppy disks are stolen or mislaid, then generate a new encryption key, and re-encrypt the existing backup tapes.

Here's how tapes can be encrypted with gpg and the SECRET.

  1. use the key for encryption by gpg during a dump
    (cat SECRET; DUMP-DATA) |
    gpg -c --passphrase-fd 0 |
    buffer -s 64k -m 32m -t > $TAPE
    DUMP-DATA is whatever generates the backup data (tar, dump, etc.)
  2. use the key for decryption during a restore
    (cat SECRET; dd if=$TAPE bs=64k 2> /dev/null) |
    gpg --passphrase-fd 0 |
    UNDUMP-DATA
    UNDUMP-DATA is the inverse of DUMP-DATA.
Charles Karney (2001-08-21)
Back to index.