Shamir's Secret Sharing — Ruby source

# Secret Sharing — Shamir's Secret Sharing over GF(256), the Galois field of
# 256 elements.
#
# Language: Ruby (3.1+, standard library only)
# Source:   CosmoDev polyglot showcase port of the Secret Sharing tool,
#           ported from src/lib/secret-sharing.ts (the canonical TypeScript
#           implementation).
# License:  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).

require 'securerandom'

module SecretSharing
  # A parsed share: its x-coordinate and its per-byte polynomial evaluations.
  ParsedShare = Struct.new(:x, :y, keyword_init: true)

  # Exponent table: GF256_EXP[i] = 3^i in GF(256). Index 255 mirrors index 0.
  GF256_EXP = Array.new(256, 0)
  # Discrete log table: GF256_LOG[3^i] = i (GF256_LOG[0] is unused).
  GF256_LOG = Array.new(256, 0)

  class << self
    # Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime".
    def xtime(a)
      ((a << 1) ^ ((a & 0x80).zero? ? 0 : 0x11b)) & 0xff
    end
  end

  # Build the log/exp tables from the generator 3.
  x = 1
  255.times do |i|
    GF256_EXP[i] = x
    GF256_LOG[x] = i
    # step to the next power of the generator 3: x *= 3 (i.e. x ^ xtime(x))
    x ^= xtime(x)
  end
  # 3 has order 255, so EXP wraps: EXP[255] === EXP[0].
  GF256_EXP[255] = 1

  class << self
    # Addition in GF(256) is bitwise XOR (also serves as subtraction).
    def gf_add(a, b)
      (a ^ b) & 0xff
    end

    # Multiply two field elements via log/exp tables.
    def gf_mul(a, b)
      return 0 if a.zero? || b.zero?

      GF256_EXP[(GF256_LOG[a] + GF256_LOG[b]) % 255]
    end

    # Multiplicative inverse of a non-zero element.
    def gf_inv(a)
      raise ArgumentError, '0 has no multiplicative inverse in GF(256)' if a.zero?

      GF256_EXP[(255 - GF256_LOG[a]) % 255]
    end

    # Divide a by b in GF(256).
    def gf_div(a, b)
      raise ArgumentError, 'Division by zero in GF(256)' if b.zero?
      return 0 if a.zero?

      GF256_EXP[(GF256_LOG[a] + 255 - GF256_LOG[b]) % 255]
    end

    # Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style.
    def eval_poly(coeffs, x)
      y = 0
      (coeffs.length - 1).downto(0) do |i|
        y = gf_add(gf_mul(y, x), coeffs[i])
      end
      y
    end

    # 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.
    def interpolate_at_zero(points)
      result = 0
      points.each_with_index do |(xj, yj), j|
        weight = 1
        points.each_with_index do |(_xm, _ym), m|
          next if m == j

          xm = points[m][0]
          weight = gf_mul(weight, gf_div(xm, xj ^ xm))
        end
        result = gf_add(result, gf_mul(yj, weight))
      end
      result
    end

    # Split a secret into total_shares 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. opts[:get_random_bytes] is injectable for deterministic tests.
    def split_secret(secret, total_shares, threshold, opts = {})
      assert_int('Total shares', total_shares)
      assert_int('Threshold', threshold)
      if threshold < 2
        raise ArgumentError,
              'Threshold must be at least 2 (a 1-of-N split is just the secret itself)'
      end
      if total_shares > 255
        raise ArgumentError,
              'Total shares must be at most 255 (share x-coordinates live in 1..255)'
      end
      if threshold > total_shares
        raise ArgumentError,
              "Threshold (#{threshold}) cannot exceed total shares (#{total_shares})"
      end

      bytes = secret.encode('UTF-8').bytes
      rand_fn = opts[:get_random_bytes] || ->(n) { SecureRandom.random_bytes(n).bytes }
      y_parts = Array.new(total_shares) { Array.new(bytes.length, 0) }
      coeffs = Array.new(threshold, 0)

      bytes.each_index do |b|
        coeffs[0] = bytes[b]
        rand_fn.call(threshold - 1).each_with_index { |v, i| coeffs[i + 1] = v } if threshold > 1
        (1..total_shares).each do |i|
          y_parts[i - 1][b] = eval_poly(coeffs, i)
        end
      end

      y_parts.each_with_index.map do |ys, idx|
        format('%02x', idx + 1) + '-' + ys.pack('C*').unpack1('H*')
      end
    end

    # Parse one "xx-hex" share string; raises on any malformed input.
    def parse_share(share)
      s = share.strip
      if s.index('-') != 2 || !s[0, 2].match?(/\A[0-9a-fA-F]{2}\z/)
        raise ArgumentError,
              %(Malformed share "#{s}" - expected the format "xx-hex…" (e.g. "01-a3b2c1"))
      end
      y_hex = s[3..]
      if !y_hex.match?(/\A[0-9a-fA-F]*\z/) || y_hex.length.odd?
        raise ArgumentError,
              %(Malformed share "#{s}" - the payload must be an even-length hex string)
      end
      x = s[0, 2].to_i(16)
      if x.zero?
        raise ArgumentError, 'Share x-coordinate 00 is invalid - shares are numbered from 01'
      end

      ParsedShare.new(x: x, y: [y_hex].pack('H*').bytes)
    end

    # 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.
    def reconstruct_secret(shares)
      raise ArgumentError, 'Need at least 2 shares to reconstruct' if shares.length < 2

      by_x = {}
      shares.each do |share|
        parsed = parse_share(share)
        # The same share pasted twice is harmless (dedupe); a colliding
        # x-coordinate with a different payload cannot belong to one split.
        existing = by_x[parsed.x]
        if existing.nil?
          by_x[parsed.x] = parsed.y
        elsif existing != parsed.y
          raise ArgumentError,
                "Two different shares both claim x=#{format('%02x', parsed.x)}" \
                ' - they cannot come from the same split'
        end
      end

      points = by_x.to_a.sort { |a, b| a[0] <=> b[0] }
      if points.length < 2
        raise ArgumentError, 'Need at least 2 distinct shares to reconstruct'
      end

      len = points[0][1].length
      if points.any? { |(_x, y)| y.length != len }
        raise ArgumentError,
              'All shares must be the same length - they do not come from the same split'
      end

      out = Array.new(len, 0)
      pair = points.map { |(x, _y)| [x, 0] }
      len.times do |b|
        points.each_with_index { |(_x, y), i| pair[i][1] = y[b] }
        out[b] = interpolate_at_zero(pair)
      end
      out.pack('C*').force_encoding(Encoding::UTF_8)
    end

    private

    def assert_int(name, v)
      return if v.is_a?(Integer)

      raise ArgumentError, "#{name} must be an integer (got #{v})"
    end
  end
end