Реализовать протокол диффи хеллмана в виде клиент серверного приложения

Обновлено: 12.05.2024

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

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

ВВЕДЕНИЕ 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), основана на предполагаемой сложности проблемы дискретного логарифмирования.

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

Ключевое соглашение

В протоколе Диффи-Хеллмана две стороны создают симметричный ключ сеанса без KDC . Перед установлением симметричного ключа эти две стороны должны выбрать два числа p и g . Первое число, p , является большим простым числом порядка 300 десятичных цифр (1024 бита). Второе число, g , служит генератором порядка p - 1 в группе . Эти два числа (группа и генератор) не должны быть конфиденциальными. Их можно передать через Internet. Они могут быть общедоступны. рис. 5.9 показывает процедуру.

Шаги перечислены ниже.

Алиса выбирает большое случайное число x , такое, что 0 , и вычисляет R₁ = g x mod p .
Боб выбирает другое большое случайное число y , такое, что 0 , и вычисляет R₂ = g y mod p .
Алиса передает Бобу R₁ . Обратите внимание, что Алиса не передает значение x ; она передает только R₁ .
Боб передает Алисе R₂ . Снова обратите внимание, что Боб не передает значение y, он передает только R₂ .
Алиса вычисляет K = (R₂) x mod p .
Боб также вычисляет K = (R₁) y mod p .

K = (g x mod p) y mod p = (g y mod p) x mod p = g xy mod p

Боб вычисляет K = (R₁) y mod p = (g x mod p) y mod p = g xy mod p

Алиса вычисляет K = (R₂) x mod p = (g y mod p) x mod p = g xy mod p

и получает то же самое значение без Боба, знающего значение x . А Боб получил это значение без Алисы, знающей значение y .

Приведем тривиальный пример, чтобы ясно понять процедуру. Наш пример использует маленькие числа, но заметим, что в реальной ситуации применяются очень большие числа. Предположим, что g = 7 и p = 23 . Тогда процедура содержит следующие шаги.

Алиса выбирает x = 3 и вычисляет R₁ = 7 3 mod 23 = 21 .
Боб выбирает y = 6 и вычисляет R₂ = 7 6 mod 23 = 4 .
Алиса передает число 21 Бобу.
Боб передает число 4 Алисе.
Алиса вычисляет симметричный ключ K = 4 3 mod 23 = 18 .
Боб вычисляет симметричный ключ K = 21 6 mod 23 = 18 .

Значение K одно и то же и для Алисы, и для Боба: g x y mod p = 7 18 = 18 .

Давайте возьмем более реальный пример. Мы используем программу, чтобы создать случайное целое число 512 битов (идеально - 1024 бит). Целое число p - число с 159 цифрами. Мы также выбираем g , x и y , как показано ниже:

Следующая таблица показывает R₁ , R₂ и K .

Анализ протокола Диффи-Хеллмана

Концепция Диффи-Хеллмана, показанная на рис. 5.10, является простой, но изящной. Мы можем представить ключ засекречивания между Алисой и Бобом - он состоит из трех частей: g , x и y . Первая часть общедоступна. Каждый знает 1/3 ключа - g , общедоступное значение. Другие две части нужно узнать у Алисы и Боба. Каждый из них знает одну часть. Алиса добавляет x как вторую часть для Боба; Боб добавляет y как вторую часть для Алисы. Когда Алиса получает 2/3 полного ключа от Боба, она добавляет последнюю часть, ее y , чтобы завершить ключ. Когда Боб получает ключ от Алисы - законченный на 2/3, он добавляет последнюю часть, свое y , чтобы завершить ключ. Обратите внимание, что хотя ключ Алисы состоит из g , y и x и ключ Боба состоит из g , x и y , эти два ключа - одни и те же, потому что g xy = g yx .

Обратите внимание также, что хотя два ключа те же самые, Алиса не может найти значение y , используемого Бобом, потому что вычисление сделано по модулю p . Алиса получает g y mod p от Боба, но не g y . Для того чтобы знать значения y , Алиса должна использовать дискретный логарифм, который мы обсуждали в предыдущей лекции.

Безопасность протокола

Замена ключа Диффи-Хеллмана восприимчива к двум атакам: атаке дискретного логарифма и атаке посредника (man-in middle)

Атака дискретного логарифма. Безопасность ключевой станции базируется на трудности проблемы дискретного логарифма . Ева может перехватить R₁ и R₂ .

Из R₁ = g x mod p и y из R₂ = g y mod p она может затем вычислить симметричный ключ: K = g xy mod p . Ключ засекречивания больше не является секретным. Чтобы cделать метод Диффи-Хеллмана защищенным от атаки дискретного логарифма , рекомендуется следующее.

Простое число p должно быть очень большим (более чем 300 десятичных цифр).
Простое число p должно быть выбрано так, чтобы p - 1 имел по крайней мере один простой делитель (больше чем 60 десятичных цифр).
Генератор должен быть выбран из группы .
Боб и Алиса должны уничтожить x и y после того, как они вычислили значение симметричного ключа. Значения x и y должны использоваться только единожды.

Атака "посредника" . Этот протокол имеет другую слабость. Еве не надо находить значения x и y , чтобы напасть на протокол. Она может использовать глупость Алисы и Боба, создающих два ключа: один между Бобом и Алисой и другой между Алисой и Бобом. Рис. 5.11 показывает ситуацию. Может случиться следующее:

Алиса выбирает x , вычисляет R ₁ = g x mod p и передает R₁ Бобу.
Ева, злоумышленник, перехватывает R₁ . Она выбирает z , вычисляет R ₂ = g z mod p и передает R ₂ Алисе и Бобу.
Боб выбирает y , вычисляет R₃ = g y mod p , передает R₃ Алисе. Ева перехватывает R₃ , и Алиса никогда не получит это число.
Алиса и Ева вычисляют K₁ = g xz mod p , который становится открытым ключом между Алисой и Евой. Алиса, однако, думает, что это -открытый ключ между ней и Бобом.
Ева и Боб вычисляют K₂ = g zy mod p , который становится открытым ключом между Евой и Бобом. Однако Боб думает, что это - открытый ключ между ним Алисой.

Эта ситуация называется " атака посредника ", поскольку Ева находится между партнерами и перехватывает R₁ , передаваемый Алисой Бобу, и R₃ , передаваемый Бобом Алисой. Это - атака передачи по цепочке , потому что напоминает короткую линейку добровольцев на пожаре, передающих друг другу ведра с водой, по цепочке от человека человеку.

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

Ключевое соглашение "от станции к станции"

Протокол "от станции к станции" - метод, основанный на методе Диффи-Хеллмана. Он применяет цифровые подписи с сертификатами открытого ключа (см. следующую секцию). Для установки ключа сеанса между Алисой и Бобом используется последовательность, показанная на рис. 5.12.

Имеются следующие шаги:

После вычисления R₁ Алиса передает R₁ Бобу (шаги 1 и 2 на рис. 5.12).
После вычисления R₂ и ключа сеанса Боб конкатенирует ID Алисы, R₁ И R₂ . Затем он подписывает результат своим секретным ключом. Боб теперь передает R₂ , подпись и собственное свидетельство общедоступного ключа Алисе. Подпись зашифрована ключом сеанса (шаги 3, 4 и 5 на рис. 5.12).
После вычисления ключа сеанса , если подпись Боба проверена, Алиса связывает ID Боба, R₁ И R₂ . Затем она подписывает результат своим собственным секретным ключом и передает это Бобу. Подпись зашифрована ключом сеанса (шаги 6, 7 и 8 на рис. 5.12).
Если подпись Алисы проверена, Боб сохраняет ключ сеанса (шаг 9 на рис. 5.12).

Безопасность протокола "от станции к станции"

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

Позже в 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). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

Алгоритм обмена ключами Диффи-Хеллмана для генерации ключей

Алгоритм основан на криптографии на эллиптических кривых, которая представляет собой метод криптографии с открытым ключом, основанный на алгебраической структуре эллиптических кривых над конечными полями. DH также использует функцию trapdoor, как и многие другие способы криптографии с открытым ключом. Простая идея понимания алгоритма DH заключается в следующем

1. Первая сторона выбирает два простых числа g и p и сообщает их второй стороне.

2. Затем вторая сторона выбирает секретный номер (назовем его a), а затем вычисляет g mod p и отправляет результат обратно первой стороне, давайте назовем результат A. Имейте в виду, что секретный номер не отправляется. для кого-то только результат есть.

3. Затем первая сторона делает то же самое, она выбирает секретное число b и вычисляет результат B, аналогичный

4. шаг 2. Затем этот результат отправляется второй стороне.

5. Вторая сторона берет полученное число B и вычисляет B a mod p

6. Первая партия берет полученное число A и вычисляет A b mod p

Здесь это становится интересным, ответ на шаге 5 совпадает с ответом на шаге 4. Это означает, что обе стороны получат один и тот же ответ независимо от порядка возведения в степень.

(g a mod p) b mod p = g ab mod p
(g b mod p) a mod p = g ba mod p

Число, которое мы указали в шагах 4 и 5, будет принято как общий секретный ключ. Теперь этот ключ можно использовать для любого шифрования передаваемых данных, таких как Blowfish, AES и т. Д.

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

1. key = (Y _A ) XB mod q -> это то же самое, что рассчитано B

2. Глобальные общественные элементы

Теперь вычисление открытого ключа Y _A Y _A = XA mod q

4. Генерация ключа для пользователя B

Выберите закрытый ключ X _B Здесь, X _B
Теперь вычисление открытого ключа Y _B Y _B = a Xb mod q

5. Расчет секретного ключа по A

6. Расчет секретного ключа по B

пример

1. Алиса и Боб используют открытые номера P = 23, G = 5

2. Алиса выбрала закрытый ключ a = 4, а Боб выбрал b = 3 в качестве закрытого ключа

3. Алиса и Боб теперь вычисляют значения x и y следующим образом:

Алиса: х = (5 4 мод 23) = 4
Боб: у = (5 3 мод 23) = 10

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

5. Алиса и Боб теперь вычисляют симметричные ключи

Алиса: k _a = y a mod p = 10 4 mod 23 = 18
Боб: k _b = x b mod p = 4 3 mod 23 = 18

6. 18 - общий секретный ключ.

Использование алгоритма Диффи-Хеллмана

Помимо использования алгоритма генерации открытых ключей, есть несколько других мест, где можно использовать алгоритм DH:

Преимущества алгоритма Диффи-Хеллмана

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

Недостатки алгоритма Диффи-Хеллмана

Вывод

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

СОДЕРЖАНИЕ

В 2002 году Хеллман предложил назвать алгоритм обмена ключами Диффи-Хеллмана-Меркла в знак признания вклада Ральфа Меркла в изобретение криптографии с открытым ключом (Hellman, 2002), написав:

Описание

Общий обзор

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

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

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

Криптографическое объяснение

Самая простая и оригинальная реализация протокола использует мультипликативную группу целых чисел по модулю p , где p - простое число , а g - первообразный корень по модулю p . Эти два значения выбраны таким образом, чтобы гарантировать, что результирующий общий секрет может принимать любое значение от 1 до p –1. Вот пример протокола с несекретными значениями синим цветом и секретными значениями красным .

Алиса и Боб публично соглашаются использовать модуль p = 23 и основание g = 5 (которое является примитивным корнем по модулю 23).
Алиса выбирает секрет целого = 4, то посылает Бобу = г моды р
- А = 5 4 мод 23 = 4
Боб выбирает секретное целое число b = 3, затем отправляет Алисе B = g b mod p
- B = 5 3 мод 23 = 10
Алиса вычисляет s = B a mod p
- s = 10 4 мод 23 = 18
Боб вычисляет s = A b mod p
- s = 4 3 мод 23 = 18
Алиса и Боб теперь делятся секретом (число 18).

И Алиса, и Боб пришли к одним и тем же значениям, потому что по модулю p

Конечно, для обеспечения безопасности этого примера потребуются гораздо большие значения a , b и p , поскольку существует только 23 возможных результата n по модулю 23. Однако, если p является простым числом не менее 600 цифр, то даже самые быстрые современные компьютеры , использующие самый быстрый известный алгоритм не может найти в данную только г , р и г мод р . Такая проблема называется проблемой дискретного логарифмирования . Вычисление g a mod p известно как модульное возведение в степень и может быть эффективно выполнено даже для больших чисел. Обратите внимание, что g совсем не обязательно должно быть большим и на практике обычно является небольшим целым числом (например, 2, 3, . ).

Таблица секретности

Теперь s - это общий секретный ключ, известный как Алисе, так и Бобу, но не Еве. Обратите внимание, что Еве бесполезно вычислять AB , которое равно g a + b mod p .

Примечание: Алисе должно быть сложно найти закрытый ключ Боба или Бобу - найти закрытый ключ Алисы. Если Алисе нетрудно найти закрытый ключ Боба (или наоборот), Ева может просто подставить свою пару закрытый / открытый ключ, вставить открытый ключ Боба в свой закрытый ключ, создать поддельный общий секретный ключ и решить Закрытый ключ Боба (и используйте его для поиска общего секретного ключа. Ева может попытаться выбрать пару открытого / закрытого ключей, которая упростит для нее поиск закрытого ключа Боба).

Здесь дается еще одна демонстрация Диффи – Хеллмана (также использующая слишком маленькие для практического использования числа) .

Обобщение на конечные циклические группы

Вот более общее описание протокола:

Алиса и Боб согласны по конечной циклической группыG порядка п и генерирующий элемент г в G . (Обычно это делается задолго до остальной части протокола; предполагается, что g известен всем злоумышленникам.) Группа G записывается мультипликативно.
Алиса выбирает случайное натуральное числоa , где 1 по модулю n Бобу.
Боб выбирает случайное натуральное число b , которое также равно 1 b mod n Алисе.
Алиса вычисляет ( g b mod n ) a mod n .
Боб вычисляет ( g a mod n ) b mod n .

И Алиса, и Боб теперь владеют элементом группы g ab , который может служить общим секретным ключом. Группа G удовлетворяет необходимому условию безопасной связи, если нет эффективного алгоритма для определения g ab с учетом g , g a и g b .

Например, протокол Диффи – Хеллмана для эллиптических кривых - это вариант, в котором вместо мультипликативной группы целых чисел по модулю n используются эллиптические кривые. Также были предложены варианты с использованием гиперэллиптических кривых . Обмен суперсингулярен ключ изогенности вариант Диффи-Хеллмана , который был разработан , чтобы быть защищенным от квантовых компьютеров .

Работа с более чем двумя сторонами

Соглашение о ключах Диффи – Хеллмана не ограничивается согласованием ключа, совместно используемого только двумя участниками. Любое количество пользователей может принять участие в соглашении, выполняя итерации протокола соглашения и обмениваясь промежуточными данными (которые сами по себе не должны храниться в секрете). Например, Алиса, Боб и Кэрол могут участвовать в соглашении Диффи-Хеллмана следующим образом, со всеми операциями, взятыми по модулю p :

Стороны согласовывают параметры алгоритма p и g .
Стороны генерируют свои закрытые ключи с именами a , b и c .
Алиса вычисляет g a и отправляет его Бобу.
Боб вычисляет ( g a ) b = g ab и отправляет его Кэрол.
Кэрол вычисляет ( g ab ) c = g abc и использует его как свой секрет.
Боб вычисляет g b и отправляет его Кэрол.
Кэрол вычисляет ( g b ) c = g bc и отправляет его Алисе.
Алиса вычисляет ( g bc ) a = g bca = g abc и использует его как свой секрет.
Кэрол вычисляет g c и отправляет его Алисе.
Алиса вычисляет ( g c ) a = g ca и отправляет его Бобу.
Боб вычисляет ( g ca ) b = g cab = g abc и использует его как свой секрет.

Злоумышленник может видеть g a , g b , g c , g ab , g ac и g bc , но не может использовать любую их комбинацию для эффективного воспроизведения g abc .

Чтобы распространить этот механизм на более крупные группы, необходимо соблюдать два основных принципа:

Эти принципы оставляют открытыми различные варианты выбора того, в каком порядке участники вносят вклад в ключи. Самое простое и очевидное решение - расположить N участников в круг и заставить N ключей вращаться по кругу, пока в конечном итоге каждый ключ не будет добавлен всеми N участниками (заканчивая его владельцем), и каждый участник внесет свой вклад в N ключей. (заканчивая своими). Однако для этого требуется, чтобы каждый участник выполнил N модульных возведений в степень.

Выбирая более оптимальный порядок, опираясь на то , что ключи могут быть продублированы, то можно уменьшить количество модульных возведения в степень , выполняемых каждым участником входа ₂ ( N ) + 1 , используя разделяй и властвуй стиле подход , данные здесь для восьми участников:

Каждый из участников A, B, C и D выполняет одно возведение в степень, что дает g abcd ; это значение отправляется в E, F, G и H. В ответ участники A, B, C и D получают g efgh .
Участники A и B выполняют по одному возведению в степень, получая g efghab , который они отправляют C и D, в то время как C и D делают то же самое, получая g efghcd , который они отправляют A и B.
Участник A выполняет возведение в степень, получая g efghcda , которую он отправляет B; аналогично, B отправляет g efghcdb в A. C и D делают аналогично.
Участник A выполняет одно последнее возведение в степень, получая секрет g efghcdba = g abcdefgh , в то время как B делает то же самое, чтобы получить g efghcdab = g abcdefgh ; опять же, C и D действуют аналогично.
Участники с E по H одновременно выполняют те же операции, используя g abcd в качестве отправной точки.

Как только эта операция будет завершена, все участники будут обладать секретом g abcdefgh , но каждый участник выполнил только четыре модульных возведения в степень, а не восемь, подразумеваемых простой круговой схемой.

Безопасность

Протокол считается защищенным от перехватчиков, если G и g выбраны правильно. В частности, порядок группы G должен быть большим, особенно если одна и та же группа используется для больших объемов трафика. Чтобы получить g ab, перехватчик должен решить проблему Диффи – Хеллмана . В настоящее время это считается трудным для групп, порядок которых достаточно велик. Эффективный алгоритм для решения проблемы дискретного логарифмирования упростил бы вычисление a или b и решение проблемы Диффи-Хеллмана, что сделало бы эту и многие другие криптосистемы с открытым ключом небезопасными. Поля с малыми характеристиками могут быть менее безопасными.

Порядка из G должен иметь большой простой множитель , чтобы предотвратить использование алгоритма Pohlig-Hellman для получения или б . По этой причине простое число Софи Жермен q иногда используется для вычисления p = 2 q + 1 , называемого безопасным простым числом , поскольку в этом случае порядок G делится только на 2 и q . г затем иногда выбирают , чтобы генерировать порядка Q подгруппу группы G , а не G , так что символ Лежандра из г никогда не показывает немного низкий порядок . Протокол, использующий такой выбор, - это, например, IKEv2 .

g часто является малым целым числом, например 2. Из-за случайной самосокращаемости задачи дискретного логарифмирования малый g так же безопасен, как и любой другой генератор той же группы.

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

Для предотвращения атак такого типа обычно требуется метод аутентификации взаимодействующих сторон друг с другом. Вместо этого можно использовать варианты Диффи – Хеллмана, такие как протокол STS , чтобы избежать подобных атак.

Практические атаки на интернет-трафик

По оценке авторов атаки Logjam, гораздо более сложный предварительный расчет, необходимый для решения проблемы дискретного журнала для 1024-битного простого числа, будет стоить порядка 100 миллионов долларов, что вполне укладывается в бюджет крупного национального разведывательного агентства, такого как США Агентство национальной безопасности (NSA). Авторы Logjam предполагают, что предварительные вычисления против широко используемых 1024-битных простых чисел DH лежат в основе утверждений в просочившихся документах NSA о том, что NSA способно взломать большую часть текущей криптографии.

Другое использование

Шифрование

Были предложены схемы шифрования с открытым ключом, основанные на обмене ключами Диффи – Хеллмана. Первая такая схема - это шифрование Эль-Гамаля . Более современный вариант - это интегрированная схема шифрования .

Прямая секретность

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

Соглашение о ключах с аутентификацией паролем

Примером такого протокола является протокол Secure Remote Password .

Открытый ключ

На практике алгоритм Диффи – Хеллмана таким образом не используется, поскольку RSA является доминирующим алгоритмом открытого ключа. Это во многом объясняется историческими и коммерческими причинами, а именно тем, что RSA Security создала центр сертификации для подписи ключей, который стал Verisign . Диффи – Хеллмана, как описано выше, нельзя напрямую использовать для подписания сертификатов. Однако с ним математически связаны алгоритмы подписи Эль-Гамаля и DSA , а также MQV , STS и компонент IKE из набора протоколов IPsec для защиты связи по Интернет-протоколу .

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