История криптографии. 
Классические шифры

В результате изучения главы 1 студент должен: знать

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

владеть

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

Основные понятия и определения криптографии

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

Наука о методах и алгоритмах шифрования называется криптографией. Людей, занимающихся криптографией, называют криптографами. Криптоаналитики являются специалистами в области криптоанализа — науки о вскрытии шифров, которая отвечает на вопрос о том, как прочесть открытый текст, скрывающийся под шифрованным. Раздел науки, объединяющий криптографию и криптоанализ, именуется криптологией.

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

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

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

Рис. 1.1. Криптографическое преобразование.

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

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

Дешифрование — процесс извлечения открытого текста из криптограммы без знания ключа (при неизвестном ключе и, возможно, неизвестном алгоритме шифрования). Термин «дешифрование» обычно применяется к процессу криптоанализа шифротекста.

Каждое криптографическое преобразование однозначно определяется ключом и описывается некоторым криптографическим алгоритмом.

История криптографии насчитывает тысячелетия, однако ее теоретическое обоснование было дано сравнительно недавно — лишь в XX в. Одной из основополагающих теоретических работ по криптографии является статья К. Шеннона (Claude Shannon) «Теория связи в секретных системах», опубликованная в открытой печати в 1949 г.¹

На рис. 1.2 изображена описанная К. Шенноном схема секретной системы.

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

Рис. 1.2. Классическая схема секретной системы.

¹ Шеннон К. Теория связи в секретных системах // Работы по теории информации и кибернетике; пер. с англ. М.: Издательство иностранной литературы, 1963. С. 333—369.

В то же время основной канал обмена сообщениями является общедоступным. Противник (Е) может перехватывать передаваемые сообщения, т. е. канал передачи шифротскстов является открытым.

Другой подход, характерный для стеганографии, состоит в сокрытии самого факта передачи секретной информации, т. е. в создании скрытого или подсознательного канала передачи сообщений. В настоящее время методы цифровой стеганографии^[1] обычно сочетаются с криптографической защитой (шифрованием) секретного сообщения. Кроме того, скрытый канал может быть создан собственно криптографическими методами (см. параграф 3.11).

Секретная система, или в современной терминологии — криптосистема, шифр (рис. 1.3), определяется как семейство взаимно-однозначных отображений множества возможных сообщений X во множество криптограмм К, проиндексированное элементами k из множества ключей:

где К — пространство ключей — набор всех возможных значений ключа k, *-{*}•.

Рис. 1.3. Подробная схема секретной системы

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

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

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

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

На практике успех вскрытия алгоритма шифрования зависит от наличия у криптоаналитика следующих ресурсов:

• • конкретного объема перехваченных зашифрованных сообщений;
• • временных ресурсов. Здесь подразумевается время, необходимое для проведения определенных вычислений; в некоторых случаях временные затраты противника могут превышать время жизни секретной информации (время, в течение которого информация должна сохранять свое свойство KOI 1фиде11 циал ы юсти);
• • вычислительных ресурсов (быстродействие и количество памяти в вычислительных системах, используемых для реализации атаки).

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

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

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

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

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

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

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

Если противник узнал (например, выкрал или купил) ключ шифрования, го говорят, что ключ был скомпрометирован.

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

Таким образом, шифр рассматривается как параметризованный алгоритм, состоящий:

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

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

Преимущества такой организации криптографической системы следующие:

• • разглашение шифра (алгоритма и ключа) не приводит к необходимости полной замены реализации всего алгоритма, достаточно заменить только скомпрометированный ключ;
• • ключи можно отчуждать от остальных компонентов системы шифрования — хранить или генерировать отдельно от реализации конкретного алгоритма;
• • появляется возможность для точной оценки «степени неопределенности» алгоритма шифрования — она равна неопределенности используемого ключа.

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

Стойкость шифра (криптографическая стойкость, криптостойкость) — это его способность противостоять криптоаналитическим атакам, т. е. степень гарантии того, что шифр невозможно взломать без знания ключа шифрования.

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

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

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

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

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

Рис. 1.4. Виды атак на криптографические системы.

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

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

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

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

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

Выбор средств защиты определяется ответом на два вопроса:

• • является ли информация для противника более ценной, чем затраты на проведение атаки;
• • является ли информация для владельца более ценной, чем стоимость защиты?

• [1] Грибунин В. Г, Оков И. Н., Туринцев И. В. Цифровая стеганография. М.: Солон-Пресс, 2009.