HitsugayaHisagi Ответов: 5

Генерация 2 случайных простых чисел в C#


Хотелось бы спросить, как мне сгенерировать 2 случайных числа, а затем проверить, является ли оно простым числом? Я хотел бы сгенерировать и то, и другое и проверить их все в один клик. Я попытался написать код на C#, но там есть несколько недопустимых аргументов. Вот мой код.


protected void btnstart_Click(object sender, EventArgs e)
        {
            BigInteger p = RandomInteger(); //generate a random number
            while (CheckIfPrime(p)==false) // number generated will be check if is prime,if false regenerate another random number
            {
                BigInteger p = RandomInteger();
            }
            txtP.Text = p.ToString(); // output the prime number
            lblresult.Text = "true"; // result true to confirm that it is the prime


            BigInteger q = RandomInteger();
            txtQ.Text = q.ToString();
            lblresult2.Text = "true"; 
        }

        public BigInteger RandomInteger() // to generate a random number
        {
            var rng = new RNGCryptoServiceProvider();
            var n = 10000000000;
            byte[] bytes = new byte[n/8];

            rng.GetBytes(bytes);

            var msb = bytes[n / 8 - 1];
            var mask = 0;
            while (mask < msb)
                mask = (mask << 1) + 1;

            bytes[n - 1] &= Convert.ToByte(mask);
            BigInteger i = new BigInteger(bytes);
            return i;
        }
        
        public bool CheckIfPrime(int n) //to check if the random number generated is prime
        {
            var isPrime = true;
            var sqrt = Math.Sqrt(n);
            for (var i = 2; i <= sqrt; i++)
                if ((n % i) == 0) isPrime = false;
            return isPrime;
        }



Спасибо!

Sergey Alexandrovich Kryukov

Если вы генерируете простое число, нет необходимости проверять, является ли оно простым. :-)
—СА

F-ES Sitecore

В дополнение к советам, которые вы уже получили, вы можете повысить эффективность вашего CheckIfPrime, сделав это

public bool CheckIfPrime(int n) //чтобы проверить, является ли сгенерированное случайное число простым
{
ВАР корень = математика.Sqrt(п.);
for (var i = 2; i <= sqrt; i++)
if ((n % i) == 0) возвращает false;
вернуть true;
}

Member 12696135

А вы пробовали?..

// Сгенерируйте два простых числа известного размера в одной строке кода
RSACryptoServiceProvider tempRsa = новый RSACryptoServiceProvider(size_in_bits);

Где 'size_in_bits' - это число от 384 (48 байт) до 16 384 (2048 байт)

DotNet создает эти два простых числа как часть нового закрытого ключа RSA, из которого затем можно украсть P и Q (два уникальных простых числа одинаковой длины), прежде чем выбросить ключ.

Я опубликовал решение (решение 5), которое, надеюсь, вы найдете полезным. Их можно массировать в систему.Численные данные.BigInteger довольно легко - и я добавил пример этого, так как вы должны убедиться, что BigInteger не рассматривает их как отрицательные числа (расширяя массив байтов дополнительным 0x00)

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

5 Ответов

Рейтинг:
41

CPallini

Я бы сделал наоборот, то есть напрямую случайным образом генерировать простое число- Вы знаете, под 10,000,000,000 там 455,052,511 простые числа (см. Сколько здесь простых чисел?[^]) так что вы можете случайным образом выбрать r между 0 и 455,052,510 а потом использовать rth простое число. Возможно, заранее вычисленные простые числа (огромные!) стол поможет.


Sergey Alexandrovich Kryukov

5ед.
—СА

CPallini

Спасибо.

Member 12696135

Я бы предположил, что если ОП использует BigIntegers, то, скорее всего, ему нужны очень большие простые числа. Если они тоже должны быть секретными (большинство криптографических), то таблица определенно отсутствует, так как размер был бы ужасающим. Не говоря уже о том, как быстро злоумышленник может проверить полмиллиона известных простых чисел на приличном домашнем компьютере.

Однако вы можете сгенерировать два больших простых числа в одной команде, используя RSACryptoServiceProvider для создания закрытого ключа RSA известного размера, а затем скопировать простые числа P и Q непосредственно из закрытого ключа.

Это позволяет быстро, безопасно и легко генерировать уникальные простые числа размером до 16 384 бит (2048 байт). (См. Решение 5)

Я буду рад вашим комментариям / критике.

Рейтинг:
33

BillWoodruff

Проблема в вашем коде заключается в том, что вы вызываете 'CheckIfPrime, передавая ему 'BigInteger, но его параметр: 'int.

Существует также проблема в том, что функция Sqrt математической библиотеки не принимает тип BigInteger. Вы можете обойти это с помощью этого:

<br />
BigInteger sqrt = Math.Exp(BigInteger.Log(bigIntValue) / 2); 
// видеть: [^].

Подумайте о диапазоне значений, в котором вы хотите, чтобы случайно выбранные простые числа находились внутри; ваше использование 'BigInteger подразумевает ... хорошо... очень крупный. Как вы знаете, определение "первичности" очень больших чисел может потребовать огромных вычислительных мощностей.

Существуют общедоступные списки простых чисел, включая очень большие простые числа; не могли бы вы реализовать свое решение, используя список, из которого вы случайно выбираете ? Здесь есть список из 5000 очень больших простых чисел (минимум 1000 цифр каждое): [^].

Повторите вопрос о получении двух случайных значений "одновременно:" если у вас есть многоядерные системы для работы, рассмотрите возможность использования параллельного программирования в .NET: [^].

Такое использование -Система.Безопасность.Криптография средство RNGCrytoServiceProvider для получения случайных больших целых чисел с определенным количеством битов:
// note this code is from a a static Class named 'Methods in a NameSpace named 'PrimeUtilties

private static RNGCryptoServiceProvider rngProvider = new RNGCryptoServiceProvider();
private static Random random = new Random(DateTime.Now.Millisecond);
private static byte[] someBytes;

public static BigInteger GetRandomBigInteger(int nBits, bool onlyPositive = true)
{
    someBytes = new byte[nBits/8];
    rngProvider.GetBytes(someBytes);
    
    BigInteger bg = new BigInteger(someBytes);
    if (onlyPositive && bg.Sign == -1) bg = bg * -1;
    
    return bg;
}
Кортеж можно использовать для возврата двух значений из метода:
public static Tuple<BigInteger, BigInteger> GetTwoRandomBigInts(int nbitsOf1 = 128, int nbitsOf2 = 128, bool onlyPositive = true)
{
    return Tuple.Create(GetRandomBigInteger(nbitsOf1, onlyPositive), GetRandomBigInteger(nbitsOf2, onlyPositive));
}

// get a Tuple with two (non-negative) BigInts
// var TwoBigOnesWith = PrimeUtilities.Methods.GetTwoRandomBigInts(512, 256, onlyPositive: true);
Но, как правило, я бы не стал утруждать себя написанием жестко запрограммированный такой метод; я бы написал более общий, который взял бы массив param или передал бы какую-то структуру, которую я бы проанализировал, чтобы сгенерировать любую связку или связку Пучков BigIntegers, которые я хотел бы создать.


Afzaal Ahmad Zeeshan

5ed, для экспоненциального метода взятия квадратного корня.

HitsugayaHisagi

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

BillWoodruff

У него может быть такая подпись:

общественная список<список<типа BigInteger&ГТ;&ГТ;GetABunchofBigIntegers(параметры типа int[] аргументы){}

Затем я мог бы проанализировать массив params, принимая по два значения за раз, интерпретируя первое значение как количество генерируемых BigIntegers, а второе значение в паре как количество битов в каждом генерируемом BigInteger. Конечно, есть много других способов сделать это.

к вашему сведению: я решил, что вы получите "лучшие" результаты, используя RNGCrytoServiceProvider, и изменил приведенный выше код.

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

HitsugayaHisagi

Я ... не могу себе представить, как выглядит этот код, не могли бы вы привести мне пример?

BillWoodruff

Привет, Хицугаяй, QA - это для того, чтобы помочь вам стать лучшим программистом и решать проблемы. Вы начинаете писать код, экспериментировать, уточнять и возвращаетесь с конкретными вопросами и примерами кода. Если я напишу код для вас, вы не будете учиться.

твое здоровье, Билл

HitsugayaHisagi

Хорошо...Я постараюсь. Я подумал, есть ли где-нибудь похожий код, чтобы посмотреть, потому что я действительно не могу найти близкий в google (или, может быть, я плохо гуглю конкретные вещи). И я совсем новичок в криптографическом программировании, так что я где-то заблудился. Но большое спасибо за ваше руководство, я попробую еще раз посмотреть. Еще раз спасибо!!! =)

CPallini

5.

Member 12696135

DotNets RSACryptoProvider уже создает два простых числа известного размера в одной команде... Он может генерировать любое простое число между 384 битами и 16 384 битами (в 8 - битных шагах), которое охватывает большинство случаев использования. Это также чертовски быстро, учитывая.

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

Я опубликовал его (как решение 5) для ваших комментариев и критики.

Рейтинг:
2

Patrice T

Ваш код имеет множество проблем.
Один из них-эффективность, вот ваш код и 2 тривиальных изменения:

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var isPrime = true;
    var sqrt = Math.Sqrt(n);
    for (var i = 2; i <= sqrt; i++)
        if ((n % i) == 0) isPrime = false;
    return isPrime;
}
для n=400 код проверяет 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var isPrime = true;
    var sqrt = Math.Sqrt(n);
    if ((n % 2) == 0) isPrime = false;
    for (var i = 3; i <= sqrt; i+= 2)
        if ((n % i) == 0) isPrime = false;
    return isPrime;
}
для n=400 код проверяет 2, 3, 5, 7, 9, 11, 13, 15, 17, 19

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var sqrt = Math.Sqrt(n);
    if ((n % 2) == 0) return false;
    for (var i = 3; i <= sqrt; i+= 2)
        if ((n % i) == 0) return false;
    return true;
}
и здесь код останавливается, как только он знает n это не простое число.

Как уже было замечено, int n параметром функции является неправильным, поскольку вы хотите проверить BigInteger.


HitsugayaHisagi

а это значит, что неразумно использовать этот код для проверки BigInteger, вы имеете в виду?

Patrice T

Да, вы должны сначала заменить int с BigInteger

HitsugayaHisagi

ты имеешь в виду типа,

public bool CheckIfPrime(BigInteger n) //чтобы проверить, является ли сгенерированное случайное число простым
{
Типа BigInteger корень = математика.Ехр(Типа BigInteger.Log(n)/2);
//но ошибки в этой части (не может неявно преобразовать тип 'double' в 'System.Численные данные.Типа BigInteger'. Существует явное преобразование)
if ((n % 2) == 0) возвращает false;
для (var i = 3; i <= sqrt; i += 2)
if ((n % i) == 0) возвращает false;
вернуть true;
}

Patrice T

что-то вроде того.

Math.Exp наверное, это неправильно. вам лучше попробовать BigInteger.Exp

HitsugayaHisagi

Хм...все еще есть проблема, "система.Численные данные.BigInteger' не содержит определения для 'Exp'.

Типа BigInteger корень = типа BigInteger.Ехр(Типа BigInteger.Log(значение)/2);
if ((value % 2) == 0) возвращает false;
для (var i = 3; i <= sqrt; i += 2)
if ((value % i) == 0) возвращает false;
вернуть true;
Я действительно проверил, и мне кажется, что использование Math.Exp на самом деле правильно.

Patrice T

Поскольку BigInteger не является родным типом, я думаю, вы должны убедиться, что каждая операция совместима с BigInteger.

Member 12696135

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

.. он использует Криптопровидер DotNet в качестве скрытого ярлыка, чтобы сделать эту работу за вас, и генерирует два простых числа известного размера в одной строке кода (хотя требуется около 5 строк кода, чтобы преобразовать их из строки XML в систему.Численные данные.BigInteger)

Он определенно намного быстрее и может генерировать простые числа длиной до 16 384 бит (2048 байт), поэтому подходит для использования с BigIntegers.

Patrice T

Цель решения состояла в том, чтобы обучить OP, обнаружив самые большие неэффективности в его коде.

Рейтинг:
2

Member 12696135

Ладно, просто выброшу это на улицу...

ЛЕГКАЯ ГЕНЕРАЦИЯ ПРАЙМА В C#.NET

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

Прежде чем мы начнем, этот метод имеет ограничения... он не может сделать действительно маленькие простые числа Однако он может создавать огромные простые числа, даже более 16 000 бит, без какой-либо суеты.

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

- таблица или случайный поиск простых чисел менее 384 бит, а также;
- это код для простых чисел между 284 битами и 16 384 битами.

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

Первый,

using system.security.cryptography

В качестве быстрого теста вы можете создать экземпляр класса RSACryptoServiceProvider... поскольку это предоставляет диапазон простых чисел, допустимых при создании ключа RSA. Подобный этому...
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider)
{
    // Now look at the following properties of myRsa...
    int min = myRSA.LegalKeySizes.MinSize;  // Usually 16,384
    int max = myRSA.LegalKeySizes.MaxSize;  // Usually    384
    int step = myRSA.LegalKeySizes.StepSize; //             8

    // Use the values above to decide on a valid keysize for the
    // prime you want to generate!  As you can see, you have a
    // LOT of options.  The size is in bits, which is why we
    // see a 'StepSize' of 8
}

Эти числа вряд ли изменятся, поэтому не стесняйтесь игнорировать вышеизложенное - я включаю его только для того, чтобы показать простые числа, которые вы можете произвести. Как только вы определили размер (между min и max, с размером шага 8) ... вы можете попросить c# создать ключ именно такого размера!

Удалите приведенный выше код, и давайте начнем генерировать простые числа...


Используйте реализацию DotNets RSA для генерации большого простого числа

Давайте начнем с симпатичного маленького 1024-битного простого числа...
// Create a temporary RSA key (we don't need the key, just it's prime)
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
    // Boom, prime generated!  Yes, that simple... let's dig it out.

    // First, output the private certificate as an XML string
    // The parameter 'true' tells c# to include the private key
    // otherwise we only get the public part.
    String xml = myRsa.ToXmlString(true);

    // Now, you're interested in the subkeys P and Q in that XML
    // so, parse the XML using a reader or some string operations.

    // It is in Base64, so if you need it as a byte array you'll also
    // have to decode it from Base64 to a byte array.  But, that is
    // up to you, and depends what format you want the prime in.
}

Да... всего 2 строки кода! Чтобы преобразовать его в BigInt, требуется около 5 строк кода. Не стесняйтесь пожертвовать пиво.

Вот формат xml - файла, все значения кодируются Base64 ...

<RSAKeyValue>
    <Modulus> ... </Modulus>
    <Exponent> ... </Exponent>
    <P> Your prime 'P' of the required size </P>
    <Q> another useful prime 'Q', close in size to 'P' </Q>
    <DP> ... </DP>
    <DQ> ... </DQ>
    <InverseQ> ... </InverseQ>
    <D> ... </D>
</RSAKeyValue>


Теперь я намеренно избегаю показывать, как анализировать Base64, поскольку только вы знаете, где вы хотите сохранить это число. Но здесь, в CodeProject, есть много фрагментов кода, которые показывают, как анализировать XML (или, как вариант, разбивать строки) и декодировать Base64 в двоичные байты. В этом нет ничего особенного.

Но одно предупреждение... если вы собираетесь поместить его в контейнер без знака, вам нужно следовать правилам - так как представление, полученное из Base64, будет без знака, но может иметь самый значительный набор битов.

Итак, если вы хотите поместить его в Система.Численные данные.BigInteger .. помните, что вы должны сделать массив байтов на один байт больше чем требует номер. Это происходит потому, что массив байтов должен быть добавлен ноль чтобы убедиться, что BigInteger не считает его отрицательным.


И вот это все : )

Теперь вы знаете, как генерировать большие простые числа между 48 байтами (384 бита) и 2048 байтами (16 384 бита), не возясь с играми в угадайку или используя большие таблицы простых чисел... и все это в нескольких строках кода.

И все, что нам нужно было сделать, это злоупотребить классом RSACryptoServiceProvider, чтобы он выполнил наши требования ; )

Надеюсь, это кому-то поможет.


РЕДАКТИРОВАТЬ: Ответ расширенный - быстрый и грязный пример синтаксического анализа в BigInteger
using system.security.cryptography;
using system.numerics;
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
    byte[] sbin; // The raw byte array (looks signed)
    byte[] ubin; // The cooked byte array

    // Export RSA certificate to an XML string
    String xml = myRsa.ToXmlString(true);

    // Locate <P> in the Base64 certificate (quick and dirty code)
    int s = xml.IndexOf("<P>")+3;
    int l = xml.IndexOf("<",s)-s;
    // Convert P from Base64 to a raw byte array
    sbin = Convert.FromBase64String(xml.Substring(s, l));
    // Postfix a null byte to keep BigInteger happy
    ubin = new byte[sbin.Length + 1]; ubin[sbin.Length] = 0;
    Buffer.BlockCopy(sbin, 0, ubin, 0, sbin.Length);
    // Convert the bytes into positive BigNumber
    BigInteger bigprime = new BigInteger(ubin);

    // Write it to the console
    Console.WriteLine(bigprime);
}


Member 12696135

Быстрые комментарии к приведенному выше ответу :

1. "Система.Цифры", возможно, придется добавить в качестве ссылки в Обозреватель решений
2. 16,384-битные простые числа очень трудно генерировать, это может занять пару минут
3. Вы можете посетить https://www.alpertron.com.ar/ECM.HTM чтобы проверить ваши простые числа
4. Всегда добавляйте правильную проверку ошибок и обработку исключений

5. Если вы используете эти простые числа для криптографии, Всегда стирайте (перезаписывайте) чувствительные переменные, прежде чем они выйдут из области видимости!!!

Наслаждаться ;)

BillWoodruff

+5 интересно, с нетерпением ждем mtomsty7dying кода позже. спасибо, Билл

Рейтинг:
17

HitsugayaHisagi

Поэтому я попробовал этот код, и он работает нормально для меня.

Random rand = new Random();
            BigInteger p = BigInteger.genPseudoPrime(128, 10, rand);
            txtP.Text = p.ToString();

            Random rand2 = new Random();
            BigInteger q = BigInteger.genPseudoPrime(128, 10, rand2);
            do
            {
                q = BigInteger.genPseudoPrime(128, 10, rand2);
            }
            while (p == q);
            txtQ.Text = q.ToString();



использование библиотеки DLL из Шифрование клиент/сервер плюс дополнительные услуги[^]

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


Member 12696135

Следует отметить, что система DotNets ".Численные данные.BigInteger" не имеет метода genPseudoPrime. В противном случае это хороший ответ, но я бы беспокоился о проблемах зависимостей, которые создаст эта библиотека... а также о том, являются ли эти простые числа безопасными для использования.

Крипто-библиотека DotNets уже может создать два уникальных простых числа заданного размера в одной команде (см. Решение 5) ... так что, вероятно, это было бы моим предпочтительным решением в большинстве случаев.