In todays digital world passwords and other types of secrets are omnipresent and they secure access to various assets dear to our hearts, some of those can have tremendous tangible or moral value. For such assets it’s worth to select really good and strong password, which basically means long and hard to remember. How to ensure ourselves in case of memory failure? We can write it down and lock in secure place, share with trusted person etc., but still there is one point of of failure – secure place can be robbed, that person can betray us. Can cryptography  provide us with better options?  Yes it can with help of method called Secret sharing – we can split secret into n parts – called shared secrets – and distribute them to different places/people. Later we (or someone else) need to collect k (k > 0 and k <= n) shared secret to recover original secret. k is called threshold and it is defined when generating shared secrets – so we for instance generate n=5 shared secrets, but only k=3 will be needed to recover original secret.

I believe you can easily imagine  many other real life scenarios where secret sharing can be useful and for sure it’s used in many applications and systems today. Cryptography provides several algorithms for secure (by design) secret sharing.  Most common is Shamir’s Secret Sharing based on linear algebra approach. There are many tools and libraries for Shamir’s scheme (and further advancements of original algorithm),  you can for instance try ssss, which provides command line tool that you can easily install into your Linux and also there is an online demo. Another family of secret sharing schemes is based on Chinese Reminer Theorem, where especially Asmuth-Bloom scheme is interesting.  I have not seen many implementation for Asmuth-Bloom secret sharing so I created one in Rust.

My implementation contains also command line utility so you can easily play with in on your computer:

If you do not have cargo and rustc you can easily install with

curl -sSf https://static.rust-lang.org/rustup.sh | sh

Then install with cargo:

cargo install asmuth_bloom_secret_sharing

And create shared secrets:

#ensure cargo binaries are on the path
PATH=$PATH:$HOME/.cargo/bin
# and generate shared secrets
asmuth_bloom_secret_sharing generate -n 5 -t 3 my_biggest_secret

The output is:

200p2l:400p4r:2v6a0f1bvhdgqjn0c05eg11oia9v
200p2l:400p5h:m08u392jbfptt071kv3eq3teqaq
200p2l:400p65:2bjrjd73hgsavd805g5g7ohv7kre
200p2l:400p6h:3cr8v18kfqmon2h9vl7j1fi779eo
200p2l:400p71:1k03mp7e6fg2ap6ahi1tt3p0bbtf

Each line represents one shared secret. Later we can recover original secret from any 3 shared secrets (as threshold was 3):

asmuth_bloom_secret_sharing recover -t 3 <<EOF
200p2l:400p5h:m08u392jbfptt071kv3eq3teqaq
200p2l:400p6h:3cr8v18kfqmon2h9vl7j1fi779eo
200p2l:400p4r:2v6a0f1bvhdgqjn0c05eg11oia9v
EOF
echo

And indeed we will see our secret again:

my_biggest_secret