For Perfect Security (and Data Resilience) … Here’s Shamir Secret Shares and Rust

For Perfect Security (and Data Resilience) … Here’s Shamir Secret Shares and Rust

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. It is, in its purest form, a method that gives perfect security, as you cannot determine anything about the original data unless you have enough of the shares to meet the threshold. So let’s match, Shamir’s Secret Shares (SSS) with a highly secure programming language: Rust.

Shamir’s Secret Shares

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 (paper). 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

Basic theory

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 = (17–15)/(1–0) =2

and from here we can determine the point it cuts the y-axis ©:

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² + 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.

https://asecuritysite.com/shares/go_sss

Coding

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

Here is the running code:

Conclusions

Shamir’s Secret Shares have so many applications, including breaking up an encryption key into a number of parts and then distributing it to trusted entities. If this encryption key is ever lost, the trusted entities can come back together and reconstruct it. If you want to learn more about secret shares, try here:

https://asecuritysite.com/shares

and for Rust:

https://asecuritysite.com/rust

Asecuritysite is free of charge. If you want to support its maintainance, consider subscribing to this blog: