Алгоритм обмена ключа Диффи-Хеллмана - раздел Философия, Конспект лекций по дисциплине Программно-аппаратные средства защиты информации Основные понятия и определения Первая Публикация Данного Алгоритма Открытого Ключа Появилась В Статье...
Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.
Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.
Алгоритм основан на трудности вычислений дискретных логарифмов . Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q - 1 . Это означает, что если А является примитивным корнем простого числа Q, тогда числа
A mod Q, A2 mod Q, . . . , AQ - 1 mod Q
являются различными и состоят из целых от 1 до Q - 1 с некоторыми перестановками. В этом случае для любого целого Y < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что
Y = A
Х mod Q, где 0 <= X <= (Q - 1)
Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как
ind
A, Q (Y).
Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.
| Общеизвестные элементы
|
| Q
| простое число
|
| A
| A < Q и A является примитивным корнем Q
|
| Создание пары ключей пользователем I
|
| Выбор случайного числа Хi ( закрытый ключ )
| Xi < Q
|
| Вычисление числа Yi ( открытый ключ )
| Yi = AXi mod Q
|
| | | | |
| Создание открытого ключа пользователем J
|
| Выбор случайного числа Хj ( закрытый ключ )
| Xj < Q
|
| Вычисление случайного числа Yj ( открытый ключ )
| Yj = AXj mod Q
|
| Создание общего секретного ключа пользователем I
|
| K = (Yj)Xi mod Q
|
| | | |
| Создание общего секретного ключа пользователем J
|
| K = (Yi)Xj mod Q
|
Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Хi < Q и вычисляет Yi = AXi mod Q. Аналогично пользователь Jнезависимо выбирает случайное целое число Хj < Q и вычисляет Yj = AXj mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как К = (Yj)Xi mod Q, и пользователь J вычисляет ключ как K = (Yi)Xj mod Q. В результате оба получат одно и то же значение:
K = (Y
j)
Xi mod Q = (A
Xj mod Q)
Xi mod Q = (A
Xj )
Xi mod Q по правилам модульной арифметики = A
Xj Xi mod Q = (A
Xi )Xj mod Q = (A
Xi mod Q)
Xj mod Q = (Y
i)
Xj mod Q
Таким образом, две стороны обменялись секретным ключом. Так как Хi и Хj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить
Xj = inda, q (Yj)
Безопасность обмена ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислитьэкспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается неразрешимой.
Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Yj, создать свою пару открытого и закрытого ключа (Xоп, Yоп) и послать каждому из участников свойоткрытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.
Все темы данного раздела:
II. Активная атака
Активной называется такая атака, при которой противник имеет возможность модифицировать передаваемые сообщения и вставлять свои сообщения. Различают следующие типы
Сервисы безопасности
Основными сервисами безопасности являются следующие:
Конфиденциальность - предотвращение пассивных атак для передаваемых или хранимых данных.
Модель сетевого взаимодействия
Модель безопасного сетевого взаимодействия в общем виде можно представить следующим образом:
Модель безопасности информационной системы
Существуют и другие относящиеся к безопасности ситуации, которые не соответствуют описанной выше модели сетевой безопасности. Общую модель этих ситуаций можно проиллюстрировать следующим образом:
Сеть Фейстеля
Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обр
Криптоанализ
Процесс, при котором предпринимается попытка узнать Х, K или и то, и другое, называется криптоанализом. Одной из возможных атак на алгоритм шифрования является лобовая атака, т
Дифференциальный и линейный криптоанализ
Рассмотрим в общих чертах основной подход, используемый при дифференциальном и линейном криптоанализе. И в том, и в другом случае предполагается, что известно достаточно большое колич
Используемые критерии при разработке алгоритмов
Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен:
· Манипулировать данными в больших блоках, предпочтительно размером 16
Принципы разработки
Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 г
Последовательность преобразований отдельного раунда
Теперь рассмотрим последовательность преобразований, используемую в каждом раунде.
Дешифрование
Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи Kiиспользуются в обратной последовательности. K16 исп
Недостатки двойного DES
Простейший способ увеличить длину ключа состоит в повторном применении DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрова
Тройной DES с двумя ключами
Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость лобовой атаки до 2168
Алгоритм Blowfish
Blowfish является сетью Фейстеля, у которой количество итераций равно 16. Длина блока равна 64 битам, ключ может иметь любую длину в пределах 448 бит. Хотя перед
Генерация подключей
Подключи вычисляются с использованием самого алгоритма Blowfish.
1. Инициализировать первый Р -массив и четыре S-boxes фиксированной строкой.
2. Выполнить опе
Криптографическая стойкость
Следующие характеристики IDEA характеризуют его криптографическую стойкость:
1. Длина блока: длина блока должна быть достаточной, чтобы скрыть все статистиче
Последовательность преобразований отдельного раунда
Рассмотрим последовательность преобразований отдельного раунда.
Одним из основных элементов алгоритма, обеспечивающих диффузию, является структура, называемая МА (умножение/с
Создание подключей
Пятьдесят два 16-битных подключа создаются из 128-битного ключа шифрования следующим образом. Первые восемь подключей, которые обозначим как Z1, Z2, ...,
Дешифрование
Процесс дешифрования аналогичен процессу шифрования. Дешифрование состоит в использовании зашифрованного текста в качестве входа в ту же самую структуру IDEA, но с другим набор
Алгоритм ГОСТ 28147
Алгоритм ГОСТ 28147 является отечественным стандартом для алгоритмов симметричного шифрования. ГОСТ 28147 разработан в 1989 году, является блочным алгоритмо
Режимы выполнения алгоритмов симметричного шифрования
Для любого симметричного блочного алгоритма шифрования определено четыре режима выполнения.
ECB - Electronic Codebook - каждый блок из 64 бит незашифрова
Режим ECB
Данный режим является самым простым режимом, при котором незашифрованный текст обрабатывается последовательно, блок за блоком. Каждый блок шифруется, используя один и тот же ключ. Если сообщение дл
Режим CBC
Для преодоления недостатков ECB используют способ, при котором одинаковые незашифрованные блоки преобразуются в различные зашифрованные. Для этого в качестве входа алгоритма используе
Режим CFB
Блочный алгоритм предназначен для шифрования блоков определенной длины. Однако можно преобразовать блочный алгоритм в поточный алгоритм шифрования, используя последние два режима. Поточный
Режим OFB
Данный режим подобен режиму CFB. Разница заключается в том, что выход алгоритма в режиме OFB подается обратно в регистр, тогда как в режиме CFB в регистр подается результат при
Случайность
Обычно при создании последовательности псевдослучайных чисел предполагается, что данная последовательность чисел должна быть случайной в некотором определенном статистическом смысле. Следующ
Источники случайных чисел
Источники действительно случайных чисел найти трудно. Физические генераторы шумов, такие как детекторы событий ионизирующей радиации, газовые разрядные трубки и имеющий течь конденсатор могут быть
Генераторы псевдослучайных чисел
Первой широко используемой технологией создания случайного числа был алгоритм, предложенный Лехмером, который известен как метод линейного конгруента. Этот алгоритм параметризуется четырьмя числами
Циклическое шифрование
Рис. 3.14.Циклическое шифрование
В данном случ
Генератор псевдослучайных чисел ANSI X9.17
Один из наиболее сильных генераторов псевдослучайных чисел описан в ANSI X9.17. В число приложений, использующих эту технологию, входят приложения финансовой безопасности и PGP.
Историческая справка
2 января 1997 года NIST объявил о начале разработки AES, и 12 сентября 1997 года были представлены официальные требования к алгоритмам. В этих требованиях указывалось, что целью NI
Обзор финалистов
Все пять финалистов являются итерационными блочными алгоритмами шифрования: они определяют преобразование, которое повторяется определенное число раз над блоком шифруемых или дешифруемых данных. Ши
Критерий оценки
В сентябре 1997 года, объявив об алгоритмах кандидатов, специалисты NIST определили общий критерий, который должен использоваться при сравнении алгоритмов.
Критерий оценки бы
Качественный или количественный критерий
На одной из первых встреч по планированию второго этапа обсуждений была рассмотрена возможность количественного подхода, используя который каждый алгоритм или комбинация алгоритмов будет получать о
Количество алгоритмов AES
В течение первого и второго этапов обсуждений было высказано несколько аргументов относительно количества алгоритмов, которые должны быть выбраны для включения в AES. Дополнительно был сдела
Запасной алгоритм
Как уже отмечалось, существует взаимосвязь между обсуждениями проблемы нескольких алгоритмов AES и выбором запасного алгоритма, особенно в случае единственного алгоритма AES. Backu
Модификация алгоритмов
На первом и втором этапах обсуждения был отмечен интерес к увеличению числа раундов в некоторых алгоритмах. Во многих случаях увеличение количества раундов объяснялось. Так, про Rijndael
Размер машинного слова
Одной из проблем, которая возникает в программных реализациях, является лежащая в их основе архитектура. Платформы, на которых специалисты NIST выполняли тестирование, ориентированы н
Языки реализации ПО
Выполнение также зависит от использования конкретного языка (например, ассемблер, компилируемый или интерпретируемый язык высокого уровня). В некоторых случаях играет роль конкретное ПО. Сущ
Изменение скорости выполнения в зависимости от длины ключа
Программное выполнение MARS, RC6 и Serpent не очень сильно изменяется в зависимости от длины ключа. Однако для Rijndael иTwofish установление ключа или шиф
Краткий вывод о скорости выполнения на основных программных платформах
Огромное количество информации собрано относительно скорости финалистов на различных программных платформах. Эти платформы включают 32-битные процессоры (реализации на С и Java), 64-битные п
Окружения с ограничениями пространства
В некоторых окружениях, обладающих небольшими объемами RAM и/или ROM для таких целей, как хранение кода (обычно в ROM), представление объектов данных, таких как S-boxes (которые могут
Замечания по финалистам
MARS имеет определенные сложности в силу гетерогенной структуры раунда (четыре различных типа раунда). Для S-boxes необходимо 2 Kbytes ROM, что не является проблемой,
Основные требования к алгоритмам асимметричного шифрования
Создание алгоритмов асимметричного шифрования является величайшим и, возможно, единственным революционным достижением в истории криптографии.
Алгоритмы шифрования с открыт
Криптоанализ алгоритмов с открытым ключом
Как и в случае симметричного шифрования, алгоритм шифрования с открытым ключом уязвим для лобовой атаки. Контрмера стандартная: использовать большие ключи.
Криптоси
Основные способы использования алгоритмов с открытым ключом
Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа.
Шифрование с о
Описание алгоритма
Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифро
Создание ключей
Создание ключей включает следующие задачи:
1. Определить два простых числа р и q.
2. Выбрать е и вычислить d.
Прежде всего, рассмотрим проблемы, связанные с выбором р и q
Обсуждение криптоанализа
Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:
1. Лобовая атака: перебрать все возможные закрытые ключи.
2. Разложить n на два простых со
Требования к хэш-функциям
Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока да
Простые хэш-функции
Все хэш-функции выполняются следующим образом. Входное значение (сообщение, файл и т.п.) рассматривается как последовательность n-битных блоков. Входное значение обрабатывается последователь
Использование цепочки зашифрованных блоков
Существуют различные хэш-функции, основанные на создании цепочки зашифрованных блоков, но без использования секретного ключа. Одна из таких хэш-функций была предложена Рабином.
Шаг 4: обработка последовательности 512-битных (16-словных) блоков
Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как HMD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую фу
Шаг 5: выход
После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения.
Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512
Алгоритм MD4
Алгоритм MD4 является более ранней разработкой того же автора Рона Ривеста. Первоначально данный алгоритм был опубликован в октябре 1990 г., незначительно измененная версия была опубликована
Усиление алгоритма в MD5
Алгоритм MD5 имеет следующее свойство: каждый бит хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций fF, fG, fH
Шаг 4: обработка сообщения в 512-битных (16-словных) блоках
Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.
Шаг 5: выход
После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.
Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битног
Сравнение SHA-1 и MD5
Оба алгоритма, SHA-1 и MD5, произошли от MD4, поэтому имеют много общего.
Можно суммировать ключевые различия между алгоритмами.
&nbs
Требования к цифровой подписи
Аутентификация защищает двух участников, которые обмениваются сообщениями, от воздействия некоторой третьей стороны. Однако простая аутентификация не защищает участников друг от друга
Прямая и арбитражная цифровые подписи
При использовании прямой цифровой подписи взаимодействуют только сами участники, т.е. отправитель и получатель. Предполагается, что получатель знает открытый ключ отп
Подход DSS
DSS использует алгоритм, который разрабатывался для использования только в качестве цифровой подписи. В отличие от RSA, его нельзя использовать для шифрования или обмена ключам
Проверка подписи
Получатель выполняет проверку подписи с использованием следующих формул. Он создает величину v, которая является функцией от компонент общего открытого ключа, открытого ключа отправит
Новости и инфо для студентов