Задание 2.1. Система с открытым ключом Диффи-Хелмана

Сгенерировать секретные ключи для пяти абонентов по методу Диффи-Хеллмана (DH). Для этого взять значение секретного ключа x из таблицы 1. Соответствующие значения открытого ключа вычислить и результаты внести в таблицу. Вариант задания определяется по номеру i (предпоследняя цифра) и j (последняя цифра зачетной книжки) – требуемая для реализации этого алгоритма число x.

Число j – начальный номер для второго абонента при выборе числа x. Для выбора x для связи с пятью абонентами необходимо по циклической процедуре выбрать x по последней цифре зачетки. Например, цифры в зачетной книжке (15). Выбираем для первого абонента x=11, т.к. i =1. Для второго по второй цифре x =29, т.к. j= 5. Для третьего по формуле (j +1)=i выбираем x= 31, т.к. j =6. Для четвертого выбираем x = 37, j =7. Для пятого выбираем x = 39, т.к. j=8. Если, например, последняя цифра (27) больше пяти - пусть j =7, то выбираем x = 31,37, 39,41, 7.

Рекомендуемые значения p = 30803, g = 2.

Таблица 2.1 - Исходные данные:

Методические указания к решению задания 2.1

Первая система с открытым ключом — система Диффи-Хеллмана.

Эта криптосистема была открыта в середине 70-х годов американ­скими учеными Диффи (Whitfield Diffie) и Хеллманом (Martin Hell-man) и привела к настоящей революции в криптографии и ее практи­ческих применениях. Это первая система, которая позволяла защи­щать информацию без использования секретных ключей, передавае­мых по защищенным каналам. Для того чтобы продемонстрировать одну из схем применения таких систем, рассмотрим сеть связи с N пользователями, где N — большое число. Пусть мы хотим органи­зовать секретную связь для каждой пары из них. Если мы будем использовать обычную систему распределения секретных ключей, то каждая пара абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется ключей.

Если абонентов 100, то требуется 5000 ключей, если же абонен­тов 10⁴, то ключей должно быть 5∙10⁷. Мы видим, что при большом числе абонентов система снабжения их секретными ключами стано­вится очень громоздкой и дорогостоящей.

Диффи и Хеллман решили эту проблему за счет открытого рас­пространения и вычисления ключей. Перейдем к описанию предло­женной ими системы.

Пусть строится система связи для абонентов А,В,С,....

У каж­дого абонента есть своя секретная и открытая информация. Для организации этой системы выбирается большое простое число р и некоторое число g, 1 < g < р — 1 такое, что все числа из множе­ства {1, 2, ∙ ∙ ∙, р — 1} могут быть представлены как различные сте­пени g mod p (известны различные подходы для нахождения таких чисел g, один из них будет представлен ниже). Числа р и g известны всем абонентам.

Абоненты выбирают большие числа X_a,X_b,X_c, которые хра­нят в секрете (обычно такой выбор рекомендуется проводить случай­но, используя датчики случайных чисел). Каждый абонент вычис­ляет соответствующее число Y, которое открыто передается другим абонентам,

Y_А = g^Xa mod р,

Y_B = g^Xb mod р.. (1)

Yс = g^Xc mod р.

В результате получаем следующую таблицу.

Таблица 2.2 - Ключи пользователей в системе Диффи-Хеллмана

Допустим, абонент А решил организовать сеанс связи с В, при этом обоим абонентам доступна открытая информация из таблицы 2. Абонент А сообщает В по открытому каналу, что он хочет передать ему сообщение. Затем абонент А вычисляет величину

Z_AB = (Y_B)^ХА modp. (2)

Никто другой, кроме А, этого сделать не может, так как число Х_А секретно.

В свою очередь, абонент В вычисляет число

Z_BA = (Y_A)^XBmodp. (3)

На рисунке 1 представлена схема обмена ключами в системе Диффи-Хеллмана.

Остановимся теперь на упомянутой выше задаче выбора числа р. При произвольно заданном g она может оказаться трудной зада­чей, связанной с разложением на простые множители числа g - 1. Дело в том, что для обеспечения высокой стойкости рассмотренной системы число g - 1 должно обязательно содержать большой простой множитель. Поэтому часто рекомендуют использовать следующий подход.

Число р выбирается таким, чтобы выполнялось равенство

р=2q+1 (где q- также простое число)

и были справедливы неравенства

1 < g < р - 1 и g^q mod р 1.

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

Рисунок 1 - схема обмена ключами в системе Диффи-Хеллмана

Пример.

Пусть g = 43. Выберем пара­метр p. Попробуем взять q=17 401.

Соответственно р=2*17 401+1=34 803. Проверим: 43¹⁷⁴⁰¹ mod 34 803 = 17 746. Необходимые условия выполняются, значит, такое р подходит. Итак, мы выбрали параметры р = 34 803, g = 43. Теперь каждый або­нент выбирает секретное число и вычисляет соответствующее ему открытое число. Пусть выбраны Х_A = 7, Х_B = 13. Вычисляем Y_A = 43⁷ mod 34 803 = 11 689, Y_B = 43¹³ mod 34 803 = 14 479. Пусть А и В реши­ли сформировать общий секретный ключ. Для этого А вычисляет Z_AB = 14479⁷ mod 34 803=6 415, а В вычисляет Z_BA = 11 689¹³ mod 34 803 = 6 415. Теперь они имеют общий ключ 6 415, который не передавался по кана­лу связи.

Контрольные вопросы

1. Какими преимуществами перед другими алгоритмами с закрытым ключом обладает система Диффи-Хеллмана?

2. Дайте краткую характеристику системы Диффи-Хеллмана.

3. Объясните, почему число р, необходимое при вычислении секретных ключей, следует выбирать большим?

Поиск по сайту: