Implémentation Java du partage secret de Shamir
J'ai essayé d'implémenter le partage secret de Shamir en Java mais j'ai un problème.
Quand je mets K>10 le secret n'est plus reconstruit. Qui peut m'aider? C'est ce que j'ai fait. Quel est le problème?
Dans un premier temps je choisis N et K, ensuite j'ai la génération de coefficients, la création de partages et enfin la 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;
}
5
Author: Esterlinkof, 2013-10-11
4 answers
On dirait que votre implémentation souffre d'erreurs numériques dans la partie de reconstruction secrète (l'utilisation de double provoque des erreurs d'arrondi).
Cependant, il y a aussi un problème dans la partie génération d'actions, mais je ne suis pas en mesure de le souligner.
J'ai réécrit votre code en utilisant l'exemple Java de Shamir's Secret Sharing. C'est rapide et sale mais correct (j'espère).
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);
}
}
3
Author: karbi79, 2015-10-17 06:22:24
L'implémentation du partage secret de Shamir de Karbi79 n'est pas valide. Cela pourrait ressembler à une bonne réponse [le test de base fonctionne bien], mais ce n'est pas le cas!
La bonne mise en œuvre du partage secret de Shamir a fait mon ami. C'est son 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);
}
}
Partage secret.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;
}
6
Author: JerzySkalski, 2015-12-19 00:21:47
Https://github.com/codahale/jsecretsharing
// build 10 shares, of which 2 are required to recover the secret
ShareBuilder builder = new ShareBuilder("Je suis Batman. Sérieusement.".getBytes (), 2, 512); Liste partages = constructeur.construire(10);
// prend 2 actions, récupère le secret Liste someShares = new ArrayList(); someShares.ajouter actions.obtenir (2)); someShares.ajouter actions.obtenir (7)); ShareCombiner combiner = nouveau ShareCombiner(someShares); Système.ERR.println(nouvelle chaîne (combiner.combiner()));
Je suis batman// omg Je suis batman
2
Author: wcc526, 2016-06-23 13:06:23
Code similaire mais avec une meilleure implémentation (je pense). Vous pouvez utiliser des secrets de chaîne maintenant.
Voici le 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"}));
}
}
Et pour 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;
}
La sortie :
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
0
Author: Mahmud Ibr, 2020-05-05 17:15:20