C# случайный генератор BigInt
Я собираюсь реализовать алгоритм DSA, но существует проблема:
выберите "p", простое число с битами L, где 512 <= L <= 1024 и L является кратным 64
Как я могу реализовать случайный генератор того числа? Int64 имеет "только" 63 бита длиной.
1 ответ
Вы можете сгенерировать случайное число с n битами, используя этот код:
var rng = new RNGCryptoServiceProvider();
byte[] bytes = new byte[n / 8];
rng.GetBytes(bytes);
BigInteger p = new BigInteger(bytes);
Результат, конечно, случайный и не обязательно простой.
Класс BigInteger был введен в .NET 4.0 Framework.
Для генерации больших простых чисел Википедия говорит :
Для больших простых чисел, используемых в криптографии, обычно используется модифицированная форма просеивания: случайно выбранный диапазон нечетных чисел желаемый размер просеивается против ряда относительно небольших нечетных простых чисел (обычно все простые числа меньше 65000). Остальные простые числа-кандидаты проверяются в случайном порядке с помощью стандартного теста на простоту, такого как критерий простоты Миллера-Рабина для вероятных простых чисел.
Итак, вы можете сделать что-то вроде этого:
var p = Enumerable.Range(0, numberOfCandidates)
.Select(i => RandomOddNumber(bits))
.Where(x => !primesLessThan65000.Contains(x))
.Where(x => PrimalityTest(x))
.FirstOrDefault();