Сгенерировать секретные ключи для абонентов A, B, C, D и по методу Диффи-Хеллмана (DH). Для этого взять значение g из таблицы 1.1 (i - предпоследняя цифра номера зачетной книжки), а значение р подобрать согласно методическим указаниям.

Число j (последняя цифра номера зачетной книжки) – номер для первого абонента (абонента А) при выборе числа Х_А. Значения X_B, X_C, X_D, X_E для остальных четырех абонентов необходимо выбрать по циклической процедуре, прибавляя каждый раз по единице.

Например, цифры в зачетной книжке (15). Выбираем число g = 3, т.к. i= 1. Значение Х_А равно 29 (т. к. j =5). Для второго абонента значение Х_В будет равно 31 (j =5+1=6), Для третьего Х_С = 37, т. к. j =7. Для пятого выбираем Х_Е = 41, т.к. j=9. Если, например, последняя цифра номера зачетной книжки 7 (больше пяти), то выбираем Х_А=37, Х_В=39, Х_С=41, Х_D=7, Х_E= 11.

Таблица 1.1 Исходные данные для числа g :

Таблица 1.2 Исходные данные для чисел X_A, X_B, X_C, X_D, X_E:

Методические указания к решению задания 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 р.

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

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

Допустим, абонент А решил организовать сеанс связи с В, при этом обоим абонентам доступна открытая информация из табл. 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 - схема обмена ключами в системе Диффи-Хеллмана

Пример 2.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. Объясните, почему число р, необходимое при вычислении секретных ключей, следует выбирать большим?

2.2 Шифрование по алгоритму Шамира

Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблиц 2.1 и 2.2 соответственно. По номеру j (последняя цифра номера зачетной книжки) выбирается требуемое для реализации этого алгоритма число р. По i (предпоследняя цифра номера зачетной книжки) студент выбирает сообщение для зашифровывания, передаваемое первым абонентом. Выбор сообщений для других абонентов производится циклически, согласно процедуре (i + 1). Например, последние цифры номера зачетной книжки – (63). Выбираем для трех абонентов p = 41, m_A=24, m_B=24, m_C=24.

Таблица 2.1 – исходные данные для выбора сообщений ( m )

Таблица 2.2 – исходные данные для выбора числа р