Shamir's secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message.
Secret Shares in Rust in Rust |
Background
In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm that allows a secret to be split into parts, and only when a number of them are added together will the original message be created [here]. In these times when we need to integrate trust, his algorithm has many application areas.
So let’s take an example ... let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately, we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.
In Shamir’s scheme, the number of generals can be represented by the number of shares, and the number of generals who are required to generate the secret is represented by the threshold. Thus, in this example, we have a share value of six and a threshold value of three. So we give out one of the shares to each of the generals so that none of them has the same one. We will then require three generals to put together their shares in order for them to generate the password for the missile. To solve this problem and generate the shares (and also check the answer), I’ve created this Web page [here].
So for a password of “Fire The Missile”, with a share of six, and a threshold of three we get:
000if30kGfSjyDNilwU0Tyz5awf2uk=001PoYDi8eMEoMI6Zkbkn2n1GABoas=002HxjSfFEEakXLqUnfGolr27XG3Ws=003qGMlZ/Fa9+YOyozQWch/6nnYpik=004RHyZDtPQP9/yXgv4cojC6Zg6Ets=0058wduFXOOonw3Pc73McnW2FQkaZk=
for which each of these can be distributed to each of the generals. When three of them combine their codes, the result will be:
< Trying a share of 1: ‰ýôgÒ ÍŠ\Ñå¬ÚéTrying a share of 2: ?D·CümQFH¤Ú¼A7™r¹ÌTrying a share of 3: Fire The Missile
The basic theory relates to the number of points within a mathematical equation, that are required to reveal what the equation is (and thus determine the secret). For example, if we have a secret of 15, and can only be revealed when two people combine their information. For this, we thus need a linear equation, such as:
\(y=2x + 15\)
The two pieces of information that could be generated to reveal the equation would thus be two points on this line, such as: (0,15) and (1,17). If we only know one point, such as (1,17), we cannot determine the equation of the line, but knowing two points we can determine the gradient:
\(m=\frac{(17–15)}{(1–0)} =2\)
and from here we can determine the point it cuts the y-axis (c):
c=y -mx=17- 2×0=15
and thus we have the equation (y=2x + 15), where the secret is 15. In this example, we have only two shares, but if we require three shares we need a parabola, such as:
\(y=2x^2 + 5x + 15\)
and share three points on the equation to generate the secret. If we require four shares then a cubic curve is required, and so on. In most situations, it would be too processor intense to encrypt data with the secret share method, especially if we had a complete equation (such as using any 8 from 10 shares), so we often use symmetric encryption (such as for AES or ChaCha) to encrypt the data, and then create a share of the key. For example, if we had an 8 from 10 secret share policy, we would generate a 256-bit encryption key and then encrypt the data. Next, we would then take the 256-bit AES key and create a secret share where 8 of the 10 shares can come together to recreate the key.
Code
First we create the project with:
cargo new sss
We then go into the sss folder, and add the following to the cargo.toml file:
[package] name = "shares" version = "0.1.0" authors = ["billbuchanan"] edition = "2018" [dependencies] threshold-secret-sharing = "0.2"
Next we go into the src folder, and edit the main.rs file with:
extern crate threshold_secret_sharing as tss; use std::env; fn main() { let mut thres=8; let n_shares=20; let p= i64::pow(2,19)-1; let mut secret = 1000; let args: Vec String = env::args().collect(); if args.len()> 1 { secret = args[1].clone().parse::().unwrap(); } if args.len()> 2 { thres= args[2].clone().parse:: ().unwrap(); } let ref tss = tss::shamir::ShamirSecretSharing { threshold: thres, share_count: n_shares, prime: p }; let shares = tss.share(secret); println!("\nShares:"); for x in 0..n_shares-1 { print!("{} ", shares[x]); } println!("\n\nShares to reconstruct:"); let recovered_index: Vec = (0..thres+1).collect(); let recovered_share: &[i64] = &shares[0..thres+1]; for x in 0..recovered_index.len() { print!("[{} {}] ", recovered_index[x],recovered_share[x]); } let recover_secret = tss.reconstruct(&recovered_index, recovered_share); print!("\n\nRecovered: {} ", recover_secret); }
Finally we simply build with:
cargo build
and we then run with:
>> cargo run Shares: 175565 357904 221353 33400 8045 67734 245363 237966 439249 12636 240740 160316 386142 79066 372229 28514 92573 227044 444392 Shares to reconstruct: [0 175565] [1 357904] [2 221353] [3 33400] [4 8045] [5 67734] [6 245363] [7 237966] [8 439249] [9 12636] [10 240740] Recovered: 5