Криптографические методы защиты информации. Односторонние функции и система Диффи-Хеллмана. (Лекция 2) презентация

КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ

ПРЕДЫСТОРИЯ И ОСНОВНЫЕ ИДЕИ Для того, чтобы лучше понять идеи, лежащие в основе ряда криптографических схем и алгоритмов, рассмотрим три практически важные проблемы. Чуть позже мы увидим, насколько легко и красиво они решаются при помощи так называемых односторонних функций. Проблемы следующие: Проблема хранения паролей в компьютере; Проблема ПВО; Проблема, возникающая в сетях с удаленным доступом.

ПРОБЛЕМА ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕ При хранении логинов и паролей в компьютере администратор может прочитать их и воспользоваться в своих целях.

ПРОБЛЕМА, ВОЗНИКАЮЩАЯ В СИСТЕМАХ ПРОТИВОВОЗДУШНОЙ ОБОРОНЫ При пересечении границы самолет посылает сигнал о том, что он «свой». «Враг» перехватывает сигнал и затем, перелетая через границу, отсылает перехваченный сигнал. База принимает его за «своего».

КАК РЕШАТЬ ЭТИ ПРОБЛЕМЫ? Для решения этих и некоторых других проблем можно использовать односторонние функции.

ОДНОСТОРОННЯЯ ФУНКЦИЯ (ОПРЕДЕЛЕНИЕ) Функция называется односторонней, если она вычисляется относительно быстро, а обратную к ней вычислить за реальное время невозможно. То есть теоретически можно, но практически нельзя. Например, y=f(x) вычисляется за 10 секунд, x=f-1(y) вычисляется за 100000 лет.

ОДНОСТОРОННЯЯ ФУНКЦИЯ, КОТОРУЮ МЫ БУДЕМ ИСПОЛЬЗОВАТЬ Возведение в степень по модулю y = ax mod p. Пример. Вычислим a64. Медленный (наивный) способ: a64 = a*a*a* … *a (63 умножения).

БЫСТРЫЙ СПОСОБ УМНОЖЕНИЯ Быстрый способ: a64 = (((((a2)2)2)2)2)2 (6 умножений) 64 = 26.

НЕДОСТАТОК РАССМОТРЕННОГО СПОСОБА – ОН РАБОТАЕТ ТОЛЬКО ДЛЯ СТЕПЕНЕЙ ДВОЙКИ. Можно ли расширить его так, чтобы возводить в степень можно было любые числа? Идея. 768169 = 765536 * 72048 * 7512 * 764 * 78 * 70

БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ОПИСАНИЕ АЛГОРИТМА)

БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ПРИМЕР)

БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ПСЕВДОКОД)

ДИСКРЕТНЫЙ ЛОГАРИФМ Дискретный логарифм – это функция, обратная к y = ax mod p. x = logay mod p. Не существует эффективных алгоритмов ее вычисления. Определение. Вычисление дискретного логарифма называется дискретным логарифмированием.

МЕТОДЫ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ

СРАВНЕНИЕ СЛОЖНОСТИ ПРЯМОЙ И ОБРАТНОЙ ФУНКЦИИ БЫСТРОГО ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ

РЕШЕНИЕ ПРОБЛЕМЫ ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕ На компьютере хранится не логин и пароль, а логин и y(пароль) т.е. y = aпароль mod p. (параметры a и p как-то выбираются и могут быть известны всем) Когда пользователь входит в систему, то от его введенного пароля вычисляется односторонняя функция и сравнивается с хранящимся на компьютере значением.

РЕШЕНИЕ ПРОБЛЕМЫ ПВО База генерирует случайное число R и передает (открыто) его самолету. Самолет вычисляет y = aпароль|R mod p. и передает сигнал на базу. Если «враг» перехватит y и отошлет его на базу, то за «своего» не сойдет. Потому что для него число R уже будет другим.

ВЫВОДЫ Надежность рассмотренных криптосистем основана на том, что враг не может практически вскрыть систему. Фактически мы предлагаем врагу решить задачу дискретного логарифмирования для больших чисел. Однако не доказано, что более эффективных алгоритмов не существует. Поэтому может быть кто-то придумает очень быстрый алгоритм дискретного логарифмирования, и вся криптография устареет в один миг.

КРИПТОСИСТЕМА С ЗАКРЫТЫМ (СЕКРЕТНЫМ) КЛЮЧОМ

КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ

ОТЛИЧИЕ КРИПТОСИСТЕМЫ С ЗАКРЫТЫМ КЛЮЧОМ ОТ КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ Криптосистема с закрытым (секретным) ключом подразумевает наличие защищенного канала, по которому передается секретный ключ. Криптосистема с открытым ключом не подразумевает наличие защищенного канала, по которому передается секретный ключ.

ПРИМЕРЫ СЕКРЕТНЫХ КАНАЛОВ (ЭТО ДОРОГИЕ КАНАЛЫ) Личная встреча Курьерская почта Охраняемый поезд ………… Дорогой канал – это значит труднодоступный, медленный, имеющий высокую стоимость. Им нельзя воспользоваться в любой момент.

ПРИМЕРЫ НЕЗАЩИЩЕННЫХ КАНАЛОВ ( ЭТО ДЕШЕВЫЕ КАНАЛЫ) Интернет Телефон Обычная почта E-mail ………. Дешевый канал – это значит легкодоступный, быстрый, имеющий невысокую стоимость. Им можно воспользоваться в любой момент.

ЕЩЕ ОДИН НЕДОСТАТОК ОБМЕНА СЕКРЕТНЫМИ КЛЮЧАМИ Вопрос. Сколько нужно ключей, если N абонентов хотят общаться попарно безопасно? Ответ N*(N-1)/2 Примерно N2/2

СИСТЕМА ДИФФИ-ХЕЛЛМАНА (ПЕРВАЯ КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ) Цель системы Диффи-Хеллмана – без помощи защищенного канала сформировать секретный ключ, который будет использоваться при шифровании какой-то системой с секретным ключом. То есть сама система Диффи-Хеллмана выступает в роли защищенного канала.

СИСТЕМА ДИФФИ-ХЕЛЛМАНА ДЛЯ АБОНЕНТОВ A, B, C…. (ВЫБОР ПАРАМЕТРОВ) Выбрать большое простое p. Выбрать g, такое что числа 1, 2, …. ,p-1 могут быть представлены как степени g по модулю p. Алгоритм, как это сделать, описан далее. Каждый абонент выбирает свое число X и хранит его в секрете. Каждый абонент вычисляет число Y и публикует его. Общий секретный ключ вычисляется на основании открытого ключа собеседника и своего секретного ключа.

ПАРАМЕТРЫ ПОЛЬЗОВАТЕЛЕЙ В СИСТЕМЕ ДИФФИ-ХЕЛЛМАНА

ВЫЧИСЛЕНИЕ ОБЩЕГО КЛЮЧА С ПОМОЩЬЮ СИСТЕМЫ ДИФФИ-ХЕЛЛМАНА

ВЫБОР ПАРАМЕТРА G

СИСТЕМА ДИФФИ-ХЕЛЛМАНА (ПРИМЕР)

ЛИТЕРАТУРА Рябко, Фионов Основы современной криптографии Глава 2

ПРАКТИЧЕСКОЕ ЗАДАНИЕ Реализуйте одностороннюю функцию – быстрое возведение в степень по модулю. Реализуйте систему Диффи-Хеллмана. Не забудьте, что для возведения в степень нужно использовать созданную одностороннюю функцию.