10. Введение в теоретико-числовую и сложностную проблематику

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

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

Учитывая сказанное выше, можно констатировать, что на данный момент теоретико-сложностной подход позволяет доказывать стойкость криптографических схем только с привлечением каких-либо недоказанных предположений. Поэтому возникают следующие две задачи: во-первых, найти наиболее слабые из таких предположений; во-вторых, описать, в предположении наличия всех необходимых объектов, способы построения эффективных и стойких криптографических схем. В процессе исследований было установлено, что необходимым и достаточным условием существования стойких криптографических схем многих типов является предположение о существовании односторонних функций. Односторонние функции рассматриваются в главе 14. Там же обсуждаются псевдослучайные генераторы, используемые для создания стойких шифраторов. Глава 15 посвящена доказательствам с нулевым разглашением -- основному математическому аппарату, применяемому при разработке доказуемо стойких криптографических протоколов различных типов.

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

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

получаемые в результате схемы достаточно эффективны;

длины секретных ключей короче, чем в других предлагаемых схемах;

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

Известен ряд примеров доказуемо стойких схем, основанных на теоретико-числовых задачах. В частности, криптосистема и схема электронной подписи Рабина являются стойкими (против пассивного противника) в предположении трудности задачи факторизации. Стойкость же большинства схем остается не обоснованной. Очевидно лишь одно: если будет найден эффективный алгоритм дискретного логарифмирования или факторизации, то все схемы, основанные на данной задаче, окажутся нестойкими. Поэтому понятно, какую важность приобретают поиски новых методов решения этих задач. Обзор текущего состояния дел в этой области дается в главах 11 и 12. В главе 13 рассматриваются методы проверки простоты целых чисел, необходимые для реализации каждой из криптографических схем, основанных на теоретико-числовых задачах.