Разделение секрета: схема Шамира в связке с TweetNaCl.js

Криптографическая идея схемы

Схема разделения секрета Шамира основана на свойствах полиномов над конечными полями. Секрет интерпретируется как свободный член полинома степени t − 1, а каждая доля — как точка на этом полиноме.

Ключевые свойства:

  • восстановление секрета требует не менее t частей;
  • любые t − 1 частей не дают информации о секрете;
  • восстановление выполняется через интерполяцию Лагранжа.

В криптографической практике чаще всего используется поле GF(2^8) или простое поле GF(p). В связке с TweetNaCl.js удобнее работать с байтовыми массивами (Uint8Array) и реализовать операции в GF(256).

TweetNaCl.js и криптографические примитивы

TweetNaCl.js предоставляет низкоуровневые операции:

  • генерацию случайных байтов (nacl.randomBytes)
  • хэширование
  • симметричное и асимметричное шифрование

Сама библиотека не реализует схему Шамира, но предоставляет надежный источник энтропии и безопасную основу для криптографических конструкций.

Математическая модель

Секрет ( S ) разбивается через полином:

[ f(x) = S + a_1 x + a_2 x^2 + + a_{t-1} x^{t-1}]

Каждая доля:

[ (x_i, f(x_i))]

Восстановление через интерполяцию:

[ S = f(0)]

Работа в конечном поле GF(256)

Для практической реализации используется арифметика над байтами.

Основные операции:

  • сложение: XOR
  • умножение: логарифмы/экспоненты или таблицы
  • деление: обратное умножение

Простейший вариант — табличная реализация GF(256).

const GF256 = (() => {
  const exp = new Uint8Array(512);
  const log = new Uint8Array(256);

  let x = 1;
  for (let i = 0; i < 255; i++) {
    exp[i] = x;
    log[x] = i;
    x ^= x << 1;
    if (x & 0x100) x ^= 0x11d;
  }

  for (let i = 255; i < 512; i++) {
    exp[i] = exp[i - 255];
  }

  function mul(a, b) {
    if (a === 0 || b === 0) return 0;
    return exp[log[a] + log[b]];
  }

  function div(a, b) {
    if (a === 0) return 0;
    return exp[(log[a] + 255 - log[b]) % 255];
  }

  return { mul, div };
})();

Генерация коэффициентов полинома

Секрет разбивается на байты. Для каждого байта строится свой полином.

import nacl from "tweetnacl";

function randomCoefficients(t) {
  const coeffs = new Uint8Array(t);
  nacl.randomBytes(coeffs);
  return coeffs;
}

Формирование долей

Каждая доля — это пара (x, y), где x — индекс участника.

function evalPolynomial(coeffs, x) {
  let result = 0;
  let power = 1;

  for (let i = 0; i < coeffs.length; i++) {
    result ^= GF256.mul(coeffs[i], power);
    power = GF256.mul(power, x);
  }

  return result;
}

Разделение секрета

Секрет кодируется как массив байтов. Для каждого байта создаётся полином.

function splitSecret(secret, t, n) {
  const shares = Array.from({ length: n }, () => ({
    x: 0,
    y: new Uint8Array(secret.length),
  }));

  for (let i = 0; i < n; i++) {
    shares[i].x = i + 1;
  }

  for (let byteIndex = 0; byteIndex < secret.length; byteIndex++) {
    const coeffs = randomCoefficients(t);
    coeffs[0] = secret[byteIndex];

    for (let shareIndex = 0; shareIndex < n; shareIndex++) {
      const x = shares[shareIndex].x;
      shares[shareIndex].y[byteIndex] = evalPolynomial(coeffs, x);
    }
  }

  return shares;
}

Интерполяция Лагранжа

Восстановление секрета требует вычисления значения полинома в точке 0.

function lagrangeInterpolate(x, xs, ys) {
  let result = 0;

  for (let i = 0; i < xs.length; i++) {
    let numerator = 1;
    let denominator = 1;

    for (let j = 0; j < xs.length; j++) {
      if (i === j) continue;

      numerator = GF256.mul(numerator, x ^ xs[j]);
      denominator = GF256.mul(denominator, xs[i] ^ xs[j]);
    }

    const term = GF256.div(numerator, denominator);
    result ^= GF256.mul(ys[i], term);
  }

  return result;
}

Восстановление секрета

function recoverSecret(shares) {
  const length = shares[0].y.length;
  const secret = new Uint8Array(length);

  const xs = shares.map(s => s.x);

  for (let byteIndex = 0; byteIndex < length; byteIndex++) {
    const ys = shares.map(s => s.y[byteIndex]);
    secret[byteIndex] = lagrangeInterpolate(0, xs, ys);
  }

  return secret;
}

Использование TweetNaCl.js для защиты секретов

TweetNaCl.js применяется как источник криптографической стойкости:

  • генерация случайных коэффициентов
  • защита исходного секрета перед разделением
  • комбинация с шифрованием

Часто используется гибридная схема:

  1. секрет шифруется симметричным ключом
  2. ключ делится через Шамира
  3. данные хранятся отдельно

Гибридное шифрование и разделение ключа

Типовая схема:

  • nacl.secretbox шифрует данные
  • ключ 32 байта делится через Shamir
const key = nacl.randomBytes(32);
const nonce = nacl.randomBytes(24);

const encrypted = nacl.secretbox(message, nonce, key);
const shares = splitSecret(key, 3, 5);

Особенности реализации в JavaScript

Критические моменты:

  • отсутствие встроенной поддержки GF(256)
  • необходимость оптимизации операций XOR-ориентированных вычислений
  • контроль длины массивов
  • защита от утечки через слабую энтропию

Ошибки, возникающие в практических реализациях

Типовые проблемы:

  • использование Math.random() вместо криптографического генератора
  • некорректная реализация обратных элементов в поле
  • потеря байтов при сериализации долей
  • несогласованность типов (Buffer / Uint8Array)

Формат хранения долей

Часто используется структура:

{
  "x": 3,
  "y": "base64-encoded-bytes"
}

или бинарный формат:

  • 1 байт: индекс
  • N байт: значение доли

Масштабирование схемы

При увеличении размера секретов применяются оптимизации:

  • потоковая обработка байтов
  • предвычисление таблиц GF(256)
  • параллелизация по байтам
  • разделение на чанки фиксированного размера

Связка с современными WebCrypto подходами

TweetNaCl.js часто используется вместе с WebCrypto API:

  • WebCrypto: генерация случайных значений
  • TweetNaCl.js: совместимость и переносимость
  • Shamir: распределение ключей между участниками

Такая архитектура обеспечивает независимость от платформы и детерминированность восстановления секрета.

Оглавление