Задание на лабораторную работу

2. Используя алгоритм шифрования данных в криптосистеме RSA, написать программу шифрования и дешифрования произвольного набора символов на любом языке программирования.

Лабораторная работа №5

Алгоритм электронной цифровой подписи RSA

 

Цель работы: изучить алгоритмы электронной цифровой подписи и освоить их практическое применение.

 

Теоретическое введение

Схема электронной цифровой подписи предназначена для обеспечения в электронных сетях защищенного документооборота, аналогично тому, как в сфере традиционного документооборота для защиты бумажных документов используются подписи и печати. Таким образом, технология ЭЦП предполагает наличие группы абонентов, посылающих друг другу подписанные электронные документы. ЭЦП обладает всеми свойствами настоящей подписи. Для того, чтобы стать абонентом системы ЭЦП, каждый пользователь должен создать пару ключей – открытый и закрытый. Открытые ключи абонентов могут быть зарегистрированы в сертифицированном удостоверяющем центре, однако в общем случае это не является обязательным условием взаимодействия абонентов системы ЭЦП.

В настоящее время системы ЭЦП могут строиться на различных алгоритмах двухключевой криптографии. Одним из первых для этих целей стал применяться алгоритм RSA. Помимо криптографического алгоритма, схема ЭЦП требует применения так называемых однонаправленных или хеш – функций. Хеш-функция называется однонаправленной, поскольку позволяет легко вычислять значение хеша от любого документа. При этом обратная математическая операция, то есть вычисление исходного документа по его хеш – значению представляет значительные вычислительные трудности. Из других свойств хеш – функций следует отметить, что выходные значения (хеш) всегда имеют строго определенную длину для каждого вида функций, кроме того, алгоритм вычисления хеш – функции построен таким образом, что каждый бит входного сообщения влияет на все биты хеша. Хеш является как бы сжатым «дайджестом» входного сообщения. Разумеется, учитывая, что существует бесконечное множество всевозможных сообщений, и что хеш имеет фиксированную длину, возможно существование не менее двух различных входных документов, которые дают одинаковые значения хешей. Однако, стандартная длинна хеша задается таким образом, чтобы при существующих вычислительных мощностях компьютеров нахождение коллизий, то есть различных документов, дающих одинаковые значения функций было вычислительно сложной задачей.

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

Существует достаточно большое разнообразие вариантов построения хеш – функций. Обычно они строятся на основе итеративной формулы, например, H_i = h (H_i-1, M_i), где в качестве функции h может быть взята некоторая легко вычисляемая функция шифрования.

На рисунке 1. изображена обобщенная схема ЭЦП на основе криптографического алгоритма RSA.

 

e, n

ЭЦП не достоверна

M

S = me(mod n)

Сообщение М

h(M)

S

m = m´ ?

Рис. 1. Обобщенная схема ЭЦП.

Генератор ключей (e,d), модуль (n)

d, n

h(M)

Абонент - отправитель

Канал

Абонент - получатель

m´= Sd (mod n)

ЭЦП достоверна

нет

да

 

Алгоритм электронной цифровой подписи (ЭЦП) RSA

1.1. Действия абонента – отправителя сообщения.

1.1.1. Выбираются два больших и взаимно-простых числа p и q;

1.1.2. Вычисляем модуль RSA. n=p*q;

1.1.3. Определяем функцию Эйлера: φ(n)=(p-1)(q-1);

1.1.4. Выбираем секретный ключ e с учетом условий: 1<e≤φ(n),

HOD (e, φ(n))=1;

1.1.5. Определяем открытый ключ d, с учетом условий: d<n, e*d ≡ 1(mod φ(n)).

Формирование ЭЦП

 

1.2.1. Вычисляем хеш сообщения М: m = h(M).

1.2.2. Шифруем хеш сообщения на секретном ключе абонента – отправителя и отправляем полученную ЭЦП, S = m^e(mod n), абоненту – получателю вместе с открытым текстом документа М.