Visual C ++ BigInt и SecureRandom? Есть ли библиотека BigInt с modPow? - PullRequest
Новая
       13

Visual C ++ BigInt и SecureRandom? Есть ли библиотека BigInt с modPow?

2 голосов
/ 04 марта 2010

Я должен портировать некоторый криптографический код на Visual C ++ из Java, который (Visual C ++) я не очень знаком с Я нашел библиотеку в http://sourceforge.net/projects/cpp-bigint/, которую я могу использовать для больших целых чисел.

Однако он не имеет эквивалента классу javas SecureRandom. Я нашел проект в c ++ с именем beecrypt, но не смог заставить его работать с Visual Studio 2008.

Кто-нибудь имеет опыт работы с этими типами библиотек? Я тоже видел gmp, но не смог найти тот, который работал с visual studio с нуля.

Прежде чем я отправлюсь по неправильной дороге, какой-нибудь совет?

Спасибо!

---- UPDATE -------

Кажется, у меня есть подтверждение концепции работы с cpp-bigint сверху с небольшими числами. В библиотеке нет функции modPow. На данный момент я создал цикл for вроде: 

for(RossiBigInt i("0",DEC_DIGIT); i< r; i++)

{ х = х * г; х = х% р; }

Это дает мне x = g ^ r mod p, но это очень медленно. Кто-нибудь знает о других библиотеках BitInteger с функцией modPow или знает, как мне быстрее вычислить это?

Спасибо!

Ответы [ 2 ]

2 голосов
/ 05 марта 2010

Функция modPow может быть эффективно оценена с помощью алгоритма "квадрат и умножение". В Java это выглядело бы так (если бы у Java BigInteger его еще не было): 

/* Compute x^n mod m. */
static BigInteger modPow(BigInteger x, BigInteger n, BigInteger m)
{
    if (n.signum() < 0)
        throw new IllegalArgumentException("bwah, negative exponent");
    BigInteger r = BigInteger.ONE;
    for (int i = n.bitLength() - 1; i >= 0; i --) {
        if (n.testBit(i))
            r = r.multiply(x).mod(m);
        if (i > 0)
            r = r.multiply(r).mod(m);
    }
    return r;
}

При этом число итераций цикла равно длине, в битах, показателя степени, так что вычислительное время является приемлемым.

Вы по-прежнему получаете одно или два модульных сокращения за итерацию, так что это не будет самый быстрый алгоритм возведения в степень за все время (модульные сокращения значительно дороже, чем умножение). Типичные реализации modPow () используют сокращение Монтгомери, которое является умным приемом, который объединяет все модульное сокращение в одну аналогичную операцию в конце.

Если у вас есть время, реализация собственного модульного возведения в степень была бы очень педагогической; Вы начнете с прочтения главы 14 «Руководства по прикладной криптографии», которую можно бесплатно загрузить с с этого сайта . Однако в этом суровом мире, где мирские соображения бюджета часто ограничивают креативность и свободное время, вы, вероятно, были бы довольны уже внедренной библиотекой. GMP, как известно, довольно хорош, но несколько сложен в использовании в Windows. Возможно, вам повезет больше с NTL .

0 голосов
/ 04 марта 2010

Для генерации случайных данных в Windows вы также можете использовать CryptoAPI, а именно метод CryptGenRandom .

...