Генерация случайного большого простого числа с помощью forge (или другого подхода JavaScript)

Мне нужно генерировать случайное большое (около 4096 бит) простое число в JavaScript, и я уже использую forge. Forge должен иметь своего рода генератор для таких задач, поскольку он реализует RSA, который также опирается на случайные простые числа. Однако я не нашел что-то в документации к кузнице, когда вы просто хотите получить случайное простое число (что-то вроде var myRandomPrime = forge.random.getPrime(4096); было бы здорово).

Итак, что будет лучшим подходом для получения такого простого (с или без подделки) в JavaScript?

Источник

3 ответа

Решение

Обновление 06/11/2014: Теперь с версией кузницы 0.6.6 вы можете использовать это:

var bits = 1024;
forge.prime.generateProbablePrime(bits, function(err, num) {
    console.log('random prime', num.toString(16));
});

Найти большие простые числа в JavaScript сложно - это медленно, и вы не хотите блокировать основной поток. Для правильной работы требуется некоторый достаточно настраиваемый код, а код в forge специализирован для генерации ключа RSA. Нет никакого вызова API, чтобы просто произвести большое случайное простое число.

Есть некоторые дополнительные операции, которые выполняет код RSA в forge, которые вам не нужны, если вы просто ищете одно простое число. При этом самая медленная часть процесса заключается в том, чтобы найти простые числа, а не в этих дополнительных операциях. Тем не менее, код RSA также генерирует два простых числа (когда вам нужен только один), и они не имеют тот же размер битов, который вы ищете. Поэтому, если вы используете API-интерфейс forge, вам нужно будет передать битовый размер 8196 (я полагаю... это не в моей голове, так что это может быть неточно), чтобы получить 4096-битное простое число.

Один из способов найти большое случайное простое число заключается в следующем:

  1. Создайте случайное число, которое имеет желаемое количество битов (убедитесь, что установлен MSB).
  2. Выровняйте число на границе 30k+1, так как все простые числа имеют это свойство.
  3. Запустите тест на простоту (медленная часть) на вашем номере; если это пройдет, вы сделали, если нет, добавьте к числу, чтобы добраться до следующих 30k+1 границы и повторите. "Быстрый" тест на простоту состоит в проверке на малые простые числа и последующем использовании Миллера-Рабина (см. Руководство по прикладной криптографии 4.24).

Шаг № 3 может выполняться долго - и это обычно довольно нежелательно для JavaScript (с узлом или в браузере). Чтобы смягчить это, вы можете попытаться ограничить количество времени, затрачиваемое на тестирование простоты, до некоторого приемлемого периода времени (N миллисекунд) или вы можете использовать Web Workers для фонового процесса. Конечно, оба эти подхода усложняют код.

Вот некоторый код для генерации 4096-битного случайного простого числа, которое не должно блокировать основной поток:

var forge = require('node-forge');
var BigInteger = forge.jsbn.BigInteger;

// primes are 30k+i for i = 1, 7, 11, 13, 17, 19, 23, 29
var GCD_30_DELTA = [6, 4, 2, 4, 2, 4, 6, 2];
var THIRTY = new BigInteger(null);
THIRTY.fromInt(30);

// generate random BigInteger
var num = generateRandom(4096);

// find prime nearest to random number
findPrime(num, function(num) {
  console.log('random', num.toString(16));
});

function generateRandom(bits) {
  var rng = {
    // x is an array to fill with bytes
    nextBytes: function(x) {
      var b = forge.random.getBytes(x.length);
      for(var i = 0; i < x.length; ++i) {
        x[i] = b.charCodeAt(i);
      }
    }
  };
  var num = new BigInteger(bits, rng);

  // force MSB set
  var bits1 = bits - 1;
  if(!num.testBit(bits1)) {
    var op_or = function(x,y) {return x|y;};
    num.bitwiseTo(BigInteger.ONE.shiftLeft(bits1), op_or, num);
  }

  // align number on 30k+1 boundary
  num.dAddOffset(31 - num.mod(THIRTY).byteValue(), 0);

  return num;
}

function findPrime(num, callback) {
  /* Note: All primes are of the form 30k+i for i < 30 and gcd(30, i)=1. The
  number we are given is always aligned at 30k + 1. Each time the number is
  determined not to be prime we add to get to the next 'i', eg: if the number
  was at 30k + 1 we add 6. */
  var deltaIdx = 0;

  // find prime nearest to 'num' for 100ms
  var start = Date.now();
  while(Date.now() - start < 100) {
    // do primality test (only 2 iterations assumes at
    // least 1251 bits for num)
    if(num.isProbablePrime(2)) {
      return callback(num);
    }
    // get next potential prime
    num.dAddOffset(GCD_30_DELTA[deltaIdx++ % 8], 0);
  }

  // keep trying (setImmediate would be better here)
  setTimeout(function() {
    findPrime(num, callback);
  });
}

Можно настроить различные настройки, чтобы настроить его в соответствии с вашими потребностями, например, установить количество времени (которое является лишь оценкой) для запуска тестера простоты, прежде чем отправиться в суд, чтобы повторить попытку следующего запланированного такта. Вы, вероятно, захотите какую-то обратную связь UI каждый раз, когда он освобождается. Если вы используете узел или браузер, который поддерживает setImmediate Вы можете использовать это вместо setTimeout также, чтобы избежать зажима, чтобы ускорить вещи. Но обратите внимание, что на создание 4096-битного случайного простого числа в JavaScript потребуется некоторое время (по крайней мере, на момент написания этой статьи).

Forge также имеет реализацию Web Worker для генерации ключей RSA, которая предназначена для ускорения процесса, позволяя нескольким потокам запускать тест на простоту с использованием различных входных данных. Вы можете посмотреть на источник кузницы (prime.worker.js например), чтобы увидеть это в действии, но это сам по себе проект для правильной работы. ИМО, тем не менее, это лучший способ ускорить процесс.

В любом случае, надеюсь, приведенный выше код поможет вам. Я бы запустил его с меньшим размером, чтобы проверить это.

Источник

Он выполняет больше работы, чем вам требуется, но вы всегда можете использовать forge для генерации пары ключей и извлечения из нее одного из простых чисел.

//generate a key pair of required size
var keyPair = forge.pki.rsa.generateKeyPair(4096);

//at this point we have 2 primes p and q in the privateKey
var p = keyPair.privateKey.p;
var q = keyPair.privateKey.q;

Тип р и д BigInteger они имеют p.toByteArray() метод для доступа к их представлениям в виде байтового массива.

Источник

Если вы решите реализовать свой собственный метод, вы можете прочитать " Близко к генерации простых чисел с меньшим числом случайных битов", в котором есть обсуждение и алгоритмы для более быстрой генерации хорошо распределенных больших n-битных простых чисел. Публикация FIPS 186-4 также содержит много информации, включая алгоритмы для проверенной простой конструкции Шоу-Тейлора.

В ответе Длонгли используется метод "PRIMEINC", который эффективен, но не является хорошим распределением (это может иметь или не иметь значение для вас, и в любом случае он получил хорошую основу для использования). Обратите внимание, что FIPS рекомендует множество тестов MR (это может быть смягчено, если ваша библиотека включает тест Lucas или BPSW).

Относительно проверенных простых чисел, мой опыт использования GMP заключается в том, что, по крайней мере, до 8192 битов, и Shawe-Taylor, и Maurer FastPrime работают медленнее, чем при использовании алгоритма Фуке и Тибучи A1 в сочетании с BPSW + дополнительные тесты MR. Ваш пробег может варьироваться, и, конечно, проверенные простые методы в результате получают проверенное простое число.

Источник
Другие вопросы по тегам