Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
акула
Случайный оракул (random oracle) представляет собой абстрактную функцию, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе случайный оракул на выход выдаёт строку истинно случайных чисел фиксированной длины и записывает пару запрос/ответ в память. При последующих запросах оракул проверяет, был ли такой запрос, и в случае положительного ответа выдаёт записанный ответ. В противном случае цикл повторяется: генерируется и выводится истинно случайная строка, в память записывается пара запроса/ответа. Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при стремящемся к бесконечности количестве запросов его память и быстродействие также должны стремиться к бесконечности.
Под оракулом функции (function oracle) может пониматься черный ящик, обладающий секретным ключом, к которому злоумышленник может обратиться с просьбой выполнить криптографическую операцию, и затем делать на основании его ответов те или иные выводы. Другая аналогия может выступать представление оракула посредником между злоумышленником и неким криптографическим алгоритмом, который принимает запрос от злоумышленника, передаёт их в качестве входных данных для алгоритма, а затем возвращает результат его выполнения злоумышленнику.
Модель запросчика функции (function challenger) является объединением описанных выше моделей. В зависимости от результата подброшенной случайной монеты запросчик предоставляет доступ либо к случайному оракулу, либо к оракулу функции, тем самым за запрос атакующего алгоритма отвечая случайным значением или действительно вычисленным по алгоритму. Модель запросчика часто используется в интерактивных доказательствах в экспериментах по неразличимости выдаваемых алгоритмом значений от выбранных случайным образом.
.5 Выводы
В главе проведен системный анализ существующих методов оценки стойкости криптографических алгоритмов. Описаны элементы информационно-сложностной модели оценки стойкости, обоснован выбор её принятия. Рассмотрены основные теоретико-числовые предположения: проблема принятия решения Диффи-Хеллмана и её вычислительная разновидность. Представлена модель случайного оракула, оракула функции и запросчика.
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 - Схема взаимодействия запросчика псевдослучайной функции с атакующим алгоритмом в экспериментах по взлому ПСФ
Запросчик в эксперименте Expb для ведет себя следующим образом.
В случае если b = 0, запросчик случайным образом выбирает ключ и устанавливает функцию . Это означает, что в ходе описываемого эксперимента запросчик предоставляет доступ к оракулу для ПСФ.
В противном случае, когда b = 1, запросчик выбирает случайную функцию . Таким образом, запросчик осуществляет передачу запросов атакующего алгоритма случайному оракулу.
Атакующий алгоритм ? (адаптивно) отправляет q запросов , принадлежащих множеству X, запросчику, на которые запросчик, в свою очередь, возвращает результаты вычисления функции. В конце концов, эксперимент возвращается выдачей атакующим алгоритмом ? бита , который отображает его решение о том, значения какой именно функции (случайной или ПСФ) он получал.
Для величина Wb определяется как вероятность того, что атакующий алгоритм выдаст 1 в Expb, то есть в Expb правильно угадает, выходные значения случайной или псевдослучайной функции были им получены.
Определение 1. ПСФ является стойкой, если для всех эффективных атакующих алгоритмов величина
является пренебрежимо малой.
К сожалению, самые быстрые ПСФ построены на основе блочных шифров типа AES, и их криптографич