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