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

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

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

Криптосистема с открытым ключом определяется тремя алгоритмами:

генерации ключей;

шифрования;

дешифрования.

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

Dk2(Ek1(m))=m. (2.3.1)

Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ k1, но неизвестен соответствующий секретный ключ k2. Противник перехватил криптограмму d и пытается найти сообщение m, где:

d=Ek1(m). (2.3.2)

Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сообщения mi криптограмму di=Ek1(mi) и сравнить di c d. То сообщение, для которого di=d и будет искомым открытым текстом. Если повезёт, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2nT(n), где T(n) - время, требуемое для шифрования сообщения длины n. Если сообщение имеет длину порядка 1000 битов, то такой перебор не осуществим на практике ни на каких самых мощных компьютерах.

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

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

дать формальное определение системе данного типа;

дать формальное определение стойкости системы;

доказать стойкость конкретной конструкции системы данного типа.

Здесь сразу же возникает ряд проблем.

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

Перейти на страницу: 1 2 3

Еще статьи по теме

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

Разработка программно-аппаратной системы адаптивного аналого-цифрового преобразования сигналов звукового диапазона на базе однокристального микроконтроллера
Темой данного дипломного проекта является разработка системы адаптивного аналого-цифрового преобразования (АЦП) на базе однокристального микроконтроллера. Проблема адаптивного аналого-цифрового преобразования в настоящее в ...

Главное меню

© 2018 / www.techsolid.ru