Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
1.2.2 Уверенность в безопасности, основанная на исследовании эталонов
Как убедиться в стойкости криптографического алгоритма? Можно ли утверждать, что алгоритм надежен, так как никто не смог его взломать? К сожалению, нет. В принципе, если алгоритм еще никем не взломан, можно лишь сказать, что пока мы не знаем, как это сделать. В криптографии взломанные алгоритмы
46
Часть I. Введение
иногда играют роль эталона. Если стойкий алгоритм не обладает свойствами уже взломанного алгоритма, мы не можем даже утверждать, что он более надежен.
Несмотря на это, существует несколько исключений. В большинстве случаев взлом криптографического алгоритма или схемы сводится к решению некоторых математических задач, например, к решению определенного уравнения или вычислению обратной функции. Эти математические задачи считаются "трудноразрешимыми". Формальное определение "трудноразрешимой" задачи будет дано в главе 4. Если придерживаться неформальной, однако вполне корректной точки зрения, можно сказать, что математическая задача является трудно разрешимой, если ее невозможно решить ни одним известным методом за разумное время.
Существует великое множество хорошо известных трудноразрешимых задач, которые часто используются в современной криптографии, в частности, в асимметричных методах (см. разделы 8.3-8.14). Например, в криптографии с открытым ключом к неразрешимым задачам относятся задача факторизации целых чисел (integer factorization problem), задача дискретного логарифмирования (discrete logarithm problem), задача Диффи-Хеллмана (Diffie-Hellman problem) и некоторые родственные задачи (мы сформулируем и обсудим их в главе 8). Эти задачи можно рассматривать как эталоны, поскольку они имеют долгую историю и в настоящее время считаются действительно трудноразрешимыми.
В настоящее время стандартный способ доказательства высокой стойкости криптографических алгоритмов заключается в формальном доказательстве того факта, что атака на алгоритм эквивалентна решению одной из хорошо известных трудноразрешимых задач. Доказательство представляет собой эффективное математическое преобразование или последовательность преобразований, сводящих атаку на алгоритм к решению задачи-эталона. Такое эффективное преобразование называется редукцией (reduction). Поскольку мы практически уверены, что трудные задачи решить невозможно (особенно за время, которое отводится на атаку), мы можем прийти к вполне обоснованному выводу, что искомой атаки не существует. Такой способ доказательства называется "сведением к противоречию": поиску простого решения трудной задачи.
Криптографические алгоритмы и протоколы считаются хорошими, если формально доказана их стойкость к особой разновидности мощных атак, называемых адаптивными (adaptive attacks). В дальнейшем мы будем называть практической стойкостью (fit-to-application security) свойство алгоритма, доказанное путем формального сведения мощных атак к решению трудноразрешимых задач.
Одной из основных задач книги является доказательство практической стойкости большого количества криптографических алгоритмов и протоколов.
Глава 1. Защита информации в игре "орел или решка"
47
1.2.3 Практическая эффективность
Говоря, что математическая задача является эффективно разрешимой, мы имеем в виду, что время, необходимое для решения задачи, полиномиально зависит от ее размера. Формальное определение понятия эффективности, позволяющее точно измерить ее величину, будет введено в главе 4.
Не вдаваясь в количественные аспекты эффективности, можно сказать, что задачи разделяются на два класса: разрешимые и трудноразрешимые. Это определение играет фундаментальную роль в современной криптографии, основанной на понятии вычислительной сложности. Очевидно, криптографический алгоритм должен быть разработан так, чтобы с одной стороны он был разрешимым, а с другой — трудноразрешимым для постороннего или атакующего.
Однако следует отметить, что такое определение охватывает чрезвычайно широкое поле количественных измерений. Если время решения задачи по отношению к законному пользователю является полиномиальным, но слишком большим, то понятие "эффективности" теряет практический смысл. Таким образом, хороший криптографический алгоритм должен быть практически эффективным (practically efficient). Точнее говоря, полином, оценивающий стоимость ресурсов для пользователя, должен быть малым (т.е. иметь невысокую степень, как указано в главе 4).
В главе 14 мы обсудим работы, посвященные разработке формально обоснованных стойких криптосистем с открытым ключом. Причиной, побудившей создать эти алгоритмы, стала ненадежность основных алгоритмов шифрования с открытым ключом. (Мы называем такие ненадежные схемы "учебными", поскольку их примитивные версии рассматриваются в большинстве учебников по криптографии; они будут описаны в части III.) Однако в большей части новаторских работ по формально обоснованным стойким криптосистемам с открытым ключом изучался метод побитового шифрования (bit-to-bit encryption method) [125, 210, 241]. Некоторые из них содержали экстраординарные попытки доказательства правильного шифрования каждого отдельного бита [210] и описание способов аутентификации с открытым ключом [241]. Несмотря на то что ранние работы внесли важный вклад в теорию доказательства сильной стойкости, системы, которые в них предлагались, оказались неэффективными для приложений. После главы 14 мы продолжим изучение работ, посвященных формальному доказательству стойкости криптосистем с открытым ключом и схем цифровой подписи. Криптографические схемы, предложенные в этих работах, обладают не только повышенной стойкостью, но и прикладной эффективностью. Это действительно очень хорошие криптографические схемы.
