Как можно использовать RNGCryptoServiceProvider для генерации рук Моста?

Question

В игру "Бридж" играют 52 разных игральных карты, которые случайным образом распределяются между четырьмя игроками, каждый из которых заканчивается тринадцатью картами: так называемая "сделка". Примерно чуть менее 2^96 Мост сделок возможно. В этом документе требования к программе, генерирующей случайные сделки, описываются следующим образом:

1. Программное обеспечение должно быть в состоянии генерировать каждую возможную сделку моста, так как это также возможно с ручной обработкой.
2. Программное обеспечение должно генерировать каждую сделку с одинаковой вероятностью, без влияния номера доски, предыдущих рук или любых других обстоятельств.
3. Должно быть невозможно предсказать сделки, даже после просмотра всех других сделок на сессии.

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

Более того, так как большинство псевдослучайных генераторов берут начальное число из 32 битов, из этого следует, что эти генераторы будут способны в лучшем случае генерировать 2^32 различных сделок Bridge, в отличие от требуемых 2^96, и что, следуя так называемому парадоксу дня рождения, вполне вероятно, что такая же сделка будет заключена после получения квадратного корня из 2 32 сделок.

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

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

В приходит RNGCryptoServiceProvider, Я использовал это, используя код ниже для генерации случайных чисел, сначала в диапазоне от 1 до 52, затем в диапазоне от 1 до 51 и так далее, пока не останется одна карта.

Тестируя итоговые сделки, я довольно уверен, что этот код способен произвести любую сделку, на которую он способен с такой же вероятностью, и что вероятность того, что любая из карт окажется с одним из четырех игроков, равна 0,25.

Но поскольку сила семян, используемых в RNGCryptoServiceProvider, мне не известна, мне интересно, если:

1. Этот код сможет или может быть адаптирован для создания 2^96 различных сделок.
2. Следующая сделка с этим кодом не будет предсказуемой.

РЕДАКТИРОВАТЬ Метод получения случайных чисел, ранее упомянутых в этом вопросе, был ошибочным. Это отвлекло от основного вопроса, заключается в том, способен ли этот код произвести 2^96 различных сделок Бриджа. Я заменил генератор случайных чисел на тот, который опубликовал Стивен Тауб и Шон Фаркас в журнале MSDN

Код, используемый для создания криптографически безопасного случайного числа в диапазонах 1-52, 1-51 и т. Д. До 1-2, взятый с этого сайта

     /// <summary>
/// Returns a random number within a specified range.
/// </summary>
/// <returns>
/// A 32-bit signed integer greater than or equal to <paramref name="minValue"/> and less than <paramref name="maxValue"/>; that is, the range of return values includes <paramref name="minValue"/> but not <paramref name="maxValue"/>. If <paramref name="minValue"/> equals <paramref name="maxValue"/>, <paramref name="minValue"/> is returned.
/// </returns>
/// <param name="minValue">The inclusive lower bound of the random number returned.</param>
/// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue"/> must be greater than or equal to <paramref name="minValue"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="minValue"/> is greater than <paramref name="maxValue"/>.</exception>
public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;

    while (true)
    {
        //The cryptoProvider is of type RNGCryptoServiceProvider.
        cryptoProvider.GetBytes(uint32Buffer); //The uint32Buffer has a size of 4 bytes.
        UInt32 rand = BitConverter.ToUInt32(uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}

Answer 1

Если у вас есть генератор случайных чисел (RNG), который является "действительно единообразным", выполните следующие действия:

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

2. Самое главное, что (с частыми) интервалами, взять номер из RNG. Просто выбросьте номер, важной частью является то, что вы "зациклили" ГСЧ. При желании вы можете сделать интервалы случайными для повышения непредсказуемости. Чем больше циклов, тем лучше, поэтому я бы выбрал максимальный интервал настолько низко, насколько вы можете.

   • Существует два варианта для случайных интервалов: (а) использовать более слабый ГСЧ (который они используют) и (б) игнорировать его. В игровом автомате пользовательский ввод (нажатие "SPIN") вызывает фактическую прокачку ГСЧ. В сочетании с достаточно быстрым интервалом езды на велосипеде он считается достаточно непредсказуемым.
     
     

3. (Несколько опционально) Не ​​рисуйте все числа подряд. Подождите случайное количество времени (позволяя ГСЧ циклически повторять случайное количество раз), прежде чем рисовать следующее число (или набор чисел). Поскольку первоначальная отрисовка, скорее всего, основана на вводе пользователем, вы сможете сразу же отрисовать их все. Это не может повредить, хотя.

Это процесс, используемый в игровой (азартной) индустрии, где непредсказуемые ГСЧ строго регламентированы (и, конечно, необходимы). Дро с участием 500 карт (из 100 отдельных колод) выполняется с использованием этого метода. Обратите внимание, что используемые RNG обычно принимают 32-битные начальные значения и являются вполне приемлемыми.