Материал: Залания2017
Тема: “Нахождение чисел, относящихся к заданному показателю ”.
Теоретическая часть. Для любого числа a, взаимно простого с модулем m, существуют числа , такие что a = 1 mod p. Минимальное из чисел , т.е. число = min{}, называется показателем числа a. Если a по модулю m принадлежит показателю , то числа a0, a1, …, a – 1 по модулю m несравнимы. Показателями могут быть только делители числа p 1. Если модуль является простым числом p, то число чисел (), относящихся к показателю , равно функции Эйлера от числа , т.е. () = (). Если длина числа существенно меньше длины простого модуля, то нахождение чисел, относящихся к показателю , путем случайного выбора чисел a и проверки соотношения a = 1 mod p является вычислительно неэффективным. В реальных системах ЭЦП с сокращенной длиной подписи простой модуль p 1 имеет размер 1024 или 2048 бит, а размер показателя составляет около 160 бит. Для нахождения числа , относящегося к показателю , используется следующий вычислительно эффективный способ.
Выбирается число a, превосходящее 1 и меньшее числа p.
Вычисляется значение = (p 1)/ и число g = a mod p.
Если g 1, то в качестве числа взять число g. В противном случае повторить шаги 1 – 3.
Действительно для полученного числа 1 имеем = a(p 1)/ mod p. Следовательно, согласно теореме Ферма, имеем = a(p 1) = 1 mod p, т. е. число относится к показателю .
Экспериментальная часть. Задаются несколько простых чисел p. Для каждого из них требуется найти разложение числа p 1, выбрать несколько значений в качестве показателей и для каждого из показателей найти несколько чисел, относящихся к нему, по модулю p. Другим вариантом является следующее задание. Требуется сформировать большое простое число p, для которого можно найти разложение p 1. Для модуля p находятся несколько чисел, относящихся к показателям, в качестве которых берутся делители p 1.
Тема: “Цифровая подпись Эль-Гамаля с сокращенной длиной параметра s”.
Теоретическая часть. Уравнение проверки подписи
M = yArrs (mod p)
может выполняться также в случае, когда в качестве берется число, относящееся к показателю q, где qp 1. Для этого s должно быть вычислено из следующего соотношения
M = xAr + ks (mod q).
Можно выбрать простой модуль p таким, чтобы разложение p 1 содержало простой множитель q, размер которого существенно меньше размера p. Например, для 2048-битового модуля p длина q может составлять160 бит. В этом случае вычисляемое значение s будет иметь размер, не превышающий 160 бит. Благодаря этому достигается сокращение длины подписи почти в 2 раза (длина параметра r остается равной размеру модуля).
Экспериментальная часть. Используя заданные значения простого числа p, найти разложение числа p 1. Выбрать в качестве показателя q один из делителей p 1. Найти первообразный корень и число g, относящееся к показателю q. Сформировать секретный ключ xA, вычислить соответствующий ему открытый ключ yA = xA (mod p). Вычислить значение электронной подписи для 5 различных сообщений, фиксируя получаемые значения параметров k, r = k, s, M, yAr, rs, yArrs(mod p). Вычислить значение сокращенной электронной подписи для тех же сообщений, используя новое значение открытого ключа yA = gxA (mod p) и фиксируя получаемые значения параметров k, r = gk, s, gM, yAr, rs, yArrs(mod p). Осуществить проверку подписи по открытому ключу. Результаты оформить в виде таблицы.
Тема: “Цифровая подпись Эль-Гамаля с сокращенной длиной параметров s и r”.
Теоретическая часть. Уравнение проверки подписи
M = yArrs (mod p)
может быть преобразовано к следующему виду
r = M/syA–r/s (mod p).
При этом вместо r в степени при yA можно использовать значение некоторой хэш-функции от значения r, т. е. H(r). В этом случае уравнение проверки подписи имеет вид r = M/syA–H(r)/s (mod p). Чтобы проверка была корректной, владелец секретного ключа должен вычислить параметр s из следующего уравнения
M = xAH(r) + ks (mod q).
Поскольку при проверке подписи не требуется выполнять никаких вычислений с использованием параметра r, то проверка подписи может быть осуществлена в соответствии с уравнением
H(r) = H(M/syA–H(r)/s mod p).
В этом случае нет необходимости представлять проверяющему значение r, имеющее сравнительно большую длину. Достаточно для проверки представить значение H(r), где размер значения хэш-функции равен, например, 160 бит. Этим достигается существенное сокращение длины подписи. Если используется вариант с сокращенной длиной параметра s, то общая длина подписи составляет порядка 320 бит вместо исходной длины 2048 или 4096 бит при 1024-битовом или 2048-битовом модуле p, соответственно. Сокращение длины подписи не уменьшает стойкости системы ЭЦП, поскольку сложность задачи дискретного логарифмирования не изменяется, так как вычисления ведутся по модулю одинакового размера.
В качестве хэш-функции H(r) можно взять следующую: H(r) = r mod q, где q показатель, используемый при сокращении параметра s. Тогда приходим к следующему уравнению проверки подписи:
r = (M/syA–r/s mod p) mod q,
где (r, s) есть подпись к сообщению M, а параметр r вычисляется после выбора случайного числа k в соответствии с формулой r = (k mod p) mod q. Уравнение для вычисления параметра s имеет вид:
M = xAr + ks (mod p – 1).
Экспериментальная часть. Используя заданные значения простого числа p, найти разложение числа p 1. Выбрать в качестве показателя q один из делителей p 1. Найти первообразный корень и число g, относящееся к показателю q. Сформировать секретный ключ xA, вычислить соответствующий ему открытый ключ yA = xA (mod p). Вычислить значение электронной подписи для 5 различных сообщений, фиксируя получаемые значения следующих значений
k, r = (k mod p) mod q, s, M/s mod p, yAr/s mod p, M/syA–r/s mod p.
Осуществить проверку подписи по открытому ключу. Результаты оформить в виде таблицы. Выполнить аналогичные вычисления в варианте с сокращенным размером параметра s, используя в качестве основания число g.
Тема: “Электронная цифровая подпись rsa”.
Теоретическая часть. Теорема Эйлера: для любых взаимно простых целых чисел M и n, где M<n, выполняется соотношение
M (n) = 1 (mod n).
В криптосистеме RSA в качестве числа M используется сообщение, которое необходимо подписать или зашифровать. Будем полагать, что условие взаимной простоты чисел M и n выполняется. Например, это обеспечивается тем, что в данной криптосистеме выбирается число n, равное произведению двух больших простых множителей, поэтому вероятность того, что случайное сообщение не будет взаимно простым с модулем, является пренебрежимо малым.
Формирование ключей. Каждый пользователь выбирает два больших не равных между собой простых числа p и q, находит их произведение n = pq и вычисляет значение функции Эйлера от n:
(n) = (p 1)(q 1).
Значение n является частью открытого ключа. Числа p и q являются частью закрытого ключа. Числа p и q должны иметь специальную структуру, в частности, по крайней мере одно из чисел (p 1) или (q 1) должно иметь один большой простой множитель. Размер модуля n должен быть не менее 1024 бит. Затем выбирается целое число d такое, что d < (n) и НОД(d, (n)) = 1 и вычисляется e, удовлетворяющее условию
ed = 1 (mod (n)).
Секретным ключом является тройка чисел p, q, d. Открытым ключом является пара чисел n, e, которая сообщается всем пользователям.
Процедура подписывания:
S = M d (mod n).
Процедура проверки подписи:
M = S e (mod n).
Если M = M, то сообщение M признается подписанным.
Экспериментальная часть. Используя заданные значения простых чисел p и q, вычислить модуль n, затем сформировать открытый и закрытый ключи e и d. Используя закрытый ключ, подписать 10 различных сообщений и осуществить проверку подписи по открытому ключу. Результаты оформить в виде таблицы.
Тема: “Слепая” подпись Чаума”.
Теоретическая часть. Слепая подпись Чаума основана на криптосистеме RSA. Пусть пользователь A желает подписать некоторое сообщение M у пользователя B таким образом, чтобы последний не мог прочесть подписываемое сообщение. Для этого необходимо осуществить следующие шаги:
Пользователь A генерирует случайное простое число k – такое, что НОД(k, n) = 1, где n – часть открытого ключа пользователя B. Затем А вычисляет значение M = k eM (mod n) и предъявляет его пользователю B, чтобы последний подписал M в соответствии со стандартной процедурой подписывания в системе RSA. Подписывающий не может прочесть сообщение M, поскольку оно преобразовано путем наложения на него “разового” ключа k e с использованием операции модульного умножения.
Пользователь B подписывает сообщение M: S = (k eM) d = kM d (mod n). Заметим, что по значению подписи S к сообщению M подписывающий не имеет возможности вычислить M d. Заметим также, что по значению M d легко вычислить M: (M d) e = M (mod n). Это означает, что после получения значения S = M d (mod n), пользователь A должен держать его в секрете от подписавшего.
После получения от пользователя В значения S, используя расширенный алгоритм Евклида, пользователь А вычисляет для числа k мультипликативно обратный элемент (k–1) в поле вычетов по модулю n и формирует подпись пользователя В к сообщению M: S = k 1S = k 1kM d = M d (mod n).
Экспериментальная часть. Используя заданные значения простых чисел p и q, вычислить модуль n, затем сформировать открытый и закрытый ключи e и d. Осуществить процедуру выработки подписи «вслепую» в соответствии с протоколом Чаума для 6 различных сообщений, фиксируя для каждого из них значения k, k 1 (mod n), M, M, S и S. Осуществить проверку правильности полученной подписи путем непосредственного вычисления значения S = M d (mod n). Результаты оформить в виде таблицы.
Тема: “ Схема подписи Онга-Шнора-Шамира ”.
Теоретическая часть.
Данная схема основана на использовании составного модуля n, что обеспечивает сложность извлечения квадратных корней по модулю n. Открытый ключ состоит из двух частей: RSA-модуля n и числа h, которое генерируется следующим образом. Генерируется секретный ключ в виде случайного числа k взаимно простого с модулем n. Затем по секретному ключу вычисляется h:
.
Для вычисления подписи (S1, S2) к сообщению M выбирается случайное число r, такое, что r и n являются взаимно простыми. Затем используются соотношения:
;
.
Уравнение проверки подписи имеет вид
.