Файл: Образовательная программа Компьютерный анализ и интерпретация данных к защите допустить Зав каф. Сиб.docx

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

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

---

ГЛАВА 2. КОМПЬЮТЕРНЫЙ АНАЛИЗ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

2.1. Понятие псевдослучайных чисел и генераторов псевдослучайных чисел

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

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

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

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

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

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

---

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

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

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

Линейно конгруэнтный метод (ЛКМ) – один из самых популярных представителей ГПСЧ. Одна из причин широкого использования этого метода заключается в его простоте. Данный метод описывается следующей формулой:

(2.1)

, где X_n - текущее значение ПСЧ;

a, c, m - параметры метода.

Для достижения наилучшего результата генерации последовательности большую роль играет выбор значений для параметров. Неудачные значения могут быть причиной малого периода итоговой последовательности. Например, параметр m должен быть простым числом, а параметры a и c – взаимно простыми. В таблице 2.1 приведено описание и ограничения всех параметров метода.

Таблица 2.1

Параметры линейно-конгруэнтного метода

Параметр	Тип	Ограничения	Описание
a	простое	0 ≤ a < m	Множитель (мультипликатор)
c	простое	0 ≤ с < m	Приращение (инкремент)
m	натуральное	m ≥ 2	Модуль, а также диапазон значений в последовательности (от 0 до m)
X0	натуральное	0 ≤ X0 ≤ m	Начальное состояние (seed)

---

ЛКМ обладает высокой скоростью генерации ПСЧ, однако имеет существенные недостатки: ограниченная равномерность распределения, короткий период и низкая криптографическую стойкость.

Выходные последовательности данного метода имеют так называемую «решетчатую» структуру, то есть являются легко предсказуемыми, и следовательно его метода в криптографии нежелательно [5].

Очевидно, что длина периода ЛКМ не может быть больше числа m, так как значение, получаемое на выходе на каждой итерации есть результат деления по модулю на m. При этом длина периода равна m только в том случае, когда параметры метода удовлетворяют следующим трем условиям:

1) числа c и m – взаимно простые (то есть НОД (c, m) = 1);

2) значение (a – 1) кратно p для всех простых p – делителей m;

3) значение (a – 1) кратно 4, если m кратно 4.

На практике параметр m выгодно выбирать равным 2^e, где e – это количество бит в машинном слове. Это связано с тем, что данная величина параметра позволяет избавиться от относительно затратной по времени операции приведения по модулю.

В таблице 2.2 приведен пример работы генератора при следующих значениях: X₀ = 6; a = 2; c = 3; m = 10.

Таблица 2.2

Пример работы Линейно-конгруэнтного метода

Xn	Вычисления	Результат
X0		6
X1	= (2*6 + 3) mod 10 = 15 mod 10 =	5
X2	= (2*5 + 3) mod 10 = 13 mod 10 =	3
X3	= (2*3 + 3) mod 10 = 9 mod 10 =	9
X4	= (2*9 + 3) mod 10 = 21 mod 10 =	1
X5	= (2*1 + 3) mod 10 = 5 mod 10 =	5

Значение, выдаваемое генератором на 5 шаге, идентично значению на 1 шаге. Очевидно, что далее последовательность будет повторяться.

Таким образом, генератор образует группу значений {5, 3, 9, 1}, называемую периодом.

---

---