Роберт Кавью [1]

Введение. Случайные числа широко используются в самых разных приложениях современной информатики: в вычислительных методах, имитационном моделировании (Монте-Карло), системах защиты информации и др. Их генерирование – одна из базовых проблем в реализации криптографических систем, ибо только абсолютно случайное число может рассматриваться в качестве надежного синтезатора безупречного ключа [2, 3].

Шифрование применялось еще в античности. А «краткое руководство по использованию шифров для обмена любовными посланиями содержит даже Камасутра» [4].

Но преобразование информации долгое время носило в основном детерминированный характер. Современные шифры уже содержат случайные (хаотические) компоненты. И как ни странно, но уязвимость многих реальных систем криптографической защиты информации очень часто зависит именно от способа генерирования случайных чисел [5].

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

Тогда прибегают к алгоритмическим приемам на вычислительных машинах.

Компьютеры конструктивно относятся к детерминированным системам, поэтому синтез случайных чисел на них не является тривиальной задачей [6].

В современных ЭВМ имеются аппаратные или программные средства для генерирования случайных чисел, которые симулируют хаотический процесс с равномерным законом распределения и являются важнейшим криптографическим примитивом. Имитируемые последовательности, хотя и детерминированные, их статистические свойства по определенным критериям близки к характеристикам случайных чисел.

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

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

В других задачах последнее вовсе не обязательно.

Постановка задачи. В последнее время достигнуты определенные успехи в части разработки устойчивых генераторов случайных (псевдослучайных) чисел (ГСЧ).

Этот процесс особенно интенсифицировался с развитием компьютерной техники и криптографии. Повышенные требования к защите информации и шифровальным процедурам потребовали формирования числовых последовательностей с очень большими периодами.

Для выявления возможных отклонений от случайности синтезируются эффективные статистические тесты [7], основанные на методах теории информации.

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

Причем с достаточно высокими требованиями, например, к той же равномерности распределения чисел на выбранном интервале.

Так, при обработке данных часто очень важен беспристрастный выбор n случайных записей из файла, содержащего N записей. Подобная задача появляется, в частности, при контроле качества или других статистических вычислениях [8, п.3.4.2].

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

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

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

Целью работы является алгоритмизация генерирования равномерно распределенных псевдослучайных чисел на основе золотого сечения (ЗС).

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

формате PDF (247Кб)