для решения каких задач может использоваться алгоритм диффи хеллмана
«Криптосистемы-протоколы»: Диффи—Хеллмана, Эль-Гамаля, MTI/A(0), STS
Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам. Предыдущие разделы главы «Криптографически протоколы»: 1, 2, 3
Как и создатели трёхпроходных протоколов из предыдущего раздела, авторы следующих алгоритмов считали их не просто математическими конструкциями, обеспечивающие некоторую элементарную операцию (например, шифрование с открытым ключом), но пытались вокруг одной-двух формул построить законченную систему распространения ключей. Некоторые из этих конструкций, преобразовавшись, используются до настоящего времени (например, протокол Диффи-Хеллмана), некоторые — остались только в истории криптографии и защиты информации.
Позже в 1990-х годах будут разделены математические асимметричные примитивы (шифрование и электронная подпись) и протоколы, эти примитивы использующие, что будет продемонстрировано в разделе про асимметричные протоколы.
Протокол Диффи—Хеллмана
Первый алгоритм с открытым ключом был предложен Диффи и Хеллманом в работе 1976 года «Новые направления в криптографии» (Bailey Whitfield Diffie, Martin Edward Hellman, «New directions in cryptography», [Diffie, Hellman 1976]). Данный протокол, который также можно назвать схемой Диффи—Хеллмана, стал первым, позволивший уменьшить требования к каналу связи для установления защищённого соединения без предварительного обмена ключами.
Протокол позволяет двум сторонам создать общий сеансовый ключ используя такой канал связи, который может прослушивать злоумышленник, но в предположении, что последний не может менять содержимое сообщений.
Пусть 
— большое простое число, 
— примитивный элемент группы 
, 
, причём , 
и известны заранее. Функцию считаем однонаправленной, то есть вычисление функции при известном значении аргумента является лёгкой задачей, а её обращение (нахождение аргумента) при известном значении функции — трудной. (Обратную функцию 
называют функцией дискретного логарифма. В настоящий момент не существует быстрых способов вычисления такой функции для больших простых .)
Протокол обмена состоит из следующих действий.
Протокол обеспечивает только генерацию новых сессионных ключей (цель G10). В отсутствие третей доверенной стороны он не обеспечивает ни аутентификацию сторон (цель G1), из-за отсутствия проходов с подтверждением владения ключом отсутствует аутентификация ключа (цель G8). Зато, так как протокол не использует длительные «мастер»-ключи, можно говорить о том, что он обладает свойством совершенной прямой секретности (цель G9).
Протокол можно использовать только с такими каналами связи, в которые не может вмешаться активный криптоаналитик. В противном случае протокол становится уязвим к простой «атаке посередине».
В результате Алиса и Боб получили новые сессионные ключи, но «защищённый» канал связи установили не с друг с другом, а со злоумышленником, который теперь имеет возможность ретранслировать или изменять все передаваемые сообщения между Алисой и Бобом.
Протокол Диффи—Хеллмана отличается от большей части протоколов распространения ключей из-за того, что не использует другие криптографические примитивы (функции шифрования, электронно-цифровой подписи или хеширования), но сам по себе является в некотором смысле криптографическим примитивом для построения более сложных протоколов. Он обеспечивает генерацию случайного числа в распределённой системе без доверенного центра. Причём ни одна из сторон не может заставить другую сторону использовать старый сессионный ключ, в отличие от, например, протокола Yahalom.
Протокол можно изменить таким образом, чтобы вместо мультипликативной группы простого умножения использовать аддитивную группу сложения точек эллиптической кривой. В этом случае стороны по прежнему будут выбирать некоторые случайные целые числа, но не возводить генератор-число в степень, а умножать генератор-точку на загаданное число.
Протокол Эль-Гамаля
Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.
Протокол не обеспечивает гарантию выбора нового сессионного ключа в каждом сеансе протокола (G10), а использование «мастер»-ключа 
для передачи сеансового ключа позволяет злоумышленнику вычислить все сессионные ключи из прошлых сеансов при компрометации закрытого ключа 
(цель G9).
Протокол MTI/A(0)
В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).
Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .
Из-за сложности задачи дискретного логарифмирования злоумышленник не сможет получить 
или 
из передаваемых сообщений, а предварительная публикация открытых ключей гарантирует, что сессионный ключ получат только легальные пользователи. Случайный выбор 
и 
гарантирует, что обе стороны могут быть уверены в создании нового сессионного ключа в каждом сеансе протокола.
Как и другие представители криптосистем-протоколов, MTI не разрабатывался с учётом возможности компрометации закрытых «мастер»-ключей 
и (цель G9).
Протокол Station-to-Station
Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.
Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .
Каждая из сторон 
и 
обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи 
и открытым ключом для шифрования и проверки подписи .
Где 
это функция проверки электронной подписи на открытом ключе 
, а 
— функция расшифрования с использованием закрытого ключа 
.
Протокол состоит из четырёх проходов, три из которых включают передачу сообщений ([Черёмушкин 2009]).
Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.
Как и все остальные «криптосистемы-протоколы», протокол Station-to-Station основывается на некотором внешнем источнике информации об открытых ключах участников, не подвергая сомнению корректность и надёжность этого источника. Что, в общем случае, неверно. Если информация о ключах участников нужно получать извне при каждом сеансе протокола (например, если участников много, и запомнить ключи всех возможности нет), то канал получения открытых ключей будет основной целью активного криптоаналитика для рассмотренных протоколов. Как от этого защититься с использованием примитивов асимметричной криптографии — в следующем разделе.
Литература
Автор будет благодарен за фактические и другие замечания к тексту.
Криптографические алгоритмы с открытым ключом и их использование
Вопросы практического использования алгоритма RSA
На протяжении многих лет алгоритм RSA активно используется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях. Открытое шифрование на базе алгоритма RSA применяется в популярном пакете шифрования PGP, операционной системе Windows, различных Интернет-браузерах, банковских компьютерных системах. Кроме того, различные международные стандарты шифрования с открытым ключом и формирования цифровой подписи используют RSA в качестве основного алгоритма.
Для обеспечения высокой надежности шифрования необходимо, чтобы выступающее в качестве модуля число N было очень большим – несколько сотен или тысяч бит. Только в этом случае будет практически невозможно по открытым параметрам определить закрытый ключ. Так, известно, что в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного модуля. Для этого с помощью сети Интернет было задействовано более тысячи компьютеров.
Алгоритм Диффи-Хеллмана
Основные сведения
Первая публикация данного алгоритма появилась в 70-х годах ХХ века в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом. Алгоритм Диффи-Хеллмана не применяется для шифрования сообщений или формирования электронной подписи. Его назначение – в распределении ключей. Он позволяет двум или более пользователям обменяться без посредников ключом, который может быть использован затем для симметричного шифрования. Это была первая криптосистема, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам. Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии – проблему распределения ключей.
Формирование общего ключа
Затем первый пользователь выбирает число Х1 (X1
, которое желательно формировать с помощью датчика случайных чисел. Это будет закрытый ключ первого пользователя, и он должен держаться в секрете. На основе закрытого ключа пользователь 1 вычисляет число
которое он посылает второму абоненту.
Аналогично поступает и второй пользователь, генерируя Х2 и вычисляя
Это значение пользователь 2 отправляет первому пользователю.
После этого у пользователей должна быть информация, указанная в следующей таблице:
| Общие параметры | Открытый ключ | Закрытый ключ | |
| Пользователь 1 | Р, А | Y1 | Х1 |
| Пользователь 2 | Y2 | Х2 |
Пользователи 1 и 2 могут использовать значение Z в качестве секретного ключа для шифрования и расшифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им.
Алгоритм Диффи — Хеллмана
В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.
Содержание
История [ ]
Годом позже был изобретен первый алгоритм асимметричного шифрования RSA, который решил проблему общения через незащищённый канал кардинально, уже не требуя, чтобы каждая сторона имела копию одного и того же секретного ключа.
В 2002 году Мартин Хеллман писал:
«Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана. Однако, когда система была впервые описана на бумаге Диффи и мной, это была система распространения публичных ключей, концепция которой была выработана Меркле, и поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркле“, если ее связывают с именами. Я надеюсь что это небольшое изменение поможет признанию равного вклада Меркле в изобретение криптографии с открытыми ключами.» [1]
В патенте U.S. Patent 4,200,770 (англ.) (в настоящее время истёкшем), описывающем данный алгоритм, изобретателями значатся Хеллман, Диффи и Меркле.
Описание алгоритма [ ]
Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение 
и пересылает его второму, а второй вычисляет и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (т.е. у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него и полученного по сети вычисляет значение , а второй абонент на основе имеющегося у него и полученного по сети вычисляет значение . Как нетрудно видеть, у обоих абонентов получилось одно и то же число: . Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления по перехваченным и , если числа выбраны достаточно большими.
Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ
При работе алгоритма, каждая сторона:
Криптографическая стойкость [ ]
Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K=g ab mod p по известным p, g, A=g a mod p и B=g b mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования. Однако, хотя умение решать проблему дискретного логарифмирования позволит взломать алгоритм Диффи — Хеллмана, обратное утверждение до сих является открытым вопросом (другими словами, эквивалентность этих проблем не доказана).
Необходимо еще раз отметить, что алгоритм Диффи — Хеллмана работает только на линиях связи, надёжно защищённых от модификации. Если бы он был применим на любых открытых каналах, то давно снял бы проблему распространения ключей и, возможно, заменил собой всю асимметричную криптографию. Однако, в тех случаях, когда в канале возможна модификация данных, появляется очевидная возможность вклинивания в процесс генерации ключей «злоумышленника-посредника» по той же самой схеме, что и для асимметричной криптографии.
См. также [ ]
ar:تبادل مفتاح ديفي-هيلمان cs:Diffie-Hellman de:Diffie-Hellman-Schlüsselaustausch en:Diffie-Hellman key exchange es:Diffie-Hellman fa:پروتکل تبادل کلید دیفی-هلمن fi:Diffie-Hellman fr:Échange de clés Diffie-Hellman he:פרוטוקול דיפי-הלמן it:Scambio di chiavi Diffie-Hellman ja:Diffie-Hellman鍵共有 nl:Diffie-Hellman-sleuteluitwisselingsprotocol pl:Protokół Diffiego-Hellmana pt:Diffie-Hellman simple:Diffie-Hellman key exchange tr:Diffie-Hellman
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
Протокол Диффи — Хеллмана
Протокол Ди́ффи-Хе́ллмана [1] (DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричное шифрование|симметричного шифрования.
Содержание
Описание алгоритма
Самый распространенный пример во всех учебных пособиях: Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны два числа g и p, желательно простых, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб — число b. Затем Алиса вычисляет значение (1):
и пересылает его Бобу, а Боб вычисляет (2):
и передаёт Алисе. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть, у него нет возможности вмешаться в процесс передачи).
На втором этапе Алиса на основе имеющегося у неё a и полученного по сети B вычисляет значение (3):
Боб на основе имеющегося у него b и полученного по сети A вычисляет значение (4):
Как нетрудно видеть, у Алисы и Боба получилось одно и то же число (5):
При работе алгоритма каждая сторона:
Пример
Протокол Диффи — Хеллмана для конференц-связи
< k = y ′ x ( p ) k = z ′ y ( p ) k = y ′ z ( p ) ⇒ k = g x y z ( mod p ) <\displaystyle