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

23
задан Michael Myers 1 November 2011 в 14:40
поделиться

16 ответов

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

2
ответ дан 29 November 2019 в 00:56
поделиться

Метаответ:

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

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

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

23
ответ дан 29 November 2019 в 00:56
поделиться

Только отметить: __ int64 и долго долго нестандартные расширения. Никакой, как не гарантируют, будет поддерживаться всеми компиляторами C++. C++ основан на C89 (он вышел в 98, таким образом, он не мог быть основан на C99)

(C, имеет поддержку 'длинного длинный' начиная с C99)

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

1
ответ дан 29 November 2019 в 00:56
поделиться

Я имел большой успех с помощью библиотека LibTomCrypt для моих потребностей crypto. Это быстро, минимизировано, и портативно. Это может сделать Ваш RSA для Вас или просто обработать математику, если Вы хотите.

1
ответ дан 29 November 2019 в 00:56
поделиться

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

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

1
ответ дан 29 November 2019 в 00:56
поделиться

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

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

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

2
ответ дан 29 November 2019 в 00:56
поделиться

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

Используя длинный длинный определенно плохой подход.

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

0
ответ дан 29 November 2019 в 00:56
поделиться

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

1
ответ дан 29 November 2019 в 00:56
поделиться

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

, настолько легко реализовать материал crypto плохо.

3
ответ дан 29 November 2019 в 00:56
поделиться

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

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

необходимо смочь получить другие библиотеки сверхбольшого числа.

, С другой стороны, попытка, реализовывая прототип в Python и видит, достаточно ли это быстро.

3
ответ дан 29 November 2019 в 00:56
поделиться

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

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

12
ответ дан 29 November 2019 в 00:56
поделиться

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

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

13
ответ дан 29 November 2019 в 00:56
поделиться

Видеть размер долгой долгой попытки это:

#include <stdio.h>

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

    return 0;
}

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

3
ответ дан 29 November 2019 в 00:56
поделиться

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

0
ответ дан 29 November 2019 в 00:56
поделиться

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

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

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

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

3
ответ дан 29 November 2019 в 00:56
поделиться

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

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
ответ дан 29 November 2019 в 00:56
поделиться
Другие вопросы по тегам:

Похожие вопросы: