combine method

String combine(List<String> shares, bool isBase64)

Takes a string array of shares encoded in Base64 or Hex created via Shamir's Algorithm Note: the polynomial will converge if the specified minimum number of shares or more are passed to this function. Passing thus does not affect it Passing fewer however, simply means that the returned secret is wrong.

Implementation

String combine(List<String> shares, bool isBase64) {
  String rs = "";
  if (shares.isEmpty) {
    throw new Exception("shares is NULL or empty");
  }

  // Recreate the original object of x, y points, based upon number of shares
  // and size of each share (number of parts in the secret).
  //
  // points[shares][parts][2]
  var points;
  if (isBase64) {
    points = decodeShareBase64(shares);
  } else {
    points = decodeShareHex(shares);
  }

  // Use Lagrange Polynomial Interpolation (LPI) to reconstruct the secret.
  // For each part of the secret (clearest to iterate over)...
  List<BigInt> secrets = [];
  int numSecret = points[0].length;
  for (int j = 0; j < numSecret; j++) {
    secrets.add(BigInt.zero);
    // and every share...
    for (int i = 0; i < shares.length; i++) {
      // LPI sum loop
      // remember the current x and y values
      BigInt ax = points[i][j][0]; // ax
      BigInt ay = points[i][j][1]; // ay
      BigInt numerator = BigInt.one; // LPI numerator
      BigInt denominator = BigInt.one; // LPI denominator
      // and for every other point...
      for (int k = 0; k < shares.length; k++) {
        // LPI product loop
        if (k != i) {
          // combine them via half products
          // x=0 ==> [(0-bx)/(ax-bx)] * ...
          BigInt bx = points[k][j][0]; // bx
          BigInt negbx = -bx; // (0-bx)
          BigInt axbx = ax - bx; // (ax-bx)
          numerator = (numerator * negbx) % prime; // (0-bx)*...
          denominator = (denominator * axbx) % prime; // (ax-bx)*...
        }
      }

      // LPI product: x=0, y = ay * [(x-bx)/(ax-bx)] * ...
      // multiply together the points (ay)(numerator)(denominator)^-1 ...
      BigInt fx = (ay * numerator) % prime;
      fx = (fx * (denominator.modInverse(prime))) % prime;

      // LPI sum: s = fx + fx + ...
      BigInt secret = secrets[j];
      secret = (secret + fx) % prime;
      secrets[j] = secret;
    }
  }

  // recover secret string.
  rs = mergeBigIntToString(secrets);
  return rs;
}