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

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

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

Физико-математический факультет

Кафедра информатики

 

КУРСОВОЙ ПРОЕКТ

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

Выполнил:

Студент

Физико-математического  факультета

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

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

Научный руководитель:

Старший преподаватель

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

Оглавление

ВВЕДЕНИЕ 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. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

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

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

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

«До этого я и представить  себе не мог, насколько тесно связано  шифрование и теория информации», -говорит он.В статьях Шенона вопросы кодирования рассматривались в связи с задачей снижения электростатических помех, мешающих передаче радиосигналов.

«Шифрование, -  заметил Хеллман , - решает диаметрально противоположную задачу. Вы вносите искажения при помощи ключа. Для того, кто слышит сигнал и не знает ключа, он будет выглядеть максимально искаженным. Но легитимный получатель, которому известен секретный ключ, может удалить эти помехи».

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

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

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

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

«Я думал о том, как обеспечить защиту коммуникаций между терминалом и компьютером, - рассказывает Меркл. - Я понял, что если оба, и терминал, и компьютер, используют случайные числа, восстановить ключ при передаче по открытым линиям связи будет невозможно».

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

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

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

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

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

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

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

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

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

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

A = g^amod p   (1)

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

B = g^bmod p (2)

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

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

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

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

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

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

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

A = g^a mod p/ B=g^bmod p

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

K = B^a mod p/ K=A^bmod 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¹⁰⁰ и p порядка 10³⁰⁰. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

3. Блок-Схема

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Протокол Диффи-Хеллмана отлично  противостоит пассивному нападению, но в случае реализации атаки «человек посередине» он не устоит. В самом  деле, в протоколе ни Алиса, ни Боб  не могут достоверно определить, кем  является их собеседник, поэтому вполне возможно представить следующую  ситуацию, при которой Боб и  Алиса установили связь с Меллори, который Алисе выдает себя за Боба, а Бобу представляется Алисой. И  тогда вместо протокола Диффи-Хеллмана получаем, что-то похожее на следующее: