Подтвердить что ты не робот

С++ обрабатывает очень большие целые числа

Я использую алгоритм RSA для шифрования/дешифрования и для расшифровки файлов, с которыми вам приходится иметь дело с некоторыми довольно большими значениями. Более конкретно, такие вещи, как

P = C^d % n
  = 62^65 % 133

Теперь это действительно единственные расчеты, которые плохо делают. Я пробовал использовать библиотеку BigInteger от Matt McCutchen, но при связывании получаю много ошибок компилятора, таких как:

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

Итак, мне было интересно, как лучше всего будет обрабатывать действительно большие целые числа, которые выходят из алгоритма RSA.

Я слышал, что возможно было бы объявить ваши переменные как double long, поэтому...

long long decryptedCharacter;

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


Ну, например, я пытаюсь скомпилировать и запустить следующую программу с помощью dev С++:

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

тогда я получаю эти ошибки.

Derek, я подумал, что включив файл BigIntegerLibrary.hh, что компилятор выполнит и скомпилирует все необходимые файлы, которые он будет использовать.

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

4b9b3361

Ответ 1

Мета-ответ:

Если вы используете библиотеку для арифметики bigint, спросите себя, почему вы не используете библиотеку для всей реализации RSA.

Например, http://www.gnu.org/software/gnu-crypto/ содержит реализацию RSA. Он имеет ту же лицензию, что и GMP.

Однако они не имеют такой же лицензии, как http://mattmccutchen.net/bigint/, которая, как мне представляется, была помещена в общедоступное США.

Ответ 2

Я бы предложил использовать gmp, он может обрабатывать произвольно длинные int и имеет приличные привязки С++.

afaik на текущем аппаратном/программном обеспечении long longs составляет 64 бит, поэтому unsigned может обрабатывать номера до (2 ** 64) -1 == 18446744073709551615, что немного меньше, чем номера, с которыми вам придется иметь дело с RSA.

Ответ 3

Tomek, похоже, что вы неправильно связываетесь с кодом BigInteger. Я думаю, вы должны решить эту проблему, а не искать новую библиотеку. Я взглянул на источник, и BigInteger::BigInteger(int) определенно определен. Краткий взгляд показывает, что остальные тоже.

Ошибки ссылок, которые вы получаете, подразумевают, что вы либо пренебрегаете компиляцией источника BigInteger, либо пренебрегаете включением результирующих объектных файлов при связывании. Обратите внимание, что источник BigInteger использует расширение "cc", а не "cpp", поэтому убедитесь, что вы также компилируете эти файлы.

Ответ 4

Чтобы увидеть размер длинного длинного, попробуйте следующее:

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

На моей машине он возвращает 8, что означает 8 байтов, которые могут хранить 2 ^ 64 значения.

Ответ 5

Для RSA вам нужна библиотека bignum. Номера слишком велики, чтобы вписаться в 64-битный длинный. У меня когда-то был коллега в университете, которому было поручено реализовать RSA, в том числе построить свою собственную библиотеку bignum.

Как это происходит, у Python есть библиотека бигмуна. Написание обработчиков bignum достаточно мал, чтобы вписаться в задание на компьютерную науку, но все же имеет достаточно gotchas, чтобы сделать его нетривиальной задачей. Его решение состояло в том, чтобы использовать библиотеку Python для генерации тестовых данных для проверки его библиотеки bignum.

Вы можете получить другие библиотеки bignum.

В качестве альтернативы попробуйте реализовать прототип в Python и посмотрите, достаточно ли он достаточно.

Ответ 6

Если вы не внедряете RSA в качестве школьного задания или чего-то еще, я бы предложил посмотреть библиотеку crypto ++ http://www.cryptopp.com

Просто так легко реализовать криптографические файлы.

Ответ 7

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

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}

Ответ 8

Существует более безопасная реализация RSA, чем просто большие числа. Простая реализация RSA имеет тенденцию утечки частной информации через боковые каналы, особенно время (в простых словах: время вычисления зависит от обработанных данных, что позволяет злоумышленнику восстанавливать некоторые, возможно, все биты частного ключа). Хорошие реализации RSA реализуют контрмеры.

Кроме модульного возведения в степень, существует целый бизнес дополнений, который не является концептуально трудным, но, как и весь код ввода/вывода и анализа, есть место для тонких ошибок. Самый простой код для записи - это код, который уже был написан кем-то другим.

Еще один момент заключается в том, что после того, как ваш код RSA будет запущен и запущен, вы можете начать просмотр расширений и других ситуаций, например. "Что делать, если закрытый ключ, который я хочу использовать, находится не в ОЗУ, а в смарт-карте?". Некоторые существующие реализации RSA на самом деле являются API, которые могут справиться с этим. В мире Microsoft вы хотите найти CryptoAPI, который интегрирован в Windows. Вы также можете посмотреть NSS, что браузер Firefox использует для SSL.

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

Ответ 9

Я попробовал бы библиотеку GMP - она ​​надежная, хорошо протестированная и обычно используемая для этого типа кода.

Ответ 10

Openssl также имеет тип Bignum, который вы можете использовать. Я использовал его, и он работает хорошо. Легко обернуть на языке оо, например С++ или objective-C, если хотите.

https://www.openssl.org/docs/crypto/bn.html

Кроме того, если вы не знали, чтобы найти ответ на уравнение этой формы x ^ y% z, найдите алгоритм, называемый модульным возведением в степень. Большинство библиотек crypto или bignum будут иметь функцию специально для этого вычисления.

Ответ 11

Длинный int обычно представляет собой 64 бита, которых, вероятно, недостаточно для обработки целого числа, большого. Вероятно, вам понадобится библиотека bigint.

См. также этот вопрос о переполнении стека

Ответ 12

Проверьте свою компиляторную документацию. Некоторые компиляторы имеют типы, такие как __int64, которые дают вам свой размер. Возможно, у вас есть некоторые из них.

Ответ 13

Только для того, чтобы отметить: __int64 и long long являются нестандартными расширениями. Ни один из них не поддерживается всеми компиляторами С++. С++ основан на C89 (он вышел в 98, поэтому он не может быть основан на C99)

(C поддерживает "длинный длинный" с C99)

Кстати, я не думаю, что 64-битные целые числа решают эту проблему.

Ответ 14

Тот факт, что у вас есть проблема с использованием библиотеки biginteger, не означает, что это плохой подход.

Использование долгого времени, безусловно, плохой подход.

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

Ответ 15

У меня был большой успех, используя библиотеку LibTomCrypt для моих криптографических потребностей. Он быстрый, тощий и портативный. Он может сделать ваш RSA для вас или просто обработать математику, если вы хотите.

Ответ 16

Я использовал GMP, когда я написал реализацию RSA.