10. (24,10,25)

Если соберутся вместе любые три или больше сотрудников, то ключ S легко восстанавливается сложением соответствующих элементов всех десяти фрагментов по модулю 29. Если соберется вместе менее трех сотрудников, то на подбор ключа S им потребуется столько же усилий, сколько требуется любому одному сотруднику.

В общем случае при заданных n и h число фрагментов ключей равно

Криптостойкость ключа не зависит от числа сотрудников, если их меньше h и ключ легко собирается, если число сотрудников равно или больше h.

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

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

1. Arto Salomaa Public-Key Criptography. Springer-Verlag. 1990. Berlin Heidelberg New York London Paris Tokyo Hong Kong Barselona.(Перевод на русский).

2. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. М. Высшая школа. 1999, 110 стр.

3. Шеннон К. Работы по теории информации и кибернетике, М, ИЛ, 1963.

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

Порядок выполнения лабораторной работы

1. Прочитайте теоретическую часть и запустите программу на компьютере.

2. Для схемы разделение секрета среди n участников при пороге также равном n. Введите число участников - n, сам разделяемый секрет из 3-х произвольных чисел и модуль P – некоторое простое число. Автоматически для n-1 участника получите произвольные фрагменты секрета, а для n-го участника - вычисленные по методике, описанной в теоретической части. Нажмите кнопку «Собрать», сравните результат, который выдаст компьютер, с исходным ключом и в случае неверного ответа найти свою ошибку. Повторите операцию для других фрагментов ключа.

3. Разделение секрета среди n участников при произвольном пороге k, основанное на китайской «Теореме об остатках». Введите число участников, необходимых для сборки ключа – k (общее число участников – n = 5). Для каждого участника выберите и введите числа m_i (i= 1,…,5), автоматически получите ограничения на значения ключа. В соответствии с ними выберите и введите ключ. Для каждого участника автоматически получите число а_i, вычисленное по методике, описанной в теоретической части. Выберите k произвольных участников (укажите их номера «галочкой») и убедитесь в том, что секретный ключ будет собран правильно. Повторите последнее действие при всех возможных сочетаниях участников по k из n.Выберите число участников больше k, укажите их номера и убедитесь в том, что ключ собран правильно. Выберите число участников меньше k и укажите их номера. Проанализируйте составленный в этом случае ключ. Изменяя значения чисел m_i, получите ограничения ключа. Проанализируйте защищенность.

4. Разделение секрета среди n участников при пороге k, основанное на свойствах равновесных кодов. Выберите и введите число участников n и порог k. Выберите секретный ключ и получите его компоненты по методике, изложенной выше. Для каждого участника сформируйте и введите распределение фрагментов ключа. Выберите номера участников, собирающих ключ, укажите их номера и убедитесь в том, что ключ собран правильно. Повторите последнее действие при всех возможных сочетаниях участников по k из n.Убедиться в том, что если число участников больше или равно k, то ключ собирается правильно, а если меньше, то ключ вообще не может быть собран.

5. Оформите отчет. Отчет должен содержать:

a) Титульный лист с указанием университета, кафедры, дисциплины, названия лабораторной работы, № группы, фамилии студента и преподавателя.

b) Все решения, выполненные вручную.

с) Комментарии при проверке решений на компьютере.

Лабораторная работа №4 Исследование криптографической системы rsa

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

Теоретические пояснения

1. Идея криптосистемы rsa

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

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

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

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

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

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

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

При зашифровании получаем S^e  C mod n. Здесь C – зашифрованный фрагмент текста. При расшифровании C^d = S^ed = S^1+(n)k = S^(n)k S  S mod n. (6)

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

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

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

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

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

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

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

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

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

3.Криптографические протоколы

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

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

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

Рассмотрим задачу, в которой клиенты банка 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. Затем как банкир, так и клиенты находят значения  (N) – банкир и  (n_i) – все клиенты.

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

0  D   (N) , ( D,  (N) ) = 1 – банкир и

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

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

DT  1 mod  (N), 0  T   (N) – банкир,

dt  1 mod  (n_i), 0  t   (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. После чего и банкир и клиент вычисляют сначала функции Эйлера: (23*11) = 220;  (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.