5

我尝试在 Java 中实现 Shamir 的秘密共享，但我遇到了一些问题。

当我设置 K>10 时，不再重建秘密。谁能帮我？这就是我所做的。有什么问题？

最初我选择 N 和 K，接下来是系数的生成，份额的创建，最后是重建。

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; 
}
4

4 回答 4

6

karbi79 的 Shamir 的秘密共享实现无效。它看起来像是很好的答案[基本测试工作正常]，但事实并非如此！

Shamir Secret Sharing 的正确实施结交了我的朋友。这是他的代码：

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;
}
于 2015-12-19T00:21:47.977 回答
3

看起来您的实现在秘密重建部分存在数值错误（使用双重导致舍入错误）。

但是，共享生成部分也存在问题，但是我无法指出。

我已经使用Shamir's Secret Sharing中的 Java 示例重写了您的代码。这是快速和肮脏但正确的（我希望）。

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);

    }
}
于 2014-05-05T10:49:45.870 回答
2

https://github.com/codahale/jssecretsharing

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

ShareBuilder builder = new ShareBuilder("我是蝙蝠侠。说真的。".getBytes(), 2, 512); 列出共享 = builder.build(10);

// 获取 2 个共享，恢复秘密列表 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()));

// 天哪，我是蝙蝠侠

于 2016-06-23T13:06:23.027 回答
0

类似的代码，但实现更好（我认为）。您现在可以使用字符串秘密。

这是代码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"}));
    }
}

对于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;
}

输出：_

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
于 2020-05-05T16:44:00.300 回答