Обмен ключами по схеме Деффи-Хеллмана
Обмен ключами по схеме Диффи-Хеллмана реализован в целом ряде коммерческих продуктов.
Цель схемы — обеспечить двум пользователям защищенную возможность сообщить друг другу ключ, чтобы они могли прибегнуть к ней для шифрования последующих сообщений. Сам по себе алгоритм ограничивается процедурой обмена ключами.
Эффективность алгоритма Диффи-Хеллмана опирается на трудность вычисления дискретных логарифмов. Формально дискретный логарифм можно определить следующим образом. Сначала определяется первообразный корень простого числа р как число, степени которого порождают все целые числа от 1 до р — 1. Это значит, что если а является первообразным корнем простого числа р, то все числа
a mod р , a2 mod р , ..., ap-l mod р
должны быть разными и представлять все целые числа от 1 до р - 1 в некоторой перестановке.
Для любого целого числа b и любого первообразного корня а простого числа р однозначно определяется показатель степени i, при котором
b = ai mod р , где 0 < i < (р - 1).
Этот показатель степени обычно называется дискретным логарифмом, или индексом b по основанию а, рассматриваемому по модулю р. Это значение записывается в форме inda,p(b).
Теперь мы можем описать обмен ключами по схеме Диффи-Хеллмана, иллюстрацией которой служит рисунок 1. В этой схеме имеется два открытых для всех чисел: простое число q и целое число a, являющееся первообразным корнем q. Предположим, пользователи А и В намерены обменяться ключами. Пользователь А выбирает случайное целое число Хa < q и вычисляет
|
|
|
Ya = aХа mod q .
Точно так же пользователь В независимо выбирает случайное целое число Хв < q и вычисляет Yb = aХb mod q. Каждая сторона сохраняет значение X в тайне и делает значение Y свободно доступным другой стороне. Пользователь А вычисляет ключ по формуле К = (Yb)Хa mod q, а пользователь В — по формуле К = (Ya)Хb mod q. Эти. две формулы вычисления дают одинаковые результаты, как показано ниже.
К = (Yb)Xa mod q
= (aXb mod q)Xa mod q
= (aXb )Xa mod q (по правилам арифметики в классах вычетов)
= aXaXb mod q
= (aXa)Xb mod q
= (aXa mod q)Xb mod q
= (Ya)Xb mod q.
Итак, обе стороны обменялись секретным ключом. А поскольку при этом ХА и ХB были только в личном использовании и поэтому сохранились в тайне, противнику придется работать только с q, a, Ya и Yb. Таким образом, ему придется вычислять дискретный логарифм, чтобы определить ключ. Например, чтобы определить ключ пользователя В, противнику нужно вычислить
Xb = inda,q (Yb).
После этого он сможет вычислить ключ К точно так же, как это делает пользователь В.
Защищенность обмена ключами по схеме Диффи-Хеллмана опирается фактически на то, что в то время, как степени по модулю некоторого простого числа вычисляются относительно легко, вычислять дискретные логарифмы оказывается очень трудно. Для больших простых чисел последнее считается задачей практически неразрешимой.
|
|
|
Пример. Обмен ключами строится на использовании простого числа q = 97 и его первообразном корне a = 5. Пользователи А и В выбирают секретные ключи Хa =36 и Хb = 58 соответственно. Каждый вычисляет свой открытый ключ:
Ya = 536 = 50 mod 97 ,
Yb = 558 = 44 mod 97 .
После того как пользователи обменяются открытыми ключами, каждый из них может вычислить общий секретный ключ:
К = (Yb)Xa mod 97 = 4436 = 75 mod 97,
К = (Ya)Xb mod 97 = 5058 = 75 mod 97 .
Имея {50, 44}, противнику не удастся с легкостью вычислить 75.
На рисунке 2 представлен простой протокол, в котором применяются вычисления в соответствии со схемой Диффи-Хеллмана. Предположим, что пользователь А собирается установить связь с пользователем В и использовать секретный ключ, чтобы шифровать сообщения, передаваемые с помощью такой связи. Пользователь А может генерировать одноразовое секретное значение Хa , вычислить значение Ya и отослать последнее пользователю В. В ответ пользователь В генерирует секретное значение ХB, вычисляет YB и посылает Yb пользователю А. Оба пользователя могут теперь вычислить общий ключ. Необходимые открытые значения q и a должны быть известны заранее. Пользователь А может также выбрать эти значения на свое усмотрение и включить их в первое сообщение.
|
|
|
Для примера другой возможности использования алгоритма Диффи-Хеллмана рассмотрим некоторую группу пользователей (например, всех пользователей локальной сети) и предположим, что каждый из этих пользователей должен сгенерировать секретное значение Хa для долгосрочного применения и вычислить открытое значение Ya. Все полученные таким образом открытые значения вместе с глобальными открытыми значениями q и a сохраняются централизованно в некотором каталоге. В любой момент пользователь В может получить доступ к открытому значению пользователя А, вычислить секретный ключ и использовать его для пересылки шифрованного сообщения пользователю А. Если централизованно хранящийся каталог надежен, то этот форма коммуникации обеспечивает как конфиденциальность, так и определенную степень аутентификации. Поскольку только пользователи А и В могут определить ключ, другой пользователь не может прочитать сообщение (конфиденциальность). Получатель А знает, что только пользователь В мог создать сообщение, используя этот ключ (аутентификация). Однако такая схема не защищена от атак на основе воспроизведения сообщений.
|
|
|
| Глобальные открытые элементы | |
| q | Простое число |
| a | a < q и a - первообразный корень q |
| Вычисление ключа пользователем А | |
| Выбор секретного Ха | Ха < q |
| Вычисление открытого Yа | Yа = aXa mod q |
| Вычисление ключа пользователем В | |
| Выбор секретного Хb | Хb < q |
| Вычисление открытого Yb | Yb = aXb mod q |
| Вычисление секретного ключа пользователем А | |
| K = (Yb)Xa mod q | |
| Вычисление секретного ключа пользователем B | |
| K = (Ya)Xb mod q | |
Рисунок 1 – Алгоритм обмена ключами по схеме Деффи-Хеллмана
| Пользователь А |
| Пользователь В | |
| Генерировать случайное Ха < q; Вычислить Yа = aXa mod q | Генерировать случайное Хb < q; Вычислить Yb = aXb mod q | ||
| Вычислить K = (Ya)Xb mod q | |||
| Вычислить K = (Yb)Xa mod q | |||
Рисунок 2 – обмен ключами по схеме Деффи-Хеллмана
Задание
1. Рассмотрите схему Деффи-Хеллмана с общим простым числом q =11 и первообразным корнем a = 2.
- Если пользователь А имеет открытый ключ Ya = 9 , то каким будет личный ключ пользователя А, Ха ?
- Если пользователь В имеет открытый ключ Yb = 3, то каким будет их общий секретный ключ К ?
2. В 1985 году Т. Эль-Гамаль (Т. ElGamal) предложил схему с открытым ключом, основанную на использовании дискретных логарифмов и очень близкую к схеме Диффи-Хеллмана. Как и в случае схемы Диффи-Хеллмана, глобальными элементами схемы Эль-Гамаля являются простое число qи число a— первообразный корень q. Пользователь А выбирает личный ключ Ха и вычисляет открытый ключ Yа, как в схеме Диффи-Хеллмана. Пользователь А шифрует предназначенный для пользователя В открытый текст
М < qследующим образом.
- Выбирается такое случайное целое число k, что
- 1 <= k <=q - 1.
- Вычисляется К = (Yb)k(mod q).
- Текст М шифруется, как пара целых чисел (С1, С2), где C1 = ak(mod q),
- С2 = KM(mod q).
Пользователь В восстанавливает открытый текст следующим образом.
- Вычисляется К = (C1)Xb(mod q).
- Вычисляется М = (С2К-1) mod q .
Покажите, что эта система работает; т.е., что процедура дешифрования действительно восстанавливает открытый текст.
3. Рассмотрите схему Эль-Гамаля с общим простым числом q = 71 и первообразным корнем a = 7.
- Если пользователь В имеет открытый ключ Yb = 3, а пользователь А выбирает случайное число k = 2, то каким будет шифрованный текст для М = 30?
- Если теперь пользователь А выберет другое значение k, так что сообщение М = 30 будет кодироваться как С = (59, С2), то каким при этом будет целое число С2?
Содержание отчёта
Отчёт должен содержать:
1. задание к работе;
2. решение задач.
Контрольные вопросы
1. Сертификаты открытых ключей
2. Публичное объявление открытых ключей
3. Публично доступный каталог
4. Авторитетный источник открытых ключей
Литература
Основная:
1. Столлингс В. Криптография и защита сетей: принципы и практика, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. - 672 с.
2. Анин Б.Ю. Защита компьютерной информации. – СПб.: БХВ – Санкт-Петербург, 2000. - 384 с.
3. Введение в криптографию / Под общей ред. В.В. Ященко. – СПб.: Питер, 2001. – 288с.
4. Аскеров Т. М. Защита информации и информационная безопасность. Учебное пособие / Под общей редакцией К. И. Курбакова. М.; Рос. экон. акад., 2001. 387 с.
5. Баричев С. В. Криптография без секретов. М: Наука. 1998. 120 с.
6. Барсуков В. С, Вододазский. В. В. Интегральная безопасность информационно-вычислительных и телекоммуникационных сетей (часть 1). Технология электронных коммуникаций. М., 1993. 146 с.
7. Барсуков В. В., Физическая защита информационных систем /Jetlnfo online, 1997. № 1(32).
8. Вербицкий О. В. Вступление к криптологии. Львов: Издательство науково-техничмой литературы, 1998. 300 с.
9. Гайкович В., Першин А. Безопасность электронных банковских систем. Москва. Компания «ЕДИНАЯ ЕВРОПА», 1994. 331 с.
10. Галатенко В. А. Информационная безопасность. М.: Финансы и статистика, 1997. 158 с.
11. Герасименко В. А. Зашита информации в автоматизированных системах обработки данных (кн. 1). М.: Энергоатомиздат, 1994. 400 с.
12. Герасименко В. А., Малюк А. А. Основы защиты информации. М.: МИФИ, 1997.537 с.
13. Герасименко В. А., Партыка Т. Л. Каталог программных средств защиты информации от несанкционированного доступа в АСОД. Метод, указания. М.: ГКНТ, 1984. 214 с.
14. Герасименко В. А., Партыка Т. Л., Каталог каналов утечки информации в АСОД. Метод, указания. М.: ГКНТ, 1985. 273 с.
15. Герасименко В. А., Скворцов А. А., Харитонов И. Е. Новые направления применения криптографических методов защиты информации. М.; Радио и связь, 1989. 360 с.
16. Гостехкомиссия России. Руководящий документ. Автоматизированные системы. Защита от несанкционированного доступа к информации. Классификация автоматизированных систем и требования позащите информации. М.: Военное издательство, 1992. 39 с.
17. Гостсхкомиссия России. Руководящий документ. Зашита от несанкционированного доступа к информации. Термины и определения. М.: Военное издательство, 1992. 12 с.
18. Гостехкомиссия России. Руководящий документ. Концепция защиты средств вычислительной техники и автоматизированных систем от несанкционированного доступа к информации. М.; Военное издательство, 1992. 12 с.
19. Грегори С. Смит. Программы шифрования данных // Мир ПК, 1997. № 3. С. 58-68.
20. 17.ДиффиУ. Первые десять лет криптографии с открытым ключом //ТИИЭР, т. 76(1988)6 Т5б. С. 54-74.
21. Зима В. М., Молдовян А. А., Молдовян Н. А. Защита компьютерных ресурсов от несанкционированных действий пользователей. Учебное пособие. СПб., 1997. 189 с.
22. Касперский Е. Компьютерные вирусы в MS-DOS. M.: Эдель-Рснессанс, 1992.
23. Криптология — наука о тайнописи // Компьютерное обозрение. 1999. № 3. С. 10-17.
24. Лопатин В. Н. Информационная безопасность России: Челопек. Общество. Государство / Санкт-Петербургский университет МВД России. СПб.: Фонд «Университет». 2000. 428 с.
25. Мельников В. Защита информации в компьютерных системах. М.: «Финансы и статистика», «Электронинформ», 1997. 364 с.
26. Миллер В. Использования эллиптических кривых в криптографии. М., 1986. С 417-426.
Дополнительная:
1. Нечаев В. И. Элементы криптографии (Основы теории защиты информации). Учебное пособие для ун-тов и пед. вузов / Под ред. В. А. Садовничего. М.: Высшая школа, 1999. 109 с.
2. Расторгуев С. П. Программные методы защиты информации в компьютерах и сетях. М.: Издательство Агентства «Яхтсмен», 1993. 188 с.
3. Ростовцев А. Г., Михайлова Н. В. Методы криптоанализа классических шифров. М.: Наука, 1995. 208 с.
4. Ухлинов Л. М. Международные стандарты в области обеспечения безопасности данных в сетях ЭВМ. Состояние и направления развития. М.: Электросвязь, 1991.
5. Федеральный закон «Об информации, информатизации и защите информации». Собрание законодательства Российской Федерации. 20 февраля 1995 г. Официальное издание. М.: Издательство «Юридическая литература», Администрация Президента Российской Федерации. С 1213—1225.
6. Кодекс Российской Федерации об административных правонарушениях. М.: Инфра-М, 2002. 304 с.
7. Жельников В. криптография от папируса до компьютера. М.: ABF, 1996
8. Саломаа А. Криптография с открытым ключом. М.: Мир, 1995.
Дата добавления: 2019-09-13; просмотров: 335; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!