Технология выполнения задания. Задание. 1.Известны значение модуля шифрования N, открытого ключа e и открытого текста

Задание. 1. Известны значение модуля шифрования N, открытого ключа e и открытого текста. Кодирование символов сообщения осуществляется с помощью таблицы 17. Найти значение шифр-текста Y, полученного при шифровании текста на открытом ключе (N, e) по алгоритму RSA.

Таблица 17. Таблица кодирования символов открытого текста

Символ

а

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

код

Символ

р

с

т

y

ф

х

ц

ч

ш

щ

ь

ы

ъ

э

ю

я

код

1. Выбрать параметры шифра и открытый текст в соответствии с номером варианта (табл.18, выбор осуществляется по порядковому номеру в официальном списке группы).

Таблица 18. Варианты задания

1.	N = 3149; e = 13; морж	14.	N = 1763; e = 11; враг
2.	N = 5767; e = 17; приз	15.	N = 4307; e = 17; курс
3.	N = 5609; e = 17; гусь	16.	N = 1739; e = 17; друг
4.	N = 2491; e = 19; окно	17.	N = 1927; e = 19; град
5.	N = 5063; e = 11; лиса	18.	N = 2257; e = 17; зной
6.	N = 6319; e = 17; свет	19.	N = 4087; e = 13; перо
7.	N = 2923; e = 19; гном	20.	N = 3403; e = 11; вред
8.	N = 4087; e = 13; глаз	21.	N = 3071; e = 11; рука
9.	N = 4331; e = 11; гриб	22.	N = 4891; e = 17; снег
10.	N = 8633; e = 13; мышь	23.	N = 4559; e = 17; день
11.	N = 3713; e = 11; муха	24.	N = 5561; e = 19; ночь
12.	N = 3953; e = 17; лист	25.	N = 8051; e = 11; чудо
13.	N = 1961; e = 11; жезл

Изучить теоретическое описание алгоритма RSA. Выполнить шифрование по аналогии с рассмотренным далее примером.

Пример: N = 2537, e = 23, требуется зашифровать по алгоритму RSA текст «зима».

2. Подготовить открытый текст к шифрованию, задав для него числовое представление.

· Закодировать текст с помощью таблицы 17:

з	и	м	а

Объединить коды символов текста в общую последовательность символов: числовое представление открытого текста X = 18412311.

· Разбить последовательность цифр X на части так, чтобы X_i < N, ни одна часть не содержит ведущих нулей. Поскольку N =2537, X_i <2537:

X ₁=1841, X ₂=2311.

3. Зашифровать X ₁ по формуле: Y = X^e mod N. Для вычислений можно использовать табличный процессор MS Excel. Зашифруем сначала X ₁:

· В новой книге MS Excel в ячейку A1 внести номер шага: 1, в ячейку B1 – значение X ₁ (в примере – число 1841).

· В ячейку А2 внести номер шага: 2, в ячейку B2 – итерационную формулу для вычисления остатка от деления по модулю N, в примере формула примет вид:

=ОСТАТ( 1841* B1; 2537 )

· Выделить диапазон ячеек A1:A2 и растянуть вниз, заполнив ячейки столбца А рядом данных до значения e (в примере = 23) включительно.

· Выделить ячейку В2 и растянуть вниз (скопировать ее) в диапазон ячеек столбца B строки с номером e включительно (в примере – до ячейки В23).

· Результат вычисления X ₁ = 1841²³ mod 2537 находится в последней заполненной ячейке столбца B.

В примере – результат находится в ячейке B23, это 580 (рис.53).

Результат шифрования X ₁: Y ₁=580.

4. Аналогичным образом зашифровать X ₂, результат шифрования Y ₂=2373.

Рис.53. Пример вычисления шифр-текста RSA в MS Excel

5. Получить шифр-текст Y, объединив символы числовых последовательностей Y ₁ и Y ₂.

В примере получен шифр-текст Y =5802373.

Задание. 2. Криптограмма Y получена шифрованием на известном открытом ключе (N, e) по алгоритму RSA. Вычислить секретный ключ d и получить открытый текст, если кодирование символов сообщения осуществлялось с помощью таблицы 17.

6. Выбрать параметры шифра и открытый текст в соответствии с номером варианта (табл.19, выбор осуществляется по порядковому номеру в официальном списке группы).

Таблица 19. Варианты задания

1.	N = 437; e = 115; Y = 416384
2.	N = 253; e = 139; Y = 54207
3.	N = 143; e = 23; Y = 3318
4.	N = 221; e = 91; Y = 162106
5.	N = 493; e = 69; Y = 40313
6.	N = 299; e = 61; Y = 35172

Окончание таблицы 19. Варианты задания

7.	N = 209; e = 53; Y = 19074
8.	N = 319; e = 51; Y = 197270
9.	N = 299; e = 139; Y = 295271
10.	N = 209; e = 131; Y = 6028
11.	N = 377; e = 197; Y = 22215
12.	N = 391; e = 145; Y = 28177
13.	N = 143; e = 113; Y = 14059
14.	N = 667; e = 227; Y = 458575
15.	N = 187; e = 59; Y = 117147
16.	N = 377; e = 121; Y = 217189
17.	N = 221; e = 35; Y = 12632
18.	N = 391; e = 47; Y = 10349
19.	N = 323; e = 131; Y = 278136
20.	N = 319; e = 33; Y = 311142
21.	N = 341; e = 53; Y = 1018
22.	N = 143; e = 37; Y = 3779
23.	N = 299; e = 83; Y = 229181
24.	N = 247; e = 59; Y = 195147
25.	N = 391; e = 169; Y = 248313

Выполнить дешифровку криптограммы по аналогии с рассмотренным далее примером.

Пример: N = 551; e = 89; Y = 265478.

7. Сначала надо получить ключ расшифровки. Для вычисления личного ключа получателя криптограммы (N, d) необходимо решить задачу разложения числа N на простые множители. Эта задача является вычислительно сложной, ее можно решить перебором всех простых чисел до тех пор, пока не будет найден один из множителей. В общем случае такой перебор неэффективен, и при используемых на практике параметрах шифра RSA невозможен в силу вычислительной сложности. Однако поскольку в примере N – небольшое число, разложение его на множители практически осуществимо. Для решения задачи разложения на множители можно воспользоваться инструментом Поиск решения MS Excel:

· На новом листе книги MS Excel ввести в ячейки A1 и B1 значение 10. В ячейку B2 ввести формулу: = A1 * B1.

· Проверить наличие инструмента Поиск решения на вкладке Данные в группе Анализ. Если инструмент отсутствует, следует его включить, для этого выполнить команду Файл/Параметры, перейти на вкладку Надстройки, в строке Управление выбрать Надстройки Excel и щелкнуть кнопку Перейти, затем в окне Надстройки установить флажок рядом с пунктом Поиск решения и нажать ОК (рис.54).

Рис.54. Включение надстройки Поиск решения

· Выбрать ячейку B2 (в которой подсчитано произведение двух множителей) и вызвать инструмент Поиск решения (вкладка Данные).

· В окне Поиск решения установить целевую ячейку – $B$2 равной значению N (в примере – 551), в поле Изменяя ячейки переменных выделить диапазон ячеек $A$1:$B$1, в группе В соответствии с ограничениями нажать кнопку Добавить, в окне Добавление ограничения в поле Ссылка на ячейку выделить диапазон ячеек $A$1:$B$1, в следующем поле выбрать значение цел и нажать ОК (рис.55). Будет установлено ограничение $A$1:$B$1 = целое. Результирующий вид окна настроек инструмента Поиск решения показан на рис.56.

Рис.55. Задание ограничений на изменяемые ячейки

Рис.56. Настройка инструмента Поиск решения

· В окне Поиск решения выбрать метод решения Поиск решения нелинейных задач методом ОПГ, затем нажать кнопку Параметры и на вкладке Все методы установить Максимальное время: 1000 и Предельное число итераций: 10000. Нажать ОК.

· После того, как инструмент Поиск решения полностью настроен, в окне Поиск решения нажать кнопку Выполнить. Будет выдано окно Результаты поиска решения с сообщением о том, что решение найдено – установить переключатель в позицию Сохранить найденное решение и нажать ОК. В ячейках A1 и B1 будут получены значения простых множителей числа N.

В рассматриваемом примере после выполнения поиска решения в ячейке A1 будет установлено значение 19, а в ячейке B1 – 29. Это и есть множители числа N =551.

ПРИМЕЧАНИЕ: Если один из множителей получен равным 1, то следует изменить начальные значения в ячейках A1 и B1, а затем повторно выполнить поиск решения.

8. Получили: p =19, q =29. Поскольку оба числа простые, легко вычислить значение φ(N):

φ(N) = φ(p * q) = (p -1)*(q -1) = 18*28 = 504.

9. Зная значение φ(N) и e, можно вычислить секретный ключ d из условия e * d º 1(mod φ(N)), d º e ^-1(mod φ(N)). Для вычисления d можно воспользоваться расширенным алгоритмом Евклида:

· Сформировать первую строку (U) расширенного алгоритма Евклида: на новом листе в ячейку A1 занести значение φ(N) – 504, в ячейку B1 – 0.

· Сформировать вторую строку (V) расширенного алгоритма Евклида: в ячейку A2 занести значение e – 89, в ячейку B2 – 1.

· Вычислить значение k = u₁ div v₁: в ячейку C3 занести формулу: = ЧАСТНОЕ (A1, A2).

· Сформировать строку T={u₁ mod v₁, u₂-k*v₂} расширенного алгоритма Евклида: в ячейку A3 занести формулу: = ОСТАТ(A1, A2), в ячейку B3 – формулу: = B1 - B2 * C3.

· Выделить диапазон ячеек A3:C3 и растянуть (скопировать) на несколько строк вниз, пока в столбце A не будет получено нулевое значение.

Результаты реализации расширенного алгоритма Евклида для рассматриваемого примера показаны на рис.57.

Рис.57. Пример реализации расширенного алгоритма Евклида

· Значение d находится в предпоследней строке в столбце B, то есть, в строке, предшествующей строке, начинающейся с 0. Строка с результатом должна начинаться с 1.

Для рассматриваемого примера значение личного ключа d содержится в ячейке B6, d =17.

ПРИМЕЧАНИЕ: Если полученное значение d – отрицательное, следует взять его по модулю φ(N). Для этого можно использовать функцию ОСТАТ() или просто сложить d со значением φ(N).

10. Подготовить последовательность Y к расшифровке, разбив ее на части Y_i таким образом, чтобы каждая часть Y_i < N и не содержала бы ведущих нулей.

В рассматриваемом примере N =551, значит Y_i <551, получаем Y ₁=265, Y ₂=478.

11. Вычислить X ₁, используя формулу X = Y^d mod N, вычисления производятся аналогично пункту 3 (текущей лабораторной работы).

Для рассматриваемого примера X ₁ = 265¹⁷ mod 551:

· A1: 1, B1: =265,

· А2: 2, B2: =ОСТАТ(265* B1; 551), растянуть A1:A2 и B2 вниз до строки с номером d (=17), результат: 151 (рис.58).

X ₁=151.

Рис.58. Пример расшифровки RSA

· Выполнить проверку для X ₁, используя формулу: Y = X^e mod N (вычисления производятся аналогично, в результате вычислений должно быть получено исходное значение Y ₁).

X ₁ ^e mod N = 151⁸⁹ mod 551 = 265 = Y ₁.

Расшифровано правильно.

12. Аналогичным образом получить и провести проверку значения X ₂.

Для рассматриваемого примера:

X ₂ = Y ₂ ^d mod N = 478¹⁷ mod 551 = 127.

Проверка:

X ₂ ^e mod N = 127⁸⁹ mod 551 = 478 = Y ₂, расшифровано правильно.

13. Преобразовать полученные значения в текстовое сообщение:

· Сформировать общую числовую последовательность X объединением расшифрованных частей X ₁ и X ₂: X =151127.

· Поскольку известно, что кодировка символов сообщения производилась с помощью таблицы 17, в которой каждому символу сопоставлено двузначное число, разбить последовательность X на пары символов: 15, 11, 27.

· Используя таблицу 17, найти символы, соответствующие полученным числовым кодам:

д	а	р

Зашифрованное сообщение содержит текст «дар».

14. Показать результаты выполнения лабораторной работы преподавателю.

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

1. Какой ключ должен использовать отправитель сообщения для шифрования в асимметричных криптосистемах?

(Открытый ключ получателя)

2. Какой ключ использует получатель сообщения для расшифровки присланного ему шифр-текста в асимметричных криптосистемах?

(Свой личный ключ)

3. Почему вычисление степени числа по модулю проводится не напрямую по формуле, а с использованием итерационного алгоритма?

(При больших значениях основания и степени вычислить значение степени по модулю напрямую невозможно из-за вычислительной сложности и ограничений размерности операндов целочисленных операций в большинстве компьютерных систем.

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

Итерационный алгоритм помогает снизить трудоемкость вычислений за счет ограничения размерности чисел, над которыми производятся вычисления)

4. Какая информация необходима для шифрования сообщения по алгоритму RSA?

(Для шифрования необходимо знать открытый ключ получателя, то есть пару чисел (e, N))

5. Какая информация необходима для расшифровки сообщения по алгоритму RSA?

(Для расшифровки сообщения необходимо владеть личным ключом d, соответствующим открытому ключу (e, N), на котором было зашифровано сообщение, и знать параметр N)

6. С помощью какого алгоритма может быть вычислено число, обратное заданному по модулю?

(Для вычисления используется расширенный алгоритм Евклида)

7. Какая дополнительная информация необходима для вычисления личного ключа алгоритма RSA d при известном открытом ключе (е, N)?

(Необходимо знание мастер-ключа, то есть простых множителей p и q числа N)

8. Можно ли на практике вычислить личный ключ RSA d только на основе знания открытого ключа (е, N)?

(В используемых на практике системах шифрования RSA параметры шифра таковы, что вычисление личного ключа на основе знания только открытого ключа невозможно в силу вычислительной сложности)

Лабораторная работа №13. Изучение электронной цифровой подписи Эль-Гамаля

Появление криптографии с открытым ключом позволило решать задачи, которые ранее считались неразрешимыми. К таким задачам относится использование цифрового аналога собственноручной подписи абонента – электронной цифровой подписи (ЭЦП).

Электронная цифровая подпись обеспечивает те же свойства, что и собственноручная подпись автора сообщения, то есть гарантирует выполнение следующих свойств:

· Подлинность подписи можно проверить;

· Подпись нельзя подделать (данную подпись может поставить только ее обладатель и никто другой);

· Подпись является неотъемлемой частью документа и не может быть перенесена в другой документ.

· Подписанный документ не подлежит никаким изменениям.

· Автор подписи не может от нее отказаться.

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

Наиболее распространена технология ЭЦП, основанная на совместном применении алгоритмов хеширования и шифрования с открытым ключом (RSA или Эль-Гамаля).

Для подтверждения авторства, шифрование проводится личным ключом абонента, расшифровку (и, таким образом, проверку подлинности автора) может произвести любой пользователь открытым ключом абонента (рис.59).

Рис.59. Подтверждение авторства с помощью криптографии с открытым ключом

Как правило, шифруется не само сообщение, а его «дайджест» – значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста и используется алгоритм хеширования (хеш-функция), ставящий в соответствие тексту произвольной длины некоторое число фиксированной длины.

Рассмотрим алгоритм подписи Эль-Гамаля, который лежит в основе стандартов ЭЦП.

Сначала выбираются параметры системы Эль-Гамаля, общие для всех абонентов группы: простое число p и число g, 1< g < p -1; для обеспечения стойкости системы числа p и g выбираются специальным образом.

Затем, каждый абонент группы выбирает свой личный ключ – случайное число x, 1 < x < p -1, которое держится в секрете. Затем вычисляется открытый ключ y по формуле: y = g^x mod p. Абонент публикует свой открытый ключ, чтобы каждый мог проверить его подпись.

Алгоритм формирования подписи выглядит следующим образом:

1. Пусть M – подписываемое сообщение. Отправитель вычисляет хеш-значение подписываемого сообщения h = h (M). Значение h должно удовлетворять неравенству 0 < h < p.

2. Далее отправитель выбирает случайное число k, 0 < k < p -1, взаимно простое с p -1, и вычисляет числа:

r = g^k mod p,

u = (h - xr) mod (p -1),

s = k ^-1 u mod (p -1)

k ^-1 – число, обратное k по модулю p -1, k ^-1 существует, так как k и p -1 – взаимно просты.

3. Подпись (r, s) добавляется к сообщению, и тройка (M, r, s) передается получателю.

Проверка подписи:

4. Получатель заново вычисляет хеш-значение присланного сообщения h (M) и проверяет подпись, используя равенство:

y^r r^s = g^h (mod p).

Если подпись верна, то это равенство выполняется.

Отметим, что число k выбирается заново для каждого нового подписания сообщения и должно держаться в секрете.

Используемые на практике алгоритмы хеширования достаточно сложны, поэтому будем использовать учебный алгоритм формирования хеш-значения h (M). Будем считать, что сообщение M представлено в числовом виде, M_i, i =1,…, n – цифры, представляющие сообщение M.

Учебный алгоритм хеширования:

1. Выбирается число h ₀ – вектор инициализации. h ₀ может быть выбрано случайно или получено неслучайным образом, например, как длина сообщения в символах.

2. Для каждого символа сообщения вычисляется значение h_i = (M_i + h_{i -1})² mod (p-1), i =1,…, n.

3. Значение h_n вычисленное для последнего символа, увеличенное на 1, является хеш-значением сообщения: h (M)= h_n +1.

Следует отметить, что вычисленное по этому алгоритму хеш-значение зависит от всех символов сообщения M.