Алгоритм для преобразования случайных байтов для целых чисел


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

byte[] GetRandomBytes(int count) -> int NextInteger(int min, int max)

Еще один способ думать об этом было бы: у меня RNGCryptoServiceProvider , но предпочел бы интерфейс к случайным.

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

Вопрос 1: мой алгоритм звука?

Вопрос 1А: это ниже реализация звука (на C#) (конкретно: RandomSourceBase.Следующий(инт, инт))?

using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace ConsoleApplication1
{
    public abstract class RandomSourceBase
    {
        public abstract byte[] GetRandomBytes(int numberOfBytes);

        public int Next()
        {
            return Next(0, Int32.MaxValue);
        }
        public int Next(int maxValue)
        {
            return Next(0, maxValue);
        }
        public int Next(int minValue, int maxValue)
        {
            if (minValue < 0)
                throw new ArgumentOutOfRangeException("minValue", minValue, "MinValue must be greater than or equal to zero.");
            if (maxValue <= minValue)
                throw new ArgumentOutOfRangeException("maxValue", maxValue, "MaxValue must be greater than minValue.");

            int range = maxValue - minValue;
            if (range == 1)     // Trivial case.
                return minValue;

            // Determine how many bits are required for the range requested.
            int bitsRequired = (int)Math.Ceiling(Math.Log(range, 2) + 1);
            int bitmask = (1 << bitsRequired) - 1;

            // Loop until we get a number within the range.
            int result = -1;
            while (result < 0 || result > range - 1)
            {
                var bytes = this.GetRandomBytes(4);
                result = (Math.Abs(BitConverter.ToInt32(bytes, 0)) & bitmask) - 1;
            }
            return result + minValue;
        }
    }
    public class CryptoRandomSource : RandomSourceBase
    {
        private RNGCryptoServiceProvider _RandomProvider;
        public CryptoRandomSource()
        {
            this._RandomProvider = new RNGCryptoServiceProvider();
        }

        public override byte[] GetRandomBytes(int numberOfBytes)
        {
            var result = new byte[numberOfBytes];
            this._RandomProvider.GetBytes(result);
            return result;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TestNextInt32(new CryptoRandomSource(), 50);
            TestNextInt32(new CryptoRandomSource(), 64);
            Console.ReadLine();
        }

        private static void TestNextInt32(RandomSourceBase randomness, int max)
        {
            var distributionTable = new Dictionary<int, int>();
            for (int i = 0; i < max; i++)
                distributionTable.Add(i, 0);

            Console.WriteLine("Testing CryptoRandomStream.Next({0})...", max);
            int trials = max * 50000;
            for (int i = 0; i < trials; i++)
            {
                var choice = randomness.Next(max);
                distributionTable[choice] = distributionTable[choice] + 1;
            }
            for (int i = 0; i < max; i++)
                Console.WriteLine("{0}, {1}", i, distributionTable[i]);
            Console.WriteLine();
        }
    }
}

Вопрос 2: если предположить, GetRandomBytes фактически случайный, мой алгоритм / реализация также быть случайным (в частности, равномерное распределение?).

Я сделал несколько тестов и графически распределение в Excel. Они выглядят случайными-выход для меня. Но, Ну, я не эксперт по безопасности, и, конечно, статистику я сделал в 2003 году, и моя память не очень хорошая! Конкретно, я не знаю, если варианты до 800 или ~1.6% (точка № 3 на 50 график) является приемлемым или если я сделал что-то ужасно неправильно.

0..49 0..63

(Заметим, что ось Y не обнуляется. 50,000-нужное число).

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

Реальной жизни код (для тех, кому интересно): http://readablepassphrase.codeplex.com/SourceControl/changeset/changes/aa085616bc23 Соответствующий код находится в: багажник/ReadablePassphrase/случайный



1732
4
задан 26 ноября 2011 в 04:11 Источник Поделиться
Комментарии
2 ответа

Да, алгоритм, как описано здравая, хотя и не самое эффективное использование случайных чисел источник. Однако, есть несколько сюрпризов в коде. Оформление по умолчанию следующий() способен вернуться 2^31 - 1 различных значений немного неожиданно и слегка искажает распределение младших бит. Может быть, стоит изменить имена тоже, в случае, если вы хотите, чтобы добавить новые типы продукции. Я бы скорректировать следующим образом:

    public int NextInt32()
{
byte[] bytes = GetRandomBytes(4);
int i = BitConverter.ToInt32(bytes);
return i & Int32.MaxValue;
}

public int NextInt32(int maxExcl)
{
if (maxExcl <= 0) throw new ArgumentOutOfRangeException("maxExcl", maxExcl, "maxExcl must be positive");

// Let k = (Int32.MaxValue + 1) % maxExcl
// Then we want to exclude the top k values in order to get a uniform distribution
// You can do the calculations using uints if you prefer to only have one %
int k = ((Int32.MaxValue % maxExcl) + 1) % maxExcl;
while (true)
{
int rnd = NextInt32();
if (rnd <= Int32.MaxValue - k)
return rnd % maxExcl;
}
}

public int NextInt32(int minIncl, int maxExcl)
{
if (minIncl < 0)
throw new ArgumentOutOfRangeException("minIncl", minIncl, "minValue must be non-negative");
if (maxExcl <= minIncl)
throw new ArgumentOutOfRangeException("maxExcl", maxExcl, "maxExcl must be greater than minIncl");

return minIncl + NextInt32(maxExcl - minIncl);
}

3
ответ дан 26 ноября 2011 в 06:11 Источник Поделиться

Я думаю, что зацикливание до тех пор, пока число в диапазоне всплывает очень странная идея. Первая потенциальная проблема, которая приходит на ум-это вероятность того, что при определенных обстоятельствах (скажем, максимум = минимум + 2) может быть зацикливание в течение длительного времени. Более тщательный анализ кода показывает, что такая возможность есть, но за счет значительных сложностей. Почему бы просто не применить оператор модуля между генерироваться случайное 32-разрядное целое число и нужный диапазон? Это позволит упростить ваш код и существенно уменьшить его длину. Это намного легче сказать, короткий и простой отрывок кода звука, чем длительный и сложный.

1
ответ дан 26 ноября 2011 в 11:11 Источник Поделиться