Чижов Иван Владимирович, к.ф.-м.н.
* Похожа на ЯЩИК с Врезным замком * Ключ – это ключ от замка * Зашифровать = закрыть ящик и запереть замок * Расшифровать = отпереть замок и открыть ящик ГОСТ AES
Достоинства * Достаточная стойкость при сравнительно коротком ключе * Как правило очень быстрые алгоритмы Недостатки * Как распределять и передавать ключи, особенно когда абоненты находятся далеко друг от друга?
Появление сети Интернет * 1957 – Министерство обороны США дает задание на создание компьютерной сети * 1969 – Создание сети ARPA.NET между Калифорнийским университетом в Лос-Анджелесе, Стэнфордским исследовательским центром, Университетом Юты и Университетом штата Калифорния в Санта-Барбаре. * 1971 – первая почтовая программа
Задачи защиты информации * Конфиденциальность – нужна по большей части военным для защиты гос. тайны (до появления Интернета) * Целостность – нужна как военным, так и нам с вами (появление сетей) * Доступность – нужна в основном нам с вами (распространение Интернета)
Задача * АНЯ находится в Москве, а БОРИС отдыхает в Магадане. Для обмена сообщениями они хотят использовать блоковый шифр (ящик с врезным замком). Как им выработать общий секретный ключ шифрования? * Головоломка Меркля АНЯ БОРИС
АНЯ БОРИС Известно ВСЕМ. Для удобства Секретны. Покупаются по согласованию в магазине
АНЯ БОРИС
АНЯ БОРИС
АНЯ БОРИС
АНЯ БОРИС
АНЯ БОРИС
АНЯ БОРИС Должен перебрать 3 ключа
АНЯ БОРИС
АНЯ БОРИС Должна перебрать 3 ключа
АНЯ БОРИС
СЕМЕН - РЕДИСКА Перехватил от АНИ 5 опробований
СЕМЕН - РЕДИСКА Перехватил от БОРИСА 3 опробования 8 опробований
Выводы * Для получения ключа легальному абоненту требуется выполнить N операций опробывания ключа * Для получения ключа злоумышленнику требуется выполнить около N*N операций опробывания ключа * Такой разрыв в настоящее время недостаточен!!!!
1976 года «New Directions in Cryptology» Whitfield Diffie, Martin Hellman
АНЯ БОРИС 1. Выбирают общий цвет по телефону
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет 3. Смешивают свой цвет с общим
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет 4. Обмениваются цветами по почте друг с другом
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет 5. Смешивают свой цвет с полученным от товарища
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет 5. Смешивают свой цвет с полученным от товарища
АНЯ БОРИС 1. Выбирают общий цвет по телефону 2. Каждый выбирает свой секретный цвет 6. Получают общий секретный ключ – общий цвет
СЕМЕН - РЕДИСКА Перехватил от АНИПерехватил от БОРИСАЗнает общий цвет
СЕМЕН - РЕДИСКА Перехватил от АНИПерехватил от БОРИСАЗнает общий цвет
СЕМЕН - РЕДИСКА Знает Найти
СЕМЕН - РЕДИСКА Семен, даже не пытайся - это сложная задача
Как складывать, умножать и делить элементы этого множества?
Сложение Остаток от деления (a+b) на p Умножение Остаток от деления ab на p
P=12
Вычитание Деление
Примеры p=12 Сложение 7+11=18 mod 12= 6
Примеры p=12 Умножение 7*11=77 mod 12= 6*12+5=5 mod 12
Примеры p=12 Вычитание 7-11 = -4 mod 12= 12-4 = 8
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = 9 7 * 4 = 28 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = 9 7 * 4 = 28 mod 12 = 4 7 * 5 = 35 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = 9 7 * 4 = 28 mod 12 = 4 7 * 5 = 35 mod 12 = 11 7 * 6 = 42 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = 9 7 * 4 = 28 mod 12 = 4 7 * 5 = 35 mod 12 = 11 7 * 6 = 42 mod 12 = 6 7 * 7 = 49 mod 12 = ?
Примеры p=12 Деление 11/7 = 11 (1/7) mod 12 = 11*7=77 mod 12=5 Поиск обратного элемента 7 * 2 = 14 mod 12 = 2 7 * 3 = 21 mod 12 = 9 7 * 4 = 28 mod 12 = 4 7 * 5 = 35 mod 12 = 11 7 * 6 = 42 mod 12 = 6 7 * 7 = 49 mod 12 = 1
Примеры p=12 С делением не просто!!!! Когда p=12, то делить на 2 нельзя, так как у него нет обратного элемента!!!! 2 * 2 = 4 2 * 3 = 6 2 * 4 = 8 2 * 5 = 10 2 * 6 = 0 2 * 7 = 14 mod 12 = 2 2 * 8 = 16 mod 12 = 4 2 * 9 = 18 mod 12 = 6 2 * 10 = 20 mod 12 = 8 2 * 11 = 22 mod 12 = 10
Это не случайно: 12 НЕ ПРОСТОЕ ЧИСЛО
Примеры p=12 p должно быть простым! Например, p=13 или p=17
Пусть p - простое Рассмотрим немного другое множество В нем корректно определены только умножение и деление
ФАКТ Существует такой элемент g, что все остальные элементы могут быть представлены как степень этого элемента
Пример p=13 Рассмотрим g = 2 2^0 = 1 mod 13 2^1 = 2 mod 13 2^2 = 4 mod 13 2^3 = 8 mod 13 2^4 = 3 mod 13 2^5 = 6 mod 13 2^6 = 12 mod 13 2^7 = 11 mod 13 2^8 = 9 mod 13 2^9 = 5 mod 13 2^10 = 10 mod 13 2^11 = 7 mod 13 2^12 = 1 mod 13
Пример p=13 Рассмотрим g = 2 1 = 2^12 mod 13 2 = 2^1 mod 13 3 = 2^4 mod 13 4 = 2^2 mod 13 5 = 2^9 mod 13 6 = 2^5 mod 13 7 = 2^11 mod 13 8 = 2^3 mod 13 9 = 2^8 mod = 2^10 mod = 2^7 mod = 2^6 mod 13
Итак,
Проблема дискретного логарифмирования Дано: простое число p, образующий g по модулю p натуральное число a Найти: число x такое, что x называется ДИСКРЕТНЫМ ЛОГАРИФМОМ числа a по основанию g по модулю p
Проблема дискретного логарифмирования Проблема поиска дискретного логарифма числа является трудной, хотя это до сих пор не доказано!
АНЯ БОРИС 1. Выбирают g и модуль p по телефону
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 2. Каждый выбирает секретное число
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 3. Вычисляют и отправляют друг другу = mod =
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 3. Вычисляют и отправляют друг другу
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 4. Вычисляют общий ключ = mod =
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 4. Вычисляют общий ключ mod =
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 4. Вычисляют общий ключ mod =
СЕМЕН - РЕДИСКА Перехватил от АНИПерехватил от БОРИСАЗнает общие параметры mod
СЕМЕН - РЕДИСКА Знает Нужно найти
АНЯ БОРИС 1. Выбирают g=2 и модуль p=13 по телефону 2 13
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 2. Каждый выбирает секретное число
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 3. Вычисляют и отправляют друг другу 2 13
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 3. Вычисляют и отправляют друг другу 2 13
АНЯ БОРИС 1. Выбирают g и модуль p по телефону 4. Вычисляют общий ключ 2 13
АНЯ БОРИС Вычисления Как это быстро вычислить?
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
АНЯ БОРИС Вычисления
Проблема Диффи-Хеллмана Решив проблему дискретного логарифмирования, можно решить проблему Диффи-Хеллмана. Верно ли обратное утверждение – неизвестно!
Чижов Иван Владимирович, к.ф.-м.н.
Рекомендуемые книги для чтения * Сингх. С. Книга шифров. Тайная история шифров и их расшифровки, М:АСТ, 2007 * Нечаев В.И. Элементы криптографии. Основы теории защиты информации, М: Высшая школа, 1999 * Шнайер Б. Прикладная криптография, М:Триумф, 2002 * Шнайер Б. Практическая криптография, М:Вильямс, 2005 * Тилборг К.Х.А. Основы криптологии, М:МИР, 2006 * Саломаа А. Криптография с открытым ключом, М:МИР, 1995