 |
Схема асимметричного шифрования
|
|
|
|
Асимметричные криптосистемы (системы открытого шифрования, с открытым ключом - public key systems) – смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования. Одно из них – зашифрование –
является абсолютно открытым для всех. Другое же – расшифрование –
остается секретным за счет секретности ключа расшифрования. Таким образом, любой, кто хочет что-либо зашифровать, пользуется открытым преобразованием. Но расшифровать и прочитать это сможет лишь тот, кто владеет секретным ключом.
Рис. 30. Обобщенная схема асимметричной криптосистемы
В настоящий момент во многих асимметричных криптосистемах вид преобразования определяется ключом. У пользователя есть два ключа – секретный и открытый. Открытый ключ публикуется в общедоступном месте, и каждый, кто захочет послать сообщение этому пользователю – зашифровывает текст открытым ключом. Расшифровать сможет только упомянутый пользователь с секретным ключом. Таким образом, отпадает проблема передачи секретного ключа, как в симметричных системах. Однако, несмотря на все свои преимущества, эти криптосистемы достаточно трудоемки и медлительны. Стойкость асимметричных криптосистем базируется, в основном, на алгоритмической трудности решить за приемлемое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредитирована будет вся система и все сообщения, зашифрованные с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Примеры систем открытого шифрования – RSA, Эль-Гамаля (EL Gamal).
Алгоритм Диффи-Хеллмана
АлгоритмДиффи-Хеллмана (Diffie-Hellman) использует функцию дискретного возведения в степень. Сначала генерируются два больших простых числа n и q. Эти два числа не обязательно хранить в секрете. Далее один из партнеров P1 генерирует случайное число x и посылает другому участнику будущих обменов P2 значение
|
|
|
A = qx mod n
По получении А партнер P2 генерирует случайное число у и посылает участнику обмена P1 вычисленное значение
B = qy mod n
Партнер P1, получив В, вычисляет Kx = Bx mod n, а партнер P2 вычисляет Ky = Ay mod n. Алгоритм гарантирует, что числа Ky и Kx равны и могут быть использованы в качестве секретного ключа для шифрования. Ведь даже перехватив числа А и В, трудно вычислить Kx или Ky. Схематично, работа алгоритма Диффи-Хеллмана представлена на рис. 31.
Рис. 31. Алгоритм Диффи-Хеллмана
Алгоритм Диффи-Хеллмана, обеспечивая конфиденциальность передачи ключа, не может гарантировать того, что он прислан именно тем партнером, который предполагается. Для решения этой проблемы был предложен протокол STS (station-to-station). Этот протокол для идентификации отправителя использует технику электронной подписи. Подпись шифруется общим секретным ключом, после того как он сформирован. Подпись включает в себя идентификаторы как P1, так и P2. (см. также RFC-2786 "Diffie-Hellman USM Key Management Information Base and Textual Convention. M. St. Johns. March 2000").
Алгоритм RSA
Первое практическое воплощение принцип открытого шифрования получил в системе RSA, разработанной в 1977 году в Массачусетском Технологическом Институте (США) и получившей свое название от первых букв фамилий авторов: Рональд Ривест (R.Rivest), Эди Шамир (A.Shamir), Леонард Адлеман (L.Adleman).
Идея авторов состояла в том, что взяв целое число N в виде произведения двух больших простых чисел N=P*Q, легко подобрать пару чисел Y и X, таких, чтобы для любого целого числа M, меньшего N, справедливо соотношение:
(MX)Y =M mod N
В качестве открытого ключа шифрования в системе RSA выступают ключ Y и модуль N, а секретным ключом для расшифрования сообщений является число X.
|
|
|
Процедура шифрования сообщения M, рассматриваемого как целое число (такое допущение возможно вследствие того, что любой контент может быть представлен в числовой форме при обработке в средствах вычислительной техники), меньшее N (при необходимости длинное сообщение разбивается на отрезки, шифруемые независимо), состоит в вычислении значения:
C=MY mod N
Расшифрование осуществляется аналогично с использованием секретного ключа X:
M=CX mod N
Математически строго можно доказать, что определение по паре чисел (N, Y) секретного ключа X, не проще разложения на простые множители числа N, то есть нахождения P и Q. Задача же разложения на множители целого числа изучается в математике с древнейших времен и известна как сложная вычислительная задача. На настоящий момент разложение числа из нескольких сотен десятичных знаков потребует от современных вычислительных машин сотен лет непрерывной работы.
Схематично, работа алгоритма RSA представлена на рис.32.
Рис. 32. Алгоритм RSA
Кроме системы RSA известен целый ряд систем открытого шифрования, основанных на других сложных математических задачах, таких как задача об укладке рюкзака, задачи декодирования линейных кодов и прочих. Однако все они не получили достаточно широкого распространения и являются, в основном, теоретическими разработками.
Алгоритм Эль-Гамаля
Алгоритм Эль-Гамаля (EL Gamal), предложенный в 1985 году, может использоваться для формирования электронной цифровой подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число P и два случайных числа G и X, каждое из которых меньше P. Затем вычисляется:
Y = GX mod P
Общедоступными ключами являются Y, G и P, а секретным ключом является X. Для подписи сообщения M выбирается случайное число K, которое является простым по отношению к (P-1). После этого вычисляется:
a = GK mod P
Далее из уравнения
M = (Xa + Kb) mod (P-1)
находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число K следует хранить в секрете. Для верификации подписи необходимо проверить равенство:
|
|
|
Yaab mod P = GM mod P
Пара a и b представляют собой зашифрованный текст. Следует заметить, что зашифрованный текст имеет размер больше исходного. Для расшифрования производится вычисление:
M = b/aX mod P.
Схематично, работа алгоритма Эль-Гамаляпредставлена на рис. 33.
Рис. 33. Алгоритм Эль-Гамаля
|
|
|
