Описание основ PGP
PGP представляет собой гибридную систему, которая включает в себя алгоритм с открытым ключом (асимметричный алгоритм) и обычный алгортм с секретным ключом (симметричный алгоритм), что дает высокую скорость, характерную для симметричных алгоритмов и существенные удобства, характерные для криптографии с открытым ключом. С точки зрения пользователя PGP ведет себя как система с открытым ключом. В криптосистемах с открытым ключом генерируется с помощью специального математическог алгоритма пара ключей - один открытый и один секретный. Сообщение шифруется с помощью одного ключа, и дешифруется с помощью другого (причем неважно каким именно из двух ключей производится шифрование). Сообщение нельзя расшифровать с помощью ключа шифрования. Обычно вы опубликовываете свой открытый ключ, делая его доступным любому, кто захочет послать вам зашифрованное сообщение. Такой человек зашифрует сообщение вашим открытым ключом, при этом ни он сам, ни кто другой не могут расшифровать шифрованное сообщение. Только вы можете расшифровать сообщение, то есть тот человек, который имеет секретный ключ, соответствующий открытому ключу. Очевидно, что секретный ключ должен храниться в секрете своим обладателем.Огромным преимуществом такого способа шифровки является то, что в отличие от обычных методов шифрования, нет необходимости искать безопасный способ передачи ключа адресату. Другой полезной чертой таких криптосистем является возможность создать цифровую "подпись" сообщения, зашифровав его своим секретным ключом. Теперь, с помощью вашего открытого ключа любой сможет расшифровать сообщение и таким образом убедиться, что его зашифровал действительно владелец секретного ключа.
PGP использует для шщифрования алгоритм с открытым ключом RSA в паре с обычным методом шифрования IDEA. В методе IDEA для шифрования используется один ключ, и как и в других симметричных криптосистемах, тот же ключ дешифровывает сообщение. PGP использует алгоритм RSA для зашифровки ключа IDEA с помощью открытого ключа адресата. Адресат приняв сообщение с помощью PGP расшифрует этот секретный ключ IDEA. Далее остальная часть сообщения расшифровывается принимающей стороной методом IDEA.
Шифрованный методом Ключ K шифруется \
IDEA с ключом K методом RSA |
текст с пом. открытого |
| ключа E Алисы |
| |
| | \ Эту копию PGP использует Боб
| | / он знает открытый ключ Алисы
V V |
Сообщение состоит |
из RSA-шифрованного |
ключа K и текста, |
зашифрованного по IDEA /
||
||
\/
Сообщение по e-mail
отправляется к Алисе
||
||
\/
\
Ключ IDEA расшифровывается |
секретным ключом RSA Алисы |
|
|| \ Алиса использует свою копию
|| / PGP и знает свой секретный ключ.
\/ |
|
Текст расшифровывается |
с пом. ключа IDEA /
Математические основы RSA
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.Для того, чтобы найти подходящую пару, для которой это равенство верно, нам надо знать функцию Эйлера переноса? (Euler's totient function), 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 выдеожал огромное число попыток вскрытия.
Sherry Mayo / ANU / scmayo@rschp2.anu.edu.au
Главная страница | Вводные статьи | Введение в криптографию