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

Июль 24, 2022

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

Содержание

2. ПРЕДЫСТОРИЯ И ОСНОВНЫЕ ИДЕИ Для того, чтобы лучше понять идеи, лежащие в основе ряда криптографических схем
3. ПРОБЛЕМА ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕ При хранении логинов и паролей в компьютере администратор может прочитать их
4. ПРОБЛЕМА, ВОЗНИКАЮЩАЯ В СИСТЕМАХ ПРОТИВОВОЗДУШНОЙ ОБОРОНЫ При пересечении границы самолет посылает сигнал о том, что он
5. КАК РЕШАТЬ ЭТИ ПРОБЛЕМЫ? Для решения этих и некоторых других проблем можно использовать односторонние функции.
6. ОДНОСТОРОННЯЯ ФУНКЦИЯ (ОПРЕДЕЛЕНИЕ) Функция называется односторонней, если она вычисляется относительно быстро, а обратную к ней вычислить
7. ОДНОСТОРОННЯЯ ФУНКЦИЯ, КОТОРУЮ МЫ БУДЕМ ИСПОЛЬЗОВАТЬ Возведение в степень по модулю y = ax mod p.
8. БЫСТРЫЙ СПОСОБ УМНОЖЕНИЯ Быстрый способ: a64 = (((((a2)2)2)2)2)2 (6 умножений) 64 = 26.
9. НЕДОСТАТОК РАССМОТРЕННОГО СПОСОБА – ОН РАБОТАЕТ ТОЛЬКО ДЛЯ СТЕПЕНЕЙ ДВОЙКИ. Можно ли расширить его так, чтобы
10. БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ОПИСАНИЕ АЛГОРИТМА)
11. БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ПРИМЕР)
12. БЫСТРЫЙ АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ (ПСЕВДОКОД)
13. ДИСКРЕТНЫЙ ЛОГАРИФМ Дискретный логарифм – это функция, обратная к y = ax mod p. x =
14. МЕТОДЫ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ
15. СРАВНЕНИЕ СЛОЖНОСТИ ПРЯМОЙ И ОБРАТНОЙ ФУНКЦИИ БЫСТРОГО ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ
16. РЕШЕНИЕ ПРОБЛЕМЫ ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕ На компьютере хранится не логин и пароль, а логин и
17. РЕШЕНИЕ ПРОБЛЕМЫ ПВО База генерирует случайное число R и передает (открыто) его самолету. Самолет вычисляет y
18. ВЫВОДЫ Надежность рассмотренных криптосистем основана на том, что враг не может практически вскрыть систему. Фактически мы
19. КРИПТОСИСТЕМА С ЗАКРЫТЫМ (СЕКРЕТНЫМ) КЛЮЧОМ
20. КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ
21. ОТЛИЧИЕ КРИПТОСИСТЕМЫ С ЗАКРЫТЫМ КЛЮЧОМ ОТ КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ Криптосистема с закрытым (секретным) ключом подразумевает
22. ПРИМЕРЫ СЕКРЕТНЫХ КАНАЛОВ (ЭТО ДОРОГИЕ КАНАЛЫ) Личная встреча Курьерская почта Охраняемый поезд ………… Дорогой канал –
23. ПРИМЕРЫ НЕЗАЩИЩЕННЫХ КАНАЛОВ ( ЭТО ДЕШЕВЫЕ КАНАЛЫ) Интернет Телефон Обычная почта E-mail ………. Дешевый канал –
24. ЕЩЕ ОДИН НЕДОСТАТОК ОБМЕНА СЕКРЕТНЫМИ КЛЮЧАМИ Вопрос. Сколько нужно ключей, если N абонентов хотят общаться попарно
25. СИСТЕМА ДИФФИ-ХЕЛЛМАНА (ПЕРВАЯ КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ) Цель системы Диффи-Хеллмана – без помощи защищенного канала сформировать
26. СИСТЕМА ДИФФИ-ХЕЛЛМАНА ДЛЯ АБОНЕНТОВ A, B, C…. (ВЫБОР ПАРАМЕТРОВ) Выбрать большое простое p. Выбрать g, такое
27. ПАРАМЕТРЫ ПОЛЬЗОВАТЕЛЕЙ В СИСТЕМЕ ДИФФИ-ХЕЛЛМАНА
28. ВЫЧИСЛЕНИЕ ОБЩЕГО КЛЮЧА С ПОМОЩЬЮ СИСТЕМЫ ДИФФИ-ХЕЛЛМАНА
29. ВЫБОР ПАРАМЕТРА G
30. СИСТЕМА ДИФФИ-ХЕЛЛМАНА (ПРИМЕР)
31. ЛИТЕРАТУРА Рябко, Фионов Основы современной криптографии Глава 2
33. Скачать презентацию

Слайд 2

ПРЕДЫСТОРИЯ И ОСНОВНЫЕ ИДЕИ
Для того, чтобы лучше понять идеи, лежащие в

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

Слайд 3

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

администратор может прочитать их и воспользоваться в своих целях.

Слайд 4

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

о том, что он «свой».
«Враг» перехватывает сигнал и затем, перелетая через границу, отсылает перехваченный сигнал. База принимает его за «своего».

Слайд 5

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

использовать односторонние функции.

Слайд 6

ОДНОСТОРОННЯЯ ФУНКЦИЯ (ОПРЕДЕЛЕНИЕ)
Функция называется односторонней, если она вычисляется относительно быстро, а обратную

к ней вычислить за реальное время невозможно.
То есть теоретически можно, но практически нельзя.
Например,
y=f(x) вычисляется за 10 секунд,
x=f-1(y) вычисляется за 100000 лет.

Слайд 7

ОДНОСТОРОННЯЯ ФУНКЦИЯ, КОТОРУЮ МЫ БУДЕМ ИСПОЛЬЗОВАТЬ
Возведение в степень по модулю
y

= ax mod p.
Пример. Вычислим a64.
Медленный (наивный) способ: a64 = a*a*a* … *a
(63 умножения).

Слайд 8

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

Слайд 9

НЕДОСТАТОК РАССМОТРЕННОГО СПОСОБА – ОН РАБОТАЕТ ТОЛЬКО ДЛЯ СТЕПЕНЕЙ ДВОЙКИ.
Можно ли

расширить его так, чтобы возводить в степень можно было любые числа?
Идея.
768169 = 765536 * 72048 * 7512 * 764 * 78 * 70

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

ДИСКРЕТНЫЙ ЛОГАРИФМ
Дискретный логарифм – это функция, обратная к y = ax

mod p.
x = logay mod p.
Не существует эффективных алгоритмов ее вычисления.
Определение.
Вычисление дискретного логарифма называется дискретным логарифмированием.

Слайд 14

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

Слайд 15

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

МОДУЛЮ

Слайд 16

РЕШЕНИЕ ПРОБЛЕМЫ ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕ
На компьютере хранится не логин и

пароль, а логин и y(пароль) т.е.
y = aпароль mod p.
(параметры a и p как-то выбираются
и могут быть известны всем)
Когда пользователь входит в систему, то от его введенного пароля вычисляется односторонняя функция и сравнивается с хранящимся на компьютере значением.

Слайд 17

РЕШЕНИЕ ПРОБЛЕМЫ ПВО
База генерирует случайное число R и передает (открыто) его

самолету.
Самолет вычисляет
y = aпароль|R mod p.
и передает сигнал на базу.
Если «враг» перехватит y и отошлет его на базу, то за «своего» не сойдет. Потому что для него число R уже будет другим.

Слайд 18

ВЫВОДЫ
Надежность рассмотренных криптосистем основана на том, что враг не может практически

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

Слайд 19

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

Слайд 20

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

Слайд 21

ОТЛИЧИЕ КРИПТОСИСТЕМЫ С ЗАКРЫТЫМ КЛЮЧОМ ОТ КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ
Криптосистема с

закрытым (секретным) ключом подразумевает наличие защищенного канала, по которому передается секретный ключ.
Криптосистема с открытым ключом не подразумевает наличие защищенного канала, по которому передается секретный ключ.

Слайд 22

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

значит труднодоступный, медленный, имеющий высокую стоимость. Им нельзя воспользоваться в любой момент.

Слайд 23

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

легкодоступный, быстрый, имеющий невысокую стоимость. Им можно воспользоваться в любой момент.

Слайд 24

ЕЩЕ ОДИН НЕДОСТАТОК ОБМЕНА СЕКРЕТНЫМИ КЛЮЧАМИ
Вопрос.
Сколько нужно ключей, если N абонентов

хотят общаться попарно безопасно?
Ответ
N*(N-1)/2
Примерно N2/2

Слайд 25

СИСТЕМА ДИФФИ-ХЕЛЛМАНА (ПЕРВАЯ КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ)
Цель системы Диффи-Хеллмана – без помощи

защищенного канала сформировать секретный ключ, который будет использоваться при шифровании какой-то системой с секретным ключом.
То есть сама система Диффи-Хеллмана выступает в роли защищенного канала.

Слайд 26

СИСТЕМА ДИФФИ-ХЕЛЛМАНА ДЛЯ АБОНЕНТОВ A, B, C…. (ВЫБОР ПАРАМЕТРОВ)
Выбрать большое простое p.
Выбрать

g, такое что числа 1, 2, …. ,p-1 могут быть представлены как степени g по модулю p. Алгоритм, как это сделать, описан далее.
Каждый абонент выбирает свое число X и хранит его в секрете.
Каждый абонент вычисляет число Y и публикует его.
Общий секретный ключ вычисляется на основании открытого ключа собеседника и своего секретного ключа.

Слайд 27

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

Слайд 28

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

Слайд 29

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

Слайд 30

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

Слайд 31

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

Содержание

ПРЕДЫСТОРИЯ И ОСНОВНЫЕ ИДЕИДля того, чтобы лучше понять идеи, лежащие в

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

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

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

ОДНОСТОРОННЯЯ ФУНКЦИЯ (ОПРЕДЕЛЕНИЕ)Функция называется односторонней, если она вычисляется относительно быстро, а обратную

ОДНОСТОРОННЯЯ ФУНКЦИЯ, КОТОРУЮ МЫ БУДЕМ ИСПОЛЬЗОВАТЬВозведение в степень по модулю y

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

НЕДОСТАТОК РАССМОТРЕННОГО СПОСОБА – ОН РАБОТАЕТ ТОЛЬКО ДЛЯ СТЕПЕНЕЙ ДВОЙКИ.Можно ли

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

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

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

ДИСКРЕТНЫЙ ЛОГАРИФМДискретный логарифм – это функция, обратная к y = ax

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

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

РЕШЕНИЕ ПРОБЛЕМЫ ХРАНЕНИЯ ПАРОЛЕЙ В КОМПЬЮТЕРЕНа компьютере хранится не логин и

РЕШЕНИЕ ПРОБЛЕМЫ ПВО База генерирует случайное число R и передает (открыто) его

ВЫВОДЫНадежность рассмотренных криптосистем основана на том, что враг не может практически