Shamir's Secret Sharing — C++ source

// secret-sharing — Shamir's Secret Sharing over GF(256), the Galois field of
// 256 elements.
//
// Language: C++ (C++17, standard library only)
// Ported from src/lib/secret-sharing.ts (the canonical TypeScript implementation).
// display source — part of CosmoDev's polyglot tool pages.
//
// Pure math, zero dependencies. Addition in GF(256) is XOR; multiplication
// uses discrete log/exp tables built from the generator 3 (0x03) under the
// same reduction polynomial as AES (x^8 + x^4 + x^3 + x + 1 = 0x11B).
//
// Split: for each byte of the secret, build a random polynomial of degree
// K-1 whose constant term is the secret byte, then evaluate it at x = 1..N.
// Reconstruct: with K or more shares, Lagrange interpolation at x = 0
// recovers each constant term. Fewer than K shares reveal nothing
// (information-theoretic security).
//
// The TS reference encodes the secret with TextEncoder (UTF-8); a C++
// std::string already carries UTF-8 bytes, so it is used verbatim.

#include <algorithm>
#include <array>
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <random>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

namespace secret_sharing {

using Bytes = std::vector<uint8_t>;

/** Exponent table: GF256_EXP[i] = 3^i in GF(256). Index 255 mirrors index 0. */
std::array<uint8_t, 256> GF256_EXP;
/** Discrete log table: GF256_LOG[3^i] = i (GF256_LOG[0] is unused). */
std::array<uint8_t, 256> GF256_LOG;

/** Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime". */
uint8_t xtime(uint8_t a) {
  return uint8_t((uint16_t(a) << 1) ^ ((a & 0x80) != 0 ? 0x11b : 0));
}

bool tables_ready = ([] {  // build the log/exp tables once, at static init
  uint8_t x = 1;
  for (int i = 0; i < 255; i++) {
    GF256_EXP[i] = x;
    GF256_LOG[x] = uint8_t(i);
    // step to the next power of the generator 3: x *= 3 (i.e. x ^ xtime(x))
    x = uint8_t(x ^ xtime(x));
  }
  // 3 has order 255, so EXP wraps: EXP[255] === EXP[0].
  GF256_EXP[255] = 1;
  return true;
})();

/** Addition in GF(256) is bitwise XOR (also serves as subtraction). */
uint8_t gfAdd(uint8_t a, uint8_t b) { return uint8_t(a ^ b); }

/** Multiply two field elements via log/exp tables. */
uint8_t gfMul(uint8_t a, uint8_t b) {
  if (a == 0 || b == 0) return 0;
  return GF256_EXP[(uint16_t(GF256_LOG[a]) + GF256_LOG[b]) % 255];
}

/** Multiplicative inverse of a non-zero element. */
uint8_t gfInv(uint8_t a) {
  if (a == 0) throw std::invalid_argument("0 has no multiplicative inverse in GF(256)");
  return GF256_EXP[(255 - GF256_LOG[a]) % 255];
}

/** Divide a by b in GF(256). */
uint8_t gfDiv(uint8_t a, uint8_t b) {
  if (b == 0) throw std::invalid_argument("Division by zero in GF(256)");
  if (a == 0) return 0;
  return GF256_EXP[(uint16_t(GF256_LOG[a]) + 255 - GF256_LOG[b]) % 255];
}

/** Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style. */
uint8_t evalPoly(const Bytes& coeffs, uint8_t x) {
  uint8_t y = 0;
  for (std::size_t i = coeffs.size(); i-- > 0;) {
    y = gfAdd(gfMul(y, x), coeffs[i]);
  }
  return y;
}

using Point = std::pair<uint8_t, uint8_t>;  // (x, y)

/**
 * Lagrange interpolation at x = 0 over distinct-x points - recovers the
 * polynomial's constant term. Subtraction is XOR, so (0 - xm) = xm and
 * (xj - xm) = xj ^ xm.
 */
uint8_t interpolateAtZero(const std::vector<Point>& points) {
  uint8_t result = 0;
  for (std::size_t j = 0; j < points.size(); j++) {
    const uint8_t xj = points[j].first;
    const uint8_t yj = points[j].second;
    uint8_t weight = 1;
    for (std::size_t m = 0; m < points.size(); m++) {
      if (m == j) continue;
      const uint8_t xm = points[m].first;
      weight = gfMul(weight, gfDiv(xm, uint8_t(xj ^ xm)));
    }
    result = gfAdd(result, gfMul(yj, weight));
  }
  return result;
}

// --- hex + random helpers -----------------------------------------------------

static std::string toHex(const Bytes& bytes) {
  static const char* DIGITS = "0123456789abcdef";
  std::string out;
  out.reserve(bytes.size() * 2);
  for (uint8_t b : bytes) {
    out += DIGITS[b >> 4];
    out += DIGITS[b & 0x0f];
  }
  return out;
}

static int hexValue(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'a' && c <= 'f') return c - 'a' + 10;
  if (c >= 'A' && c <= 'F') return c - 'A' + 10;
  return -1;
}

static Bytes fromHex(const std::string& hex) {
  Bytes out(hex.size() / 2);
  for (std::size_t i = 0; i < out.size(); i++) {
    out[i] = uint8_t(hexValue(hex[i * 2]) << 4 | hexValue(hex[i * 2 + 1]));
  }
  return out;
}

static bool isHex(const std::string& s) {
  if (s.empty()) return true;
  for (char c : s) {
    if (hexValue(c) < 0) return false;
  }
  return true;
}

/** Default CSPRNG: one call fills the buffer from std::random_device. */
static Bytes defaultRandomBytes(std::size_t n) {
  Bytes out(n);
  std::random_device rd;
  for (std::size_t i = 0; i < n; i++) out[i] = uint8_t(rd());
  return out;
}

static void assertPositiveInt(const char* name, int v) {
  if (v <= 0) throw std::invalid_argument(std::string(name) + " must be an integer >= 1");
}

/**
 * Split a secret into totalShares shares (x = 1..N) where any threshold of
 * them reconstruct it. Returns hex share strings like "01-a3b2c1..." - the
 * two-digit hex x-coordinate, a dash, then one hex byte per secret byte.
 */
std::vector<std::string> splitSecret(const std::string& secret, int totalShares, int threshold) {
  assertPositiveInt("Total shares", totalShares);
  assertPositiveInt("Threshold", threshold);
  if (threshold < 2) {
    throw std::invalid_argument("Threshold must be at least 2 (a 1-of-N split is just the secret itself)");
  }
  if (totalShares > 255) {
    throw std::invalid_argument("Total shares must be at most 255 (share x-coordinates live in 1..255)");
  }
  if (threshold > totalShares) {
    throw std::invalid_argument("Threshold (" + std::to_string(threshold) +
                                ") cannot exceed total shares (" + std::to_string(totalShares) + ")");
  }

  const Bytes bytes(secret.begin(), secret.end());  // UTF-8 bytes, verbatim
  std::vector<Bytes> yParts(totalShares, Bytes(bytes.size()));
  Bytes coeffs(threshold);

  for (std::size_t b = 0; b < bytes.size(); b++) {
    coeffs[0] = bytes[b];
    if (threshold > 1) {
      const Bytes rand = defaultRandomBytes(threshold - 1);
      for (int i = 1; i < threshold; i++) coeffs[i] = rand[i - 1];
    }
    for (int i = 1; i <= totalShares; i++) {
      yParts[i - 1][b] = evalPoly(coeffs, uint8_t(i));
    }
  }

  std::vector<std::string> shares;
  shares.reserve(totalShares);
  for (int idx = 0; idx < totalShares; idx++) {
    char x[3];
    snprintf(x, sizeof(x), "%02x", idx + 1);
    shares.push_back(std::string(x) + "-" + toHex(yParts[idx]));
  }
  return shares;
}

/** A parsed share: its x-coordinate and its per-byte polynomial evaluations. */
struct ParsedShare {
  uint8_t x;
  Bytes y;
};

/** Parse one "xx-hex" share string; throws on any malformed input. */
ParsedShare parseShare(const std::string& share) {
  // Trim ASCII whitespace from both ends.
  std::size_t begin = 0, end = share.size();
  while (begin < end && std::isspace(static_cast<unsigned char>(share[begin]))) begin++;
  while (end > begin && std::isspace(static_cast<unsigned char>(share[end - 1]))) end--;
  const std::string s = share.substr(begin, end - begin);

  if (s.find('-') != 2 || s.size() < 3 || !isHex(s.substr(0, 2)) || s.substr(0, 2).size() != 2) {
    throw std::invalid_argument("Malformed share \"" + s + "\" - expected the format \"xx-hex…\" (e.g. \"01-a3b2c1\")");
  }
  const std::string yHex = s.substr(3);
  if (!isHex(yHex) || yHex.size() % 2 != 0) {
    throw std::invalid_argument("Malformed share \"" + s + "\" - the payload must be an even-length hex string");
  }
  const int x = hexValue(s[0]) << 4 | hexValue(s[1]);
  if (x == 0) {
    throw std::invalid_argument("Share x-coordinate 00 is invalid - shares are numbered from 01");
  }
  return {uint8_t(x), fromHex(yHex)};
}

/**
 * Reconstruct the secret from an arbitrary collection of share strings.
 * Needs at least 2 distinct shares (the threshold of the original split);
 * anything less than the true threshold K yields garbage without warning -
 * that is the security property of the scheme, not a bug.
 */
std::string reconstructSecret(const std::vector<std::string>& shares) {
  if (shares.size() < 2) throw std::invalid_argument("Need at least 2 shares to reconstruct");
  std::unordered_map<int, Bytes> byX;
  for (const auto& share : shares) {
    const ParsedShare parsed = parseShare(share);
    // The same share pasted twice is harmless (dedupe); a colliding
    // x-coordinate with a different payload cannot belong to one split.
    auto existing = byX.find(parsed.x);
    if (existing == byX.end()) {
      byX.emplace(parsed.x, parsed.y);
    } else if (existing->second != parsed.y) {
      char x[3];
      snprintf(x, sizeof(x), "%02x", parsed.x);
      throw std::invalid_argument("Two different shares both claim x=" + std::string(x) +
                                  " - they cannot come from the same split");
    }
  }
  std::vector<std::pair<int, Bytes>> points(byX.begin(), byX.end());
  std::sort(points.begin(), points.end(),
            [](const auto& a, const auto& b) { return a.first < b.first; });
  if (points.size() < 2) {
    throw std::invalid_argument("Need at least 2 distinct shares to reconstruct");
  }
  const std::size_t len = points[0].second.size();
  for (const auto& [x, y] : points) {
    if (y.size() != len) {
      throw std::invalid_argument("All shares must be the same length - they do not come from the same split");
    }
  }

  Bytes out(len);
  std::vector<Point> pair;
  for (const auto& [x, y] : points) pair.emplace_back(uint8_t(x), 0);
  for (std::size_t b = 0; b < len; b++) {
    for (std::size_t i = 0; i < points.size(); i++) pair[i].second = points[i].second[b];
    out[b] = interpolateAtZero(pair);
  }
  return std::string(out.begin(), out.end());  // UTF-8 bytes back to a string
}

}  // namespace secret_sharing