- •Вопрос 1.
- •Вопрос 2.
- •Вопрос 3.
- •Формальное описание
- •Комментарии к алгоритму.
- •Вопрос 4.
- •Умножение и факторизация
- •Возведение в квадрат и извлечение квадратного корня по модулю
- •Дискретное экспоненцирование и логарифмирование
- •Криптографические хэш-функции
- •Другие претенденты
- •Вопрос 6.
- •1. Заполнение памяти.
- •2. Определение ключа.
- •Вопрос 7.
- •Вопрос 8.
- •Вопрос 9.
- •Применение.
- •Преимущества
- •Недостатки.
- •Вопрос 10.
- •Вопрос 11.
- •Обеспечение целостности данных с использование шифрации и mac
- •Вопрос 12.
- •Использование хеш-функций
- •Симметричная схема
- •Асимметричная схема
- •Пример алгоритмов.
- •Модели атак и их возможные результаты.
- •Вопрос 13.
- •Вопрос 14.
- •Вопрос 15.
- •Вопрос 16.
Формальное описание
Входные данные: a — целое число, b — натуральное, нечётное, больше единицы.
Выходные данные: — символ Якоби
1 (проверка взаимной простоты). Если НОД (a, b)≠1, выход из алгоритма с ответом 0.
2 (инициализация). r:=1
3 (переход к положительным числам).
Если a<0 то
a:=-a
Если b mod 4 = 3 то r:=-r
Конец если
4 (избавление от чётности). t:=0
Цикл ПОКА a – чётное
t:=t+1
a:=a/2
Конец цикла
Если t – нечётное, то
Если b mod 8 = 3 или 5, то r:=-r.
Конец если
5 (квадратичный закон взаимности). Если a mod 4 = b mod 4 = 3, то r:=-r.
c:=a; a:=b mod c; b:=c.
6 (выход из алгоритма?). Если a≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом r.
Комментарии к алгоритму.
В алгоритме везде берётся наименьший положительный вычет (то есть остаток от деления).
На четвёртом шаге используется мультипликативность символа Якоби, а затем вычисляется символ Якоби . Чтобы избежать лишнего возведения в степень, проверяется только остаток от деления b на 8.
На пятом шаге тоже вместо возведения в степень используется проверка остатков от деления.
Сложность алгоритма равна битовых операций.
Вопрос 4.
Функция f: {0, 1}* → {0, 1}* является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью.
Существование.
Существование односторонних функций не доказано. Если f является односторонней функцией, то нахождение обратной функции является трудновычислимой (по определению), но легкопроверяемой задачей (путем вычисления f на ней). Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, не известно, влечет ли за собой P ≠ NP существование односторонних функций.
Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи.
Формальное определение…
Пусть - множество всех двоичных строк длины . Под функцией мы понимаем семейство , где , . Для простоты изложения мы предполагаем, что пробегает весь натуральный ряд и что каждая из функций всюду определена.
Функция называется честной, если существует полином такой, что для всех .
Определение 1. Честная функция называется односторонней, если
1. Существует полиномиальный алгоритм, который для всякого вычисляет .
2. Для любой полиномиальной вероятностной машины Тьюринга выполнено следующее. Пусть строка выбрана наудачу из множества (обозначается ). Тогда для любого полинома и всех достаточно больших
Вероятность здесь определяется случайным выбором строки и случайными величинами, которые использует в своей работе.
Условие 2 качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга может по данному найти из уравнения лишь с пренебрежимо малой вероятностью.
Далее описаны несколько претендентов на односторонние функции. Не известно, являются ли они действительно односторонними. Но обширные исследования пока не смогли найти эффективный обратный алгоритм к каждой из них.