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

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

Задание на выполнение лабораторной работы.

1. Изучить теоретическую часть работы и технологию шифрования с открытым ключом

2. Изучить теоретические аспекты электронной подписи

3. Установить и настроить программу PGP на компьютере

4. Сгенерировать открытый и закрытый ключи

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

6. Обменяться текстом, подписанным электронной подписью и исследовать механизмы проверки электронной подписи

Описание основ PGP

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

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

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

Математические основы RSA

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

Алгоритм RSA и генерация ключей

Функция шифровки, используемая в RSA выглядит так C = T^E mod N, где T представляет собой шифруемый текст, C - зашифрованный текст, а E представляет собой открытый ключ. Другими словами, T возводится в степень E по модулю N. Для примера, 2 в степени 3 дает 8, а 2 в степени3 по модулю 7 есть 8 mod 7, что равно 1. Функция дешифрования выглядит так: T = C^D mod N где D представляет собой секретный ключ. Пара ключей E и D должна быть выбрана так, что E является обратным к D по отношению к операции возведения в степень по модулю N. Иными словами, (T^E mod N)^D mod N = T^ED mod N = T.

Для того, чтобы найти подходящую пару, для которой это равенство верно, нам надо знать функцию Эйлера переноса, J(N) для данного значения модуля N. Функция Эйлера представляет собой количество чисел в интервале от 1 до N-1, которые являются простыми относительно N. Для нахождения функции J(N), в свою очередь, найти простые факторы N.

Фундаментальная теорема арифметики: Любое не простое число может быть представлено как произведение уникального набора простых чисел.

Относительно простые числа: Два числа называются относительно простыми, если среди их простых факторов нет одинаковых.

Итак, нам надо найти набор простых факторов числа N для того, чтобы вычислить функцию Эйлера. J(N). Нахождение этих факторов является задачей чрезвычайно сложной - практически абсолютно невозможно для достаточно больших N, и именно этот факт и делает PGP таким надежным методом шифрования. Для заданных N и E вы не можете найти D (и, таким образом, расшифровать сообщение) не зная простых факторов числа N, что настолько трудно, что PGP является виртуально невскрываемой при достаточно больших N.

Практический способ сгенерировать пару ключей - это сначала сгенерировать само N путем умножения двух больших простых чисел P и Q, так что простые факторы N мы уже знаем. Для числа, которое имеет только два простых фактора (как в нашем случае), функция Эйлера равна:

J(N) = (P-1)(Q-1)

Теперь мы выбирает некоторое число E, которое является простым относительно J(N) (зачем нам это условие мы увидим ниже). Нам надо найти D, которое является обратным к E по отношению к операции возведения в степень по модулю N. Это можно сделать, зная J(N).

Имеется правило в модульной арифметике, гласящее, что если операция возведения в степень использует модуль N, то показатели экспонент должны использовать модуль J(N). Например рассмотрим,

(T^E mod N)^D mod N = T^ED mod N

Оказывается, что умножать показатели степени E и D мы должны с использованием mod J(N), а не mod N. Для того, чтобы для заданного показателя шифровки E найти подходящее обратное число D, нам следует удовлетворить равенство:

T^ED mod N = T

Для этого достаточно, чтобы ED mod J(N) = 1, так как T^1 mod N = T. Так что проблема нахождения D сводится к проблеме нахождения числа, обратного E по модулю J(N), что с вычислительной точки зрения тривиально. Следует отметить, что в модульной арифметике есть закон, гласящий, что для заданного модуля M число может иметь обратное относительно операции умножения по модулю M только если оно является относительно простым по отношению к M. Вот почему мы выбирали E как не имеющее общих простых факторов с J(N), так, чтобы у него имелость обратное D по модулю J(N). Тривиальные комбинации E и D (например E = D) отбрасываются как неподходящие с точки зрения секретности, и тогда выбираем новое E.

Когда мы выбрали значение N, и сгенерировали наши ключи E и D, можно забыть о P, Q и J(N) так как они сделали свое дело. Мы имеем подходящие ключи шифровки и дешифровки E и D

C = T^E mod N and T = C^D mod N

(на самом деле совершенно не важно какой из ключей D или E считается ключом шифровки). Не зная чисел P и Q практически невозможно вычислить J(N) и, следовательно, найти D по заданному E при больших значениях N, так что шифрование является надежным.

Итоговый список шагов, необходимых для генерации ключа

• Выбираем пару произвольных больших простых чисел P и Q и находим N путем умножения
• Вычисляем функцию Эйлера числа N, J(N) = (P -1)(Q -1)
• Выбираем число E так, чтобы оно было относительно простым по отношению к J(N)
• Находим D, обратное число к E по отношению к операции умножения по модулю J(N), и тривиальные значения отбраковываем как несекретные (E = D)
• Найдя подходящую пару ключей, ключ E объявляем открытым и его можно использовать для шифровки сообщений, адресованных владельчу пары E и D: C = T^E mod N
• Ключ D держится в секрете и используется для дешифровки полученных сообщений: T = C^D mod N

Надежность RSA

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

Важно отметить, что не было доказано, что безопасность RSA целиком зависит от проблемы нахождения простых факторов большого числа. Однако все другие способы нахождения D по заданному E оказались эквивалентны по затратам задаче факторизации N. Есть вероятность, что будет найден алгоритм для нахождения E -того корня по модулю N более простым путем, чем факторизация N. Тем не менее, до сих пор не был найден такой алгоритм и RSA выдержал огромное число попыток вскрытия.