Лабораторная работа №12. Изучение шифра rsa

В отличие от рассмотренных ранее шифров, шифр RSA является асимметричным (криптосистемой с открытым ключом). Это значит, что используются два ключа: открытый (public key) и личный (private key), причем, если шифрование проводилась одним ключом, расшифровка производится парным к нему ключом. В зависимости от типа решаемых задач для шифрования может использоваться либо открытый, либо личный ключ.

Для решения задачи обеспечения секретности сообщения, оно шифруется открытым ключом (ОК) получателя, тогда расшифровка может быть произведена только его личным ключом (ЛК) – рис.52.

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

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

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

Рис.52. Криптография с открытым ключом:

обеспечение секретности

Перед началом процесса шифрования исходный текст должен быть переведен в числовую форму (с помощью таблицы замен), этот метод считается известным. В результате текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке от 0 до N-1, (о выборе числа N будет рассказано далее). Процесс шифрования одинаков для каждого блока. Поэтому можно считать, что блок исходного текста представлен числом X, 0 ≤ X ≤ N‑1.

Конечно, выбор блоков неоднозначен, но и не совсем произволен. Например, во избежание двусмысленностей, не следует выделять блоки, начинающиеся с нуля.

Разбиение числа на блоки можно произвести различными способами. При этом промежуточные результаты зависят от способа разбиения, однако конечный результат – не зависит.

При расшифровке, наоборот, полученная последователь­ность блоков соединяется вместе и получается большое число. После этого числа заменяют буквами в соответствии с таблицей замен для получения исходного сообщения.

Поскольку должен существовать однозначный алгоритм вычленения кода символа из общей последовательности блоков, использование ASCII-кодировки не подходит (в ASCII на каждый символ приходится разное число десятичных разрядов от 1 до 3). Например, можно кодировать символы нормативного алфавита двузначными числами, старший разряд которых отличен от нуля.

Опишем процесс шифрования. Для каждого абонента вырабатывается своя пара ключей. Для этого генерируются два больших простых числа p и q (мастер-ключ), вычисляется произведение N = p*q. Затем вычисляется значение функции Эйлера (N) от числа N. Поскольку p и q – простые числа, (N) = (p-1)*(q-1).

Затем вырабатывается случайное число e, такое что: e<(N), e – взаимно простое со значением функции (N).

После этого ищется число d из условия e*d = 1(mod φ(N)). Так как e и (N) – взаимно просты, НОД(e,(N))=1, то такое число d существует и оно единственно. Число d можно найти с помощью расширенного алгоритма Евклида.

Пара (N, e) является открытым ключом абонента и помещается в открытый доступ.

Пара (N, d) является личным (секретным) ключом. Для расшифровки достаточно знать секретный ключ.

Числа p, q, (N) в дальнейшем не нужны, поэтому они уничтожаются.

Пользователь A, отправляющий сообщение X абоненту B, выбирает из открытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение Y = X^e (mod N).

Чтобы получить исходный текст, абонент B вычисляет Y^d (mod N) =X.

Пример: Пусть p = 7, q = 17. Тогда N = 7*17 = 119, φ(N) = 6*16 = 96.

Выбираем значение е: e<96, (e,96)=1. Пусть выбрано e = 5.

Находим d: e*d = 1(mod φ(N)), d = e^-1 (mod φ(N)). Получаем d = 77, так как 77*5 = 4*96+1.

Открытый ключ (119,5), личный ключ (119,77). Пусть Х = 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 19⁵ = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, Y = 195 mod 119 = 66, расшифровка: X = 66⁷⁷ mod 119 = 19.

Упрощение вычислений

Как шифрование, так и расшифровка в RSA предполагают использование операции возведения целого числа в целую степень по модулю N. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю N, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами арифметики в классах вычетов a*b mod N = = ((a mod N)*b) mod N = ((a mod N)*(b mod N)) mod N. Таким образом, можно рассмотреть промежуточные результаты по модулю N. Это делает вычисления практически выполнимыми.

Например, для вычисления 88³ mod 23, можно выполнить следующее преобразование:

88³ mod 23 = ((88 mod 23)*88 mod 23)*88 mod 23 =

= ((19*88) mod 23)*88 mod 23= (1672 mod 23)*88 mod 23 = 16*88 mod 23 = 1408 mod 23 = 5.

Существует более эффективный алгоритм вычисления большой степени числа, основанный на возведении в квадрат по модулю N. Степень x при вычислении значения a^x представляется в виде последовательности операций умножения на 2 и сложения с 1. Пусть, например, требуется вычислить a¹⁰⁰ mod N. Представим степень как 100 = 2(2(1+2*2*2(1+2))). Тогда возведение в степень a¹⁰⁰ = (((((a²*a)²)²)²*a)²)²,

a¹⁰⁰ mod N = (((((((a² mod N)*(a mod N))² mod N)² mod N)² mod N)*(a mod N))² mod N)² mod N.

Вычислим 7¹⁰⁰ mod 23, получаем 16:

	72 mod 23	x*7 mod 23	x2 mod 23	x2 mod 23	x2 mod 23	x*7 mod 23	x2 mod 23	x2 mod 23
x	3	21	4	16	3	21	4	16

Таким образом, возведение в степень 100 производится путем 2 умножений и 6 возведений в квадрат по модулю (8 операций умножения).

Количество операций умножения при вычислении a^x методом повторного возведения в квадрат не превосходит 2log x.

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

На вход алгоритма подаются числа φ(N), e, φ(N)>e.

1. Формируются строки: U={u₁,u₂}  {φ(N), 0}; V={v₁,v₂}  {e, 1}.

2. ПОКА v₁0:

3. k  u₁ div v₁

4. T={t₁,t₂}  {u₁ mod v₁, u₂-k*v₂}

5. U  V, V  T

6. РЕЗУЛЬТАТ U={u₁,u₂}={НОД(φ(N),e), d}

Пусть, например, e = 19, φ(N) = 28, требуется найти значение d = e^‑1 (mod φ(N)).

Расширенный алгоритм Евклида:

шаг	1	2	3	результат	строки		k
	U				28	0
	V	U			19	1
1	T	V	U		9	-1	1
2		T	V	U	1	3	2
3			T	V	0	-28	9

В начале в строку U записываются значения {28,0}, а в строку V – {19,1} (это две первые строки в схеме). Вычисляется T (третья строка). После этого в качестве U берется вторая, а в качестве V – третья строка в схеме, и вычисляется новое значение T (четвертая строка). Этот процесс продолжается до тех пор, пока первый элемент строки V не окажется равным 0. Тогда строка U (предпоследняя в схеме) содержит ответ.

В данном примере, НОД(28,19)=1, d=3.

Задание

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

Технология выполнения задания

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

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

Символ	а	б	в	г	д	е	ж	з	и	й	к	л	м	н	о	п
код	11	30	13	14	15	31	17	18	41	20	25	38	23	24	21	26
Символ	р	с	т	y	ф	х	ц	ч	ш	щ	ь	ы	ъ	э	ю	я
код	27	28	29	12	16	32	33	34	35	36	37	22	39	40	19	42

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

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

	N = 3149; e = 13; морж		N = 1763; e = 11; враг
	N = 5767; e = 17; приз		N = 4307; e = 17; курс
	N = 5609; e = 17; гусь		N = 1739; e = 17; друг
	N = 2491; e = 19; окно		N = 1927; e = 19; град
	N = 5063; e = 11; лиса		N = 2257; e = 17; зной
	N = 6319; e = 17; свет		N = 4087; e = 13; перо
	N = 2923; e = 19; гном		N = 3403; e = 11; вред
	N = 4087; e = 13; глаз		N = 3071; e = 11; рука
	N = 4331; e = 11; гриб		N = 4891; e = 17; снег
	N = 8633; e = 13; мышь		N = 4559; e = 17; день
	N = 3713; e = 11; муха		N = 5561; e = 19; ночь
	N = 3953; e = 17; лист		N = 8051; e = 11; чудо
	N = 1961; e = 11; жезл

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

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

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

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

з	и	м	а
18	41	23	11

Объединить коды символов текста в общую последовательность символов: числовое представление открытого текста 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. Варианты задания

	N = 437; e = 115; Y = 416384
	N = 253; e = 139; Y = 54207
	N = 143; e = 23; Y = 3318
	N = 221; e = 91; Y = 162106
	N = 493; e = 69; Y = 40313
	N = 299; e = 61; Y = 35172

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

	N = 209; e = 53; Y = 19074
	N = 319; e = 51; Y = 197270
	N = 299; e = 139; Y = 295271
	N = 209; e = 131; Y = 6028
	N = 377; e = 197; Y = 22215
	N = 391; e = 145; Y = 28177
	N = 143; e = 113; Y = 14059
	N = 667; e = 227; Y = 458575
	N = 187; e = 59; Y = 117147
	N = 377; e = 121; Y = 217189
	N = 221; e = 35; Y = 12632
	N = 391; e = 47; Y = 10349
	N = 323; e = 131; Y = 278136
	N = 319; e = 33; Y = 311142
	N = 341; e = 53; Y = 1018
	N = 143; e = 37; Y = 3779
	N = 299; e = 83; Y = 229181
	N = 247; e = 59; Y = 195147
	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, найти символы, соответствующие полученным числовым кодам:

15	11	27
д	а	р

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

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 параметры шифра таковы, что вычисление личного ключа на основе знания только открытого ключа невозможно в силу вычислительной сложности)