C ++ обрабатывает очень большие целые числа - PullRequest
Новая
       73

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

20 голосов
/ 24 сентября 2008

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

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

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

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.

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

long long decryptedCharacter;

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

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

#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;
}

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

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

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

Ответы [ 16 ]

23 голосов
/ 24 сентября 2008

Мета-ответ:

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

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

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

12 голосов
/ 24 сентября 2008

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

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

12 голосов
/ 24 сентября 2008

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

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

4 голосов
/ 24 сентября 2008

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

#include <stdio.h>

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

    return 0;
}

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

3 голосов
/ 25 февраля 2010

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

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

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

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

3 голосов
/ 25 февраля 2010

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

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); 
      }
  }
}
3 голосов
/ 24 сентября 2008

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

Просто так плохо реализовать криптовалюту.

3 голосов
/ 24 сентября 2008

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

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

Вы должны быть в состоянии получить другие библиотеки bignum.

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

2 голосов
/ 24 сентября 2008

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

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

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

2 голосов
/ 24 сентября 2008

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

Страница:
...