Новые конструкции криптографических примитивов, основанные на полугруппах, группах и линейной алгебре

• Автор: Николенко, Сергей Игоревич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 120 с.

Оглавление
1 Введение
1.1 Криптография как раздел информатики
1.2 Модели вычислений
1.3 Основные определения современной криптографии
2 Новые конструкции полных односторонних функций
2.1 Введение
2.2 Задача достижимости с распределением для полусистем

2.3 Задача Поста
2.4 Полная односторонняя функция, основанная на задаче
поиска замощения
2.5 Полная односторонняя функция, основанная на полуси-
стемах Туэ
2.6 Полная односторонняя функция на базе задачи Поста
2.7 Полные односторонние функции и Б1з1ПР-трудные комбинаторные задачи
2.8 Полные односторонние функции в большей общности
3 Новые конструкции криптографических примитивов, доказуемо надёжных в слабом смысле
3.1 Введение
3.2 Определения
3.3 Матрицы сложных функций
3.4 Исключение гейтов
3.5 Две конструкции

3.6 Семейство функций с секретом, надёжных в слабом смысле
3.7 Функция с секретом с экспоненциальной гарантией надёжности
4 Новые алгебраические конструкции криптографических примитивов
4.1 Алгебраическая криптография
4.2 Ослабленные результаты современной криптографии
4.3 Доказуемый взлом
4.4 Определения
4.5 Криптосистемы, основанные на инвариантах групп, и их
доказуемый взлом
4.6 Дерево групп
4.7 Листья дерева
4.8 Атаки на криптосистемы, основанные на инвариантах
4.9 Схема согласования ключа Аншель-Аншеля-Голдфельда
и её устойчивость против взлома с доказательством
Литература

Глава
Введение
1.1 Криптография как раздел информатики
Классическая криптография, понимаемая как способ передать сообщение так, чтобы противник не сумел его расшифровать, применялась, наверное, с тех самых пор, как люди впервые задумались о том, как передавать друг другу сообщения. Различного рода шифры, в том числе весьма изящные, применялись ещё в античности. Древние греки (точнее, спартанцы) использовали так называемые скиталы: цилиндры, на которые наматывались узкие полоски пергамента. Затем текст писали на полоске поперёк цилиндра; получался перестановочный шифр, для декодирования которого нужно было снова намотать пергамент на цилиндр такой же толщины [78]. Юлий Цезарь считается изобретателем шифра Цезаря, в котором каждый символ алфавита заменяется на другой, отстоящий от него в алфавите на некоторое фиксированное число позиций (смещение). Краткое руководство по использованию шифров для обмена любовными посланиями содержит даже «Камасутра».
Довольно давно' появились и первые работы, направленные на взлом шифров. Разумеется, если кто-то что-то от кого-то скрывает, значит, это может иметь ценность, и эту ценность порой можно было добыть успешной дешифровкой. Такие, сугубо прикладные работы, конечно, велись с самого появления шифров. Однако появлялись и теоретические исследования. Например, и шифр Цезаря, и большинство других кодов и шифров, использовавшихся в античности и средние века, не были устойчивы против метода частотного анализа, при котором наиболее вероятная расшифровка того или иного сим-

1Д состоит из следующих правил для каждой строки и Є В:
ей —> Зіші,
вій —>
и$1$ —> Б2и$,
иЭ2 —> 52П,
$Э2 $Э,
где б, Б], вг, $ — вспомогательные символы. Эти правила нужны для того, чтобы переписать исходную строку БХ$ в $эх$. Поскольку X можно единственным образом записать как щ ... ит для некоторых гц 6 £>, это преобразование можно выполнить за 2т + 1 < 2|х| + 1 шагов.
ТД состоит из правил подстановки, соответствующих инструкциям машины Тьюринга.
1. Для каждого состояния ч £ С2 {Н}, р 6 (Д а, Ь, с 6 {0,1, В):
7ТМ(ч, а) = (р,Ь, К) =4 час —> Ърс, ча$ —> ЪрВ$ € 1Д.
2. Для каждого состояния Ч е <3 {Н}, р е СД а, Ь, <1 6 {0,1, В} и с € {0,1, $},
7Гдд(ч, а) = (р,Ь,1_) =4 брас —> p6.bc, б.чВ$ —> рбЪВ$ е 1Д
для а ф В, с ф $, или Ъ Ф В.
В] и 1Д полностью аналогичны конструкции, приведённой в [134], где она используется для доказательства полноты в среднем задачи эквивалентности слов в полусистеме Туэ. Благодаря свойствам динамической двоичной схемы использующиеся в системе строки однозначно декодируются, а правила подстановки соотвествуют инструкциям машины Тьюринга. Третья часть конструкции [134] направлена на то, чтобы перевести результат из $зу$, где -у — результат вычисления машины Тьюринга, в запись последовательности вычислений (протокола) машины Тьюринга. Это и используется для доказательства того, что недетерминированные полусистемы Туэ DistNP-cлoжны.