Асимметричные криптосистемы

2.2.2. Асимметричные криптосистемы

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

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

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

Криптосистема с открытым ключом определяется тремя алгоритмами: генерации ключей, шифрования и расшифрования. Алгоритм генерации ключей открыт, всякий может подать ему на вход случайную строку r надлежащей длины и получить пару ключей (k₁, k₂). Один из ключей (например, k₁) публикуется, он называется открытым, а второй, называемый секретным, хранится в тайне. Алгоритмы шифрования и расшифрования таковы, что для любого открытого текста m .

Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ k₁, но неизвестен соответствующий се­кретный ключ k₂. Противник перехватил криптограмму d и пытается найти сообщение m, где . Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сооб­щения m_i криптограмму и сравнить d_i с d. То сообщение, для которого d_i = d и будет искомым открытым текстом. Если пове­зет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2ⁿT(n), где T(n) – время, требуемое для шифрования сообщения длины п. Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах.

Мы рассмотрели лишь один из возможных способов атаки на кри­птосистему и простейший алгоритм поиска открытого текста, назы­ваемый обычно алгоритмом полного перебора. Используется также и другое название: «метод грубой силы». Другой простейший алгоритм поиска открытого текста – угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изощренные алгоритмы поиска откры­того текста.

Система Эль-Гамаля – это криптосистема с открытым ключом, основанная на проблеме логарифма. Система включает как алгоритм шифрования, так и алгоритм цифровой подписи.

Множество параметров системы включает простое число p и целое число g, степени которого по модулю p порождают большое число элементов Z_p. У пользователя A есть секретный ключ a и открытый ключ y, где y = g^a (mod p). Предположим, что пользователь B желает послать сообщение m пользователю A. Сначала B выбирает случайное число k, меньшее p. Затем он вычисляет

y₁ = g^k (mod p) и y₂ = m Е (y^k (mod p)),

где Е обозначает побитовое "исключающее ИЛИ". B посылает A пару (y₁, y₂).

После получения шифрованного текста пользователь A вычисляет

m = (y₁^a mod p) Е y₂.

Известен вариант этой схемы, когда операция Е заменяется на умножение по модулю p. Это удобнее в том смысле, что в первом случае текст (или значение хэш-функции) необходимо разбивать на блоки той же длины, что и число y^k (mod p). Во втором случае этого не требуется и можно обрабатывать блоки текста заранее заданной фиксированной длины (меньшей, чем длина числа p).

Система Ривеста-Шамира-Эйделмана (Rivest, Shamir, Adlеman – RSA) представляет собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Кратко алгоритм можно описать следующим образом:

Пользователь A выбирает пару различных простых чисел p_A и q_A , вычисляет n_A = p_Aq_A и выбирает число d_A, такое что НОД(d_A, j(n_A)) = 1, где j(n) – функция Эйлера (количество чисел, меньших n и взаимно простых с n. Если n = pq, где p и q – простые числа, то j(n) = (p  1)(q  1)). Затем он вычисляет величину e_A, такую, что d_AЧe_A = 1 (mod j(n_A)), и размещает в общедоступной справочной таблице пару (e_A, n_A), являющуюся открытым ключом пользователя A.

Теперь пользователь B, желая передать сообщение пользователю A, представляет исходный текст

x = (x₀, x₁, ..., x_n–1), x О Z_n , 0 Ј i < n,

по основанию n_A:

N = c₀+c₁ n_A+....

Пользователь В зашифровывает текст при передаче его пользователю А, применяя к коэффициентам с_i отображение :

,

получая зашифрованное сообщение N'. В силу выбора чисел d_A и e_A, отображение является взаимно однозначным, и обратным к нему будет отображение

Пользователь А производит расшифрование полученного сообщения N', применяя .

Для того чтобы найти отображение , обратное по отношению к , требуется знание множителей n_A = p_Aq_A. Время выполнения наилучших из известных алгоритмов разложения при n > 10¹⁴⁵ на сегодняшний день выходит за пределы современных технологических возможностей.

Рассмотренная выше криптосистема Эль-Гамаля основана на том, что проблема логарифмирования в конечном простом поле является сложной с вычислительной точки зрения. Однако, конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 1985 году Коблиц и Миллер независимо друг от друга предложили использовать для построения криптосистем алгебраические структуры, определенные на множестве точек на эллиптических кривых.

Похожие работы

Защита информации

Скачать

40302

0

0

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

Автоматизация системы бюджетирования финансовой службы

Скачать

568458

20

78

... для реализации системы бюджетирования Консультационной группы "Воронов и Максимов". Статья о проблемах выбора системы бюджетирования - в проекте "УПРАВЛЕНИЕ 3000". Бюджетный автомат Если вы решитесь на автоматизацию системы бюджетирования компании, перед вами сразу встанут вопросы: что выбрать, сколько платить, как внедрять. Примеряйте! О ЧЕМ РЕЧЬ В “Капитале” на стр. 44, 45 мы рассказали ...

Тенденции развития системы высшего образования в Украине и за рубежом: основные направления

Скачать

26363

0

0

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

Особенности профильного обучения в старших классах

Скачать

61070

3

3

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