Определения

Данный раздел предназначен для размещения сведений об основных определениях, свойствах и видах протоколов, об уязвимостях и атаках на протоколы, а также необходимых сведений из теории чисел, алгебры, теории сложности и т.д. 


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

Противником (adversary) называется субъект или коалиция субъектов, который является внешним по отношению к участникам криптографического протокола, наблюдающий за передаваемыми сообщениями, и, возможно, вмешивающийся в работу участников, путем перехвата, искажения (модификации), вставки (создания новых), повтора и перенаправления сообщений, блокирования передачи и т.п. с целью нарушения безопасности. Нарушителем (adversary) называется участник криптографического протокола, нарушающий предписанные протоколом действия. Противник может образовывать коалицию с нарушителем. У терминов противник и нарушитель существуют синонимы: внешний нарушитель (outside adversary) и внутренний нарушитель (inside adversary), соответственно. Нарушителя также называют нечестным участником (dishonest party). Честным участником (honest party) называют участника крипографического протокола, владеющего всей необходимой информацией, в том числе, если требуется, секретными ключами, и выполняющий все свои действия в соответствии с протоколом. Противники и нарушители бывают активные и пассивные. Активный противник (active adversary) — это противник, который вмешивается в ход выполнения криптографического протокола. Пассивный противник (passive adversary, eavesdropper) — это противник, который может получать некоторую информацию о выполнении криптографического протокола, но не вмешивается в его работу. Активный нарушитель (active adversary) — это нарушитель, который недопустимым образом влияет на ход выполнения криптографического протокола. Пассивный нарушитель (passive adversary, eavesdropper) — это нарушитель, который ограничивается сбором и анализом информации о ходе выполнения криптографического протокола, но не вмешивается в него. Как правило, полный анализ всех результатов однократного выполнения криптографического протокола позволяет обнаружить присутствие активного противника или активного нарушителя. Полный анализ результатов неоднократного выполнения криптографического протокола не позволяет обнаружить присутствие пассивного противника или пассивного нарушителя.

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

К определению и оценке криптографической стойкости развиваются два основных подхода — теоретическая стойкость и практическая стойкость.

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

Существуют следующие виды вычислительной сложности.

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

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

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

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

 

Коммуникационная сложность является показателем эффективности реализации криптографических протоколов.