I needed a method for sharing a secret that required multiple agents to coordinate before the secret could be recovered. This is useful for encrypting keys used in critical backups. I decided to use an implementation of Shamir's Secret Splitting Scheme (The S in RSA).

Currently I'm using a program called 'ssss' ( http://point-at-infinity.org/ssss/ ) to do secret sharing.

This program is also a Debian package in unstable (http://packages.debian.org/unstable/utils/ssss).

sudo apt-get install ssss

It's simply to compile if you can't use the Debian package. The source package currently lacks an install target for make, you'll have to install by hand or patch the make file.

wget http://point-at-infinity.org/ssss/ssss-0.5.tar.gz
sha1sum ssss-0.5.tar.gz
tar -xzvf ssss-0.5.tar.gz
cd ssss-0.5/
sudo apt-get install xmltoman libgmp3-dev libgmp3
make

Here is an article on the background of secret splitting with a (k, n) threshold scheme:
http://szabo.best.vwh.net/secret.html

The secret being shared in this example could be a static key to an encrypted disk image.
Here's how we generated the split keys (this step can take a while):
ssss-split -t 4 -n 6 -w encrypted-backup-key -s 1024
encrypted-backup-key-1-a10ed337cc73ea186d8d23c0df395b0aad8a7b01cae866eb5ea48d7767787cc55a0e41aa1ea4189f761f75cd2047f9a4c686b1a665a6af3ea2c5361fe48f1354ad9de19b4ea1ab6e6a84033274b862eca667c1700a91661e9a28267dd7687e3ed4798479f1e5c621662caac06027066df84a4d3477d2d9730b8c6f9e0f6a8ab6
encrypted-backup-key-2-e1f1f289f1d152191144d5ddb6f8c588582a665a28a869103eddeda8fd066e56811c63b6259c71732dfceceaafb924f4e3790a862f82a293d64a7286fb00296fa3ef195a76d9d8aa91eeff5f679ba5458b84a8b823ea9a840acd36064f32b1b89dea519e2cb149359524735351cd676359f474beee2ecb7a7aafe45a5d2606f4
encrypted-backup-key-3-fdd3c734308ed001a06dd57cfb4e7810f3f3a853446e8a62323d7fe75c83e9d812bb6139ece18537be4a7104667b355b8ffe07e0ff78fe4ad4ffbff9aa5be670e5d3fa3f9f66a2a2f30d2383b62ac0bbe51c7f1a216fa2356cdfd775942d7249c404e05c012bddfc9ff548721b81ee270f6360c301463ad5f7545195b30024b8
encrypted-backup-key-4-457ad2ea649ad65bda6779ab42f4e209017efacf19d7c8817488b595da68e6aaa823e1beb05ce1d07c6ccd37e9c88b9376ed4347450a8379cd13dd52e2866908ccb1607679cf96436bf16cb8cdb1f8a1702fd72f398816b91552a883b36ecc1fad661a99dad8ca5e084f8a812f11b6213e95aecbf26a6e5a73fcdc0751e775d1
encrypted-backup-key-5-c98f78d6472ea4d434736448bb71aa6e8696a58c1329278070ee89aa53cd721c8778f8b2d3ef7507610c3f1d4dce71f6b3febb2ac8e5c543d91c0854ab393c5d019d765fde02662203cb619ffe13647aa0e16708022880e94529f6af0b96b1a6dd5f99924a2c15cd09fd989e26353fe16ca9c80fe99ee0a9d1d3ca3202a7a0f7
encrypted-backup-key-6-a8df666bbf5bfdfbf6c0a8d0bad7df122b559a433d19309d019ab59599f346fe2592eda9bd4bddcc274379b219b97b33c528ea1c38ebfd2880e77c3f857f32f319ce64067a9f0134ed123e0529175198f1aec1ca591821b1b91f986a540302b0c76229e6eda40c6dec331371910f5fe7c44114f6995a0c18ff5906032a2ec222

Each line is a single key for distribution to the parties involved. This example means that we need four out of six people to give their keys over before we'll be able to decrypt the shared secret.

Here's how we'd recover the key with any four of the total six keys:
ssss-combine -t 4
Enter 4 shares separated by newlines:
Share [1/4]: 2-e1f1f289f1d152191144d5ddb6f8c588582a665a28a869103eddeda8fd066e56811c63b6259c71732dfceceaafb924f4e3790a862f82a293d64a7286fb00296fa3ef195a76d9d8aa91eeff5f679ba5458b84a8b823ea9a840acd36064f32b1b89dea519e2cb149359524735351cd676359f474beee2ecb7a7aafe45a5d2606f4
Share [2/4]: 5-c98f78d6472ea4d434736448bb71aa6e8696a58c1329278070ee89aa53cd721c8778f8b2d3ef7507610c3f1d4dce71f6b3febb2ac8e5c543d91c0854ab393c5d019d765fde02662203cb619ffe13647aa0e16708022880e94529f6af0b96b1a6dd5f99924a2c15cd09fd989e26353fe16ca9c80fe99ee0a9d1d3ca3202a7a0f7
Share [3/4]: 3-fdd3c734308ed001a06dd57cfb4e7810f3f3a853446e8a62323d7fe75c83e9d812bb6139ece18537be4a7104667b355b8ffe07e0ff78fe4ad4ffbff9aa5be670e5d3fa3f9f66a2a2f30d2383b62ac0bbe51c7f1a216fa2356cdfd775942d7249c404e05c012bddfc9ff548721b81ee270f6360c301463ad5f7545195b30024b8
Share [4/4]: 1-a10ed337cc73ea186d8d23c0df395b0aad8a7b01cae866eb5ea48d7767787cc55a0e41aa1ea4189f761f75cd2047f9a4c686b1a665a6af3ea2c5361fe48f1354ad9de19b4ea1ab6e6a84033274b862eca667c1700a91661e9a28267dd7687e3ed4798479f1e5c621662caac06027066df84a4d3477d2d9730b8c6f9e0f6a8ab6
Resulting secret: MyExampleSecret

Note that we stripped off the unique token of 'encrypted-backup-key-' and left the preceeding number. If we hadn't we'd get an error that looks like:

FATAL: invalid syntax.

Any of the 4 keys will decrypt to reveal the secret. That secret is the password to the encrypted disk image that all parties involved have.

So what's a practical example that you can use?

Let's say that you have 6 system administrators on your site. Let's say that all 6 administrators have gpg keys. Let's also say you'd like to secure your backups.

Each night your system runs backups and encrypts them with a randomly generated secret. I'll leave this process up to you. You could easily take the output of ssss encrypt each key from the resulting split to a different administrator and then email the encrypted data to each administrator.

To recover the backup key for last night, it would require that you entered the correct number of keys from threshold you specified when invoking ssss or another program like it.