Получить конгруэнцию алгоритма RSA javascript для больших чисел - PullRequest
Новая
       34

Получить конгруэнцию алгоритма RSA javascript для больших чисел

0 голосов
/ 28 сентября 2019

В алгоритме асимметричной криптографии RSA каждый пользователь имеет открытый ключ ( n , e ) и закрытый ключ ( d ) для отправки и получения в зашифрованном виде.сообщения от других пользователей.

Для шифрования сообщения он заменяет символы на их коды ascii: 

HELLO -> 72-69-76-76-79

и отправляет сообщение в зашифрованном виде с помощью RSA ( c ), должен вычислять 

c = m^e % n

для каждого символа m в сообщении с использованием открытых ключей n и e .

для расшифровки сообщения, которое получает пользователь, необходимо рассчитать: 

m = c^d % n (is the same to say m is congruent to c^d mod n)

для каждого номера c присвоением секретного ключа d .

Немногопример:

пользователь Beto получил открытые ключи: 

n = 64523 
e = 127

и его закрытый ключ: 

d = 15583

, если какой-либо пользователь хочет отправить сообщение в Beto: 

ABAC -> 65-66-65-67

чтобы зашифровать сообщение, которое пользователь должен был вычислить 

65^127 % 64523 = 27725
66^127 % 64523 = 6407
65^127 % 64523 = 27725
67^127 % 64523 = 2523

, а зашифрованный код был 27725-6407-27725-2523

Чтобы расшифровать сообщение пришлосьрассчитать: 

27725^15583 % 64523 = 65
6407^15583 % 64523 = 66
27725^15583 % 64523 = 65
2523^15583 % 64523 = 67

и он получил расшифрованное сообщение 65-66-65-67 => ABAC.

Теперь вопрос:

У меня есть этот код длярешить последнюю часть, но я не могу использовать ее с большими числами (как в примере): 

function getCongruence(c, d, n) {
  return Math.pow(c,d) % n;
}

console.log(getCongruence(5,3,7)); // = 6 cuz 5^3=125 and 125 % 7 => 125 - 7*17 = 125 -119
console.log(getCongruence(19,11,17)); // = 8 cuz 19^11=116490258898219 % 17 = 8
console.log(getCongruence(27725,15583,64523)); // should be 65 but it shows NaN
.as-console-wrapper { max-height: 100% !important; top: 0; }

Как получить результат, если использовать большие числа?

Могу ли я использовать другой алгоритм, чтобы найти ответ?

есть библиотека, которую я могу использовать для этого?

1 Ответ

1 голос
/ 28 сентября 2019

Редактировать

Согласно предложению @ Гарольда, итеративное возведение в квадрат по квадратуре - самый быстрый способ приблизиться к этому, я оставлю свой оригинальный наивный рекурсивный метод ниже для сравнения.

Редактировать 2

Добавлена ​​функция для обработки инверсии BigInt для очень маленьких чисел.Использовал предложение @ harold для перемещения сокращения по модулю внутри функции для повышения производительности.

Итеративное возведение в степень путем возведения в квадрат: 

const handleBigInverse = x => {
  const stringX = x.toString();

  if (stringX.length > 21) {
    const approximate = Number(stringX.slice(0, 21));
    const e = stringX.length - 21;

    const inverse = 1 / approximate;
    const inverseString = inverse.toString();

    const splitString = inverseString.split("e");
    splitString[1] = (Number(splitString[1]) - e).toString();

    return splitString.join("e");
  } else {
    const inverse = 1 / Number(x);
    return inverse.toString();
  }
};

const iterativeExpBySqWithMod = (x, n, mod) => {
  let bigX = BigInt(x);
  let bigN = BigInt(n);

  if (n < 0) {
    if (!mod || Math.abs(mod) >= 1) {
      return handleBigInverse(iterativeExpBySqWithMod(x, -n));
    } else {
      return (
        handleBigInverse(iterativeExpBySqWithMod(x, -n)) % mod
      ).toString();
    }
  }
  if (mod) {
    const bigMod = BigInt(mod);
    let result = BigInt(1);

    while (bigN > 0) {
      if (bigN % BigInt(2) == 1) {
        result = (result * bigX) % bigMod;
      }
      bigX = (bigX * bigX) % bigMod;
      bigN /= BigInt(2);
    }
    return result;
  } else {
    let result = BigInt(1);
    while (bigN > 0) {
      if (bigN % BigInt(2) == 1) {
        result *= bigX;
      }
      bigX *= bigX;
      bigN /= BigInt(2);
    }
    return result;
  }
};

// Big numbers output a bigInt
console.log(iterativeExpBySqWithMod(27725, 15583, 64523)); //65n

// Small numbers output a string
console.log(iterativeExpBySqWithMod(72552, -50102)); //"5.550317946486025e-243529"

Наивная рекурсивная:

Настройка maxStack параметр в зависимости от среды, в которой он будет работать: 

function getCongruence(c, d, n, maxStack) {
  return getPow(BigInt(c), BigInt(d), BigInt(maxStack)) % BigInt(n);
}

const recursivePow = (value, exponent, total) => {
  if (exponent > 1) {
    exponent--;
    return recursivePow(value, exponent, total) * value;
  } else {
    if (total) {
      return total * value;
    } else {
      return value;
    }
  }
};

const getPow = (value, exponent, maxStack) => {
  let total = BigInt(0);

  while (exponent > maxStack) {
    total = recursivePow(value, maxStack, total);
    exponent -= maxStack;
  }
  return recursivePow(value, exponent, total);
};

console.log(getCongruence(27725, 15583, 64523, 3000)); //65n
...