kcrypt3.c

// ---------------------------------------------------------------------------
//      KCrypt3 - 3rd iteration of the KCrypt algorithm.
//      Written on Sunday, 26th of January 2025 by Kamila Szewczyk.
// ---------------------------------------------------------------------------
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <stdlib.h>

// ---------------------------------------------------------------------------
//      Galois field tables and factorial cache.
// ---------------------------------------------------------------------------
typedef uint8_t gf;
typedef unsigned _BitInt(2048) uint2048_t;
static gf LOG[256], EXP[510], PROD[256][256];
static uint2048_t FACT[208];
static void gentab(uint8_t poly) {
  for (int l = 0, b = 1; l < 255; l++) {
    LOG[b] = l;  EXP[l] = EXP[l + 255] = b;
    if ((b <<= 1) >= 256)
      b = (b - 256) ^ poly;
  }
  for (int i = 1; i < 256; i++)
    for (int j = 1; j < 256; j++)
      PROD[i][j] = EXP[LOG[i] + LOG[j]];
  int k = 0;
  for (FACT[k] = 1; ++k < 208; FACT[k] = FACT[k - 1] * k);
}
#define gf_mul(a, b) PROD[a][b]
static uint8_t gf_div(uint8_t a, uint8_t b) {
  if (!a || !b) return 0;
  int d = LOG[a] - LOG[b];
  return EXP[d < 0 ? d + 255 : d];
}

// ---------------------------------------------------------------------------
//      Lagrange interpolation and Horner's method in the Galois field.
//      Uses the optimised (numerically unstable) quadratic-time algorithm.
// ---------------------------------------------------------------------------
static void lagrange(gf * x, gf * y, int n, gf * coef) {
  gf c[n + 1]; memset(c, 0, sizeof(gf) * (n + 1)); c[0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = i; j > 0; j--)
      c[j] = c[j - 1] ^ gf_mul(c[j], x[i]);
    c[0] = gf_mul(c[0], x[i]);  c[i + 1] = 1;
  }
  gf P[n]; memset(P, 0, sizeof(gf) * n);
  for (int i = 0; i < n; i++) {
    gf d = 1, t;
    for (int j = 0; j < n; j++)
      if (i != j) d = gf_mul(d, x[i] ^ x[j]);
    t = gf_div(y[i], d);
    coef[n-1] ^= gf_mul(t, P[n-1] = 1);
    for (int j = n - 2; j >= 0; j--)
      coef[j] ^= gf_mul(t, P[j] = c[j+1] ^ gf_mul(x[i], P[j+1]));
  }
}

static gf horner(gf * coef, int n, gf x) {
  gf result = coef[n];
  for (int i = n - 1; i >= 0; i--)
    result = gf_mul(x, result) ^ coef[i];
  return result;
}

// ---------------------------------------------------------------------------
//      Generates the field permutation for the associated index (key)
//      using the factorial number system.
// ---------------------------------------------------------------------------
static void key_perm(gf perm[208], uint2048_t i) {
  int j, k;
  for (k = 0; k < 208; ++k) {
    perm[k] = i / FACT[208 - 1 - k];
    i = i % FACT[208 - 1 - k];
  }
  for (k = 208 - 1; k > 0; --k)
    for (j = k - 1; j >= 0; --j)
      if (perm[j] <= perm[k])
        perm[k]++;
  for (k = 0; k < 208; ++k)
    perm[k] += 48;
}

// ---------------------------------------------------------------------------
//      Block encoders/decoders.
// ---------------------------------------------------------------------------
typedef struct { uint32_t k3[3]; uint2048_t pi; } block_key_t;

static void encode_block(gf in[32], gf out[32],
    uint32_t IV, block_key_t key) {
  gf x[48], y[48], coeff[48] = { 0 }, perm[208];
  for (int i = 0; i < 48; i++) x[i] = i;
  for (int i = 0; i < 32; i++) y[i] = in[i];
  for (int i = 0; i < 4; i++) y[32 + i] = (IV >> (i * 8)) & 0xff;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 4; j++)
      y[36 + j + i * 4] = (key.k3[i] >> (j * 8)) & 0xff;
  lagrange(x, y, 48, coeff); key_perm(perm, key.pi);
  for (int i = 0; i < 32; i++) out[i] = horner(coeff, 47, perm[207 - i]);
}

static void decode_block(gf in[32], gf out[32],
    uint32_t IV, block_key_t key) {
  gf x[48], y[48], coeff[48] = { 0 }, perm[208];
  key_perm(perm, key.pi);
  for (int i = 0; i < 16; i++) x[i] = i + 32;
  for (int i = 0; i < 4; i++) y[i] = (IV >> (i * 8)) & 0xff;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 4; j++)
      y[4 + j + i * 4] = (key.k3[i] >> (j * 8)) & 0xff;
  for (int i = 0; i < 32; i++)
    x[i + 16] = perm[207 - i], y[i + 16] = in[i];
  lagrange(x, y, 48, coeff);
  for (int i = 0; i < 32; i++) out[i] = horner(coeff, 47, i);
}

// ---------------------------------------------------------------------------
//      Secure randomness source. Supports Windows, DOS and Unix systems.
// ---------------------------------------------------------------------------
#ifdef _WIN32
#include <windows.h>
static void secrandom(void * buf, size_t len) {
  HCRYPTPROV hp;
  CryptAcquireContext(&hp, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  CryptGenRandom(hp, len, buf);
  CryptReleaseContext(hp, 0);
}
#elif __unix__
#include <fcntl.h>
#include <unistd.h>
static void secrandom(void * buf, size_t len) {
  int fd = open("/dev/urandom", O_RDONLY);
  if (fd < 0) {
    fprintf(stderr, "? /dev/urandom %s", strerror(errno)); exit(1);
  }
  read(fd, buf, len);
  close(fd);
}
#elif __MSDOS__
static void secrandom(void * buf, size_t len) { // Doug Kaufman's NOISE.SYS
  FILE * f = fopen("/dev/urandom$", "rb");
  if (!f) {
    fprintf(stderr, "? /dev/urandom$ %s", strerror(errno)); exit(1);
  }
  fread(buf, 1, len, f);
  fclose(f);
}
#endif

// ---------------------------------------------------------------------------
//      CTR mode of operation. Assumes buffers are aligned to 32 bytes.
// ---------------------------------------------------------------------------
#define ROTL2K(x, b) (uint2048_t)(((x) << (b)) | ((x) >> (2048 - (b))))

static void encode_ctr(gf * in, gf * out, uint32_t len, block_key_t key) {
  uint32_t IV; secrandom(&IV, 4);
  for (int i = 0; i < 4; i++) out[i] = (len >> (i * 8)) & 0xff;
  for (int i = 0; i < 4; i++) out[4 + i] = (IV >> (i * 8)) & 0xff;
  out += 8;
  for (size_t i = 0; i < len; i += 32) {
    encode_block(in + i, out + i, IV, key);
    IV++; key.pi = ROTL2K(key.pi, 1) + 1;
  }
}

static uint32_t decode_ctr(gf * in, gf * out, block_key_t key) {
  uint32_t IV = 0, len = 0;
  for (int i = 0; i < 4; i++) len |= in[i] << (i * 8);
  for (int i = 0; i < 4; i++) IV |= in[4 + i] << (i * 8);
  in += 8;
  for (size_t i = 0; i < len; i += 32) {
    decode_block(in + i, out + i, IV, key);
    IV++; key.pi = ROTL2K(key.pi, 1) + 1;
  }
  return len;
}

// ---------------------------------------------------------------------------
//      Command-line stub.
// ---------------------------------------------------------------------------
static uint32_t file_size(FILE * f) {
  fseek(f, 0, SEEK_END);
  uint32_t size = ftell(f);
  fseek(f, 0, SEEK_SET);
  return size;
}

#define E(x, y) \
  if(x) { fprintf(stderr, "? %s %s", y, strerror(errno)); return 1; }

int main(int argc, char * argv[]) {
  gentab(0x1d);
  if (argc < 2) {
    fprintf(stderr, "kcrypt3 [e|d|g]\n"); return 1;
  }
  switch(argv[1][0]) {
    case 'e': case 'd': {
      if (argc < 5) {
        fprintf(stderr,
          "kcrypt3 %c <key_file> <input_file> <output_file>\n", argv[1][0]);
        return 1;
      }
      FILE * key_file = fopen(argv[2], "rb"); E(!key_file, argv[2]);
      FILE * in_file = fopen(argv[3], "rb"); E(!in_file, argv[3]);
      FILE * out_file = fopen(argv[4], "wb"); E(!out_file, argv[4]);
      block_key_t key; E(fread(&key, sizeof(block_key_t), 1, key_file) != 1, argv[2]);
      uint32_t len = file_size(in_file);
      gf * in = malloc(len + 32), * out = malloc(len + 32);
      if (argv[1][0] == 'e') {
        E(fread(in, 1, len, in_file) != len, argv[3]);
        encode_ctr(in, out, len, key);
        E(fwrite(out, 1, len + 32, out_file) != len + 32, argv[4]);
      } else {
        E(fread(in, 1, len, in_file) != len, argv[3]);
        len = decode_ctr(in, out, key);
        E(fwrite(out, 1, len, out_file) != len, argv[4]);
      }
      free(in);  free(out);
      E(fclose(in_file), argv[3]);
      E(fclose(out_file), argv[4]);
      E(fclose(key_file), argv[2]);
      break;
    }
    case 'g': {
      if (argc < 3) {
        fprintf(stderr, "kcrypt3 g <key_file>\n"); return 1;
      }
      FILE * key_file = fopen(argv[2], "wb"); E(!key_file, argv[2]);
      block_key_t key;
      secrandom(&key, sizeof(block_key_t));
      E(fwrite(&key, sizeof(block_key_t), 1, key_file) != 1, argv[2]);
      E(fclose(key_file), argv[2]);
      break;
    }
    default: {
      fprintf(stderr, "? %s", argv[1]);
      return 1;
    }
  }
}