Использование систем с открытым распределением ключей для абонентских сетей

Лабораторная работа 6

Исследование криптографической системы RSA

Цель работы: Ознакомиться с классической криптосистемой с открытым ключом RSA и вариантами ее использования.

Теоретическая часть

Идея криптосистемы RSA

Наиболее широко распространенной системой с открытым ключом является криптосистема RSA (Rivest, Shamir, Adleman). Идея системы состоит в том, что очень сложно разложить произведение двух простых чисел на сомножители, т.е. найти эти сомножители. Сама же идея системы RSA исключительно проста.

Пусть p и q – два случайно выбранных простых числа (каждое примерно по 100 десятичных разрядов). Обозначим: n = pq и j(n) = (p-1)(q-1), где j (n) – функция Эйлера от n. Случайно выбирается большое число d >1, такое, что (d, j(n)) = 1, и вычисляется e,

1 < e < j(n), удовлетворяющее сравнению: ed º 1 mod j(n).

Числа n, e и d называются соответственно модулем, экспонентой зашифрования и экспонентой расшифрования.

Числа n и e образуют открытый ключ, а p,q, j(n) и d секретную лазейку. При этом секретная лазейка включает в себя взаимозависимые величины. Так, если известно p (и, конечно, n и e), то остальные числа лазейки вычисляются просто:

q = n/p; j(n) = (p-1)(q-1); d находится из условия: ed º 1 mod j(n).

Зашифрование обеспечивается возведением числового фрагмента текста S в степень e по модулю n. Расшифрование достигается возведением результата предыдущего шага в степень d.

При зашифровании получаем S^e º C mod n. Здесь C – зашифрованный фрагмент текста. При расшифровании

C^d = S^ed = S^1+j(n)k = S^j(n)k S º S mod n. (*)

Справедливость (*) легко видна, так как из сравнения ed º 1 mod j(n) следует, что

ed = 1 + j(n)k, где k – некоторое целое.

Пример. Пусть p = 11, q = 13. Тогда n = 143, j(n) = 120.

Выберем d из условия: ( d, j(n)) = 1, например, d = 37, тогда из сравнения: ed º 1 mod j(n) находим e = 13. Действительно, 13*37 = 481 º 1 mod 120.

Для зашифрования возьмем фрагмент текста, который закодирован, например, числом S = 42. 42¹³ º 3 mod 143, т.е. шифр фрагмента C = 3.

Для расшифрования возведем число 3 в степень 37: 3³⁷ º 42 mod 143. Таким образом, легальный получатель вычисляет значение исходного кода фрагмента.

Использование систем с открытым распределением ключей для абонентских сетей

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

1). Пусть несколько абонентов A, B, C, договорились об обмене информацией. Они могут выбрать некоторое общее простое число p, такое, что p-1 раскладывается на простые сомножители в первой степени. Число вида N = p₁p₂p₃…p_k называется эвклидовым числом. Каждый из участников выбирает два числа меньших и взаимно простых с p-1 так, чтобы:

a₁a₂ º b₁b₂ º c₁c₂ º 1 mod (p-1).

Пусть абонент A хочет передать сообщение S абоненту B. Он кодирует свое сообщение возведением в степень a₁: S^a1 º S₁ mod p и передает его B. Тот в свою очередь кодирует полученное сообщение возведением в степень b₁: S₁^b1 º S₂ mod p и возвращает его A. A возводит его в степень a₂ и передает его B: S₂^a2 º S₃ mod p. B возводит его в степень b₂ и читает сообщение. Справедливость результата следует из сравнения: a₁b₁a₂b₂ º 1 mod (p – 1).

Пример. Пусть абоненты A, B и C выбрали число p = 103. Это число простое, причем 103-1 = 102 – эвклидово число, так как представляется в виде произведения простых чисел в первых степенях: 102 = 2*3*17. Каждый из участников выбирает пару секретных ключей:

A: a₁ = 25, a₂ = 49,

B: b₁ = 19 , b₂ = 43,

C: c₁ = 35, c₂ = 35.

Пусть теперь A посылает к B сообщение S = 67. Он возводит его в степень 25 и находит остаток по модулю 103: 67²⁵ º 86 mod 103. B возводит его в степень b₂ = 19 и отправляет результат к A: 86¹⁹ º 96 mod 103. A возводит полученное сообщение в степень 49 и передает его B: 96⁴⁹ º 21 mod 103. B получив сообщение, возводит его в степень 43 и читает исходный текст: 21⁴³ º 67 mod 103. Таким образом, S = 67.

Открытым ключом в этой системе является модуль p. Недостатком такой системы является большое число передач от одного абонента к другому.

2). Пусть имеется абонентская сеть и требуется обеспечить связь между любой парой пользователей. Если из одного центра заранее передать открытые ключи g и p каждому пользователю, то они могут выработать общий ключ следующим образом. Пусть абонент A сам придумал ключ k₁, а абонент B ключ k₂ (это индивидуальные секретные ключи абонентов). A посылает к B сообщение g^k1 mod p, а B посылает к A сообщение g^k2 mod p. B возводит полученное сообщение в степень k₂, а А в степень k₁. В результате они выработают одинаковый общий ключ: g^k1k2 = g^k2k1 º K mod p, после чего возможен обмен информацией по открытому каналу с использованием любой классической (симметричной) криптосистемы.

Банки и клиенты

Рассмотрим задачу, в которой клиенты банка v₁,v₂,…v_k передают шифрованное распоряжение ответственному работнику банка B (банкиру). При этом кроме конфиденциальности должна обеспечиваться узнаваемость клиента, чтобы по полученному сообщению банкир B сумел идентифицировать автора сообщения и выполнить именно его распоряжение.

Банкир B выбирает некоторое число N = PQ, где P и Q – большие простые числа. Каждый из клиентов v_i (i = 1,2,3,…,k) также выбирают свои значения n_i = p_iq_i, причем желательно, чтобы N > n_i. Затем как банкир, так и клиенты находят значения j (N) – банкир и j (n_i) – все клиенты.

После чего каждый выбирает свой открытый ключ D - ,банкир и d_i – клиенты из условий:

0 < D < j (N) , ( D, j (N) ) = 1 – банкир и

0 < d_i < j (n_i), (d_i, j (n_i))= 1 – клиенты.

Затем банкир и клиенты находят свои секретные ключи T и t_i из сравнений:

DT º 1 mod j (N), 0 < T < j (N) – банкир,

dt º 1 mod j (n_i), 0 < t < j (n_i) – клиенты.

После этих операций открыто публикуется телефонная книга с открытыми ключами:

B: N, D

v_i: n_i, d_i.

Пусть теперь некоторый клиент v_i хочет передать распоряжение m банкиру B. Он шифрует его сначала своим секретным ключом (возводя m в степень t_i по mod n_i, а затем открытым ключом банкира: m₁ º m^ti mod n_i, m₂ º m₁^D mod N. Сообщение m₂ передается по открытому каналу связи. Банкир, получив сообщение m₂ сначала расшифровывает его своим секретным ключом T, а затем открытым ключом d_i клиенты v_i. В результате получает:

m₃ º m₂^T mod N, m₄ º m₃^di mod n_i. При этом m₄ = m, т.е. банкир B расшифровывает переданное ему распоряжение, при этом заодно и идентифицирует (узнает) клиента. Это похоже на проверку подписи клиента и иногда называется “электронная подпись”. Если клиент из открытой телефонной книги узнает, что банкир выбрал число N < n_i, то изменив порядок шифровки получит тот же результат, если банкир также изменит порядок расшифровки.

Пример.Пусть банкир выбрал простые числа P = 23, Q = 11; клиент v: p = 13, q = 7. После чего и банкир и клиент вычисляют сначала функции Эйлера: j(23*11) = 220; j (13*7) = 72, затем выбирают открытые и вычисляют секретные ключи, например: D = 71, T = 31; d = 29, t = 5. Открыто публикуются числа: P*Q = 253, p*q = 91, D = 71, d = 29. Секретным ключом банкира является число T = 31, а секретным ключом клиента t = 5.

Пусть клиент решил дать секретное поручение банкиру в виде числа m = 41. Он шифрует его своим секретным ключом t, а затем открытым ключом банкира D:

41⁵ º 6 mod 91, 6⁷¹ º 94 mod 253. Это сообщение (число 94) по открытому каналу передается банкиру. Банкир расшифровывает сообщение сначала своим секретным ключом T, а затем открытым ключом клиента d: 94 ³¹ º 6 mod 253, 6²⁹ º 41 mod 77. Банкир принимает указание клиента в виде числа 41.

Практическое задание

1. Запустите программу RSA. Введите номер Вашего задания (число от 1 до 30). Выберите первый режим: “Общий ключ для двух пользователей”. Выберите некоторое простое число p и число g – примитивный корень по модулю p. Примитивным корнем g по модулю p называется число, все степени которого g₁,g₂,…g_n-1 различны. Придумайте некоторые произвольные числа k₁ и k₂ (ключи). На ЭВМ будет выведен протокол, обеспечивающий выработку общего ключа K. Вручную проверьте правильность вычислений.

2. Выберите следующий режим ”Передача шифрованных сообщений”. Возьмите два простых числа p и q, найдите их произведение n= pq и функцию Эйлера j(n). Выберите d из условия (d, j(n)) = 1 и введите в ЭВМ все данные. Посмотрите, какой закрытый ключ будет вычислен ЭВМ. Выберите некоторый символ, ЭВМ переведет его в код ASCII и выведет на экран. Нажмите указание “Зашифровать” и запишите полученное сообщение. Это сообщение будет отправлено к Вашему абоненту. Затем нажмите команду “Расшифровать” и убедитесь, что расшифрование выполнено правильно. При ошибках (Ваших) в выборе простых чисел и вычислении j(n) и d зашифрование будет невозможным. В этом случае проанализируйте свои ошибки.

3. Выберите режим “Сообщение от клиентов банку”. Представив себя банкиром B, выберите простые числа P и Q; затем представив себя клиентами v_i , выберите несколько пар простых чисел p_i и q_i , вычислите и за банкира и за клиентов значения функций Эйлера и все открытые ключи. Введите все данные в ЭВМ. Выберите некоторый символ, введите номер клиента и выбранный символ. ЭВМ переведет символ в код ASCII и выведет на экран. Зашифруйте его и передайте банку. В ответ получите протокол с этапами зашифрования и расшифрования. Проанализируйте этот протокол и запишите, какие действия выполняются им. Если результат положительный, то Вам будет предложено использовать сформированные Вами данные для посимвольной передачи неизвестного Вам сообщения от выбранного Вами клиента банку. Запишите полученное после расшифровки сообщение.

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

1. Опишите алгоритм RSA.

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

3. Опишите алгоритм использования систем с открытым распределением ключей для систем банков и клиентов.

Использованные источники

1. Ерош И.Л., Дискретная математика. Математические вопросы криптографии. Учебное пособие. СПбГУАП. 2001г.

2. Ерош И.Л. Дискретная математика. Теория чисел. Учебное пособие. СПбГУАП.2001г.