Java Implementation of Shamir's Secret Sharing

Question

I tryed to implement Shamir's Secret Sharing in Java but I have some problem.

When I put K>10 the secret is no more reconstructed. Who can help me? This is what i've done. What's the problem?

Initially I choose N and K, next I have the generation of coefficients, the creation of shares and finally the reconstruction.

import java.math.BigInteger;
import java.util.Random;


public class Main {
    public static void main(String[] args){

        //INIT
        int N = 55;
        int K = 11;

        BigInteger secret = new BigInteger("123");
        modLength = secret.bitLength() + 1;
        BigInteger primeNum = genPrime();
        BigInteger[] coeff = new BigInteger[K-1];
        BigInteger[] partecipants = new BigInteger[K];
        for (int i=0;i<K;i++)
            partecipants[i] = new BigInteger(Integer.toString(i+1));
        System.out.println("Prime Number: "+primeNum);
        for (int i=0;i<K-1;i++){
            coeff[i] = randomZp(primeNum);
            System.out.println("a"+(i+1)+": "+coeff[i]);
        }

        //SHARES
        BigInteger[] shares = new BigInteger[N];
        for(int i=0;i<N;i++){
            BigInteger toAdd= secret;
            for(int j=0;j<K-1;j++){
                BigInteger power = new BigInteger(Integer.toString((int)(Math.pow((i+1),(j+1)))));
                toAdd=toAdd.add(coeff[j].multiply(power));  
            }
            shares[i] = toAdd.mod(primeNum);
            System.out.println("Share n."+(i+1)+": "+shares[i]);
        }
        //INTERPOLAZIONE
        BigInteger secret2= new BigInteger("0");
        double term;
        for (int i=0;i<K;i++){
            term = 1;
            BigInteger sharePartecipanteNow = shares[(partecipants[i].intValue())-1];
            for (int j=0;j<K;j++){
                if (partecipants[i].intValue()!=partecipants[j].intValue()){

                    BigInteger num = new BigInteger(Integer.toString(partecipants[j].intValue()*(-1)));
                    BigInteger den = new BigInteger(Integer.toString(partecipants[i].intValue()-partecipants[j].intValue()));
                    term = term*(num.doubleValue())/(den.doubleValue());
                }

            }
            term = term*sharePartecipanteNow.intValue();
            secret2 = secret2.add(new BigInteger(Integer.toString((int)term)));
        }
        while(secret2.intValue()<0)
            secret2 = secret2.add(primeNum);
        System.out.println("The secret is: "+secret2.mod(primeNum));
    }

    private static BigInteger genPrime() { 
        BigInteger p=null; 
        boolean ok=false; 
        do{
            p=BigInteger.probablePrime(modLength, new Random()); 
            if(p.isProbablePrime(CERTAINTY)) 
                ok=true; 
        }while(ok==false); 
        return p; 
    }

    private static BigInteger randomZp(BigInteger p) { 
        BigInteger r; 
        do{
            r = new BigInteger(modLength, new Random()); 
        } while (r.compareTo(BigInteger.ZERO) < 0 || r.compareTo(p) >= 0); 
         return r; 
    }

    private static final int CERTAINTY = 50; 
    private static int modLength; 
}

score 6 · Answer 1 · answered Dec 19 '15 at 00:21

karbi79's Shamir's Secret Sharing implementation is not valid. It could look like fine answer [basic test works fine], but it's not!

Proper implementation of Shamir Secret Sharing made my friend. It's his code:

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.Random;

public final class Shamir
{
    public static SecretShare[] split(final BigInteger secret, int needed, int available, BigInteger prime, Random random)
    {
        System.out.println("Prime Number: " + prime);

        final BigInteger[] coeff = new BigInteger[needed];
        coeff[0] = secret;
        for (int i = 1; i < needed; i++)
        {
            BigInteger r;
            while (true)
            {
                r = new BigInteger(prime.bitLength(), random);
                if (r.compareTo(BigInteger.ZERO) > 0 && r.compareTo(prime) < 0)
                {
                    break;
                }
            }
            coeff[i] = r;
        }

        final SecretShare[] shares = new SecretShare[available];
        for (int x = 1; x <= available; x++)
        {
            BigInteger accum = secret;

            for (int exp = 1; exp < needed; exp++)
            {
                accum = accum.add(coeff[exp].multiply(BigInteger.valueOf(x).pow(exp).mod(prime))).mod(prime);
            }
            shares[x - 1] = new SecretShare(x, accum);
            System.out.println("Share " + shares[x - 1]);
        }

        return shares;
    }

    public static BigInteger combine(final SecretShare[] shares, final BigInteger prime)
    {
        BigInteger accum = BigInteger.ZERO;

        for(int formula = 0; formula < shares.length; formula++)
        {
            BigInteger numerator = BigInteger.ONE;
            BigInteger denominator = BigInteger.ONE;

            for(int count = 0; count < shares.length; count++)
            {
                if(formula == count)
                    continue; // If not the same value

                int startposition = shares[formula].getNumber();
                int nextposition = shares[count].getNumber();

                numerator = numerator.multiply(BigInteger.valueOf(nextposition).negate()).mod(prime); // (numerator * -nextposition) % prime;
                denominator = denominator.multiply(BigInteger.valueOf(startposition - nextposition)).mod(prime); // (denominator * (startposition - nextposition)) % prime;
            }
            BigInteger value = shares[formula].getShare();
            BigInteger tmp = value.multiply(numerator) . multiply(modInverse(denominator, prime));
            accum = prime.add(accum).add(tmp) . mod(prime); //  (prime + accum + (value * numerator * modInverse(denominator))) % prime;
        }

        System.out.println("The secret is: " + accum + "\n");

        return accum;
    }

    private static BigInteger[] gcdD(BigInteger a, BigInteger b)
    { 
        if (b.compareTo(BigInteger.ZERO) == 0)
            return new BigInteger[] {a, BigInteger.ONE, BigInteger.ZERO}; 
        else
        { 
            BigInteger n = a.divide(b);
            BigInteger c = a.mod(b);
            BigInteger[] r = gcdD(b, c); 
            return new BigInteger[] {r[0], r[2], r[1].subtract(r[2].multiply(n))};
        }
    }

    private static BigInteger modInverse(BigInteger k, BigInteger prime)
    { 
        k = k.mod(prime);
        BigInteger r = (k.compareTo(BigInteger.ZERO) == -1) ? (gcdD(prime, k.negate())[2]).negate() : gcdD(prime,k)[2];
        return prime.add(r).mod(prime);
    }

    public static void main(final String[] args)
    {
        final int CERTAINTY = 256;
        final SecureRandom random = new SecureRandom();

        final BigInteger secret = new BigInteger("123");

        // prime number must be longer then secret number
        final BigInteger prime = new BigInteger(secret.bitLength() + 1, CERTAINTY, random);

        // 2 - at least 2 secret parts are needed to view secret
        // 5 - there are 5 persons that get secret parts
        final SecretShare[] shares = Shamir.split(secret, 2, 5, prime, random);


        // we can use any combination of 2 or more parts of secret
        SecretShare[] sharesToViewSecret = new SecretShare[] {shares[0],shares[1]}; // 0 & 1
        BigInteger result = Shamir.combine(sharesToViewSecret, prime);

        sharesToViewSecret = new SecretShare[] {shares[1],shares[4]}; // 1 & 4
        result = Shamir.combine(sharesToViewSecret, prime);

        sharesToViewSecret = new SecretShare[] {shares[0],shares[1],shares[3]}; // 0 & 1 & 3
        result = Shamir.combine(sharesToViewSecret, prime);
    }
}

SecretShare.java:

import java.math.BigInteger;

public class SecretShare
{
    public SecretShare(final int number, final BigInteger share)
    {
        this.number = number;
        this.share = share;
    }

    public int getNumber()
    {
        return number;
    }

    public BigInteger getShare()
    {
        return share;
    }

    @Override
    public String toString()
    {
        return "SecretShare [num=" + number + ", share=" + share + "]";
    }

    private final int number;
    private final BigInteger share;
}

`modInverse()` and `gcdD()` methods here are unnecessary, as the native [BigInteger#modInverse(java.math.BigInteger)](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/math/BigInteger.html#modInverse(java.math.BigInteger)) could be used instead. — Radoslav Stoyanov, Feb 19 '21 at 19:29

score 3 · Accepted Answer · edited Oct 17 '15 at 06:22

Looks like your implementation suffers from numerical errors in secret reconstruction part (using double causes rounding errors).

However there is also a problem in shares generation part, however I'm not able to point it out.

I have rewritten your code using Java example from Shamir's Secret Sharing. This is quick and dirty but correct (I hope).

import java.math.BigInteger;
import java.util.Random;

public final class Shamir {

    public final class SecretShare {
        public SecretShare(final int num, final BigInteger share) {
            this.num = num;
            this.share = share;
        }

        public int getNum() {
            return num;
        }

        public BigInteger getShare() {
            return share;
        }

        @Override
        public String toString() {
            return "SecretShare [num=" + num + ", share=" + share + "]";
        }

        private final int num;
        private final BigInteger share;
    }

    public Shamir(final int k, final int n) {
        this.k = k;
        this.n = n;

        random = new Random();
    }

    public SecretShare[] split(final BigInteger secret) {
        final int modLength = secret.bitLength() + 1;

        prime = new BigInteger(modLength, CERTAINTY, random);
        final BigInteger[] coeff = new BigInteger[k - 1];

        System.out.println("Prime Number: " + prime);

        for (int i = 0; i < k - 1; i++) {
            coeff[i] = randomZp(prime);
            System.out.println("a" + (i + 1) + ": " + coeff[i]);
        }

        final SecretShare[] shares = new SecretShare[n];
        for (int i = 1; i <= n; i++) {
            BigInteger accum = secret;

            for (int j = 1; j < k; j++) {
                final BigInteger t1 = BigInteger.valueOf(i).modPow(BigInteger.valueOf(j), prime);
                final BigInteger t2 = coeff[j - 1].multiply(t1).mod(prime);

                accum = accum.add(t2).mod(prime);
            }
            shares[i - 1] = new SecretShare(i - 1, accum);
            System.out.println("Share " + shares[i - 1]);
        }

        return shares;
    }

    public BigInteger getPrime() {
        return prime;
    }

    public BigInteger combine(final SecretShare[] shares, final BigInteger primeNum) {
        BigInteger accum = BigInteger.ZERO;
        for (int i = 0; i < k; i++) {
            BigInteger num = BigInteger.ONE;
            BigInteger den = BigInteger.ONE;

            for (int j = 0; j < k; j++) {
                if (i != j) {
                    num = num.multiply(BigInteger.valueOf(-j - 1)).mod(primeNum);
                    den = den.multiply(BigInteger.valueOf(i - j)).mod(primeNum);
                }
            }

            System.out.println("den: " + den + ", num: " + den + ", inv: " + den.modInverse(primeNum));
            final BigInteger value = shares[i].getShare();

            final BigInteger tmp = value.multiply(num).multiply(den.modInverse(primeNum)).mod(primeNum);
            accum = accum.add(primeNum).add(tmp).mod(primeNum);

            System.out.println("value: " + value + ", tmp: " + tmp + ", accum: " + accum);
        }

        System.out.println("The secret is: " + accum);

        return accum;
    }

    private BigInteger randomZp(final BigInteger p) {
        while (true) {
            final BigInteger r = new BigInteger(p.bitLength(), random);
            if (r.compareTo(BigInteger.ZERO) > 0 && r.compareTo(p) < 0) {
                return r;
            }
        }
    }

    private BigInteger prime;

    private final int k;
    private final int n;
    private final Random random;

    private static final int CERTAINTY = 50;

    public static void main(final String[] args) {
        final Shamir shamir = new Shamir(11, 20);

        final BigInteger secret = new BigInteger("1234567890123456789012345678901234567890");
        final SecretShare[] shares = shamir.split(secret);
        final BigInteger prime = shamir.getPrime();

        final Shamir shamir2 = new Shamir(11, 20);
        final BigInteger result = shamir2.combine(shares, prime);

    }
}

It only works, if you pass to 'combine' at least X number of shares IN ORDER OF IT'S GENERATION. With example configuration 'Shamir(11,20)', 'combine' should work with any combination of 11 shares, but it works only, if you pass array with 11 or more shares in order of generation (shares 0-10)! — JerzySkalski, Dec 19 '15 at 00:22
It's unfortunate that this is another example of a non working (real & simple) SSS implementation. The one on wikipedia only works for odd numbered keys required too. Hard to find a simple implementation that actually works. — Alan Wolfe, Apr 30 '16 at 21:53

score 2 · Answer 3 · answered Jun 23 '16 at 13:06

https://github.com/codahale/jsecretsharing

// build 10 shares, of which 2 are required to recover the secret

ShareBuilder builder = new ShareBuilder("I am Batman. Seriously.".getBytes(), 2, 512); List shares = builder.build(10);

// takes 2 shares, recovers secret List someShares = new ArrayList(); someShares.add(shares.get(2)); someShares.add(shares.get(7)); ShareCombiner combiner = new ShareCombiner(someShares); System.err.println(new String(combiner.combine()));

// omg I'm batman

Code seems to have moved to here: https://github.com/codahale/shamir/blob/master/README.md — Jonathan Cross, Sep 27 '17 at 15:19

Mahmud Ibr · Answer 4 · 2020-05-05T17:15:20.217

Similar code but with better implementation (I think). You can use String Secrets now.

Here is the code, Shamir.java:

import javax.swing.*;
import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.Random;

public final class Shamir
{
    public static SecretShare[] split(final BigInteger secret, int needed, int available, BigInteger prime, Random random)
    {
        // secret > the Secret.
        // needed > the required Shares.
        // available > the total number of shares.

        //System.out.println("Prime Number: " + prime);

        final BigInteger[] coeff = new BigInteger[needed];
        coeff[0] = secret;
        for (int i = 1; i < needed; i++)
        {
            BigInteger r;
            while (true)
            {
                r = new BigInteger(prime.bitLength(), random);
                if (r.compareTo(BigInteger.ZERO) > 0 && r.compareTo(prime) < 0)
                {
                    break;
                }
            }
            coeff[i] = r;
        }

        final SecretShare[] shares = new SecretShare[available];
        for (int x = 1; x <= available; x++) // for each share of the total shares
        {
            BigInteger accum = secret;

            for (int exp = 1; exp < needed; exp++) // for each
            {
                accum = accum.add(coeff[exp].multiply(BigInteger.valueOf(x).pow(exp).mod(prime))).mod(prime);
            }
            shares[x - 1] = new SecretShare(x, accum);
            //System.out.println("Share " + shares[x - 1]);
        }

        return shares;
    }

    public static String combine (final SecretShare[] shares, final BigInteger prime)
    {
        BigInteger accum = BigInteger.ZERO;

        for(int formula = 0; formula < shares.length; formula++)
        {
            BigInteger numerator = BigInteger.ONE;
            BigInteger denominator = BigInteger.ONE;

            for(int count = 0; count < shares.length; count++)
            {
                if(formula == count)
                    continue; // If not the same value

                int startposition = shares[formula].getNumber();
                int nextposition = shares[count].getNumber();

                numerator = numerator.multiply(BigInteger.valueOf(nextposition).negate()).mod(prime); // (numerator * -nextposition) % prime;
                denominator = denominator.multiply(BigInteger.valueOf(startposition - nextposition)).mod(prime); // (denominator * (startposition - nextposition)) % prime;
            }
            BigInteger value = shares[formula].getShare();
            BigInteger tmp = value.multiply(numerator) . multiply(modInverse(denominator, prime));
            accum = prime.add(accum).add(tmp) . mod(prime); //  (prime + accum + (value * numerator * modInverse(denominator))) % prime;
        }
        String secret = new String (accum.toByteArray ());
        //System.out.println("The secret is: " + secret + "\n");

        return secret;
    }

    private static BigInteger[] gcdD(BigInteger a, BigInteger b)
    {
        if (b.compareTo(BigInteger.ZERO) == 0)
            return new BigInteger[] {a, BigInteger.ONE, BigInteger.ZERO};
        else
        {
            BigInteger n = a.divide(b);
            BigInteger c = a.mod(b);
            BigInteger[] r = gcdD(b, c);
            return new BigInteger[] {r[0], r[2], r[1].subtract(r[2].multiply(n))};
        }
    }

    private static BigInteger modInverse(BigInteger k, BigInteger prime)
    {
        k = k.mod(prime);
        BigInteger r = (k.compareTo(BigInteger.ZERO) == -1) ? (gcdD(prime, k.negate())[2]).negate() : gcdD(prime,k)[2];
        return prime.add(r).mod(prime);
    }

    private static String generateShamirShares (String secret, int nedNuShares, int totNuShares)
    {
        final BigInteger bigIntegerPassword = new BigInteger(secret.getBytes ());
        final int CERTAINTY = 256;
        final SecureRandom random = new SecureRandom();
        final BigInteger prime = new BigInteger(bigIntegerPassword.bitLength() + 1, CERTAINTY, random);
        final SecretShare[] shares = Shamir.split (bigIntegerPassword, nedNuShares, totNuShares, prime, random);

        String coPrimeNum = nedNuShares + "P:" + prime;

        StringBuilder primeAndShares = new StringBuilder (coPrimeNum);

        String[] sharei = new String [totNuShares];
        for (SecretShare share: shares)
        {
            String coShare = share.getNumber () + ":" + share.getShare ();
            sharei[share.getNumber ()-1] = coShare;

            primeAndShares.append ("\n").append (coShare);
        }

        return String.valueOf (primeAndShares);
    }

    private static String combineShamirShares (String prime, String[] shares)
    {
        String strNumOfShares = prime.substring (0,prime.indexOf ("P:"));
        int avaSharesNum = Integer.parseInt (strNumOfShares);

        if (shares.length == avaSharesNum)
        {
            SecretShare[] sharesToViewSecret = new SecretShare[avaSharesNum];
            for (int i=0; i<avaSharesNum; i++)
            {
                String coShareStr = shares[i].trim ();
                String shareStr = coShareStr.substring (coShareStr.indexOf (":")+1);
                int shareNum = Integer.parseInt (coShareStr.substring (0,coShareStr.indexOf (":")));
                sharesToViewSecret[i] = new SecretShare (shareNum, new BigInteger (shareStr));
            }
            String coPrimeStr = prime.trim ();
            String primeStr = coPrimeStr.substring (coPrimeStr.indexOf (":")+1);
            //int primeNum = Integer.parseInt (coPrimeStr.substring (0,coPrimeStr.indexOf ("P:")));
            BigInteger bigIntegerPrime = new BigInteger(primeStr);
            String result = Shamir.combine (sharesToViewSecret, bigIntegerPrime);
            return result;
        }
        return ("Sorry, you have to provide " + avaSharesNum + " shares in order to reconstruct your " +
                                   "secret.");
    }


    public static void main(final String[] args)
    {
        System.out.println (generateShamirShares ("Password@123", 4, 12));

        System.out.println (combineShamirShares ("4P:57227141335498039497719664191",
                                                 new String[]{"1:46408014906759654811274101243",
                                                              "5:35533534891431853551600686081",
                                                              "3:56475036329164407840164095940",
                                                              "4:3124698633283214142142432517"}));
    }
}

And for SecretShare.java:

import java.math.BigInteger;

public class SecretShare
{
    public SecretShare(final int number, final BigInteger share)
    {
        this.number = number;
        this.share = share;
    }

    public int getNumber()
    {
        return number;
    }

    public BigInteger getShare()
    {
        return share;
    }

    @Override
    public String toString()
    {
        return "Share"+ number + ": " + share;
    }

    private final int number;
    private final BigInteger share;
}

The Output:

4P:66911912727662985127139425997
1:18968774123286583882220506766
2:4799832019998779275182245665
3:38199612445448994408262691940
4:41174116907286121055005905205
5:2641259640822036116095371071
6:45342780336694586746493427143
7:24372767774889679592604707038
8:62472961646045161809391548361
9:14737450730146940043258584729
10:3907974717832861449168153747
11:18902447844414802927803741026
12:48638784345204641379848832177

Password@123

Java Implementation of Shamir's Secret Sharing

4 Answers4