Shamir's Secret Sharing

Question

Given n (the number of players), t (the threshold value), and s (the secret), output the n secrets generated by Shamir's Secret Sharing algorithm.

The Algorithm

For the purposes of this challenge, the computations will be done in GF(251) (the finite field of size 251, otherwise known as the integers mod 251). Ordinarily, the field would be chosen such that its size is a prime much greater than n. To simplify the challenge, the field size will be constant. 251 has been chosen because it is the largest prime representable by an 8-bit unsigned integer.

1. Generate t-1 random integers in the (inclusive) range [0, 250]. Label these a₁ through a_t-1.
2. Construct a t-1th degree polynomial using s as the constant value and the random integers from step 1 as the coefficients of the powers of x: f(x) = s + x*a₁ + x²*a₂ + ... + x^t-1*a_t-1.
3. Output (f(z) mod 251) for each z in the (inclusive) range [1, n].

Reference Implementation

#!/usr/bin/env python
from __future__ import print_function
import random
import sys

# Shamir's Secret Sharing algorithm
# Input is taken on the command line, in the format "python shamir.py n t s"

n, t, s = [int(x) for x in sys.argv[1:4]]
if t > n:
    print("Error: t must be less than or equal to n")
    exit()
if n not in range(2, 251):
    print("Error: n must be a positive integer less than 251")
    exit()
if t not in range(2, 251):
    print("Error: t must be a positive integer less than 251")
    exit()
if s not in range(251):
    print("Error: s must be a non-negative integer less than 251")
    exit()
p = 251
a = [random.randrange(0, 251) for x in range(t-1)]

def f(x):
    return s + sum(c*x**(i+1) for i,c in enumerate(a))

# Outputting the polynomial is for explanatory purposes only, and should not be included
#  in the output for the challenge
print("f(x) = {0} + {1}".format(s, ' + '.join('{0}*x^{1}'.format(c, i+1) for i,c in enumerate(a))))
for z in range(1, n+1):
    print(f(z) % p)

Verification

The following Stack Snippet can be used to verify outputs:

var validate = function() {
  $('#nts-error').attr('hidden', parseInt($('#n').val()) >= parseInt($('#t').val()));
  $('#check').prop('disabled', parseInt($('#n').val()) < parseInt($('#t').val()));
};

// the following function is taken from https://rosettacode.org/wiki/Combinations#JavaScript
var combinations = function(arr, k) {
  var i,
    subI,
    ret = [],
    sub,
    next;
  for (i = 0; i < arr.length; i++) {
    if (k === 1) {
      ret.push([arr[i]]);
    } else {
      sub = combinations(arr.slice(i + 1, arr.length), k - 1);
      for (subI = 0; subI < sub.length; subI++) {
        next = sub[subI];
        next.unshift(arr[i]);
        ret.push(next);
      }
    }
  }
  return ret;
};

// The following code is taken from https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Javascript_example with the modification that the prime is 251, not 257

var prime = 251;

/* Gives the decomposition of the gcd of a and b.  Returns [x,y,z] such that x = gcd(a,b) and y*a + z*b = x */
function gcdD(a, b) {
  if (b == 0) return [a, 1, 0];
  else {
    var n = Math.floor(a / b),
      c = a % b,
      r = gcdD(b, c);
    return [r[0], r[2], r[1] - r[2] * n];
  }
}

/* Gives the multiplicative inverse of k mod prime.  In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1  */
function modInverse(k) {
  k = k % prime;
  var r = (k < 0) ? -gcdD(prime, -k)[2] : gcdD(prime, k)[2];
  return (prime + r) % prime;
}

/* Join the shares into a number */
function join(shares) {
  var accum, count, formula, startposition, nextposition, value, numerator, denominator;
  for (formula = accum = 0; formula < shares.length; formula++) {
    /* Multiply the numerator across the top and denominators across the bottom to do Lagrange's interpolation
     * Result is x0(2), x1(4), x2(5) -> -4*-5 and (2-4=-2)(2-5=-3), etc for l0, l1, l2...
     */
    for (count = 0, numerator = denominator = 1; count < shares.length; count++) {
      if (formula == count) continue; // If not the same value
      startposition = shares[formula][0];
      nextposition = shares[count][0];
      numerator = (numerator * -nextposition) % prime;
      denominator = (denominator * (startposition - nextposition)) % prime;
    }
    value = shares[formula][1];
    accum = (prime + accum + (value * numerator * modInverse(denominator))) % prime;
  }
  return accum;
}

$('#check').click(
  function() {
    var good = true;
    var problem = [];
    var n = parseInt($('#n').val());
    var t = parseInt($('#t').val());
    var s = parseInt($('#s').val());
    combinations([...Array(n + 1).keys()].slice(1), t).forEach(
      function(xArr) {
        var xfArr = xArr.map(
          function(x) {
            return [x, parseInt($('#f' + x).val())];
          }
        );
        var L = join(xfArr);
        if (L !== s) {
          good = false;
          problem.push(xArr);
        }
      }
    );
    $('#valid').html(good ? "True" : ("False (problematic secret sets: {" + problem.map(
      function(elem) {
        return "[" + elem.join(', ') + "]";
      }) + "})"));
  }
);

$('#n').change(
  function() {
    var inputHTML = "";
    for (var i = 1; i <= parseInt($('#n').val()); i++) {
      inputHTML += 'f(' + i + '): <input type="number" min="0" max="250" value="0" id="f' + i + '"><br>\r\n';
    }
    $('#inputs').html(inputHTML);
    validate();
  }
);

$('#t').change(
  function() {
    validate();
  }
);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
n:
<input type="number" min="2" max="250" value="6" id="n">t:
<input type="number" min="2" max="250" value="3" id="t">s:
<input type="number" min="0" max="250" value="230" id="s">
<br>
<div id="nts-error" hidden="true">t must be less than or equal to n!</div>
<br>
<br>
<div id="inputs">
  f(1):
  <input type="number" min="0" max="250" value="35" id="f1">
  <br>f(2):
  <input type="number" min="0" max="250" value="95" id="f2">
  <br>f(3):
  <input type="number" min="0" max="250" value="159" id="f3">
  <br>f(4):
  <input type="number" min="0" max="250" value="227" id="f4">
  <br>f(5):
  <input type="number" min="0" max="250" value="48" id="f5">
  <br>f(6):
  <input type="number" min="0" max="250" value="124" id="f6">
</div>
<br>
<input type="submit" id="check" value="Verify">
<br>
<br>Valid:
<div id="valid"></div>

Rules

• s will be a non-negative integer less than 251, and n and t will be positive integers less than 251 and greater than 1. Furthermore, you are guaranteed that the inputs are valid (meaning t <= n).
• Input and output can be in any reasonable, unambiguous, and consistent format.
• Random numbers are to be sampled from a uniform distribution - each possible value should have equal probability of being chosen.

Answer 1

Jelly, 15 bytes

251©xX€⁵0¦ḅЀ%®

Expects t, n, and s as command-line arguments. Try it online!

How it works

251©xX€⁵0¦ḅЀ%®  Main link. Left argument: t. Right argument: n Third argument: s

251©             Yield 251 and copy it to the register.
    x            Repeat [251] t times.
     X€          Random choice each; pseudo-randomly choose t integers from
                 [1, ..., 251]. Since 251 = 0 (mod 251), this is equivalent to
                 choosing them from [0, ..., 250].
       ⁵0¦       Replace the last generated integer (index 0) with s (⁵).
          ḅЀ    Interpret the resulting array as a base-k number, for each k in
                 [1, ..., n], and convert to integer.
              ®  Yield 251 from the register.
             %   Take the generated integers modulo 251.

Answer 2

Mathematica, 59 56 bytes

Mod[Power~Array~{#2,#-1}.RandomInteger[250,#-1]+#3,251]&

Takes three arguments in the order t, n, and s. Constructs a 2d-array with n rows and t-1 columns. Each row vector j, numbered from 1 thru n, contains the powers of j thru j^t-1. Then a vector of random integer coefficients in the range 0 thru 250 is created with t-1 values. That is matrix-multiplied with the 2d-array, and then s is added element-wise and taken module 251 to get the value of the polynomial at each of the n points.

Answer 3

CJam, 27 25 bytes

{,:)@({;251mr}%@+fb251f%}

Test it here.

Answer 4

Pyth, 24 bytes

J+EmOK251tEm%s.e*b^dkJKS

Try it online!

Input order: n s t separated by linefeed.

Answer 5

JavaScript, 181 bytes

(n,t,s)=>{r=Array(t-1).fill(0).map($=>{return Math.random()*251});f=(x=>{p = 0;r.map((k,c)=>p+=k*Math.pow(x, c));return s+p});_=Array(t-1).fill(0);_.map((l,i)=>_[i]=f(i));return _;}

Ungolfed:

(n, t, s) => {
    r = Array(t - 1).fill(0).map($ =>{return Math.random() * 251});
    f = (x => {
        p = 0;
        r.map((k, c) => p += k * Math.pow(x, c));
        return s + p
    });
    _ = Array(t - 1).fill(0);
    _.map((l, i) => _[i] = f(i));
    return _;
}

I don't know how to properly check it, but I do know that it was a pain to get JS to map across a new array since apparently .map skips undefined values. If anyone sees any ways to improve, or flaws, don't hesitate to let me know.

Answer 6

MATL, 20 19 bytes

251tliq3$Yrihi:ZQw\

Input order is t, s, n.

Try it online!

Explanation

251t    % Push 251 twice
l       % Push 1
iq      % Take input t. Subtract 1
3$Yr    % Generate t-1 random integers in [1 2 ... 251]
ih      % Take input s. Concatenate with the random integers
i:      % Take input n. Generate range [1 2 ... n]
ZQ      % Evvaluate polynomial at those values
w       % Swap to move copy og 251 to the top of the stack
\       % Modulo. Implicitly display

Answer 7

C#, 138 134 bytes

(n,t,s)=>new int[n+1].Select((_,x)=>(s+new int[t-1].Select(k=>new Random(e).Next(251)).Select((c,i)=>c*Math.Pow(x+1,i+1)).Sum())%251);

C# lambda where inputs are int and output is an IEnumerable<double>. You can try my code on .NetFiddle.

I am not 100% sure about the validity of my algorithm, please comment if I misunderstood something.

4 bytes saved with @raggy's trick.

Answer 8

Julia, 48 bytes

f(n,t,s)=(1:n).^(0:t-1)'*[s;rand(0:250,t-1)]%251

Try it online!

Answer 9

JavaScript (ES6), 116 bytes

(n,t,s)=>[...Array(n)].map((_,i)=>++i&&t.reduce((r,a)=>r*i+a)%251,t=[...Array(t)].map(_=>--t?Math.random()*251|0:s))

I'd like to think this is one of the rare cases where reduce beats map.

Answer 10

Python 3 with NumPy, 103 bytes

from numpy import*
lambda n,t,s:[poly1d(append(random.randint(0,251,t-1),s))(i+1)%251for i in range(n)]

I can honestly say that I never expected to use NumPy for code golf...

An anonymous function that takes input via argument and returns a list.

How it works

from numpy import*         Import everything in the NumPy library
lambda n,t,s...            Function with input number of players n, threshold value t and
                           secret s
random.randint(0,251,t-1)  Generate a NumPy array R of t-1 random integers in [0,250]
append(...,s)              Append s to R
poly1d(...)                Generate a polynomial p of order t-1 with coefficients R and
                           constant term s
...for i in range(n)       For all integers i in [0,n-1]...
...(i+1)                   ...evaluate p(i+1), so for all integers in [1,n]...
...%251                    ...and take modulo 251
...:[...]                  return as list

Try it on Ideone

Answer 11

J, 32 30 bytes

251|(1+i.@{.)p.~{:0}251?@#~1&{

Takes a list with the values n, t, and s.

Saved 2 bytes by using the replace at index 0 idea from @Dennis's solution.

Explanation

251|(1+i.@{.)p.~{:0}251?@#~1&{  Input: [n t s]
                           1&{  Select at index 1 (t)
                    251  #~     Create that many copies of 251
                       ?@       Generate that many random integers in [0, 251)
                {:              Get the tail of the input (s)
                  0}            Replace the value at index 0 of the random integer list
                                with s to make a coefficient list of the polynomial
          {.                    Get the head of the input (n)
       i.@                      Make the range [0, n-1]
     1+                         Add 1 to each to get [1, n]
             p.~                Evaluate the polynomial at each value [1, n]
251|                            Take each value mod 251 and return

Answer 12

Java 8, 224 bytes:

(n,t,s)->{int[]W=new int[t-1];for(int i=0;i<t-1;i++){W[i]=new java.util.Random().nextInt(251);};long[]O=new long[n];for(int i=1;i<=n;i++){long T=0;for(int h=1;h<t;h++){T+=W[h-1]*Math.pow(i,h);}O[i-1]=((T+s)%251);}return O;};

A Java 8 lambda expression. Outputs a comma separated integer array, and works perfectly until values in the output array reach beyond the range of the Java's long, or 64-bit signed integer, data type, upon which -200 is output into the array.

Try It Online! (Ideone)