1.2 Углубленные комментарии

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

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

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

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

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

Теперь остановимся на исходных предположениях, в рамках которых проводится криптоанализ.

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

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

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

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

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

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

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

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

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

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

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