Введение в криптографию и шифрование

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

Криптография – наука о методах обеспечения конфиденциальности и аутентичности информации.

До 70-х годов XX века криптографией называлась область науки и практической деятельности, связанная с изучением и разработкой методов шифрования данных. В настоящее время сфера интересов криптографии включает в себя множество так называемых криптографических алгоритмов, к которым, помимо шифрования/дешифрования, относятся алгоритмы хэширования, формирования и проверки электронной подписи, распределения ключей и множество других алгоритмов, каждый из которых предназначен для противодействия определенным угрозам информационной безопасности со стороны возможного нарушителя (противника, злоумышленника) или нежелательных воздействий естественного характера. Большинство криптографических алгоритмов строятся на математической основе. Устройства, программы, документы, созданные на основе криптографических алгоритмов, называются криптографическими средствами. Система обеспечения информационной безопасности, использующая криптографические средства, называется криптографической системой. Можно сказать, что криптография изучает криптографические системы.

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

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

3.2. Шифрование

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

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

Алгоритмы шифрования делятся на две большие группы:

1. Симметричное (традиционное) шифрование.

2. Шифрование с открытым ключом.

3.3. Симметричное шифрование

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

M′ = E(M, K)

M = D(M′, K),

где E – функция шифрования (encrypt), а D – функция дешифрования (decrypt), обе используют ключ K в качестве одного из параметров.

Рис. 3.1. Симметричное шифрование

Исторически симметричное шифрование появилось первым. Более того, до 1970-х это была единственная разновидность шифрования. Симметричные алгоритмы широко применяются и в настоящее время.

Все алгоритмы симметричного шифрования можно разделить на три класса:

1. Подстановочные алгоритмы.

2. Перестановочные алгоритмы.

3. Алгоритмы, использующие подстановку и перестановку (практически все современные алгоритмы, разработанные для защиты информации в ЭВМ).

Кроме того, среди симметричных алгоритмов шифрования можно выделить:

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

2. Алгоритмы с многократно используемым ключом. Такие алгоритмы должны быть более надежными (и пройти более серьезные проверки на безопасность), поскольку у противника появляются дополнительные возможности криптоанализа.

3.4. Обзор классических алгоритмов шифрования

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

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

1. Шифр Цезаря

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

Рис. 3.2. Пример шифрования по Цезарю

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

Если в шифре Цезаря сдвиг в алфавите взять не 3, а любое секретное число K, известное отправителю и получателю сообщения, эта вариация становится полноценным шифром с ключом K. Однако легко заметить, что в качестве ключа могут быть выбраны лишь числа в диапазоне от 1 до 32 (для русского алфавита). Действительно, шифр является циклическим: Я + 1 = А, но и Я + 34 = А. То есть, число 34, выбранное в качестве ключа, будет эквивалентно ключу 1, ключ 35 – ключу 2 и т.д. Противнику ничего не стоит перебрать все 32 возможных ключа и обнаружить нужный.

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

Термин длина ключа отражает особенности современных алгоритмов шифрования. Они разрабатываются для ЭВМ, поэтому открытый текст, шифртекст и ключ представляют собой двоичные последовательности бит (иногда удобно представлять их как числа). Длина ключа – это длина соответствующей двоичной последовательности, причем, предполагается, что для шифрования может быть выбран любой ключ с равной вероятностью. Таким образом, общее число ключей равно 2ⁿ, где n – длина ключа, а вероятность «угадать» ключ с одной попытки составляет 1/2ⁿ. С ростом n сложность подбора ключа растет экспоненциально. В настоящее время надежной считается длина ключа 128 бит. С этой точки зрения длина ключа шифра Цезаря равна 5 битам, что явно небезопасно.

Чем слабее шифр, тем меньшими возможностями должен обладать противник, чтобы успешно его вскрыть. Шифр Цезаря уязвим для самой легко реализуемой атаки – на основе шифртекста. Это метод, при котором криптоаналитик восстанавливает открытый текст и/или ключ, располагая только одним или несколькими зашифрованными сообщениями. Опробуя все возможные 32 ключа, противник быстро видит, что получается в результате дешифрования – бессмысленный набор символов (следовательно, ключ не подходит), или что-то, похожее на настоящий текст. Для этого достаточно дешифровать только начало сообщения.

Этот пример наглядно демонстрирует одну из техник криптоанализа – метод грубой силы или полный перебор ключей. Этот метод служит своеобразной оценкой прочности шифра сверху. Если длина ключа мала, то не спасут никакие конструктивные особенности шифра – ведь криптоаналитик всегда может просто перебрать ключи и с вероятностью 50% найдет нужный после 2ⁿ⁻¹ попыток. Шифр Цезаря противостоять методу грубой силы не может.

2. Моноалфавитный шифр (шифр простой замены)

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

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

При шифровании каждый символ открытого текста заменяется другим символом в соответствии с ключом.

Рис. 3.3. Пример шифрования шифром простой замены

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

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

Все естественные языки имеют характерное частотное распределение символов. Например, буква «О» встречается в русском языке чаще других, а буква «Ф» – самая редкая (см. табл. 3.1).

Таблица 3.1. Частоты встречаемости букв русского языка

Символ	Вероятность	Символ	Вероятность	Символ	Вероятность
пробел	0.175	К	0.028	Ч	0.012
О	0.089	М	0.026	Й	0.010
Е	0.072	Д	0.025	Х	0.009
А	0.062	П	0.023	Ж	0.007
И	0.062	У	0.021	Ю	0.006
Н	0.053	Я	0.018	Ш	0.006
Т	0.053	Ы	0.016	Ц	0.004
С	0.045	З	0.016	Щ	0.003
Р	0.040	Ь	0.014	Э	0.003
В	0.038	Б	0.014	Ф	0.002
Л	0.03	Г	0.013

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

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

Нетрудно заметить, что шифр Цезаря также является моноалфавитным шифром.

3. Шифр Гронсфельда

Шифр Гронсфельда развивает идею, заложенную в шифре Цезаря. В качестве ключа используется последовательность цифр произвольной фиксированной длины. Каждая цифра этой последовательности записывается под одним символом открытого текста, причем если длина ключа меньше длины текста, ключ циклически повторяется. Зашифруем слово «информатика» ключом «123».

Рис. 3.4. Пример использования шифра Гронсфельда

Этот шифр относится к семейству многоалфавитных шифров (или шифров сложной замены). В многоалфавитном шифре 1-й символ открытого текста шифруется с помощью моноалфавитного шифра, ключом к которому является перестановка K₁, 2-й символ – ключом K₂ и т.д., n-й символ – ключом K_n, а n+1-й – снова ключом K₁, где n – количество используемых алфавитов (или шифров простой замены). В приведенном примере n=3.

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

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

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

Эта проблема исчезает в модификации шифра Гронсфельда, где в качестве ключа выступает не цифровая, а буквенная последовательность. Порядковый номер буквы открытого текста складывается с записанной под ней буквой ключа и получается порядковый номер буквы зашифрованного текста (который берется по модулю мощности алфавита, т.е.  Г + Э = 4 + 31 = 35; 35 mod 33 = 2 = Б; Г + Э = Б).

Рис. 3.5. Модифицированный шифр Гронсфельда

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

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

Пусть c₁ – первая буква первого шифртекста, а c₂ – первая буква второго шифртекста. По определению шифра Гронсфельда эти буквы были получены следующим образом:

c₁ = m₁ + k; c₂ = m₂ + k,

где m₁ – первая буква первого открытого текста, а m₂ – первая буква второго открытого текста, k – первый символ ключевой последовательности (которая будет идентичной в обоих случаях).

Что будет если вычесть из одного зашифрованного текста другой? Рассмотрим разность первых букв шифртекстов:

c₁ - c₂ = m₁ + k - m₂ – k = m₁ - m₂

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

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

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

4. Многобуквенные шифры

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

В шифре Плейфейера единицей шифрования является биграмма (пара букв), заменяемая другой парой букв. Он предназначен для английского алфавита. Ключом является кодовая фраза, которая записывается в первые ячейки квадратной решетки 5x5 (повторяющиеся буквы пропускаются). Затем квадрат в алфавитном порядке заполняется буквами, которые не вошли в кодовую фразу. I и J считаются одной буквой.

Заполним решетку с ключевым словом MONARCHY.

Рис. 3.6. Кодовая решетка для шифра Плейфейера

Исходный текст разбивается на биграммы. При этом если две одинаковые буквы открытого текста при разбиении образуют одну биграмму, между ними вставляется символ X. Т.е. вместо BALLOON шифруем BALXLOON.

Если буквы биграммы стоят в одной строке (столбце), они заменяются их правыми (нижними) соседями с учетом циклического сдвига. В нашем примере OR шифруется как NM, а OP – как HV.

Если буквы биграммы оказываются в разных строках и столбцах, то каждая из пары букв заменяется буквой, находящейся на пересечении ее строки и столбца, в котором находится вторая буква. Например, BE шифруется как CI, а OS – как AP.

Слово INFORMATION будет зашифровано как GAPHMORSFAAW.

Этот шифр сохраняет статистические особенности исходного текста в том смысле, что можно построить таблицу частот биграмм для языка и проанализировать частоты биграмм зашифрованного текста. Однако если букв в английском языке 26, то биграмм уже 26² = 676, поэтому задача существенно усложняется и без значительных объемов зашифрованного текста обречена на провал.

Конечно, атака с известным открытым текстом по-прежнему будет эффективной.

Другой интересный пример многобуквенного шифра – шифр Хилла. Он представляет собой систему из m линейных уравнений. Шифр заменяет каждые m букв открытого текста на m букв зашифрованного текста. Например, при m = 3 имеем систему уравнений (где n – мощность алфавита):

c₁ = (k₁₁ p₁+ k₁₂ p₂+ k₁₃ p₃) mod n

c₂ = (k₂₁ p₁+ k₂₂ p₂+ k₂₃ p₃) mod n

c₃ = (k₃₁ p₁+ k₃₂ p₂+ k₃₃ p₃) mod n

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

Шифр Хилла также хорошо скрывает частоту символов исходного сообщения, но уязвим к криптоанализу с известным открытым текстом. Поскольку система линейная, противнику понадобится m² пар «открытый текст – зашифрованный текст», чтобы вычислить ключевую матрицу. Однако наиболее эффективный метод криптоанализа для этого шифра – криптоанализ с избранным открытым текстом, когда противник имеет возможность получать зашифрованные образцы специально подобранного им открытого текста. Подумайте, что будет представлять собой зашифрованный текст, если зашифровать последовательность БАА (p₁ = 1, p₂ = 0, p₃ = 0).

5. Простая перестановка по столбцам

В перестановочных алгоритмах символы открытого текста изменяют порядок следования в соответствии с правилом, которое определяется ключом.

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

Рис. 3.7. Простейший перестановочный шифр

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

6. Поворотная решетка

Более интересный пример перестановочного шифра – поворотная решетка (решетка Флейснера). Ключом к этому шифру является квадратная решетка, стороны которой содержат четное число ячеек. Четверть ячеек решетки вырезаются по следующему принципу: если некоторая ячейка вырезана, то нельзя вырезать те ячейки, в которые она переходит при повороте решетки на 90, 180 и 270 градусов.

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

Рис. 3.8. Пример шифрования с помощью поворотной решетки

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

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

3.5. Одноразовый блокнот и надежность шифров

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

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

На практике одноразовые блокноты применяются очень редко (лишь для сообщений высшей секретности). Во-первых, изготовление такого блокнота достаточно дорого (т.к. абсолютно случайная последовательность не может генерироваться алгоритмически), а блокнот предназначен лишь для одноразового использования. Во-вторых, возникает проблема передачи ключа: единственный надежный вариант – личная встреча. Действительно, предположим у отправителя и получателя сообщения есть надежный канал обмена информацией. Тогда почему бы не передавать по этому каналу незашифрованные сообщения? Если же отправить ключ, зашифровав его другим алгоритмом, вся система окажется надежной не более, чем этот алгоритм. Эта проблема характерна для всего симметричного шифрования вообще, но, когда ключ длиннее самого текста, она, очевидно, усугубляется.

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

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

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

Одна из популярных моделей оценки надежности шифра – IND-CPA выглядит так. Представим себе черный ящик, который умеет шифровать сообщение с неизвестным нам ключом. На вход этого черного ящика подается два сообщения: m₁ и m₂. Из них случайным образом выбирается одно, шифруется и возвращается нам. Мы должны угадать какое сообщение вернулось (важно, что мы могли конструировать эти сообщения так как нам надо). Шифр будет считаться надежным, если любой вычислительно эффективный алгоритм будет определять правильное сообщение с вероятностью, отличающейся от 0.5 на пренебрежимо малую величину.

Попробуйте ответить на вопрос с подвохом: почему не ставится условие, чтобы алгоритм всегда ошибался? ☺

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

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

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

На математическом языке это звучит так:

Функция T(n) имеет порядок O(f(n)), если

∃ k, n0 т. что ∀ n > n0 T(n) ≤ k*f(n). Т.е. T(n) растет не быстрее f(n).

Простыми словами, в криптографии теория сложности используется следующим образом. Если n – это параметр, на который может влиять пользователь или разработчик системы (например, длина ключа), то алгоритм взлома должен иметь такую вычислительную сложность T(n), которая сделает его практически неприменимым. Точно построить функцию зависимости сложно, но мы можем понять, к какому классу она относится. Эти классы приведены в таблице:

Таблица 3.2. Классы вычислительной сложности

Константная	К	Обращение к элементу массива по индексу
Логарифмическая	K * log(n)	Бинарный поиск
Линейная	K * n	Перебор элементов массива
Линейный логарифм	n * log(n)	Алгоритмы быстрой сортировки
Полиномиальная	nᴷ	Алгоритмы простой сортировки (пузырьком)
Экспоненциальная	Kⁿ	Алгоритмы перебора (brute force)
Факториальная	n!	Алгоритмы комбинаторики (сочетания, перестановки и т.д.)

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

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

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