sss.c

#include <stdint.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

uint8_t gf256_add(uint8_t x, uint8_t y) {
  return x ^ y;
}

uint8_t gf256_sub(uint8_t x, uint8_t y) {
  return x ^ y;
}

uint8_t gf256_mul(uint8_t x, uint8_t y) {
  uint8_t r = 0;
  for(int i = 0; i < 8; ++i) {
    r ^= (x * (y & 1));
    x = (x << 1) ^ ((x >> 7) * 0x1b);
    y >>= 1;
  }
  return r;
}

uint8_t gf256_div(uint8_t x, uint8_t y) {
  assert(y != 0);
  uint8_t r = 0;
  uint8_t res;
  do {
    if (gf256_mul(r, y) == x) {
      res = r;
    }
    r++;
  } while(r);
  return res;
}

void lagrange_interpolation(int M, uint8_t *x, uint8_t *y, uint8_t out[32])
{
  memset(out, 0, 32);
  for (int i = 0; i < M; ++i) {
    uint8_t l = 1;
    for (int j = 0; j < M; ++j) {
      if (i != j) {
        l = gf256_div(gf256_mul(l, x[j]), gf256_sub(x[i], x[j]));
      }
    }
    for(int j = 0; j < 32; ++j) {
      out[j] = gf256_add(out[j], gf256_mul(l, y[i * 32 + j]));
    }
  }
}