О современной криптографии

В. М. Сидельников, д. ф.-м. н., профессор, академик Академии криптографии РФ,

зав. лабораторией МГУ по математическим проблемам криптографии

Опубликовано на сайте

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

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

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

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

Мы далее рассматриваем только математические преобразования информации, представленной в дискретном виде, т. е. в виде последовательности w элементов конечного алфавита A.

Известны два вида шифрования -- традиционное (оно же симметрическое) и "открытое шифрование" (асимметрическое). При традиционном шифровании законный пользователь X с помощью некоторого конечного автомата AK

(шифратора) преобразует последовательность

w=(w1,...wn), называемую открытой информацией, в шифрованную информацию . Шифратор AK (ключа), известного пользователю  X. Законные пользователи, которым предназначена информации w, осуществляют расшифрование информации также с помощью некоторого конечного автомата, зависящего от параметра K`, связанного с K. Обычно K`=K. В рассматриваемом случае каждый законный пользователь изначально обладает как преобразованием , так и преобразованием

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



В традиционном варианте шифрования законные пользователи X

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

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

Второй вид шифрования (возникший в 70-х годах XX столетия), для которого нет необходимости в дополнительном секретном канале распределения ключей, носит название "открытого шифрования". При открытом шифровании каждый абонент X сети связи строит (или доверяет кому-либо построить) "одностороннюю" функцию , которая, так же как и в первом случае, определяется некоторым секретным параметром K, известным только абоненту X. Функция строится таким образом, чтобы ее значения

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



при известном секретном параметре K также вычислялась достаточно "просто", т. е. абонент X

вычисляет "легко". Вместе с тем задача вычисления значения обратного преобразования без знания секретного параметра должна быть достаточно сложной. Вопрос о существовании такой функции FX со строго доказанными свойствами является очень непростым. К настоящему времени его решение является открытым. Имеются только "кандидаты" на роль таких функций. Некоторые из них приведены ниже.

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

Абонент Y, желающий передать открытую информацию w

абоненту X, вычисляет шифрованную информацию

и посылает ее по общедоступному каналу абоненту X, который с помощью известного только ему алгоритма вычисляет исходную информацию . Все остальные потребители при "правильно построенной" односторонней функции не могут получить w из-за того, что им для вычисления

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

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

Открытое шифрование принципиально отличается от традиционного тем, что для него не нужен абсолютно надежный канал для рассылки секретных ключей. Это свойство в некоторых случаях дает открытому шифрованию значительные практические преимущества перед традиционным. Вместе с тем необходимо отметить, что, во-первых, сложность вычисления значений "односторонней функции" и ее обратной, т. е. сложность зашифрования и расшифрования, обычно значительно выше, чем сложность этих процедур при традиционных симметрических автоматных методах шифрования, и, во-вторых, в настоящее время неизвестны практически реализуемые односторонние функции, для которых абсолютно убедительно доказана невозможность их обращения квалифицированным незаконным пользователем. Более того, в абстрактной теории сложности пока не доказано существование односторонних функций. Стойкость открытого шифрования для всех подвергнувшихся серьезному анализу односторонних функций всегда существенно ниже, чем мощность пространства параметров K, определяющих FX, и имеет тенденцию к постоянному снижению.



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

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

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

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

в тех или иных условиях. Обычно усилия направляются на вычисление ключа K. Вместе с тем в некоторых случаях можно определить w без определения ключа (бесключевое чтение). Далее под взламыванием будем понимать только задачу определения ключа.

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



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

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

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

обычно двоичную. В качестве шифрованной информации выступает последовательность ,

. Обычно в качестве функции наложения используется функция сложения в каком либо конечном поле или кольце, в частности, в двоичном случае , т. е.

. В последнем случае обратное преобразование (дешифрование) осуществляется точно так же:

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

Блочный шифратор представляет собой автомат, входами и выходами которого являются последовательности w и длины n. Входная последовательность разбивается на блоки длины n и каждый блок шифруется независимо один от другого на одном ключе K. Блочный шифратор реализует перестановку элементов пространства An, где A -- используемый алфавит. Самым известными блочными шифраторами являются американский шифратор DES (data encryption standard) и отечественный стандарт ГОСТ 28147-89  , у которых длина блока n

равна 64 и 256 соответственно. Имеются и другие типы шифраторов, существенно отличные от рассмотренных.

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



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

Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и оценки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Procedings of Eurocrypt, Journal of Cryptology.

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

Все оценки стойкости реальных криптосистем получены только относительно известных методов анализа. Особенное удивление и недоверие вызывают часто встречающиеся утверждения типа: шифратор имеет 10100 ключей, поэтому он не может быть "расколот" в разумное время.

За последние годы получил значительное развитие раздел теоретической криптографии, занимающийся изучением вопросов существования тех или иных криптографических объектов с доказуемыми (при некоторых дополнительных предположениях) оценками стойкости. В круг интересов этого раздела криптографии входят вопросы построения и обоснования свойств таких криптографических понятий как "односторонняя функция", псевдослучайный генератор, криптографический протокол (cryptographic protocol), в частности, протокол доказательства с нулевым разглашением (zero-knowledge proof protocol) и т. п. Эти понятия изучаются с точки зрения абстрактных позиций сложности вычислений.



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

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

Пусть необходимо передать элемент из конечного множества A. В качестве часто выступает значение хэш-функции. Будем предполагать, что на обоих концах канала связи имеется секретный элемент b (ключ) из множества B. Пусть функция инъективна при каждом фиксированном y и обладает тем свойством, что для каждых и c множество решений уравнения

имеет достаточно много элементов.

В рассматриваемой системе имитозащиты по общедоступному каналу связи вместо элемента из A передается элемент

. Законный пользователь знает ключ b, поэтому он, получив элемент c, решает уравнение и определяет элемент .

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

Рассмотренная выше идея может быть реализована, например, с помощью множеств , , и аффинной функции



вида , где Fq -- конечное поле с q

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

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

Наиболее известной на настоящий момент, используемой на практике и достаточно стойкой (2001 г.) является система RSA (сокращение от фамилий авторов - Rivest, Shamir, Adleman). В этой системе законный пользователь X для построения однонаправленной функции F=FX выбирает число n=nX, являющееся произведением двух достаточно больших простых чисел p и q, и целое число z=zX такое, что

, где (r,m) -- наибольший общий делитель чисел r и m, -- функция Эйлера (количество натуральных чисел, не превосходящих n и взаимно простых с n, или порядок мультипликативной группы вычетов по modn взаимно простых с n). Открытая информация, представленная целым числом w, , шифруется с помощью общеизвестной функции

, действующей на . Числа n="nX" и zX всех абонентов сети засекреченной связи обычно помещают в общедоступный справочник. Таким образом, любой абонент может послать секретное сообщение абоненту X.

Секретная информация (ключ) законного пользователя X

состоит из чисел p и q, на которые разлагается число n. Знание p и q позволяет вычислить значение функции Эйлера

, а затем с помощью алгоритма Евклида -- число z`, для которого . Очевидно, обратное преобразование имеет вид



и может быть реализовано абонентом X достаточно быстро - за операций даже без использования "быстрых" алгоритмов умножения целых чисел.

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

. В общем случае сложность решения задачи разложения является достаточно большой. В течение нескольких последних десятилетий математиками было найдены несколько нетривиальных алгоритмов разложения целых чисел на множители. В частности, удалось разложить 155-разрядное девятое число Ферма на три простых множителя. Множители имеют примерно одинаковое число разрядов. Считается, что система RSA имеет достаточную стойкость, если n имеет более 512 двоичных разрядов.

Теория кодирования доставляет много примеров стойких систем открытого шифрования. Пусть

-- линейный код над с параметрами (n,k,b), который имеет простое декодирование, и M -- его порождающая -матрица. Пусть H -- невырожденная -матрица и -- перестановочная -матрица.

Открытой информацией является k-мерный вектор

, шифрованной -- n-мерный вектор

(функция ), где -- случайный вектор веса

. Секретный ключ образуют матрицы H и , а общедоступным ключом является матрица . Случайный элемент генерирует отправитель. Матрицы H и "маскируют" матрицу M.

Получив , абонент X вычисляет следующие элементы:

, декодирует , т. е. представляет его в виде ,

, , где

, и, наконец, с помощью последнего соотношения находит w.

Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает

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

Если в качестве

взять код Боуза -- Чоудхури -- Хоквингема или код Рида -- Маллера, то при подходящем k и n мы получим стойкую систему открытого шифрования. Если же в качестве взять код Рида -- Соломона, то получим слабую систему. Кодовые системы имеют алгоритм зашифрования информации существенно более быстрый, чем системы RSA.

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

Для примера рассмотрим один популярный метод построения открытого ключа в сети абонентов Xj,

, предложенный Диффи и Хеллманом. Пусть -- конечное поле с достаточно большим числом элементов q и -- первообразный элемент мультипликативной группы G этого поля. Каждый из абонентов Xj и Xi один независимо от другого выбирают по секретному числу xj,xi, ,

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

С сохранением основной идеи метода в качестве G вместо мультипликативной группы конечного поля можно использовать любую циклическую группу. В частности, в  рассматривалась группа, образованная

-рациональными точками эллиптической кривой, заданной над некоторым подполем конечного поля . Изучались также и некоторые другие группы G.

Проблема оценки стойкости для приведенного примера на первый взгляд сводится к определению сложности вычисления

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

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

Необходимо отметить, что сложность логарифмирования определяется не только числом разрядов, требуемых для записи q -- числа элементов поля, но и некоторыми нетривиальными его теоретико-числовыми свойствами. В частности, для полей характеристики 2 и для полей, у которых в разложении q-1

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

На основе идей "открытого шифрования" в криптографии появились методы преобразования информации, открывающие новые возможности для ее использования в деловом мире. К таким методам следует отнести алгоритмы по созданию цифровой подписи, системы идентификации, пароли, системы распределения ключей и многие другие (см., например, и статьи в Proceding of Crypto, Proceding of Eurocrypt, Journal of Cryptolodgy и др.).

Цифровая подпись

сообщения w

пользователя X образуется с помощью отображения , которое характеризуются следующими свойствами:

при известном w элемент g может быть относительно просто вычислен X, но не может быть вычислен злоумышленником без привлечения очень значительных и потому недоступных ему вычислительных ресурсов (подпись не может быть подделана),

существует простой алгоритм проверки соответствия

(от подписи не может отказаться абонент X).

В общем случае в качестве цифровой подписи сообщения w можно использовать элемент

, где - односторонняя функция.

В качестве примера иного способа построения функции

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

Пользователь X вырабатывает секретное число x,

и помещает его в общедоступный справочник. Цифровой подписью сообщения w, . Секретное число r

пользователь X выбирает случайно из интервала (1,p-1). Число m определяется числами r и w с помощью соотношения .

Отметим, что, во-первых, пользователь X может достаточно просто вычислить m при известных числах

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

>


Содержание раздела

---

---

Главная сайта

---