Протокол диффи хеллмана реферат

Обновлено: 02.07.2024

Как и создатели трёхпроходных протоколов из предыдущего раздела, авторы следующих алгоритмов считали их не просто математическими конструкциями, обеспечивающие некоторую элементарную операцию (например, шифрование с открытым ключом), но пытались вокруг одной-двух формул построить законченную систему распространения ключей. Некоторые из этих конструкций, преобразовавшись, используются до настоящего времени (например, протокол Диффи-Хеллмана), некоторые — остались только в истории криптографии и защиты информации.

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

Протокол Диффи—Хеллмана

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

Протокол обмена состоит из следующих действий.

Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет сессионный ключ
Алиса вычисляет

Алиса выбирает случайное
Меллори выбирает случайное
Меллори вычисляет сессионный ключ для канала с Алисой

Протокол Диффи—Хеллмана отличается от большей части протоколов распространения ключей из-за того, что не использует другие криптографические примитивы (функции шифрования, электронно-цифровой подписи или хеширования), но сам по себе является в некотором смысле криптографическим примитивом для построения более сложных протоколов. Он обеспечивает генерацию случайного числа в распределённой системе без доверенного центра. Причём ни одна из сторон не может заставить другую сторону использовать старый сессионный ключ, в отличие от, например, протокола Yahalom.

Протокол можно изменить таким образом, чтобы вместо мультипликативной группы простого умножения использовать аддитивную группу сложения точек эллиптической кривой. В этом случае стороны по прежнему будут выбирать некоторые случайные целые числа, но не возводить генератор-число в степень, а умножать генератор-точку на загаданное число.

Стороны договорились о группе точек эллиптической кривой , её циклической подгруппе мощности и генераторе группы (или хотя бы достаточно большой подгруппы группы ).
Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет точку
Алиса вычисляет точку

Протокол Эль-Гамаля

Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

Протокол MTI/A(0)

В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Алиса сгенерировала случайное число
Боб сгенерировал случайное число
Боб вычислил сеансовый ключ
Алиса вычислила сеансовый ключ

Протокол Station-to-Station

Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Каждая из сторон и обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи и открытым ключом для шифрования и проверки подписи .

Где это функция проверки электронной подписи на открытом ключе , а — функция расшифрования с использованием закрытого ключа .

Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

Автор: Malarkey

Суть проблемы

Алгоритм Диффи-Хеллмана

Рассмотрим схему обмена секретными ключами при помощи алгоритма Диффи-Хеллмана (Diffie-Hellman Key Exchange, DHKE). Более подробно с этой темой можно ознакомиться в русскоязычной и англоязычной Википедии. Ниже показана наглядная схема обмена между двумя пользователями. Алиса и Боб хотят использовать общий ключ для шифрования переписки. Рассмотрим детально этот процесс, используя краски вместо чисел:

Алиса и Боб выбрали общую краску.
Алиса и Боб выбрали по одной секретной краске.
Алиса и Боб смешали общую и секретную краску.
Алиса и Боб обменялись получившимися смешанными красками.
Алиса смешала полученную смешанную краску от Боба со своей секретной краской.
Боб смешал полученную смешанную краску от Алисы со своей секретной краской.
Теперь у Алисы и Боба есть общая секретная краска.

(Алиса и Боб будут периодически встречаться в наших рассуждениях, так что привыкайте).

Рисунок 1: Наглядная схема получения общего секретного ключа (из Википедии)

Рабочий пример

Схема обмена секретным ключом реализована мной в коде. Ниже показан результат работы утилиты (для большей наглядности используются дополнительные флаги).

Рисунок 2: Результаты работы скрипта, реализующего алгоритм Диффи-Хеллмана

Небольшие пояснения к Рисунку 2:

Вначале Алиса выбирает простое базовое число (5) и передает через Еву информацию Бобу. Затем Алиса выбирает еще одно простое число (23), которое будет использоваться при вычислениях, и опять передает через Еву информацию Бобу. Далее Алиса и Боб выбирают секретные числа и производят математические вычисления с использованием чисел 5 и 23. Затем Алиса и Боб через Еву обмениваются полученными сведениями. Далее каждый из оппонентов вычисляет секретный ключ.

Математическая сторона вопроса

Подождите, B^a mod p и A^b mod p – это и есть секретные ключи? Тогда мы должны быть уверены, что оба выражения дают одинаковый результат. Рассмотрим еще раз весь алгоритм по шагам.

Алиса и Боб выбирают два числа g и p.
Алиса и Боб выбирают секретные числа (a и b соответственно)
Алиса и Боб вычисляют g ^ x mod p, где x – секретное число.
Алиса и Боб обмениваются полученными данными (числа A и B соответственно).
Алиса и Боб используют полученное число и секретное число для вычисления общего ключа.

В шаге 5 имеем следующее:

У Алисы: B^a mod p = (g^b mod p) ^ a mod p = g^ab mod p.

У Боба: A^b mod p = (g^a mod p) ^ b mod p = g^ab mod p.

Чтобы лучше понять, как работает этот алгоритм, нам придется глубже погрузиться в модулярную арифметику.

Когда вы вычисляете выражение y mod z, на самом деле вычисляется остаток от деления y / z (или y % z, как принято в большинстве языков программирования). Если y z выражение работает наподобие часов. По мере увеличения числа y выражение y % z будет равняться значениям в диапазоне от 0 до z – 1. Как только y станет кратно z, отсчет начинается сначала. Выясняется, что операция возведения в степень в модулярной арифметике имеет свойство транзитивности. То есть (a ^ b) ^ c mod d = (a ^ c) ^ b mod d = a^ (b ^ c) mod d. Алиса вычисляет выражение (g^b mod p) ^ a mod p, которое эквивалентно (g^b)^a mod p. В конечном счете, мы получаем выражение g^ab mod p.

Как было сказано ранее, на числа g и p накладываются определенные ограничения. Для выражения a ^ b mod c итоговый результат зависит от выбранных чисел. Рассмотрим выражение: a ^ b mod 7.

2 ^ 1 mod 7 = 2 mod 7 = 2

2 ^ 2 mod 7 = 4 mod 7 = 4

2 ^ 3 mod 7 = 8 mod 7 = 1

2 ^ 4 mod 7 = 16 mod 7 = 2

2 ^ 5 mod 7 = 32 mod 7 = 4

2^ 6 mod 7 = 64 mod 7 = 1

Понимаете, в чем дело? В результате мы имеет только 3 различных числа, и количество секретных ключей лишь половина всех чисел, которые меньше 7 (а ограниченное количество ключей напрямую влияет на уровень безопасности).

Вместо 2 возьмем 3:

3 ^ 1 mod 7 = 3 mod 7 = 3

3 ^ 2 mod 7 = 9 mod 7 = 2

3 ^ 3 mod 7 = 27 mod 7 = 6

3 ^ 4 mod 7 = 81 mod 7 = 4

3 ^ 5 mod 7 = 243 mod 7 = 5

3^ 6 mod 7 = 729 mod 7 = 1

В этом случае количество возможных секретных ключей возрастает. Если вы хотите глубже ознакомиться с данной темой, рекомендую прочитать эту статью.

Преимущества алгоритма

Алисе и Бобу удалось сгенерировать одинаковый ключ, но насколько решена наша проблема? Рассмотрим ситуацию с позиции Евы (курьера, который передает информацию).

Рисунок 3: Информация, которую видит курьер

Если скрипт запущен без флагов, на выходе показывается информацию, которую видит Ева. В примере выше Ева видит числа g и p, а также A и B. Чтобы вычислить секретный ключ, Еве нужно определить значения числа a (или b), используя выражение A = g^a mod p. Найти решение этого уравнения, которое часто называют секретно вычисляемой функцией (trap door function), довольно сложно. Подобные выражения легко вычисляются в одну сторону, но тяжело в другую (через некоторые двери вы не можете вернуться обратно). Если хотите копнуть глубже, ознакомьтесь со статьей, где описана проблема дискретного логарифмирования.

Во второй части мы рассмотрим алгоритм RSA.

В нашем телеграм канале мы рассказываем о главных новостях из мира IT, актуальных угрозах и событиях, которые оказывают влияние на обороноспособность стран, бизнес глобальных корпораций и безопасность пользователей по всему миру. Узнай первым как выжить в цифровом кошмаре!

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

Содержание работы

ВВЕДЕНИЕ 3
1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ 4
1.1. История создателей алгоритма 4
1.2. Описание алгоритма 6
1.3. Блок-Схема 8
2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА 9
2.1. Вычисление компонент ключа 9
3. КРИПТОСТОЙКОСТЬ АЛГОРИТМА 10
3.1. Решение проблемы “человек посередине” с помощью ЭЦП 11
3.2. Решение проблемы “человек посередине” протоколом MQV 12
ЗАКЛЮЧЕНИЕ 15
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 16
ПРИЛОЖЕНИЕ 17

Файлы: 1 файл

Курсовой проект.docx

Министерство образования Республики БеларусьУчреждение образования

Могилёвский государственный университет им. А.А.Кулешова

Алгоритм обмена секретным ключом Диффи-Хеллмана

3курса группы “В-Г”

Рудницкий Сергей Вячеславович

Каменская Наталья Евгеньевна

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ 4

1.1. История создателей алгоритма 4

1.2. Описание алгоритма 6

2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА 9

2.1. Вычисление компонент ключа 9

3. КРИПТОСТОЙКОСТЬ АЛГОРИТМА 10

3.1. Решение проблемы “человек посередине” с помощью ЭЦП 11

3.2. Решение проблемы “человек посередине” протоколом MQV 12

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 16

ВВЕДЕНИЕ

Криптосистема работает по определенной методологии (процедуре). Она состоит из : одного или более алгоритмов шифрования (математических формул); ключей, используемых этими алгоритмами шифрования; системы управления ключами; незашифрованного текста; и зашифрованного текста (шифртекста).

Согласно методологии сначала к тексту применяются алгоритм шифрования и ключ для получения из него шифртекста. Затем шифртекст передается к месту назначения, где тот же самый алгоритм используется для его расшифровки, чтобы получить снова текст. Также в методологию входят процедуры создания ключей и их передачи (не показанные на рисунке).

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

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

История создателей алгоритма

В 1970 году Мартин Хеллман, молодой профессор, занимавшийся вопросами проектирования электрических систем в Стенфордском университете в Пало-Альто (шт. Калифорния), увлекся проблемой передачи ключа в 1968 году, когда работал в IBM в Пенсильвании.

Хеллман рассказывает, что он прозрел после того, как прочитал статьи Клода Шенона по теории информации и криптографии, которые опубликовались в 1948 и 1949 годах.

Хеллман искал пути для решения проблемы, в то время как некий студент из MIT по имени Уайтфилд Диффи заинтересовался тем же самым. Но поиски Диффи начались значительно раньше.

К 1973 году Диффи стал лаборантом и раздражал профессоров Стенфорда по искусственному интеллекту тем, что тратил все свое время и энергию на шифрование. Наконец, он оставил в покое своего учителя, взял отпуск и, одержимый своей идеей, отправился в путешествие по Восточному и Западному побережью, где встречался с экспертами по шифрованию и разыскивал редкие манускрипты.

А в это самое время Ральф Меркл, студент Университета Беркли (шт. Калифорния), занимающийся исключительно проектированием электрических систем, бродил по университетскому городку, снедаемый мыслями о шифровании.

Пытаясь объединить разрозненные идеи по шифрованию данных, Хеллман продолжал искать единомышленников. Однако получилось наоборот: в сентябре 1973 года его нашел Диффи. Их получасовая встреча плавно перешла в обед у Хеллмана, причем разговоры затянулись далеко за полночь.

Хеллман и Диффи сообщили, что их первая статья по теории цифровых подписей вышла в декабре 1975 года. Представлена она была полгода спустя на Национальной компьютерной конференции в Нью-Йорке.

После Беркли в 1975 году Меркл сформулировал задачу защиты коммуникаций, несвязанную с подписью и сертификатом. Он взялся за решение проблемы распространения открытого ключа, исходя из предпосылки применения смешения случайных чисел. Прочитав статью Хеллмана-Диффи, Меркл встретился с первым, который уговорил Меркла перенести свою аспирантскую работу в Стенфорд.

Но внимание это улетучилось так же быстро, как и возникло. Изобретатели опередили свое время:

Задача, решение которой они предлагали, еще не была сформулирована.

Описание алгоритма

Существуют два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб— число b. Затем Алиса вычисляет значение

и пересылает его Бобу , а Боб вычисляет

и передаёт Алисе. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B a mod p = g ab mod p (3), а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение A b mod p =g ab mod p (4). Как нетрудно видеть, у Алисы и Боба получилось одно и то же число: K = g ab mod p (5). Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (3) или (4) по перехваченным g a mod p и g b mod p, если числа p,a,b выбраны достаточно большими. Наглядная работа алгоритма показана на рис.1.

Рис.1 Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

генерирует случайное натуральное число a/b — закрытый ключ
совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

p является случайным простым числом

g является первообразным корнем по модулю p

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

A = g a mod p/ B=g b mod p

обменивается открытыми ключами с удалённой стороной
вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B/ A и свой закрытый ключ a/b

K = B a mod p/ K=A b mod p

К получается равным с обоих сторон, потому что:

B a mod p = (g b mod p) a mod p = g ab mod p = (g a mod p) b mod p = A b mod p

В практических реализациях, для a и b используются числа порядка 10 100 и p порядка 10 300 . Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Блок-Схема

Генерируются два числа p и g;
Первая сторона генерирует случайное число a, вторая – b;
Каждая сторона генерирует открытый ключ A и B соответственно;
Стороны обмениваются ключами;
Благодаря полученным ключам стороны получают секретный ключ, который и используют в дальнейшем.

ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА

Демонстрационная программа, созданная с помощью Borland C++ Builder 6, позволяет наглядно продемонстрировать алгоритм обмена ключами Диффи – Хеллмана. Так же, для работы с большими числами была использована библиотека NTL.

Вычисление компонент ключа

Большую сложность представляет собой задача проверки большого числа на простоту.Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима за.

Различают детерминированные и вероятностные тесты.

Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.

Вероятностный алгоритм – алгоритмический процесс, который быстро (за полиномиальное время) вычислим и дающий ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа).

Воспользуемся вероятностным полиномиальным тестом простоты Миллера — Рабина, основанный на наблюдении. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа.

Для того, что бы значительно ускорить проверку числа на простоту, перед вызовом теста Миллера-Рабина, разделим проверяемое число по порядку на простые числа до 256 .Это исключает все четные числа и 80% нечетных чисел.

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

Рассмотрим теперь генерацию числа g, которое должно являтся первообразным корнем по модулю p.

Первообразным корнем по модулю p называется такое число g, что все его степени по модулю p пробегают по всем числам, взаимно простым с p.

В частности, для случая простого p степени первообразного корня пробегают по всем числам от до p-1.

Таким образом, алгоритм нахождения первообразного корня такой. Находим значение функции Эйлера в p, факторизуем его. Теперь перебираем все числа g=1…p , и для каждого считаем все величины . Если для текущего g все эти числа оказались отличными от , то это g и является искомым первообразным корнем.

Про скорость роста первообразных корней с ростом p известны лишь приблизительные оценки. Известно, что первообразные корни — сравнительно небольшие величины. Одна из известных оценок — оценка Шупа (Shoup), что, в предположении истинности гипотезы Римана, первообразный корень есть .

КРИПТОСТОЙКОСТЬ АЛГОРИТМА

Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K=g ab mod p по известным p, g, A=g a mod p и B=g b modp), основана на предполагаемой сложности проблемы дискретного логарифмирования.

Схема обмена ключами Диффи-Хеллмана, изобретённая в 1976 году Уитфилдом Диффи и Мартином Хеллманом под влиянием работ Ральфа Меркле (Ralph Merkle), стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи.

Работа состоит из 1 файл

Алгоритм Диффи-Хеллмана.doc

История

Схема обмена ключами Диффи-Хеллмана, изобретённая в 1976 году Уитфилдом Диффи и Мартином Хеллманом под влиянием работ Ральфа Меркле (Ralph Merkle), стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. Годом позже был изобретен первый алгоритм асимметричного шифрования RSA, который решил проблему общения через незащищённый канал кардинально, уже не требуя, чтобы каждая сторона имела копию одного и того же секретного ключа.

Описание алгоритма

Предположим, что обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = g a mod p и пересылает его второму, а второй вычисляет B = g b mod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B a mod p = g ab mod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение A b mod p = g ab mod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = g ab mod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g ab mod p по перехваченным g a mod p и g b mod p, если числа p,a,b выбраны достаточно большими.

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

генерирует случайное натуральное число a — закрытый ключ
совместно с удалённой стороной устанавливает открытые параметрыp и g (обычно значения p и g генерируются на одной стороне и передаются другой), где:

p является случайным простым числом

g является первообразным корнем по модулю p

вычисляет открытый ключA, используя преобразование над закрытым ключомA = gamod p
обменивается открытыми ключами с удалённой стороной
вычисляет общий секретный ключK, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = B a mod p

К получается равным с обоих сторон, потому что:

B a mod p = (g b mod p) a mod p = g ab mod p = (g a mod p) b mod p = A b mod p

Криптографическая стойкость

Криптографическая стойкость алгоритма Диффи- Хеллмана (то есть сложность вычисления K=g ab mod p по известным p, g, A=g a mod p и B=g b mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования. Однако, хотя умение решать проблему дискретного логарифмирования позволит взломать алгоритм Диффи-Хеллмана, обратное утверждение до сих является открытым вопросом (другими словами, эквивалентность этих проблем не доказана).

Читайте также: