Split a secret into pieces
Generate pieces, and require pieces to reconstitute the secret.
Reconstitute a secret from pieces
Usage example
Imagine you encrypt some important data using a secret (encryption key). If you forget this secret, all your data is lost. But if somebody learns the secret, he can decrypt the data.
A good middle ground is to split the secret into several pieces, and give those pieces to close friends of yours. Since none of them gets the full secret, none of them will be able to access your data. But if you forget the secret, you can ask all friends for their piece and reconstitute it.
Some friends will probably lose their piece over the years. Hence, you would like to split the secret in such a way that you only need some pieces back, say 3 out of 5.
This also means that 3 of your friends could come together and reconstitute the secret. But if you pick your friends wisely, you have a good chance that this is not going to happen.
Description
Splitting
The secret is first converted into a byte sequence \(S = s_1, s_2, …, s_l\). If your secret consists of hex digits, the input is directly translated into the corresponding bytes. Otherwise, the input is treated as text, and converted to bytes using UTF-8.
With code length \(N\), we then generate \(N - 1\) random byte sequences \(R_1, R_2, … , R_{N - 1}\) of length \(l\). The last sequence is calculated by XOR'ing (\( ⊕ \)) the secret sequence with all random sequences:
\[ R_N = R_1 ⊕ R_2 ⊕ … ⊕ R_{N - 1} ⊕ S \]
Finally, the random sequences are scattered into \(M\) pieces. For that, the random sequences are multiplied with a random \(M × N\) scatter matrix:
\[ \left[ \begin{array}{ccc} c_{11} & c_{12} & ⋯ & c_{1N} \\ c_{21} & c_{22} & ⋯ & c_{2N} \\ ⋯ \\ c_{M1} & c_{M2} & ⋯ & c_{MN} \end{array} \right] \left[ \begin{array}{c} R_1 \\ R_2 \\ ⋯ \\ R_N \end{array} \right] = \left[ \begin{array}{c} D_1 \\ D_2 \\ ⋯ \\ D_M \end{array} \right] \]
The coefficients \(c_{ik}\) are bytes (0..255), and all operations are carried out over the finite field \(GF(2^8)\). Hence, \(D_i\) are byte sequences of length \(l\).
Note that the scatter matrix is chosen such that any subset of \(N\) rows is an invertible matrix. This ensures that any subset of \(N\) pieces will allow to reconstruct the secret.
A piece \(i\) consists of the coefficients \(c_{i1}, c_{i2}, ..., c_{iN}\) and the data \(D_i\). The above calculator writes pieces as "coefficients: data", whereby both coefficients and data are hex-encoded.
Reconstitution
Given any \(N\) pieces, the scatter matrix can be written as:
\[ C = \left[ \begin{array}{ccc} c_{11} & c_{12} & ⋯ & c_{1N} \\ c_{21} & c_{22} & ⋯ & c_{2N} \\ ⋯ \\ c_{N1} & c_{N2} & ⋯ & c_{NN} \end{array} \right] \]
By construction, this matrix is invertible over the finite field \(GF(2^8)\). Hence, the random sequences \(R_i\) can be obtained as follows:
\[ \left[ \begin{array}{c} R_1 \\ R_2 \\ ⋯ \\ R_N \end{array} \right] = C^{-1} \left[ \begin{array}{ccc} D_1 \\ D_2 \\ ⋯ \\ D_N \end{array} \right] \]
yielding the secret:
\[ S = R_1 ⊕ R_2 ⊕ … ⊕ R_N \]
Security
Given \(N - 1\) pieces, an adversary may be able to retrieve \(N - 1\) random sequences, but cannot gain any information about the last random sequence, and hence cannot obtain any information about the secret \(S\).
Implementation note
Both secret splitting and reconstitution are carried out in your browser. Nothing is transmitted over the internet.
Questions, Suggestions and Bug Reports
Please direct questions, suggestions, and bug reports to Thomas Lochmatter.