Трунов Д.Н.
Копия статьи, опубликованной 17.08.2017 на сайте https://sites.google.com/site/publicworkstrunov
ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ С МЕХАНИЗМОМ ГЛУБОКОГО НАКОПЛЕНИЯ
СЛУЧАЙНЫХ ДАННЫХ DEEPRAND
Копия статьи, опубликованной 17.08.2017 на сайте https://sites.google.com/site/publicworkstrunov
Введение
Генератор случайных (или псевдослучайных) чисел – алгоритм, порождающий
последовательность чисел, элементы которой почти независимы друг от друга и подчиняются
заданному распределению [1]. Слишком явная зависимость элементов порождаемой
последовательности во многих генераторах не позволяет считать получаемые числа
случайными, потому часто их называют псевдослучайными.
В общем случае, генерируемая последовательность вычисляется по функции вида:
Xn = Func(Xn-1, K)
где Xn – текущий элемент последовательности, Xn-1 – предыдущий элемент
последовательности, а K – некая ключевая информация, влияющая на генерацию чисел и
хранимая в секрете. Чаще всего ключ K берётся из источника действительно случайных
данных, к которым относятся, например, аппаратные генераторы случайных чисел [2] или
другие источники: шум звуковой карты, измерение реакции пользователя (время между
нажатиями клавиш на клавиатуре или мыши), счётчик тактов процессора и другие.
Качество генератора определяется характеристиками ключа K и его источника, а также
свойствами генерируемой последовательности. В зависимости от назначения генератора, к
нему могут применяться те или иные требования. Особо строгие требования применяются,
например, к генераторам случайных чисел для лотерей и в средствах защиты информации для
создания паролей и ключей шифрования. Для таких целей подходят далеко не все
существующие алгоритмы.
Требования к генератору случайных чисел
Генераторы случайных чисел можно разделить на две группы: некриптографические и
криптографические. Достоинство первых – эффективная аппаратная и программная реализация.
Недостаток – предсказуемость.
Качественный генератор случайных чисел, ориентированный на использование в системах
защиты информации, должен удовлетворять следующим требованиям [3]:
* криптографическая стойкость;
* статистические свойства: генерируемая последовательность чисел по своим свойствам
не должна отличаться от истинно случайной последовательности;
* большой период формируемой последовательности;
* эффективная аппаратная и программная реализация.
Рассмотрим перечисленные требования подробнее.
Криптографическая стойкость. Основным свойством криптографически стойкого
генератора является непредсказуемость. Из этого следует, что, зная принцип работы генератора
и имея фрагмент вычисленной им последовательности Xi, Xi+1, Xi+2 … Xn, никаким анализом
невозможно определить ключ K или спрогнозировать предыдущий (Xi-1) или следующий (Xn+1)
элемент последовательности.
Статистические свойства. Генерируемая алгоритмом последовательность должна иметь
равномерное распределение, когда вероятность появления одного значения не отличается от
вероятности появления других значений. При неравномерном распределении вероятность
одних возможных значений может существенно отличаться от других. Также важно, чтобы ни один статистический тест не обнаружил в генерируемой последовательности чисел каких-либо
закономерностей, иными словами, не отличил эту закономерность от истинно случайной.
Большой период формируемой последовательности. Каким бы качественным ни был
генератор случайных чисел, рано или поздно он зациклится – начнёт выдавать
последовательность чисел, которая уже была ранее. Периодом последовательности является
количество вычисленных элементов, после которого уже вычисленная последовательность
начинает повторяться. Чем больше период, тем менее предсказуемы результаты вычисления.
Для примера рассмотрим линейный конгруэнтный генератор [4]. Это генератор
следующей формы:
Xn = (a*Xn-1 + b) mod m
Переменные a, b и m – постоянные: a – множитель, b – инкремент, m – модуль. Ключом
служит значение X0.
Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то
генератор будет генератором с максимальным периодом, который будет равен m (например, b
должно быть взаимно простым с m). Если же a, b и m подобраны неудачно, последовательность
может зациклиться намного раньше и её период будет существенно меньше m.
Эффективная аппаратная и программная реализация. Эффективность реализации важна
для лёгкого переноса алгоритма на другие платформы либо для возможности создания
относительно недорогого его аппаратного аналога. Также важна и скорость вычислений, чтобы
работа алгоритма не тормозила работу других программ, зависящих от этого алгоритма.
Идея алгоритма DeepRand
Анализ криптографических генераторов позволяет сделать два основных вывода [3]:
1) существует трудно разрешимое противоречие между качеством формируемых
последовательностей, с одной стороны, и эффективностью программной и аппаратной
реализации генераторов – с другой;
2) непредсказуемость криптографических генераторов основывается на недоказуемых
предположениях о том, что у возможного аналитика не хватит ресурсов (вычислительных,
временных или стоимостных) для того, чтобы инвертировать функцию генератора случайных
чисел.
Учитывая эти два пункта, можно заключить, что попытка найти компромисс между
качеством работы и эффективностью реализации идёт в ущерб надёжности алгоритма, которая
держится на приемлемом, но потенциально уязвимом уровне. Если же пожертвовать
эффективностью реализации и скоростью работы, то можно получить алгоритм, надёжность
которого будет существенно превышать надёжность распространённых аналогов.
При разработке нового алгоритма была поставлена задача генерировать числа, прежде
всего, с особо высокой степенью случайности и непредсказуемости, не предъявляя жёстких
требований к статистическим характеристикам и эффективности реализации. Причём алгоритм
должен функционировать в условиях домашнего компьютера и быть годным для создания
ключей шифрования и паролей, в том числе особо большой длины. Основной же идеей
алгоритма стала глубокая рандомизация (deep randomization) генерируемой последовательности
чисел за счёт применения объёмного (или глубокого) накопителя случайных данных и его
шифрования.
Реализация алгоритма
Одним из самых важных параметров любого генератора случайных чисел является длина
ключа (в битах), от которого зависит количество возможных значений первоначального
истинно случайного числа. На его основе будет генерироваться вся дальнейшая
последовательность чисел, поэтому даже большой период последовательности не играет особо
важной роли, если в алгоритме предусмотрен маленький ключ. Ключ должен быть достаточно большим, чтобы возможный аналитик физически не смог перебрать все их возможные
значения.
В алгоритме DeepRand ключ (он же накопитель случайных данных) представляет собой
массив K из 256 чисел по 32 бита каждый и дополнительное число Cur:
K: Array[0..255] of Cardinal;
Cur: Integer;
Необходимое замечание: здесь и далее фрагменты программного кода приведены с учётом
синтаксиса языка программирования Delphi, известного также как Object Pascal [5].
Таким образом, размер ключа составляет 8192 бита, что достаточно много даже для самых
требовательных задач. Но проблема в другом: где в персональном компьютере брать 8192 бита
истинно случайных данных? Поэтому в алгоритме предусмотрено поэтапное накопление
случайных данных по частям. Каждое их добавление производится с помощью функции
Randomize, которая выглядит следующим образом:
Procedure Randomize(Z: Cardinal);
Var
I: Integer; // счётчик цикла
Begin
// проверка инициализации массива
If Ini = False then
Init;
// внесение изменения в массив
K[0] := K[0] XOR Z;
// зашифровка массива
For I := 1 to 10 do
GFunc;
End;
Добавляемое число Z должно браться из источника действительно случайных данных
(будет рассмотрен далее) и может быть размером до 32 бит включительно. Само добавление
происходит выполнением операции XOR (исключающее ИЛИ) над числом Z и нулевым
элементом массива ключа. При первом добавлении вначале выполняется инициализация
массива процедурой Init, которая заполняет массив K заданными значениями и устанавливает
признак инициализации Ini в состояние «Истина» (True).
После выполнения операции XOR массив ключа 10 раз шифруется функцией GFunc,
обеспечивающей полное изменение всех элементов массива при их глубокой зависимости друг
от друга. Изменение элемента K[0] в конечном итоге отразится на всех элементах ключа.
Функция GFunc является односторонней, что означает возможность произвести только
прямое преобразование исходных данных без практической возможности обратного
преобразования. Считается, что генераторы случайных чисел с использованием односторонних
функций наиболее обоснованы математически [3], однако они не особо распространены из-за
их низкой производительности, что в нашем случае не является помехой.
Добавлять случайные данные с помощью функции Randomize можно неограниченное
количество раз. Объём накапливаемых данных не сможет превысить 8192 бита, поскольку
новые добавления будут лишь видоизменять имеющиеся данные, что также полезно с
практической точки зрения. В идеале при использовании алгоритма нужно регулярно получать
и добавлять случайные данные, чтобы исключить любые попытки предсказать результаты
генерации.
Для получения очередного случайного числа предусмотрены 3 возможные функции:
Function Random: Double;
Function IntRandom(Range: Cardinal): Cardinal;
Function Random32: Cardinal;
Функция Random возвращает дробное (с двойной точностью – double) случайное число в
диапазоне между 0 и 1. Рассмотрим её подробно.
Function Random: Double;
Var
R: Double; // переменная для вычисления случайного числа
R1: Double; // вспомогательная переменная
Begin
// проверка инициализации таблицы рандомизации
If Ini = False then
Init;
// вычисление случайного числа
R := $10000;
R := R * R;
R1 := K[Cur];
R := R1 / R;
// увеличение номера элемента таблицы рандомизации
Cur := Cur + 1;
If Cur > 255 then
Cur := 0;
// изменение таблицы рандомизации
GFunc;
// возврат результата
Result := R;
End;
Для вычисления случайного числа берётся целое число R1 = K[Cur], где Cur – это
текущий элемент массива ключа (таблицы рандомизации). После каждого вычисления значение
Cur увеличивается на единицу, а после 255 – обнуляется. Благодаря этому каждый раз будут
использованы разные элементы массива.
Поскольку число R1 может принимать значение от 0 до 4294967295, дробный результат
вычисляется как R = R1 / 4294967296. В процедуре число 4294967296 показано произведением
двух чисел $10000. Число $10000 – это шестнадцатеричная запись числа 65536. А
65536^2=4294967296.
После каждого вычисления случайного числа (не только дробного) производится
изменение массива ключа по функции GFunc. Это обеспечивает практически полную
неповторимость, случайность и непредсказуемость возвращаемых значений.
Функция IntRandom полностью основана на предыдущей функции и вычисляется
следующим образом:
IntRandom := Round(Random * (Range - 1));
Результатом функции будет целое число в диапазоне от 0 до Range-1 включительно.
Функция Random32 возвращает случайное целое 32-разрядное число без знака, просто
возвращая текущий элемент K[Cur].
Функция шифрования GFunc
Отдельного рассмотрения заслуживает функция GFunc, участвующая в
генерации/шифровании массива ключа. От качества этой функции зависят важные параметры
генерируемых случайных чисел – достаточные статистические характеристики и практическая
невозможность выявления закономерностей между числами.
Функция GFunc представляет собой цикл, в котором последовательно обрабатываются все
элементы массива K[I] с номерами I от 0 до 255. Обработка каждого числа K[I] производится в
следующем порядке:
1. Из массива берутся три 32-разрядные числа A, B, C. При этом A = K[I], B = K[I + 1], C =
K[I +2]. Если I + 1 или I + 2 выходят за пределы 255, то берутся значения L[0] или L[1]. Массив
L – временная копия массива K, сделанная до начала цикла.
2. Определяется 32-разрядный адрес Adr по некоторой функции Adr = Func1(A, B, C).
Этот адрес разбивается на четыре 8-разрядные адреса A1, A2, A3, A4.
3. По адресам A1..A4 определяются четыре 32-разрядных числа A, B, C, D, причём A =
L[A1], B = L[A2], C = L[A3] и D = L[A4].
4. Вычисляется новое значение текущего элемента массива по некоторой функции K[I] =
Func2(K[I], A, B, C, D).
Таким образом, на новое значение K[I] влияет его прежнее значение и значение ещё
четырёх элементов массива L, ещё не тронутых изменениями. Что это будут за значения,
сказать заранее практически невозможно: все адреса определяются в процессе вычисления. А
использование массива L обеспечивает необратимость вычислений: чтобы восстановить любой
элемент массива K, нужно знать оригинальные значения других элементов, а они все уже будут
изменены к концу цикла.
В функции Randomize запуск GFunc производится 10 раз. Этого достаточно, чтобы
изменение, внесённое в элемент K[0], отразилось на каждом другом элементе с вероятностью
практически 100%, что происходит благодаря вовлечённости других элементов массива на
каждом шаге вычисления.
Теперь несколько слов о функциях Func1 и Func2. Это абстрактные обозначения
некоторых вычислений, отражающие лишь задействованные при этом переменные. Так,
функция Adr = Func1(A, B, C) на самом деле выглядит следующим образом:
Adr := A AND B;
F := A AND (NOT C);
Adr := ROL32(Adr XOR F, 7);
F := (NOT B) AND C;
Adr := ROL32(Adr XOR F, 7);
Здесь F – это вспомогательное 32-разрядное целое число без знака, а ROL32 – функция
циклического сдвига влево для 32-разрядных целых чисел. Поскольку Delphi не поддерживает
операции ROL и ROR, функция ROL32 реализована отдельно:
Function ROL32(A, B: Cardinal): Cardinal;
Begin
B := B AND $1F;
Result := (A SHL B) OR (A SHR (32-B));
End;
По функции Adr = Func1(A, B, C) видно, что над числами A, B и C попарно выполняются
простые логические операции (AND, NOT), а результат накапливается в ячейке Adr с
применением операции XOR и циклического сдвига ROL32. Похожим образом реализована и
функция K[I] = Func2(K[I], A, B, C, D), которая выглядит следующим образом:
F := K[I];
F := ROL32(F XOR (A OR B), 7);
F := ROL32(F XOR (NOT (A OR C)), 7);
F := ROL32(F XOR (NOT (A XOR D)), 7);
F := ROL32(F XOR (B OR (NOT C)), 7);
F := ROL32(F XOR ((NOT B) OR D), 7);
F := ROL32(F XOR (NOT (C AND D)), 7);
K[I] := ROL32(K[I] + A + B + C + D, 5) + F;
Поскольку при вычислении применяются элементарные операции (AND, OR, XOR, NOT),
причём над разными парами чисел, все биты чисел A, B, C, D оказывают приблизительно
равное значение на конечный результат. Операция XOR на каждом шаге призвана
ликвидировать возможное смещение вероятности появления 1 или 0 в битах результата.
Циклический сдвиг ROL делает результаты вычислений более непредсказуемыми и позволяет,
в конечном итоге, любому биту исходных данных повлиять на любой бит результата.
Источники случайных данных. Примеры реализации
Алгоритм DeepRand для корректной работы должен получать случайные данные извне,
через функцию Randomize. При каждом запуске этой функции можно добавить целое число от 0
до 4294967295. Скорее всего, добавляемые числа будут намного меньше максимального
значения, но это не столь важно, поскольку случайные данные всё равно будут накапливаться.
Организацию сбора и накопления случайных данных лучше всего возложить на
программу, которая будет работать с этим генератором. Взаимодействуя с пользователем,
любая программа может собрать достаточно много случайных данных: нажатия клавиш,
движения и клики мышью и т.д. Причём собирать такие данные можно как явно, попросив
пользователя произвести некоторые действия, так и неявно, собирая данные непрерывно в
процессе работы программы. Оба способа можно комбинировать.
Нужно учесть, что объём накапливаемых данных достаточно большой и явный сбор
каких-то кликов и нажатий может оказаться для пользователя довольно скучным. Поэтому
рассматривается возможность собирать такие данные, предложив пользователю небольшую и
несложную игру. Одна из таких игр – авторская версия известной игры «Морской бой». Её
отличительная особенность – игра на одном поле (рисунок 1). Игроку не нужно расставлять
свои корабли – ему нужно лишь раскрыть корабли противника за определённое количество
ходов.
Рассмотрим, как это работает. При запуске программы определяется текущее время: часы,
минуты, секунды и миллисекунды. Всего 86400000 возможных вариантов, чуть больше 26 бит
полезных данных. Эти данные отправляются в алгоритм с помощью процедуры Randomize.
Далее программа генерирует игровую комбинацию из 10 кораблей согласно правилам их
расстановки. Игрок, кликая по игровому полю, должен раскрыть все корабли за отведённое
количество ходов. Каждый клик по игровому полю – это координаты точки клика (поле имеет
размеры 300 на 300 пикселей) и время, когда был произведён клик (в миллисекундах). Всего
300*300*1000=90000000 возможных комбинаций. Правда, если учесть, что игрок не будет
кликать по уже проверенным клеткам, а в самой клетке будет стремиться кликнуть ближе к её
центру, то наиболее вероятных комбинаций будет раза в два меньше. Но даже 40-45 млн.
возможных значений с каждого щелчка мышью – тоже весьма неплохо.
Рисунок 1 – Окно игры «Морской бой» - пример игрового сбора случайных данных
Всего за игру будет совершено около 40 кликов по игровому полю. Если считать
количество комбинаций случайных данных, то можно посчитать и так: если 40 млн.
комбинаций с каждого клика повторить хотя бы 35 раз, то это составит 40000000^35, что
приблизительно равно 10^266 возможных комбинаций. Суммарно же контейнер может вместить
около 10^2466 возможных комбинаций случайных данных.
В другой авторской программе – PassGen (рисунок 2) – реализован неявный сбор
случайных данных. Сама программа предназначена для генерации случайных чисел и паролей,
потому её пример приходится кстати. При запуске программы определяется текущее время в
часах, минутах, секундах и миллисекундах, нажатие любой кнопки, раскрытие списка «Состав
пароля», выбор состава, ввод длины пароля или диапазона числа – определяется текущее время
в секундах и миллисекундах. Каждое движение мышью в пределах окна – определяется
текущее время в миллисекундах. Все эти данные накапливаются в алгоритме DeepRand и на их
основе потом генерируются требуемые пароли и числа.
Рисунок 2 – Окно программы PassGen для генерации паролей и случайных чисел
Можно и здесь приблизительно оценить количество случайных комбинаций, например,
при генерации пароля из 10 символов. Итак, запуск программы, определяется время –
24*60*60*1000 комбинаций. Пара движений мыши – 1000^2
комбинаций. Раскрытие списка
состава пароля и выбор состава – (60*1000)^2
. Ещё пара движений мыши и 1000^2 комбинаций.
Затем удалить имевшуюся цифру в поле «Длина» и ввести две цифры (1 и 0) – всего три
нажатия клавиш и ещё (60*1000)^3
комбинаций. Пара движений мыши и клик по кнопке
«Генерировать пароль». Ещё 1000^2
*60*1000. Перемножим все числа, получим что-то около
4*10^54
. Для генерации пароля как раз хватит, но результат существенно хуже, чем в
предыдущем примере. Зато сбор случайных данных происходит неявно и регулярно.
Заключение
В алгоритме генерации случайных чисел DeepRand реализованы несколько ключевых
идей. Во-первых, механизм глубокого накопления случайных данных. В рассмотренных
примерах показано, что взаимодействие программы и пользователя достаточно непредсказуемо
в деталях и несёт в себе много случайной информации, которую важно вовремя собирать и
правильно обработать. Причём случайной информации часто бывает меньше, чем в состоянии
накопить сам генератор. То есть имеется даже некий запас объёма (или глубины).
Во-вторых, накопление может происходить постоянно в процессе работы программы и её
взаимодействия с пользователем. Чем больше случайных данных будет накоплено, тем лучше
это отразится на непредсказуемости генерируемых последовательностей. Что очень важно, в
том числе, при создании паролей и ключей шифрования. При этом накопитель физически не
может переполниться: добавляемая в него информация просто обновляет собой всю
содержащуюся в нём информацию.
В-третьих, в алгоритме DeepRand вполне допустимо чередовать генерацию и
рандомизацию (добавление случайности в алгоритм). Не во всех алгоритмах это приемлемо,
поскольку такой подход часто приводит к ухудшению статистических характеристик
генерируемых последовательностей. Кроме того, очередная рандомизация во многих
генераторах стирает следы предыдущей рандомизации и часто не является независимой от неё.
Наконец, данный алгоритм не привязан к конкретному источнику случайных данных и
может получать их из любого доступного источника. Правда, работа с источником случайных
данных, в таком случае, выходит за пределы алгоритма и возлагается на программу,
работающую с ним. В некоторых случаях это может стать недостатком, особенно при
неправильном и поверхностном подходе к работе с таким генератором.
Источники информации
1. Википедия. Генератор псевдослучайных чисел. [Электронный ресурс] Режим доступа:
https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел
2. Википедия. Аппаратный генератор случайных чисел. [Электронный ресурс] Режим
доступа: https://ru.wikipedia.org/wiki/Аппаратный_генератор_случайных_чисел
3. Абашев А.А, Жуков И.Ю., Иванов М.А., Метлицкий Ю.В., Тетерин И.И. Ассемблер в
задачах защиты информации. – М.: КУДИЦ-ОБРАЗ, 2004. – 544 с.
4. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на
языке Си. – М.: Триумф, 2002. – 816 с.
5. Marco Cantu. Object Pascal Handbook. The Complete Guide to the Object Pascal
programming language for Delphi developers. – Piacenza (Italy), July 2015
Комментариев нет:
Отправить комментарий