3. АНАЛИЗ И ПРОЕКТИРОВАНИЕ ПСЕВДОСЛУЧАЙНЫХ ФУНКЦИЙ С ПОВЫШЕННОЙ ЭФФЕКТИВНОСТЬЮ

3.1 Применение псевдослучайной функции в качестве криптографического примитива

Псевдослучайные функции (PRFs - pseudorandom functions, ПСФ) впервые были определены Голдрайхом (Oded Goldreich), Голдвассером (Sha? Goldwasser) и Микали (Silvio Micali) в 1986 году [54] и с тех пор являются фундаментальным строительным блоком в современной криптографии, имея множество различных применений. Первая идея использования ПСФ для задач шифровании была предложена создателями в [55]. На сегодняшний день ПСФ широко используются в следующих областях криптографии:

- в шифровании;

- для обеспечения целостности передаваемого сообщения;

- в механизмах электронно-цифровых подписей;

- для генерации ключей из некоторого секретного значения (например, мастер-ключа);

- для аутентификации пользователей.

Выходя за рамки криптографии, ПСФ используются даже для защиты от DoS-атак (атак типа «отказ в обслуживании»).

Кратко говоря, ПСФ неотличима (indistinguishable) от настоящей случайной функции (truly random function). Говоря неформальным языком, ПСФ называется эффективно вычислимая функция, для которой не существует эффективного атакующего алгоритма (злоумышленника), который мог бы различить ПСФ от настоящей случайной функции. Под эффективным алгоритмом понимается любой алгоритм, время выполнения которого укладывается в полиномиальное.

Более точно, ПСФ - это эффективно вычислимая функция вида , где множество K является ключевым пространством, X - областью определения, Y - областью значений. Стойкость ПСФ определяется в ходе двух экспериментов между запросчиком и атакующим алгоритмом ? (рисунок 3.1).

Рисунок 3.1 - Схема взаимодействия запросчика псевдослучайной функции с атакующим алгоритмом в экспериментах по взлому ПСФ

Запросчик в эксперименте Exp_b для ведет себя следующим образом.

В случае если b = 0, запросчик случайным образом выбирает ключ и устанавливает функцию . Это означает, что в ходе описываемого эксперимента запросчик предоставляет доступ к оракулу для ПСФ.

В противном случае, когда b = 1, запросчик выбирает случайную функцию . Таким образом, запросчик осуществляет передачу запросов атакующего алгоритма случайному оракулу.

Атакующий алгоритм ? (адаптивно) отправляет q запросов , принадлежащих множеству X, запросчику, на которые запросчик, в свою очередь, возвращает результаты вычисления функции. В конце концов, эксперимент возвращается выдачей атакующим алгоритмом ? бита , который отображает его решение о том, значения какой именно функции (случайной или ПСФ) он получал.

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

Определение 1. ПСФ является стойкой, если для всех эффективных атакующих алгоритмов величина

является пренебрежимо малой.

К сожалению, самые быстрые ПСФ построены на основе блочных шифров типа AES, и их криптографическая стойкость базируется на узкоспециальных интерактивных предположениях. Их недостаток заключается в том, что противник может осуществлять адаптивные, наиболее эффективные разновидности атак.

3.2 Постановка проблемы и обоснование выбранного решения

В 1996 Мони Наором (Moni Naor) и Омером Рейнголдом (Omer Reingold) [58] была представлена ПСФ, стойкость которой была выведена из сложности решения проблемы принятия решения Диффи-Хеллмана (DDH). ПСФ Наора-Рейнголда определяется следующим образом: на ее вход поступают m-битная строка и секретный ключ , результатом работы является

(3.1)

Вычислительная сложность этой функции составляет m-1 модулярных умножений для вычисления w и одно заключительное возведение в степень.

Алгебраическая конструкция ПСФ Наора-Рейнголда лежит в основе многих криптографических схем и даже таких алгебраических конструкций, как верифицируемые случайные функции (VRFs), рассеянные и распределенные ПСФ.

В 2010 году Дан Бонех, Харт Монтгомери и Анан Рагунатан представили в [47] конструкцию расширенного каскада и на его основе построили эффективную ПСФ, основанную на ПСФ Додиса-Ямпольского, а так же доказали ее стойкость.

Нами была разработана алгебраическая ПСФ, имеющая точно такой же размер области определения, как ПСФ Наора-Рейнголда и Бонеха-Монтгомери-Рагунатана (БМР ПСФ), но использующая более короткий секретный ключ по сравнению с ПСФ Наора-Рейнголда. Для некоторых параметров ? и n ПСФ на вход принимает входную последовательность вместе с ключом и на выход выдаёт

где (3.2)

Для области определения размером 2^m значение , в следствие чего при вычислении данной функции требуется в раз меньше умножений, но на больше возведений в степень по сравнению с (3.1) для вычисления значения w. В общей сумме нам необходимо умножений для вычисления значения w. Основным преимуществом данной ПСФ является использование меньшего объема памяти для вычисления значения функция, так как она использует ключ в раз меньший размером по сравнения с ПСФ Наора-Рейнголда. Стойкость ПСФ основывается на предположении о сложности решения ?-DDH проблемы. Взаимосвязь между стойкостью функции и значением ? следующая: чем больше ?, тем более строгим становится это предположение, и тем менее стойкой становится функция. Таким образом, необходимо выдерживать небольшое значение ?. В качестве примера можно привести значения ??= 16 или 256 как достаточно разумные.

Для доказательства стойкости получившейся ПСФ предлагается использование определенной в [47] конструкции расширенного каскада, позволяющего конструировать ПСФ с большой областью определения из ПСФ с малой областью определения. Его структура является модификацией классического каскада (рисунок 3.2а), представленного Беллари, Каннети и Кравчуком в [46], и изображена на рисунке 3.2б. Конструкция классического каскада имеет один существенный недостаток: размерность выходного значения лежащий в его основе ПСФ должна быть не менее длины секретного ключа. Расширенный каскад этого требования лишен.

Интересным свойством рассматриваемого расширенного каскада является отсутствие взаимосвязи между его стойкостью и стойкостью лежащей в его основе ПСФ. Бонех, Монтгомери и Рагунатан в [47] сформулировали достаточное условие лежащей в основе ПСФ, называемое параллельной стойкостью, существование которого обеспечивает стойкость расширенного каскада.

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

(3.3)

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

3.3 Обоснование и использование теоретико-сложностных предположений

Далее под ? будет пониматься циклическая группа (то есть группа простого порядка p с генератором (generator, порождающим элементом) g). Таким образом, . Тогда для векторов и определим операцию возведения в степень как . Возведение скаляра в степень, представленную вектором, определим как . Для матрицы и вектора также определим

где для (3.4)

и для скаляра .

Кроме того, запись [k] обозначает набор значений .

k-DDH предположение. Для обозначим как вектор вида . k-DDH (k-decisional Difffie-Hellman assumption) предположение гласит о том, что обратный элемент неотличим от выбранного случайно элемента из группы . Под неотличимостью в данном случае понимается отсутствие эффективного алгоритма решения указанной проблемы. Более точно, для алгоритма определим преимущество

(3.5)

где , h равномерно распределены на множестве ? и x равномерно распределено на . В случае, если x = 0 мы считаем элемент равным 1 в группе ?.

Определение 2. Для говорят, что k-DDH предположение выполняется в группе ? (или проблема k-DDH трудноразрешима в ?), если для всех эффективных алгоритмов ? преимущество пренебрежительно мало.

Вычислительный вариант этого предположения имеет название ?-слабой проблемы Диффи-Хеллмана (?-wDH) и впервые был введен Мицунари (Shigeo Mitsunari), Сакаи (Ryuichi Sakai) и Касахара (Masao Kasahara) в схеме обнаружения внутренних нарушителей (a traitor tracing scheme) в [57] и звучит следующим образом: для данных g и , принадлежащих группе ?, при трудно вычислить значение . В 2004 году Бонех (Dan Boneh) и Боен (Xavier Boyen) предложили схему короткой электронно-цифровой подписи (signature) [BB04c], основанной на q-сложной проблеме Диффи-Хеллмана, по сути являющейся аналогом рассматриваемой. Это предположение использовалось также в [BB04a, DY05] под названием k-обратного предположения Диффи-Хеллмана (k-DHI). Кроме перечисленных работ, существуют многочисленные протоколы на основе проблемах, подобных q-слабой проблеме Диффи-Хелмана, в том числе и [BB04b, BBG06].

Ясно, что 1-DDH () предположение подразумевает стандартное DDH предположение. Более того, для k-DDH предположение подразумевает существование также ?-DDH предположения при ?< k.

Полезная лемма. Далее нам понадобится следующая лемма из [52] (Лемма 1). Пусть - набор матриц размерности над и пусть Rk₁() - набор матриц ранга 1. Как известно, матрица, имеющая ранг 1, имеет только одну независимую строку или столбец.

Пусть ? - группа простого порядка p с генератором g. Пусть матрицы A₀ и A₁ равномерно распределены на множествах Rk₁() и соответственно. Для алгоритма определяем преимущество атакующего алгоритма ?, отличающего A₀ от A₁ как

.(3.6)

Следующая лемма демонстрирует, что если решение DDH сложно в ?, то не существует эффективных алгоритмов, способных отличить матрицу ранга 1, представленной в экспоненциальной форме, от матрицы со случайными значениями, представленной также в экспоненциальном виде.

Лемма 1. Для любого алгоритма ? существует такой атакующий DDH алгоритм ?, выполнение которого занимает примерно такое же время, как и ?, что

(3.7)

3.4 Построение конструкции классического каскада на основе классического решения

Как уже упоминалось, мы будем использовать конструкцию расширенного каскада из [47] для доказательства стойкости разработанной нами функцию. Также нам понадобится теорема из [BCK96b].

Каскадная ПСФ. Каскадная ПСФ, описание которой дается в [BCK96b], дает возможность построить стойкую ПСФ с областью определения Xⁿ из стойкой ПСФ с областью определения X. Конструкция каскада представлена на рисунке 3.2a. Для более формального описания представим некоторую стойкую ПСФ в виде . Каскад этой функции F обозначается как и определяется работой следующего алгоритма:

ВВОД ключ , начальная последовательность

ЦИКЛ ДЛЯ i ОТ 1 ДО n [ШАГ 1]

КЦ

ВЫВОД k_n.

Каскад является генерализацией GGM схемы конструирования ПСФ из псевдослучайного генератора, описанной Годрайхом, Голдвассером и Микали в [54]. Его можно рассматривать в качестве метода конвертирования ПСФ с однобитным доменом в ПСФ с n-битной областью определения. Стойкость конструкции каскада доказывается в [BCK96b] в следующей теореме.

Теорема 2. Для каждого атакующего каскад алгоритма ?, осуществляющего q запросов, существует такой алгоритм ?, атакующий F и осуществляющий также q запросов в ходе атаки, что преимущество

,(3.8)

где ? имеет приблизительно такое же время выполнения, что и ?.

ПСФ на основе расширенного каскада. Расширенный каскад определяется как функция вида

(3.9)

Областью определения расширенной функции является Xⁿ, ключ представляет собой строку вида . Конструкция расширенного каскада представлена на рисунке 3.2б и его функционирование определяется следующим алгоритмом:

ВВОД ключевая последовательность , начальная последовательность

ЦИКЛ ДЛЯ i ОТ 1 ДО n [ШАГ 1]

КЦ

ВЫВОД k_n.

Рисунок 3.2 - Классическая каскадная конструкция с ключом k (a) и конструкция расширенного каскада с ключом (б)

К сожалению, стойкость расширенного каскада совершенно не определяется стойкостью лежащей в его основе ПСФ. Теорема 3 утверждает, что расширенный каскад является ПСФ только в том случае, если лежащая в его основе ПСФ удовлетворяет условию, называемому параллельной стойкостью. Данное свойство заключается в том, что функция F продолжает оставаться стойкой при доступе противника (атакующего алгоритма) к многочисленным экземплярам функции с различными, но связанными ключами.

Для функции и целого числа q > 0 определим q связанных ключей с одним и тем же s где и . Функция F называется q-параллельно стойкой, если результирующий набор из q функций не отличим от q случайных независимых функций.

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

,(3.8)

где и определяет пару ключей , используемой функцией F. Таким образом, эмулирует q копий функции F с ключами для .

Определение 3. ПСФ является q-параллельно стойкой ПСФ, если является стойкой ПСФ.

Отметим отдельно немаловажный факт: функция F может не быть q-параллельно стойкой даже в том случае, если она является стойкой ПСФ.

Теорема 3. Если функция F является q-параллельно стойкой, то расширенный каскад является стойкой ПСФ по отношению к атакующему q запросами алгоритму.

В частности, для каждого алгоритма ?, атакующего расширенный каскад и выполняющего q запросов к нему в ходе атаки, существует такой противник ?, атакующий функцию и выполняющий q запросов к ней в ходе атаки, что

,(3.9)

где ? выполняется приблизительно такое же время, что и ?.

3.5 Применение конструкции расширенного каскада для построения псевдослучайных функций повышенной эффективности

Бонех (Dan Boneh), Монтгомери (Hart Montgomery) и Рагунатан (Ananth Raghunathan) в работе [47] продемонстрировали возможность использования расширенного каскада для проектирования новых ПСФ с большой областью определения из ПСФ с малой областью определения.

3.5.1 Реализация псевдослучайной функции Наора-Рейнголда с помощью расширенного каскада

Лежащая в основе каскада ПСФ определяется следующим образом. Пусть ? - группа простого порядка p и - функция вида

.(3.10)

Введение f в расширенный каскад приводит к образованию функции Наора-Рейнголда , определяемой как

.(3.11)

В работе [58] Наор и Рейнголд доказали стойкость своей ПСФ при существовании DDH предположения в группе ?. Бонех, Монтгомери и Рагунатан подтвердили стойкость функции Наора-Рейнголда [47] путем доказательства q-параллельной стойкости функции f, описанной в (3.10), для любого полинома q в параметре стойкости (параметре безопасности, security parameter) при экспоненциальной сложности (вычислительной неразрешимости) DDH проблемы в группе ?.

Сложность вычисления данной ПСФ составляет n-1 умножений плюс одно финальное возведение в степень.

3.5.2 Построение псевдослучайной функции Бонеха, Монтгомери и Рагунатана на основе псевдослучайной функции Додиса-Ямпольского

Бонех, Монтгомери и Рагунатан построили более эффективную ПСФ, взяв в качестве базовой функции для расширенного каскада ПСФ Додиса-Ямпольского (F_DY), описанную авторами в [53], которая имеет область определения размера ? для некоторого небольшого значения ?.

Стойкость F_DY доказана при существовании ?-DDH предположении. Напомним, что мы [?] означает набор элементов . Функция Додиса-Ямпольского имеет вид и описывается следующим образом:

.(3.12)

Как определялось ранее, значение . Евгений Додис (Yevgeniy Dodis) и Александр Ямпольский (Aleksandr Yampolskiy) стойкость своей функции доказали в следующей теореме.

Теорема 4. Если ?-DDH предположение выполняется в G, тогда функция Додиса-Ямпольского F_DY , определенная в (3.11), является стойкой ПСФ с областью определения ? в качестве полинома в параметре безопасности.

Путем введения функции Додиса-Ямпольского F_DY в расширенный каскад Бонех, Монтгомери и Рагунатан получили еще более эффективную ПСФ F_BMR, имеющую экспоненциальный размер области определения . Итоговая ПСФ F_BMR определяется следующим образом:

.(3.13)

В соответствии с теорией сложности данная функция обрабатывает бит за один блок, в то время как функция Наора-Рейнголда - только один бит за один блок. Стоимость повышения эффективности выражается в использовании более строгого предположения, а именно ?-DDH предположения, описанного раннее. Бонех, Монтгомери и Рагунатан доказали следующую теорему.

Теорема 5. ПСФ, описанная в (3.12), является стойкой при условии выполнения ?-DDH предположения в ?.

Сложность вычисления данной ПСФ определяется n сложениями плюс п-1 умножениями, финальным одним инвертированием и экспоненцированием по модулю. На сегодняшний день это наиболее быстродействующая ПСФ из числа тех, чья стойкость основывается на теоретико-числовом предположении.

3.6 Разработка псевдослучайной функции с экспоненциальной областью определения и доказательство её стойкости

Создание новой эффективной ПСФ аналогично описанному создателями расширенного каскада в [47] алгоритму: первоначально необходимо выбрать ПСФ с малой областью определения, которая ляжет в основу, а затем расширить ее область определения на основе конструкции расширенного каскада. Стойкость новой функции определяется утверждением (теорема 3) о том, что достаточным условием стойкости расширенного каскада является удовлетворение лежащей в его основе функции свойству параллельной стойкости. Для проверки соответствия этому свойству строится функция (3.8) и доказывается ее стойкость.

Если ? - группа простого порядка p, тогда исходная функция представляет отображение , где - ключевое пространство, - область определения и ? - область значения, и определяется как

.(3.14)

Введение функции (3.14) в конструкцию расширенного каскада позволяет получить ПСФ с экспоненциальной областью определения следующего вида:

.(3.15)

Если сравнить получившуюся конструкцию с ПСФ Наора-Рейнголда, то единственным отличием от нее является повышенный размер области определения, какую цель мы и преследовали.

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

Теорема 4. ПСФ, определенная в (3.15), является стойкой при условии неразрешимости ?-DDH проблемы в группе ?.

Согласно теореме 2, для доказательства стойкости новой ПСФ достаточно доказать то, что лежащая в основе расширенного каскада функция, определенная в (3.14), удовлетворяет свойству q-параллельной стойкости. Для этого необходимо определить функцию , эмулирующую q копий функции (3.14) и доказать ее стойкость.

Пусть функция определяется как

,(3.16)

где . Докажем, что она является стойкой ПСФ для всех полиномиальных значений q.

Лемма 5. Если функция f, определяемая как (3.14), является стойкой ПСФ и проблема DDH является тяжелоразрешимой в ?, то функция f является q-параллельно стойкой для любого полинома q в параметре безопасности.

В частности, для каждого атакующего ПСФ алгоритма ?, существуют такие атакующие алгоритмы ?₁ и ?₂, имеющие время выполнения приблизительно равное времени выполнения ? вплоть до полиномиального множителя, что

(3.17)

Так как предположение о сложности решения k-DDH проблемы подразумевает сложность решения DDH проблемы (при k=1 k-DDH предположение является просто DDH предположением), необходимость в дополнительном доказательстве сложности решения DDH проблемы в ? отпадает.

Таким образом, стойкость новой ПСФ зависит от выполнения двух условий: стойкости лежащей в основе каскада функции и трудноразрешимости проблемы DDH в ?. Следующая лемма ограничивает условия стойкости ПСФ f, определенной в (3.14).

Лемма 6. Если ?-DDH проблема является трудноразрешимой для группы ?, то функция f, определенная в (3.14), является стойкой ПСФ с полиномиальным размером области определения ? в качестве параметра безопасности.

В частности, для каждого алгоритма ?, атакующего ПСФ, существует такой атакующий алгоритм ? с приблизительно таким же временем выполнения, что и ? вплоть до полиномиального множителя, что

.(3.18)

Доказательство. Для того, чтобы доказать стойкость функции f, определенной в (3.14), достаточно продемонстрировать, что ? выходных значений этой функции f представляют собой выходную последовательность криптографически сильного (стойкого) псевдослучайного генератора (PRG, ПСГ). Таким образом, доказательство стойкости ПСФ сводится к доказательству того, что выходная последовательность

.(3.19)

является выходной последовательности криптографически стойкого ПСГ при условии существования ?-DDH предположения в ?.

Для определения псевдослучайного генератора необходимо ввести понятие вычислительной неразличимости двух распределений. Формально, два распределения ?₁, ?₂ называются вычислительно неразличимыми, если для любого полиномиального вероятностного алгоритма ?

.(3.20)

Неформально мы можем представить задачу следующим образом. Пусть X и Y - такие множества, что по выбранному случайным образом элементу возможно с помощью некой специальной функции G(x) породить якобы случайный элемент из Y. Будем рассматривать только случаи с мощностью множества Y намного большей мощности множества X, т.е. , иначе задача существенно упрощается. Например, рассмотрим случай, когда X = {0...1000}, Y = {0...100}. Тогда, выбрав случайный , можно легко вычислить y = x div 10, который, очевидно, будет принадлежать Y и будет случайным в силу случайности выбора x.

В случае функция G : X > Y называется псевдослучайным генератором, если и вычислительно неразличимы ( - равномерные распределения)

Напомним, что ?-DDH строка имеет вид . Если рассматривать , то отсюда обратный элемент и =. Другими словами, выходная последовательность ПСГ является представленной в ином виде ?-DDH строкой.

Лемма 7. Если ?-DDH предположение существует для группы ?, то элемент является неотличимым от случайно выбранного элемента . Более точно, для алгоритма преимущество

,(3.21)

где , .

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

Используется следующая последовательность ?+1 гибридных экспериментов между запросчиком и атакующим алгоритмом ?. Пусть ??- алгоритм, умеющий различать псевдослучайную последовательность, выработанную ПСГ G от случайной входной последовательности, от настоящей случайной последовательности. В гибридном эксперименте i запросчик заменяет первые i выходных элемента ПСГ настоящими случайными числами, в то время как последние ?-i элементов являются выработанными ПСГ.

Более точно, при поведение запросчика в гибридном эксперименте Exp_i определяется следующим алгоритмом:

ВВОД: ключи и

ВЫВОД:

ЕСЛИ ТО

ЦИКЛ ДЛЯ j ОТ 1 ДО n [ШАГ 1]:

КЦ

ИНАЧЕ

ЦИКЛ ДЛЯ j ОТ i+1 ДО ? [ШАГ 1]:

КЦ.

Для определим W_i как вероятность совпадения битов b и , то есть правильного распознавания алгоритмом ? последовательности в гибридном эксперименте i. Следует отметить, что в гибридном эксперименте Exp₀ противник ? получает для анализа псевдослучайную последовательность, выданную ПСГ, в то время как в гибридном эксперименте Exp_? противник получает не что иное, как совершенно случайную последовательность. Отсюда

.(3.22)

Из техники гибридного аргумента следует, что существует такое значение , что

.3.23)

Другими словами, в гибридных экспериментах Exp_t и Exp_t+1 получаемые противником последовательности вычислительно неразличимы:

(3.24)

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

.(3.25)

Комбинирование (3.24) и (3.25) доказывает Лемму 6.

В гибридных экспериментах Exp_t и Exp_t+1 атакующий алгоритм ?, с одной стороны, взаимодействует с ?-DDH?запросчиком, а с другой стороны, параллельно эмулирует запросчика ПСГ для атакующего алгоритма ?. Общая схема взаимодействия всех объектов в гибридных экспериментах Exp_t и Exp_t+1 отражена на рисунке 3.4.

Рисунок 3.4 - Схема взаимодействия атакующего алгоритма ? с ?-DDH?запросчиком и атакующим алгоритмом ? в гибридных экспериментах Exp_t and Exp_t+1

На этапе инициализации ?-DDH?запросчик выбирает случайным образом и бит . В случае, если , запросчик выдает алгоритму ? ?-DDH строку , а если , то запросчик выдают последовательность случайных элементов .

Атакующий алгоритм ? осуществляет свои действия в следующем порядке. На этапе инициализации случайным образом выбираются элементы . Затем алгоритм ? получает от своего ?-DDH запросчика некоторую последовательность , где может быть (то есть y - случайно выбранный элемент из множества ?) или . Затем алгоритм ? к t случайным элементам присоединяет полученную от своего запросчика строку и отправляет результирующую последовательность атакующему алгоритму ?. Наконец, атакующий алгоритм ? выдает бит своему запросчику (то есть алгоритму ?), который свидетельствует о его решении по поводу принятой им последовательности. Атакующий алгоритм ?, в завершение всего гибридного эксперимента, просто пересылает тот же самый бит своему запросчика в качестве ответа на то, случайной или ?-DDH стройкой была принятая им последовательность.

В случае если ?-DDH запросчик алгоритма ? выбирает элемент , выдаваемая им строка является случайной, и таким образом алгоритм ? эмулирует эксперимент Exp_t+1 между ПСГ запросчиком и атакующим его алгоритмом ?.

В случае если ?-DDH запросчик алгоритма ?'s выбирает элемент , выдаваемая им строка представляет собой ?-DDH?строку, и таким образом алгоритм ? эмулирует эксперимент Exp_t между запросчиком и атакующим его ?.

Таким образом, мы можем говорить о том, что различение выходной последовательности ПСГ от последовательности случайных чисел сводится к решению ?-DDH проблемы и поэтому может считаться вычислимо неразрешимой задачей. Как и требуется, равенство (3.18) выполняется, что завершает доказательство леммы 6.

Доказательство леммы 5. Наша цель - продемонстрировать явным образом, что функция , определенная в (3.21), является стойкой ПСФ. Для этого предлагается использовать описанную Бонехом, Монтгомери и Рагунатаном в [47] схему доказательства.

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

Game 0. В этой игре запросчик играет роль обычного запросчика для функции , предоставляя атакующему алгоритму ? доступ к оракулу функции , используемому случайный ключ (рисунок 3.5).

Рисунок 3.5 - Схема взаимодействия атакующего алгоритма ? с -??запросчиком в игре Game 0

Game 1. В данном случае запросчик выбирает случайную функцию вида и случайным образом генерирует значения . Затем на запрос от атакующего алгоритма возвращает вычисленное значение (рисунок 3.6).

Рисунок 3.6 - Схема взаимодействия атакующего алгоритма ? с -?запросчиком в игре Game 1

Мы утверждаем, что игры 0 и 1 неотличимы друг от друга в том случае, если функция f - стойкая ПСФ. В частности, существует такой атакующий алгоритм ?₁, время выполнения которого приблизительно равно времени выполнения атакующего алгоритма ?, что

.(3.26)

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

Атакующий алгоритм ?₁ работает описанным ниже образом. На этапе инициализации случайным образом выбираются значения . После этого атакующий алгоритм ?₁ готов обрабатывать запросы алгоритма ? в качестве запросчика и переходит в режим ожидания. Каждый раз, получая запрос от атакующего алгоритма ? вида , атакующий алгоритм ?₁ обращается к своему запросчику с вопросом x , на что последний возвращает некоторое значение y. Затем атакующий алгоритм ?₁ вычисляет значение и отправляет результат в качестве ответа на запрос атакующему алгоритму ?. После выполнения алгоритмом ? q-запросов он принимает решение о том, с оракулом какой функции он имел дело, и в соответствии с этим выдает атакующему алгоритму ?₁ выходной бит b. Игра завершается пересылкой принятого алгоритмом ?₁ бита своему запросчику в качестве решения о том, ответы какого оракула атакующий алгоритм ?₁ получал.

Когда запросчик атакующего алгоритма ?₁ эмулирует доступ к оракулу функции f со случайным образом выбранным ключом (s, h), то он на запрос x атакующего алгоритма ?₁ отвечает результатом вычисления значения ПСФ . Если для определить , то можно считать, что атакующий алгоритм ? на запрос алгоритма ? выдает значение , которое как раз является результатом вычисления псевдослучайной функции. which is precisely . Следовательно, в этом случае атакующий алгоритм ?₁ эмулирует игру Game 0 запросчика с атакующим алгоритмом ?.

Когда запросчик атакующего алгоритма ?₁ эмулирует доступ к случайному оракулу, то есть к случайной функции вида , то ответом запросчика атакующего алгоритма ? (то есть ответом атакующего алгоритма ?₁) на запрос атакующего алгоритма ? является просто некоторое значение , которое полностью совпадает с выданным бы запросчиком в игре Game 1.

Таким образом, два вышеприведенных аргумента полностью доказывают утверждение (3.24).

Game 2. Запросчик предоставляет атакующему алгоритму ? доступ к случайному оракулу, то есть оракулу случайной функции .

Рисунок 3.7 - Схема взаимодействия атакующего алгоритма ? с -??запросчиком в игре Game 3

Свидетельством неразличимости игр Game 1 и Game 2 при условии тяжелоразрешимости проблемы DDH для группы ? может служить лемма 1. Применительно к нашему случаю, в частности, существует такой атакующий DDH проблему алгоритм ?₂, что

.(3.27)

Пусть - запросы атакующего алгоритма ? к своему запросчику. Как уже было сказано, в игре Game 1 запросчик отвечает на запросы атакующего алгоритма ? с использованием случайной функции с выбранными случайным образом значениями . Пусть - матрица вида . Ясно, что A имеет ранг 1.

По окончании процедуры выдачи запросов и получения ответа в игре Game 1 атакующий алгоритм ? имеет q записей в матрице . В игре Game 2 атакующий алгоритм ? получает q случайных элементов, принадлежащих множеству ?, которые мы можем рассматривать в виде q записей в случайной матрице над ? размера. Согласно лемме 1 существует атакующий алгоритм ?₂, который, как и требуется, удовлетворяет условию (3.27).

Комбинируя (3.26) и (3.27), получаем

что и завершает доказательство теоремы 4.

Доказательство теоремы 4 следует из комбинирования теоремы 2 с леммой 9, и показывает, что функция F с параметром ? является стойкой ПСФ при существовании предположения о неразрешимости ?-DDH для группы ?.

Сложность вычисления разработанной ПСФ измеряется умножений при возведении в степень методом «возведения в квадрат и умножения» плюс одно возведение в степень. Таким образом, мы не слишком много теряем в быстродействии, но сокращаем размер ключа в раз, что приводит к уменьшению затрат на память. Помимо этого, амортизирующая сложность вычисления ПСФ будет гораздо ниже, чем сложность вычисления функции для каждого входного значения. Если рассматривать ПСФ с точки зрения аппаратной реализации, то каскадная структура позволяет осуществлять конвейерные вычисления, повышая быстродействие.

3.6 Выводы

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

Приведен пример использования расширенного каскада для построения псевдослучайных функций Наора-Рейнголда и Бонеха, Монгтгомери и Рагунатана, произведена оценка их вычислительной эффективности.

Разработана псевдослучайная функция с большой областью определения и доказана ее криптографическая стойкость. Преимущество получившейся псевдослучайной функции заключается в сокращении длины ключа при таком же порядке количества умножений. Стойкость функции основывается на предположении о сложности решения ?-DDH проблемы в ?, причем необходимо выдерживать небольшое значение ?. Например, оптимально использовать значения ??= 16 или 256.

4. БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ РАБОТЫ

4.1 Общая оценка условий труда оператора ПЭВМ

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

l В соответствии с [16] возможно выделение следующих четырех типов опасных и вредных производственных факторов [2]: физические, химические, биологические и психофизиологические.

l Физические факторы могут быть представлены в виде:

- повышенного уровня электромагнитного излучения;

- повышенного уровня рентгеновского излучения;

- повышенного уровня ультрафиолетового излучения;

- повышенного уровня инфракрасного излучения;

- повышенного уровня статического электричества;

- повышенного уровня запыленности воздуха рабочей зоны;

- повышенного содержания положительных аэроионов или пониженного содержания отрицательных аэроионов в воздухе рабочей зоны;

- пониженной или повышенной влажности воздуха рабочей зоны;

- пониженной или повышенной подвижности воздуха рабочей зоны;

- повышенного уровня шума;

- повышенного или пониженного уровня освещенности;

- повышенного уровня прямой или отраженной блесткости;

- повышенного уровня ослепленности;

- неравномерности распределения яркости в поле зрения;

- повышенной яркости светового изображения;

- повышенного уровня пульсации светового потока;

- повышенного значения напряжения в электрической цепи, замыкание которой может произойти через тело человека.

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

Психофизиологические факторы включают в себя перегрузки различных типов:

- напряжение зрения;

- напряжение внимания;

- интеллектуальные нагрузки;

- эмоциональные нагрузки;

- длительные статические нагрузки;

- монотонность труда;

- большой объем информации обрабатываемой в единицу времени;

- нерациональная организация рабочего места.

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

Так как работа над дипломным проектом проводилась на территории Рурского университете в г. Бохуме, Германия (Ruhr-Universitдt Bochum), ниже будут проанализированы вредные и опасные условия труда на рабочем месте студента в указанном университете в помещении математического факультета.

4.2 Анализ опасных и вредных производственных факторов труда оператора ПЭВМ

В соответствии с [12] в производственных помещениях, в которых работа с использованием ПЭВМ является вспомогательной, температура, относительная влажность и скорость движения воздуха на рабочих местах должны соответствовать [13] (таблица 5.1).

Таблица 5.1 - Оптимальные нормы микроклимата для помещений с ВДТ и ПЭВМ

Период года	Категория работ	Температура воздуха, С, не более	Относительная влажность воздуха, %	Скорость движения воздуха, м/с
Холодный	легкая -1а	22-24	40-60	0,1
	легкая -1б	21-23	40-60	0,1
Теплый	легкая -1а	23-25	40-60	0,1
	легкая -1б	22-24	40-60	0,2

В производственных помещениях, в которых работа с использованием ПЭВМ является основной (вычислительный центр) и связана с нервно-эмоциональным напряжением, должны обеспечиваться оптимальные параметры микроклимата для категории работ 1а (производимых сидя и не требующих физического напряжения, при которых расход энергии составляет до 120 ккал/ч) и 1б (производимых сидя, стоя или связанных с ходьбой и сопровождающиеся некоторым физическим напряжением, при которых расход энергии составляет от 120 до 150 ккал/ч.) в соответствии с [12] (таблица 5.1).

Фактические условия параметров микроклимата соответствуют гигиеническим требованиям и составляют: температура воздуха + 24С, относительная влажность воздуха колеблется в пределах 50-60 %, скорость движения воздуха обычно не превышает 0,1 м/с (исключение составляет регулярное проветривание при открытых настежь окнах и двери).

Содержание вредных химических веществ в воздухе производственных помещений, в которых работа с использованием ПЭВМ является основной или вспомогательной, не должно превышать предельно допустимых концентраций вредных веществ в воздухе рабочей зоны в соответствии с [1].

В помещениях, оборудованных ПЭВМ, должна проводиться ежедневная влажная уборка и систематическое проветривание и очистка экрана от пыли после каждого часа работы на ПЭВМ.

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

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

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

l Естественное и искусственное освещение в помещениях, в том числе и на рабочем месте оператора ПЭВМ, регламентируется нормами СанПиН 2.2.2/2.4.1340-03 Гигиенические требования к персональным электронно-вычислительным машинам и организации работы в зависимости от характера зрительной работы, системы и вида освещения, фона, контраста объекта с фоном.

Рабочие столы следует размещать таким образом, чтобы видеодисплейные терминалы были ориентированы боковой стороной к световым проемам, а естественный свет падал преимущественно слева. Окна преимущественно должны быть ориентированы на север и северо-восток. Оконные проемы должны быть оборудованы регулируемыми устройствами типа: жалюзи, занавесей, внешних козырьков [12].

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

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

Согласно [11] освещение должно обеспечивать КЕО не ниже 1,2 % в зонах с устойчивым снежным покровом и не ниже 1,5 % на остальной территории.

Нормированное значение КЕО выражается в процентах и рассчитывается по формуле [7, 10, 15]:

(4.1)

где N - номер группы обеспеченности естественным светом;

е_н - нормативное значение КЕО;

m_N - коэффициент светового климата.

Расчетное КЕО выражается в процентах и определяется по формуле:

(4.2)

где е_б - геометрический КЕО в расчетной точке при боковом освещении, учитывающий прямой свет от участка неба и рассчитывается по формуле:

(4.3)

где n₁ - количество лучей, проходящих через световые проемы при поперечном разрезе помещения в точке, расположенной в одном метре от стены;

n₂ - количество лучей через световые проемы при продольном разрезе помещения в точке, расположенной на уровне рабочей поверхности;

е_зд - геометрический КЕО в расчетной точке при боковом освещении, учитывающий свет, отраженный от участка фасадов зданий противостоящей застройки (при отсутствии противостоящих зданий принимается равным нулю);

г_а - коэффициент ориентации фасада здания, учитывающий зависимость его яркости от ориентации по сторонам горизонта;

К_з - коэффициент запаса заполнения светового проема;

k_зд - коэффициент, учитывающий изменение внутренней отраженной составляющей КЕО в помещении при наличии противостоящих зданий;

b_ф - средняя относительная яркость участка фасада противостоящей застройки, кд/м²;

в_а - коэффициент, учитывающий неравномерную яркость облачного неба;

r_О - коэффициент, учитывающий повышение КЕО при боковом освещении благодаря свету, отраженному от поверхностей помещения. Этот коэффициент зависит от средневзвешенного коэффициента отражения от стен, пола, потолка (_ср), который определяется по формуле:

(4.4)

где с_п - коэффициент отражения от потолка;

с_р - коэффициент отражения от пола;

с_с - коэффициент отражения от стен;

S_п - площадь потолка, м²;

S_с - площадь стен, м²;

S_о - площадь окон, м²;

S_р - площадь пола, м²;

ф_О - общий коэффициент светопропуска окон:

(4.5)

где ф₁ - коэффициент светопропуска материала;

ф₂ - коэффициент, учитывающий потери света в конструкциях;

ф₃ - коэффициент, учитывающий потери света в переплетах проема;

ф₄ - коэффициент, учитывающий потери света при установке солнцезащитных устройств;

ф₅ - коэффициент, учитывающий потери света в защитной сетке, устанавливаемой под фонарями, принимаемый равным значению ф₅ = 0,9.

Для рассматриваемого помещения ввиду его расположения вне территории РФ отсутствует номер группы административного района по ресурсам светового климата. Тем не менее произведем расчет КЕО, принимая группу равной 5, а коэффициент светового климата m_N и коэффициент запаса для окон общественных зданий соответственно вне зависимости от ориентации окон 0,8. Нормативное значение КЕО при боковом естественном освещении составляет 1,5%

Подставив найденные значения в формулу (4.1), находим нормированное значение КЕО:

(4.6)

Площадь рабочего помещения, потолка и пола составляет каждая 31,35 м², площадь стен 49 м², площадь окон 10,31 м², высота помещения 2,9 м. В рабочем помещении присутствует одностороннее боковое естественное освещение с юго-западной ориентацией световых проемов, что несколько не соответствует требованиям [12], однако помещения в противоположной части корпуса имеют проемы соответственно на северо-запад. Площадь световых проемов составляет 32,8% площади пола. Зрительная работы, выполняемая в помещении, классифицируется разрядом IVв (контраст объекта с фоном большой, фон светлый) как работа средней точности [15].

Количество лучей, проходящих через световые проемы при поперечном и продольном разрезах помещения в точке, расположенной в одном метре от стены, определяется по графикам А. М. Данилюка и равно 12 и 37 соответственно. Подставив эти значения в формулу (4.3), получаем геометрический КЕО в расчетной точке при боковом освещении, учитывающий прямой свет от участка неба:

(4.7)

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

Согласно [12] для внутренней отделки интерьера помещений, где расположены ПЭВМ, должны использоваться диффузно отражающие материалы с коэффициентом отражения для потолка - 0,7 - 0,8; для стен - 0,5 - 0,6; для пола - 0,3 - 0,5, что полностью соответствует описываемым условиям. Коэффициенты отражения от потолка и стен равны 0,7, так как окрашены в белый цвет, коэффициент отражения пола не превышает 0,3 ввиду серой окраски.

Подставив значения коэффициентов и площадей стен, пола, потолка и окон в формулу (4.4), получим средневзвешенный коэффициент отражения от стен, пола, потолка:

(4.8)

С учетом коэффициента светопропускания материала (стекло листовое двойное, 0,8), коэффициентов, учитывающих потери света в переплетах проема (стальные двойные открывающиеся переплеты, 0,6), несущих конструкциях (стальные фермы, 0,9), при установке солнцезащитных устройств (регулируемые жалюзи, 1,0) вычислим по формуле (5.5) общий коэффициент светопропускания окон:

(4.9)

Коэффициент, учитывающий повышение КЕО при боковом освещении благодаря свету отраженному от поверхностей помещения, является табличным значением, зависит от геометрии помещения и в данном помещении составляет Коэффициент запаса заполнения светового проема равен 1,2.

Подстановкой вычисленных коэффициентов в формулу (4.2) получим окончательное значение расчетного КЕО для рассматриваемого помещения оператора ПЭВМ:

(4.10)

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

При недостаточности или отсутствии естественного света в помещении применяют искусственное освещение.

Нормированная минимальная освещенность (освещенность на наиболее темном участке рабочей поверхности) в зоне размещения рабочего документа для оператора ПЭВМ составляет не менее 300 лк. Освещение не должно создавать бликов на поверхности экрана. Освещенность поверхности экрана не должна быть более 300 лк [12].

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

1. Определяется угол падения луча света б в расчетную точку А по формуле:

(4.11)

где d - расстояние от расчетной точки до проекции светильников;

h_р - расчетная высота, м.

2. Определяется величина силы света (J_а) в расчетной точке для угла б для люминесцентной лампы по кривой силы света или по формуле:

(4.12)

где F_л - световой поток люминисцентной лампы, Лм;

L_л - длина лампы, м.

3. Определяется освещенность горизонтальной (Е_г) и вертикальной (Е_в) поверхности:

(4.8)

(4.9)

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

В качестве источников света при искусственном освещении следует применять преимущественно люминесцентные лампы типа ЛБ и компактные люминесцентные лампы [12]. Применение светильников без рассеивателей и экранирующих решеток не допускается. Коэффициент пульсации не должен превышать 5 %.

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

Используются потолочные светильники с люминесцентными лампами OSRAM L/58W/21+840, расположенные тремя параллельными рядами по три светильника и три лампы соответственно на площадь помещения в 31,35 м². Согласно маркировке, источники света имеет цветовую температуру 4000 K, что соответствует солнечно-белому оттенку с относительно низкой светоотдачей, и индекс цветопередачи 85 Ra. Согласно [8] данный тип люминесцентных ламп подпадает под категорию ламп естественного света с улучшенной цветопередачей ЛЕЦЦ. Длина лампы составляет 1,5 м, диаметр 24 мм, потребляемая мощность 58 Ватт, световой поток - 5200 лм.

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

Схема помещения со светильниками в продольном разрезе представлена на рисунке 4.1.

Рисунок 5.1 - Схема расположения светильников в рабочем помещении

Лампы в помещении имеют коэффициент пульсации менее 5 %, что соответствует требованиям [12]. Высота подвески светильников составляет 0,5 м. Длина лампы м, по ширине помещения расстояние между светильниками составляет 0,35 между собой и 0,15 м от стен, по длине - 1,7 м и 0,7 м соответственно. Расчетная точка А находится на расстоянии 0,8 м от пола и 1,6 м от боковой стены помещения. Расстояние от расчетной точки до проекции светильников равняется 0,8 м. Расчетная высота: