Шифрование и шифры - практические аспекты

🕛 02.04.2009, 13:11

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

- в распоряжении аналитика есть фрагмент шифротекста и соответствующего ему открытого текста по размеру примерно равный размеру ключа ( | K | );

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

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

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

- анализ на основе только шифротекста - у аналитика имеется только зашифрованное сообщение размером n:

w = WGC(n);

- анализ на основе заданного открытого текста - аналитик располагает зашифрованным сообщением размером n и соответствующим ему открытым текстом:

w = WGP(n);

- анализ на основе произвольно выбранного открытого текста - в распоряжении аналитика есть возможность получить результат зашифрования для произвольно выбранного им массива открытых данных размером n:

w = WCP(n);

- анализ на основе произвольно выбранного шифротекста - в распоряжении аналитика есть возможность получить результат расшифрования для произвольно выбранного им зашифрованного сообщения размером n:

w = WCC(n);

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

Все рассмотренные характеристики трудоемкости имеют нижние границы:

wxx = inf WXX(n).

Очевидно также, что эти границы достигаются при некоторых конечных значениях параметра n, потому что при его неограниченном увеличении трудоемкость анализа, принимающего во внимание все имеющиеся в наличии данные, будет неограниченно возрастать:

wxx = WXX(nxx).

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

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

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

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

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

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

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

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

Рассмотрение следующей нашей темы - классификации шифров - начнем с двух требований, предъявляемых к практическим алгоритмам шифрования - они, в общем-то, естественны и понятны:

- шифр должен быть технически применим для закрытия массивов данных произвольного объема;

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

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

T = (T1, T2,..., Tn),

для всех i от 1 до n , где N-максимальный размер блока.

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

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

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

1. В блочных шифрах результат зашифрования очередного блока зависит только от него самого и не зависит от других блоков шифруемого массива данных:

Ti' = E(Ti).

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

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

Ti' = E(T1, T2,..., Ti).

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

Ti' = E(i,Ti).

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

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

где для всех

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

Для того, чтобы процедура шифрования была обратима, для шифрующего автомата должен существовать обратный ему автомат. Один конечный автомат является обратным другому и называется его обращением в том случае, если он преобразует любую выходную последовательность этого автомата в его входную последовательности. На рисунке 1 второй конечный автомат (правый, DFA) преобразует выходную последовательность s1s2...sK первого конечного автомата (левый, EFA) в его входную последовательность t1t2...tK, и в силу этого является его обращением.

fig.1

Рис.1. Конечный автомат и его обращение.

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

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

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

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

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

Ti' = EK(Ti).

Как следствие, при зашифровании двух одинаковых блоков данных получатся идентичные блоки шифротекста:

Из указанной особенности блочных шифров следует очевидный способ их анализа - статистический. Если известен закон распределения блоков открытого текста, то проанализировав статистику блоков шифротекста, можно установить соответствие между ними. Классическим примером такого криптоанализа является история, описанная Эдгаром По в его известном рассказе "Золотой жук". Для того, чтобы исключить подобную возможность, размер блока должен быть выбран достаточно большим. Например, при размере блока в один байт анализ шифра осуществим вручную, без использования вычислительной техники; при размере блока в 16 бит этот анализ элементарно реализуется на персональной ЭВМ и занимает несколько секунд; при размере блока в 32 бита компьютерный анализ также осуществим, хотя требует больше времени и большего необходимого объема зашифрованных данных. При дальнейшем увеличении размера блока статистический анализ становится все менее осуществимым на практике. Для большинства современных шифров выбрана величина блока в 64 бита, для нее исчерпывающий анализ практически исключен прежде всего из-за невозможности набрать соответствующую статистику шифротекстов. При еще больших размерах блока усложняется не только криптоанализ, усложняется и сам алгоритм шифрования - вот почему неразумно увеличивать его сверх необходимого. Как мы увидим в следующем выпуске, для шифров очень распространенной на сегодняшний день архитектуры, называемой "сбалансированная сеть Файстеля" (balanced Feistel network) условием эффективной реализации в виде программы для ЭВМ является равенство половинного размера блока криптоалгоритма величине машинного слова. Именно поэтому реализация отечественного стандарта шифрования - алгоритма ГОСТ 28147-89, шифра с 64-битовым размером блока, - для 32-битовых процессоров Intel x86 существенно эффективнее реализации этого же алгоритма для 16-битовых процессоров той же серии - естественно, сравнение производилось на одном и том же компьютере. В настоящее время подавляющее количество компьютеров в мире - 32 битовые, и по этой причине выбирать размер блока для упомянутой архитектуры шифров больше 64 бит совершенно бессмысленно, а с точки зрения эффективности реализации - вредно.
Хотя для блочных шифров с достаточно большим размером блока провести исчерпывающий статистический анализ в общем случае невозможно, тем не менее, анализируя зашифрованные данные, легко обнаружить наличие одинаковых блоков в исходных данных, что позволяет выявить стабильные паттерны, имеющиеся в них. Предположим, например, что целиком шифруется магнитный диск с информацией. На таком диске все незанятое пространство обычно заполнено фиксированными кодами, записанными туда при его форматировании. После шифрования на месте этого кода получатся одинаковые блоки шифротекста, что позволит злоумышленнику отличить незанятое пространство диска от пространства, заполненного полезными данными. Иногда это бывает неприемлемым, поэтому перед зашифрованием данных их очень полезно сжимать архиваторами, что существенно снижает избыточность данных и уменьшает вероятность встретить повторяющиеся блоки. В тех случаях, когда данные имеют физическую привязку - как в приведенном примере с шифрованием диска - их рекомендуется рандомизировать - модифицировать с использованием случайных или псевдослучайных.

Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:

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

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

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

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