Основные теоретические положения.

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

Исследование криптоалгоритма шифрования RSA.

Цель работы.

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

Основные теоретические положения.

Криптосистема RSA разработана Рональдом Райвестом, Ади Шамиром и Леонардом Адлеманом в 1972г. Система была названа по первым буквам их фамилий. Несмотря на сообщения последних лет об отдельных попытках успешного криптоанализа этого алгоритма, RSA по-прежнему остается одним из самых распространенных криптоалгоритмов. Поддержка RSA встроена в большинство распространенных браузеров (Firefox, IE), существует плагины RSA для Total Commandera и некоторых других ftp-клиентов. В нашей стране алгоритм не сертифицирован.

RSA относится к классу двухключевых криптосистем. Это означает, что алгоритм использует два ключа – открытый (Public) и секретный (Private).

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

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

Таким образом, криптостойкость RSA определяется используемым модулем.

Для обеспечения достаточной степени криптостойкости, в настоящее время рекомендуется выбирать длину RSA – модуля не менее 1024 бит, причем в связи с быстрым прогрессом компьютерной техники эта величина всё время растет.

Схема алгоритма шифрования данных RSA

1. Выбирают два случайных простых числа (p и q) и вычисляют модуль:

n = pq

2. Вычисляется функция Эйлера: φ(n)=(p-1)(q-1);

3. Случайным образом выбирается секретный ключ е, при этом должно выполняться условие взаимной простоты чисел е и φ(n).

4. Вычисляют ключ дешифрования по формуле:

ed = 1 mod φ(n);

заметим, что d и n также должны быть взаимно простыми числами.

5. Для шифрования необходимо разбить сообщение на блоки одинаковой длинны. Число двоичных разрядов в блоке должно соответствовать числу разрядов модуля n.

6. Шифрование блока сообщения осуществляется по формуле:

C_i=M_i^e mod n

7. Дешифрование каждого блока c_i осуществляется по формуле:

M_i= C_i^d mod n

Выбор d в качестве открытого ключа, а e в качестве секретного совершенно условный. Оба ключа совершенно равноправны. В качестве открытого ключа можно взять е, а в качестве закрытого – d.

Пример шифрования:

1. Выбираем р = 7, q = 13, модуль n = pq = 7·13 = 91;

2. Вычисляем функцию Эйлера φ(n) = (p-1)(q-1) = (7-1)(13-1) = 72;

3. С учетом условий НОД(e, φ(n)) = 1 и 1 < e ≤ φ(n), выбираем секретный ключ e = 5;

4. Исходя из условия ed = 1 mod φ(n), вычисляем парный секретный ключ 5·d = 1 mod 72, используя расширенный алгоритм Евклида, находим открытый ключ d = 29;

5. Берем открытое сообшение m = 225367 и разбиваем его на блоки одинаковой длинны m₁ = 22, m₂ = 53, m₃ = 67.

6. Шифруем: С₁ = 22⁵ mod 91 = 29, C₂ = 53⁵ mod 91 = 79, C₃ = 67⁵ mod 91 = 58;

7. Расшифровываем: M₁ = 29²⁹ mod 91 = 22, M₂ = 79²⁹ mod 91 = 53, M₃ = 58²⁹ mod 91 = 67;

Методика выполнения работы.

Задание на выполнение работы выдается преподавателем после прохождения студентами собеседования по основам криптосистем с открытым ключом.

Содержание отчета

5.1. Цель и назначенные работы.

5.2. Описание алгоритма работы криптосистемы RSA,

5.3. Блок – схема алгоритма работы криптосистемы RSA,

5.4. Выводы: преимущества и недостатки криптосистемы RSA.

Лабораторная работа №2.

Исследование электронной цифровой подписи (ЭЦП) RSA.

Цель работы.

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

Основные теоретические положения.

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

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: