Файл: Методические указания и контрольные задания по дисциплине информационная безопасность для студентов направления 09. 03. 02.doc

.


5. Для дешифрования нужно выполнить возведение в степень, используя ключ дешифрования d, т.е.

и т.д.
Задача 3.2.

Зашифровать и расшифровать сообщение САВ. Для простоты вычислений использовать небольшие числа: р =3 , q=11, открытый ключ е=7. Для вычисления секретного ключа d воспользоваться расширенным алгоритмом Евклида.
Решение.

Действия пользователя В- получателя сообщения.

1. Выбирает р =3 и q=11.

2. Вычисляет модуль n=p*q=3*11=33.

3. Вычисляет значение функции Эйлера для n = 33:

z(33) = (p –1)(q –1) = 210 = 20.

Выбирает в качестве открытого ключа е произвольное число с учетом выполнения условий:

1<  20, НОД (e, 20) = 1.

Пусть e= 7.

4. Вычисляет значение секретного ключа d, используя расширенный алгоритм Евклида при решении сравнения

d 7^–1 (mod 20).

Решение дает d= 3.

5. Пересылает пользователю А (отправителю) пару чисел (n = 33, e= 7).

Действия пользователя A-отправителя сообщения.

6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0 ... 32. Пусть буква А представляется как число 1, буква В – как число 2, буква С – как число 3. Тогда сообщение САВ можно представить как последовательность чисел 312, т.е. = 3, = 1, = 2.

7. Шифрует текст, представленный в виде последовательности чисел , и

---

, используя ключ e= 7 и n = 33, по формуле



Получает криптограмму:

С₁ = 3⁷ (mod 33) = 2187 (mod 33) = 9,

С₂ =1 ⁷ (mod 33) =1 (mod 33) =1,

С₃ = 2⁷ (mod 33) =128 (mod 33) = 29.

Отправляет пользователю В криптограмму

С₁, С₂, С₃ = 9, 1, 29.

Действия пользователя В.

8. Расшифровывает принятую криптограмму С₁, С₂, С₃, используя секретный ключ d=3, по формуле



Получает:

= 9³ (mod 33) = 729 (mod 33) = 3,

=1³ (mod 33) =1 (mod 33) =1,

= 29³ (mod 33) = 24389 (mod 33) = 2.

Таким образом, восстановлено исходное сообщение: С А В

3 1 2

Пояснение к заданию 4

Алгоритмы электронной цифровой подписи

4. Алгоритм цифровой подписи Эль Гамаля (EGSA)
Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,– задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSA, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Для того чтобы сгенерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое целое число P и большое целое число G, причем G < P. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа P (10³⁰⁸ или 2¹⁰²⁴) и G (10¹⁵⁴ или 2⁵¹²), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1< X  (P –1), и вычисляет

Y = G^X mod P.

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

---

Число X является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Для того чтобы подписать сообщение M, сначала отправитель хэширует его с помощью хэш-функции h(·) в целое число m:

m = h(M), 1< m < (P –1),

и генерирует случайное целое число K, 1< K< (P –1), такое, что K и (P –1) являются взаимно простыми. Затем отправитель вычисляет целое число a:

a = G^K mod P

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа X целое число b из уравнения

m =( X a + K  b) (mod (P –1)).

Пара чисел (a,b) образует цифровую подпись S:

S = (a,b),

проставляемую под документом M.

Тройка чисел (M,a,b) передается получателю, в то время как пара чисел (X,K) держится в секрете.

После приема подписанного сообщения (M,a,b) получатель должен проверить, соответствует ли подпись S = (a,b) сообщению M. Для этого получатель сначала вычисляет по принятому сообщению M число

m = h(M),

т.е. хэширует принятое сообщение M.

Затем получатель вычисляет значение

A = Y^a a^b (mod P)

и признает сообщение M подлинным, если, и только если

A = G^m (mod P).

Иначе говоря, получатель проверяет справедливость соотношения

Y^a a^b (mod P) = G^m (mod P).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(a,b) под документом M получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения M был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ M.

Выполнение каждой подписи по методу Эль Гамаля требует нового значения K, причем это значение должно выбираться случайным образом. Если нарушитель раскроет значение K, повторно используемое отправителем, то он сможет раскрыть секретный ключ X отправителя.
Задача 4.1

Сформировать и проверить ЭЦП Эль Гамаля при следующих начальных условиях: Р=11, G=2, секретный ключ Х=8.
Решение. Вычисляем значение открытого ключа:

Y = G^X mod P = Y = 2⁸ mod 11 = 3.

Предположим, что исходному сообщению M соответствует хэш-значение m = 5.

Для того,чтобы вычислить цифровую подпись под сообщением M, имеющем хэш-значение m = 5, сначала выберем случайное целое число K = 9. Убедимся, что числа K и (P – 1) являются взаимно простыми. Действительно,

НОД (9, 10) = 1.

---

Далее вычисляем элементы a и b подписи:

a = G^K mod P = 2⁹ mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = (X  a + K  b) (mod (P – 1)).

При m = 5, a = 6, X = 8, K = 9, P = 11 получаем

5 = (6  8 + 9  b)(mod 10)

или

9  b  – 43 (mod 10).

Решая сравнение, получаем b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3.

Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения M : m = 5, а затем вычисляет два числа:

1) Y^aa^b (mod P) = 3⁶  6³ (mod 11) =10 ;

2) G^m (mod P) = 2⁵ (mod 11) =10.

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA.

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

2. При выборе модуля P достаточно проверить, что это число является простым и что у числа (P –1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).

3. Процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSA).

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

Пояснение к заданию 5

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

Для решения этой проблем можно применить два способа:

---

1) использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы;

2) использование системы открытого распределения ключей Диффи–Хеллмана.
5.1. Алгоритм открытого распределения ключей Диффи–

Хеллмана
Алгоритм Диффи–Хеллмана был первым алгоритмом с открытыми ключами (предложен в 1976 г.). Его безопасность обусловлена трудностью вычисления дискретных логарифмов в конечном поле, в отличие от легкости дискретного возведения в степень в том же конечном поле.

Предположим, что два пользователя А и В хотят организовать защищенный коммуникационный канал.

1. Обе стороны заранее уславливаются о модуле N (N должен быть простым числом) и примитивном элементе g, (1  g  N –1).

Эти два целых числа N и g могут не храниться в секрете. Как правило, эти значения являются общими для всех пользователей системы.

2. Затем пользователи А и В независимо друг от друга выбирают собственные секретные ключи k_А и k_В (k_А и k_В – случайные большие целые числа, которые хранятся пользователями А и В в секрете).

3. Далее пользователь А вычисляет открытый ключ

y_A = (mod N),

а пользователь В – открытый ключ

y_В = (mod N).

4. Затем стороны А и В обмениваются вычисленными значениями открытых ключей y_A и y_В по незащищенному каналу.

5. Далее пользователи А и В вычисляют общий секретный ключ, используя следующие выражения:

пользователь А: К = = (mod N);

пользователь В: К´ = = (mod N).

При этом К = К´, так как = (mod N).

Схема реализации алгоритма Диффи–Хеллмана показана на рис. 5.1.

---