Генерация псевдослучайных чисел

    Довольно часто программисты в своей работе встречаются с необходимостью работать со случайными числами. Чаще всего случайные числа требуются в задачах моделирования, численного анализа и тестирования, но существует и множество других весьма специфических задач.
    Конечно, во всех современных языках программирования есть функция random или её аналоги. Эти функции чаще всего дают действительно хорошие псевдослучайные числа, но мне всегда было интересно, как эти функции работают.
    В этом топике я постараюсь объяснить, как работает линейный конгруэнтный метод (который чаще всего используется в функции random), и метод получения случайных чисел с помощью полиномиального счётчика (который часто используется для тестирования аппаратуры).

    Введение


    Сразу стоит сказать, что есть смысл генерировать случайные числа только с равномерным законом распределения, т.к. все остальные распределения можно получить из равномерного путём преобразований, известных из теории вероятности.
    Для тех, кто забыл или пока не изучал теорию вероятности, напомню, что в равномерно распределённой последовательности нулей и единиц нули в среднем(!) будут встречаться в 50% случаев. Но это вовсе не значит, что в последовательности из 1000 цифр будет ровно 500 нулей. Более того, в последовательности из 1000 цифр может быть 999 нулей, и вероятность того, что тысячный элемент будет равен нулю по-прежнему остаётся равной 0.5. На первый взгляд это кажется парадоксальным, но важно понимать, что все последовательности равновероятны. Если же мы будем рассматривать достаточно большую совокупность таких последовательностей, то в среднем(!) в каждой из них будет 500 нулей.
    Немного вспомнив теорию, мы перейдём к истории. В докомпьютерные времена случайные числа получали, вытаскивая разноцветные мячи из мешков, вытягивая карты, бросая кости. Понятно, что серьёзные исследования так проводить было нельзя, поэтому в 1927 года Типпетт опубликовал первую таблицу случайных чисел. Чуть позже люди попытались как-то автоматизировать этот процесс. Начали появляться машины, генерирующие случайные числа. Сейчас такие устройства тоже используются и называются источниками (генераторами) энтропии. Стоит заметить, что только такие устройства могут давать по-настоящему случайные числа. Но, к сожалению, генераторы энтропии довольно дороги, и не представляется возможным установить их в каждый ПК. Именно поэтому и возникла необходимость в алгоритмах получения случайных чисел.

    Первая попытка получения ПСП


    Некоторые люди думают, что получать случайные числа легко. По их мнению для этого достаточно делать случайные сложные математические действия над исходным числом. Если мы откроем второй том всем известного Кнута, то узнаем, что в 1959 Кнут тоже пробовал построить генератор, основанный на такой идее. Его алгоритм выглядел так:
    К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)
    К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.
    КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.
    К4. [Средина квадрата.] Заменить X серединой квадрата X.
    К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.
    К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.
    К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.
    К8. [Умножить.] Выполнить шаг К5.
    К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.
    К10. [Модифицировать на 99999.] Если А' < 105, присвоить X значение — X 2 +99999; иначе присвоить X значение X — 99999.
    К11. [Нормировать.] (На этом шаге А' не может быть равным нулю.) Если X <109, то умножить X на 10.
    К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х — 1).
    К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым «случайным» значением.
    Несмотря на кажущуюся сложность, этот алгоритм быстро сошёлся к числу 6065038420, которое через небольшое число шагов преобразовалось в себя же. Мораль этой истории в том, что нельзя использовать случайный алгоритм для получения случайных чисел.

    Линейный конгруэнтный метод


    В большинстве языков программирования именно этот метод используется в стандартной функции получения случайных чисел. Впервые этот метод был предложен Лехмером в 1949 году. Выбирается 4 числа:
    1. Модуль m (m>0);
    2. Множитель a (0<=a<m);
    3. Приращение c (0<=c<m);
    4. Начальное значение X0 (0<= X0<m)

    Последовательность получается с использование следующей рекуррентной формулы: Xn+1=(a* Xn+c) mod m.
    Этот метод даёт действительно хорошие псевдослучайные числа, но, если взять числа m,a,c произвольно, то результат нас скорее всего разочарует. При m=7, X0=1, a=2, c=4 получится следующая последовательность: 1,6,2,1,6,2,1,…
    Очевидно, что эта последовательность не совсем подходит под определение случайной. Тем не менее, этот провал позволил нам сделать два важных вывода:
    1. Числа m,a,c, X0 не должны быть случайными;
    2. Линейный конгруэнтный метод даёт нам повторяющиеся последовательности.

    На самом деле любая функция, отображающая конечное множество X в X, будет давать циклически повторяемый значения. Т.о. наша задача состоит в том, чтобы максимально удлинить уникальную часть последовательности (кстати, очевидно, что длина уникальной части не может быть больше m).
    Не вдаваясь в подробности доказательств, скажем, что период последовательности будет равен m только при выполнении следующих трех условий:
    1. Числа c и m взаимно простые;
    2. a-1 кратно p для каждого простого p, являющегося делителем m;
    3. Если m кратно 4, то и a-1 должно быть кратно 4.
    В завершении рассказа о линейном конгруэнтном методе надо сказать, что последовательности, получаемые с его помощью, хоть и являются в достаточном смысле случайными, тем не менее не являются криптографически стойкими. Т.к. зная 4 подряд идущих числа, криптоаналитик может составить систему уравнений, из которых можно найти a,c,m.

    Получение псевдослучайных чисел на основе полиномиального счетчика (сдвигового регистра)


    В основе алгоритма, который мы сейчас рассмотрим, лежит операция исключающего ИЛИ (сумма по модулю два). На всякий случай, напомню, как выглядит таблица истинности для данной функции:

    Схемы, представленные на рисунке ниже, являются простейшими полиномиальными счётчиками. Нулевой бит в таких схемах вычисляется на основе функции исключающего ИЛИ, а все остальные биты получаются простым сдвигом. Разряды с которых сигнал идёт на исключающее ИЛИ называются отводами.

    Рассмотрим, как будут изменяться значения в этих регистрах при начальном значении 001:


    Оба регистра начинают работу с одного и того же значения, но потом значения, генерируемые регистрами начинают быстро расходиться. Но через 6 шагов, оба регистра возвращаются в исходное состояние.
    Легко показать, что оба этих регистра сгенерировали максимально длинную последовательность, которая содержит все комбинации, кроме нулевой. Т.е. при разрядности регистра m, можно получить последовательность длинной 2m-1.
    Полиномиальный счётчик любой разрядности имеет ряд комбинаций отводов, которые обеспечат последовательность максимальной длины, использование неверных комбинаций приведёт к генерации коротких последовательностей. Отдельная и довольно сложная задача – поиск этих комбинаций отводов.
    Стоит заметить, что эти комбинации не всегда уникальны. К примеру, для 10-битного счётчика их существует две: [6;9] и [2;9], для шестиразрядного счётчика таких комбинаций двадцать восемь.
    Для того, чтобы найти эти комбинации, необходимо представить счётчик в виде полинома. Счётчики из примера будут иметь следующий вид: x2 XOR 1 и x2 XOR x XOR 1.

    Из теории известно, что необходимым и достаточным условием генерации полной последовательности является примитивность характеристического полинома. Это значит, что:
    • Характеристический полином нельзя представить в виде произведения полиномов более низкой степени;
    • Характеристический полином является делителем полинома zδ XOR 1, при(δ=2m-1, и не является делителем при любых других значениях δ<2m-1.

    Преимуществами полиномиального счётчика является простота, как программной, так и аппаратной реализации, скорость работы и криптографическая стойкость.

    Надеюсь, эта статья была полезной для вас.

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 36

      +3
      криптографическая стойкость
      Криптографическая стойкость без физического источника случайных величин? Да вы, видимо, пытаетесь ввести аудиторию в заблуждение.
        +1
        Понятно, что инициализирующий вектор должен быть ДЕЙСТВИТЕЛЬНО случайным. Уже запущенный генератор, может и реально используется в потоковых шифрах.
          +1
          Ну если только в потоковых шифрах. Для генерации ключей такие штуки использовать нельзя.
            +2
            Смотря каких ключей. Если одноразовых сеансовых — почему собственно нет?
            +2
            Тоже немного позанудствую. На самом деле использовать в криптографических целях сдвиговый регистр в том виде который описан в вашей статье это, скажем так, весьма наивно. Дело все в том, что зная длину регистра l и 2l последовательных бита вышедших из регистра, можно восстановить всю генерируемую регистром последовательность. Именно это «свойство» сдвиговых регистров не позволяет применять их в криптографических целях без дополнительных наворотов, таких, например, как использование нескольких сдвиговых регистров. Выходной бит в схеме с несколькими регистрами получается применением нелинейной булевой функции к выходным битам каждого из используемых регистров.
        +2
        Весьма познавательно, на самом деле. Как всегда не доходили руки самому разобраться — а вот в таком виде очень интересно было прочесть.
          0
          Касательно аппаратной генерации. Читал недавно на Компьютерре, что в процессорах Intel грядущего поколения будет присутствовать генератор настоящих случайных чисел.
            –2
            Присутствовать он, может, и будет, но когда его начнут поддерживать все компиляторы? Да и о старых программах не стоит забывать.
              0
              Я нисколько не усомнился в актуальности вашей статьи, это так, к слову, о светлом будущем…
                +2
                но когда его начнут поддерживать все компиляторы
                А причём тут компилятор вообще? Его должно ядро поддерживать. Далее. Компилятор генерацией случайных чисел вообще не занимается, ей занимается либо стандартная библиотека, либо эти самые значения можно получить от сервисов ОС типа /dev/random (истинно случайные значения) или /dev/urandom (псевдослучайные, но используют биты энтропии из /dev/random. Функции же из стандартной библиотеки можно передать random seed, который для бытовых нужд обычно берут из таймстампа.
                  –2
                  Может мы о разных вещах говорим, но именно компилятор транслирует вызов X<-random() в машинные коды. И если в системе команд появляется новая, то именно компилятор должен о ней узнать.
                    +2
                    компилятор там совсем не участвует, реализация находится в стандартной библиотеке. там линкер занимается делом :) но вы всеравно с kekekeks'ом о разных вещах говорите.
                      –5
                      Стандартная библиотека разве не должна быть предварительно скомпилированной? И разве все языки берут реализацию из стандартной библиотеки?
                      +1
                      Пожалуйста, поясните, каким образом появление нового устройства связано с изменением набора инструкций ассемблера?
                  +3
                  Он там уже лет десять присутствует в виде аналогового контура и доступен через такую штуку как /dev/random, например.
                    –2
                    Вас кто-то жестоко обманул.
                      0
                      Я склонен верить тому, что пишут представители Intel.
                        –2
                        Где они такое пишут? Можно ссылочку?
                        Вообще-то в основе работы /dev/random используется счетчик тактов как источник энтропии.
                          +1
                          Да чего её искать, в посте неподалёку перевод есть. Пишут там следующее:
                          более десяти лет многие из чипсетов нашего производства содержат аналоговый аппаратный генератор случайных чисел
                          . Кода ядра сейчас под рукой нет, но утром посмотрю на предмет его поддержки в /dev/random. А счётчик тактов не является случайной величиной, если кто не в курсе.
                            0
                            Я почему-то думал, что аппаратные ГСЧ практически не применяются на обычных ПК.
                            А по поводу счетчика тактов, я немного не так выразился. Используется не сам счетчик как таковой, а счетчик как величина для измерения интервалов между событиями в ядре.
                              –1
                              ну как там, с кодом-то? random.c уже отрастил себе новые функции?
                                +1
                                Я даже код смотреть не буду, на kernel.org и так всё написано:
                                The hw_random framework is software that makes use of a
                                special hardware feature on your CPU or motherboard,
                                a Random Number Generator (RNG)
                                . The software has two parts:
                                a core providing the /dev/hw_random character device and its
                                sysfs support, plus a hardware-specific driver that plugs
                                into that core.

                                To make the most effective use of these mechanisms, you
                                should download the support software as well. Download the
                                latest version of the «rng-tools» package from the
                                hw_random driver's official Web site:

                                http://sourceforge.net/projects/gkernel/

                                Those tools use /dev/hw_random to fill the kernel entropy pool,
                                which is used internally and exported by the /dev/urandom and
                                /dev/random special files.
                                Админ системы ставит пакет с демоном, демон пинает ядро, в /dev/random появляется поддержка аппаратного ГСЧ, все счастливы.
                                  –2
                                  >> в /dev/random появляется поддержка аппаратного ГСЧ, все счастливы
                                  FACEPALM.JPG
                                  Это печально, что вы не видите разницы между /dev/hw_random и /dev/random.
                                  И если какие-то левые тулзы *подменяют* A на Б, это никак не означает, что А начинает обладать признаками и свойствами Б.

                                    0
                                    Интересные же у вас критерии «левости» тулзов. Особенно в контексте вышенаписанного.
                      +2
                      Кажется на Хабре была статья об этом.
                      0
                      >Множитель a (a<=0<m);
                      >a=2

                      Так a меньше нуля или больше?
                        0
                        Разумеется, имелось в виду 0<=a<m. Спасибо.
                          0
                          ещё если я правильно понял на схеме второго полиноминального счетчика должно быть тоже два отвода, а не три? или я не понимаю как это работает.
                      • UFO just landed and posted this here
                          0
                          И получаемые значения это ничто иное как М-последовательность (mls). А для нее давно известны рекурсивные формулы генерации (хотя на регистрах проще) — что значит имея достаточно входных данных, можно восстановить всю последовательность и структуру генератора — а это уж никак не стойко.
                          Это то-же самое что и:
                          >зная 4 подряд идущих числа, криптоаналитик может составить систему уравнений, из которых можно найти a,c,m.
                          только знать нужно больше подряд идущих чисел. (есть подозрение, что это m чисел)
                          • UFO just landed and posted this here
                              +1
                              Но в таком виде как в статье использовать в криптографии такие генераторы я бы не стал.
                              • UFO just landed and posted this here
                              +1
                              я был немного не прав не m, a 2*m символов (первые m — это начальное состояние)

                          Only users with full accounts can post comments. Log in, please.