Protecting Private Keys: Shamirs Secret Sharing

We want to store our keys securely, but at the same time have protection against loss. The first requires a single copy in a protected environment, increasing the danger of loosing the key or centralised attacks, the latter requires many copies in different locations, thus threatening the security.

In past posts I have provided simple methods to store the key, here I present a much better but also more complicated method: Secret Sharing.

The key is decomposed into different parts in such a way that each part alone provides (almost) zero information. But combining a number of pieces the key can be recovered. This allows to store parts of the key in different locations, while maintaining security and being able to recover the key even when some parts get lost.

I have implemented my own version of Shamir's Secret Sharing method (please do not use the wikipedia example which uses random and is not (necessarily) suitable for security applications) from scratch and optimised towards key encryption.
In that way I can be sure that the code does exactly what I want and there are no secret backdoors implemented. I also made some small modifications to the Shamir's method that I will explain in another post.

Warning: Do use the code at your own risk. There may be bugs; only use what you understand and do not modify things that you do not understand. There are many ways to compromise the security of your keys. Please consider all keys in this post as compromised and do not use them or send money to their addresses!

First I import some dependencies. os is used for cryptographic randoms, you could instead roll your own randoms from coin tosses if you do not trust it. binascii, hashlib and b58 are only used to convert keys to int and back and np is used for one dot-product, which is easy to avoid. Below I show some examples for secrets. WIF_int is the integer corresponding to a bitcoin key and int_rand is an integer corresponding to pure entropy.

Next we have to choose a prime to define the ring on which we are working. The choice of the prime is very important. If the prime is too small, the information of the key cannot be stored within the ring and the original key cannot be recovered. It the prime is too big it is the same as working in the natural numbers and thus security is reduced and a brute force attack may become possible. I have given three primes as examples. The first can be used for very long keys. The second for standard bitcoin keys and the third for typical cryptographic sources of entropy. The code will complain when you make a bad choice. You may ignore the warning for too large prime and proceed at your won risk. Do not ignore the warning of a too small prime as you will loose the key and all of your money.

In addition the prime is needed to recover the key. So make sure to save it! It is not relevant to the security so feel free to put it online. Just dont forget it.

We also set num_locks, which specifies how many parts are required to recover the key.

Next I define a basis. Here I use the trivial one that is used in the standard version of Shamir's, but you may also use another linear independent base. If you dont know what this means, just leave this part as it is.

Then I generate random entropy to hide the key. You may replace it by a sufficient number of coin tosses if paranoid.

This is the main encoder. n_keys specifies the number of keys requested. The key output in in hex format, but can also be requested as basis 10 integer. In order to recover the private key any combination of num_locks of these keys can be used. The key consists of the coding ([a, b, c, d, ...]) and the number as seen at the bottom. Loosing the coding part can be bruteforced, loosing the key means that the part cannot be recovered.

This is the decoder. The first block prepares a number of keys used to reconstruct the private key. In reality you will simply type them in. Here I just copy them from above. Then the equations are solved in a way that does not require divisions as these are more expensive in prime rings.

The final step is performing one division. Fermat's little theorem provides an analytical solution but for the large primes we are using it would require a supercomputer. Instead I use a fast algorithm that can do division by numbers small compared to the prime very fast. It is based on prime factor decomposition and using Fermat's little theorem in that subspace to find representations of the number that can be divided trivially.
As can be seen, 4 of the 6 keys are sufficient to reconstruct the private key as requested.

This method has many applications. For example make 8 keys, distribute them in different places and you can get your private key back if and only if you are able to retrieve at least 4 parts. You can even (given you have at least 4) generate extra keys later without invalidating the old ones, when you know that some have been lost.