А.Винокуров. Серия выпусков по криптографии для электронного журнала "iNFUSED BYTES Online".
В предыдущих выпусках мы с вами выяснили некоторые подробности относительно шифров: что существуют абсолютно стойкие, так называемые совершенные шифры, которые невозможно раскрыть в принципе; что цена этой стойкости - необходимость использовать ключевую информацию, по объему не меньшую, чем защищаемые данные; что при использовании несовершенных шифров возможно однозначное дешифрование сообщения только при выполнении одного из следующих условиях:
R < 1, определение избыточности см. в предыдущем выпуске),
а в распоряжении криптоаналитика есть фрагмент шифртекста приблизительного
объема |K|/R.В большинстве практических случаев указанные условия выполняются, поэтому для реальных шифров злоумышленник, располагающий неограниченными вычислительными ресурсами и шифртекстом достаточного размера, может однозначно дешифровать сообщение. Поэтому стойкость всех современных шифров, не являющихся совершенными, базируется на вычислительной сложности дешифрования. Реально вычислительные возможности аналитика всегда ограничены, и для них может быть получена верхняя оценка. Хорошо спроектированным считается шифр, который невозможно вскрыть с вычислительными затратами, неосуществимыми за разумное время с запасом в несколько порядков даже с учетом прогнозируемого прогресса вычислительной техники.
В качестве меры трудоемкости раскрытия таких шифров обычно используется количество элементарных операций (w) некоторого типа, необходимых для дешифрования сообщения или определения ключа. Под элементарной операцией в различных случаях понимают разное, но обычно этим термином обозначают операцию, выполняемую на конкретной аппаратуре за один шаг ее работы. Например, операцию типа "сложение", для универсальных процессоров, или цикл проверки одного ключа для специальных аппаратных схем перебора ключей. Трудоемкость дешифрования зависит от того, какая информация есть в распоряжении аналитика, и сколько ее у него. Обычно различают следующие виды криптоанализа:
w = WGC(n);
w = WGP(n);
w = WCP(n);
w = WCC(n);
Предполагается, что криптоаналитик использует наилучший из доступных ему способов анализа. Конечно, последний вид криптоанализа несколько экзотичен, но, тем не менее, в соответствующих обстоятельствах возможен и он. Очевидно, что между величинами трудоемкости различных видов криптоанализа выполняются следующие соотношения:
WGC(n)
WGP(n)
Все рассмотренные характеристики трудоемкости имеют нижние границы:
wXX = inf WXX(n).
Очевидно также, что эти границы достигаются при некоторых конечных значениях параметра n, потому что при его неограниченном увеличении трудоемкость анализа, принимающего во внимание все имеющиеся в наличии данные, будет неограниченно возрастать:
wXX = WXX(nXX).
Таким образом, для каждого вида криптоанализа (XX) существует свой оптимальный объем необходимых данных (nXX), при возрастании объема имеющихся данных от нуля до этого значения трудоемкость анализа снижается до своего граничного значения (wXX), а при дальнейшем возрастании - увеличивается. Эти критические объемы данных и соответствующие величины трудоемкости анализа и представляют особый интерес для специалистов-криптографов. Понятно, что реально трудоемкость анализа зависит не только от объема анализируемых данных, но и от самих этих данных. По этой причине все приведенные выше соотношения являются оценочными, а соответствующие величины считаются заданными с точностью до порядка-двух.
Следует различать точное значение показателей трудоемкости каждого вида
анализа WXX(n) и его
текущую оценку 
, основанную на достижениях современного
криптоанализа - понятно, что оценка больше оцениваемой величины:
WXX(n), и с
развитием криптоанализа она постоянно снижается. Истинный интерес конечно же
представляет сама оцениваемая величина. Однако, как отметил еще Шеннон, не
существует способа получить точное значение трудоемкости анализа, все оценки
базируются на проверках устойчивости шифров к известным на текущий
момент видам криптоанализа, и нет гарантии, что в ближайшем или более отдаленном
будущем не будут разработаны новые методы анализа, существенно ее снижающие.
Сказанное выше означает, что при текущем положении дел в криптографии стойкость абсолютно всех шифров, что за исключением совершенных, не может быть доказательно обоснована. Вместо этого она обосновывается эмпирически как устойчивость к известным на сегодняшний день видам криптоанализа, но никто не может дать гарантии того, что завтра не будет изобретен вид криптоанализа, успешный именно для данного конкретного шифра. Вот почему не стоит доверять "новейшим шифрам" - они не прошли проверку временем. По этой же самой причинам не является разумным доверять криптоалгоритмам, которые держатся их авторами в секрете - даже при отсутствии злонамеренно оставленных там "люков" нет совершенно никакой гарантии того, что алгоритм был исследован со всей необходимой тщательностью.
Сказанное не означает, что использование секретных алгоритмов шифрования вовсе лишено смысла. Оно является допустимым и разумным при выполнении двух следующих условий:
Указанные условия выполняются, например, для спецслужб ведущих государств мира, разрабатывающих для "внутреннего потребления" собственные шифры.
Рассмотрение следующей нашей темы - классификации шифров - начнем с двух требований, предъявляемых к практическим алгоритмам шифрования - они, в общем-то, естественны и понятны:
Попытка совместить оба требования неизбежно приводит к криптоалгоритму, в котором шифрование производится пошагово, порциями - массив данных разбивается на блоки ограниченного размера, и за один шаг шифруется один блок:
T = (T1, T2, ..., Tn),
для всех i от 1 до n
|Ti|N, где
N-максимальный размер блока.
От размера шифруемого массива данных в этом случае зависит только количество шагов шифрования, но не сами шаги. Ради удобства реализации размер блока практически всегда полагают постоянным - может быть, за исключением последнего блока данных, который может быть меньше:
|T1| = |T2| = ... = |Tn-1| = N, |Tn|
По соображениям стойкости размер блока не должен значительно превышать размер ключа, лучше, если он будет меньше или равен ему.
Существуют два принципиально различающихся подхода к построению шифров с секретным ключом, соответственно им можно выделить два типа шифров - блочные и потоковые шифры:
Ti' = E(Ti).
Из этого следует, что в результате зашифрования двух одинаковых блоков открытого текста всегда получаются идентичные блоки шифртекста:
Ti = Tj
E(Ti) = E(Tj).
Ti' = E(T1, T2, ..., Ti).
Сюда же относится важный частный случай, когда результат зашифрования очередного блока зависит этого блока и от его номера:
Ti' = E(i, Ti).
По поводу разделения шифров на блочные и потоковые следует добавить, что в современной криптологии указанные понятия иногда используются в близком, но несколько отличном от сказанного выше смысле - потоковыми называют только такие шифры, в которых шифруемый за один шаг блок имеет размер один бит или один символ текста, а шифры с большим размером блока, формально относящиеся к потоковым, причисляют к блочным. Потоковые в последнем, практическом значении этого термина, шифры очень хорошо подходят для засекречивания асинхронного информационного потока - поступившая порция данных может быть немедленно зашифрована и отправлена в канал связи, нет необходимости ждать, пока наберется полный блок из нескольких битов или символов, как это было бы необходимо для блочных в том же самом, "практическом" смысле термина шифров.
Если принять во внимание требование к реализуемости криптоалгоритма
устройством с конечным числом возможных состояний, то наиболее общей моделью
потоковых шифров является конечный автомат, описываемый множеством состояний
, входным и выходным алфавитами 
и 
,
и правилами перехода и выхода 
и 
соответственно:
Xi+1 =
Ti' =
где для всех
i Xi![[in]](../../img/belongs.gif){kind=small}
,
Ti, Ti';
Множество состояний и алфавиты автомата являются конечными - собственно, именно поэтому автомат и называется конечным, - а правила перехода и выхода могут быть записаны в виде двумерной таблицы, и по этой причине иногда называются таблицами переходов и выходов соответственно. Автомат работает следующим образом: каждый символ, поступивший на его вход, вызывает изменение состояния автомата и порождение одного выходного символа. В результате входное слово преобразуется в слово точно такой же длины, составленное из символов выходного алфавита. Работа конечного автомата зависит от его начального состояния: в общем случае два идентичных автомата преобразуют одно и то же входное слово в разные выходные, если начнут свою работу с разных состояний.
![[здесь рисунок]](ib0303.gif)
Рис. 1. Конечный автомат и его обращение.
Для того, чтобы процедура шифрования была обратима, для шифрующего автомата должен существовать обратный ему автомат. Один конечный автомат является обратным другому и называется его обращением в том случае, если он преобразует любую выходную последовательность этого автомата в его входную оследовательности. На рисунке 1 второй конечный автомат (DFA, на рисунке справа) преобразует выходную последовательность s1s2...sK первого конечного автомата (EFA, на рисунке слева) в его входную последовательность t1t2...tK, и в силу этого является его обращением.
Так как работа конечного автомата зависит от его начального состояния, то для каждого допустимого начального состояния автомата должно существовать парное ему начальное состояние его обращения, при котором эти автоматы, соединенные в каскад как показано на рисунке 1, работают как тривиальный автомат, выдающий без изменения на выход все то, что поступило ему на вход. Отсюда следует, что для корректного расшифрования выполняющий эту процедуру автомат должен быть синхронизирован с шифрующим - он должен начать свою работу с состояния, парного начальному состоянию последнего, для чего ему необходима информация об этом состоянии. Эта информация называется синхропосылкой и передается до начала передачи зашифрованных данных всякий раз при установлении или восстановлении соединения после сбоя в канале связи. По вполне понятной причине синхропосылка может передаваться только в открытом виде - на момент ее получения автомат расшифрования на принимающей стороне не готов к работе.
В настоящее время одним из наиболее популярных видов потоковых шифров является шифр гаммирования, в котором соответствующий конечный автомат является безвходовым и используется для выработки последовательности элементов гаммы:
Xi+1 =
Гi =
Для наложения гаммы на данные может быть использована любая подходящая бинарная операция. Если это операция аддитивного типа, шифр называется аддитивным, если же используется операция побитового сложения по модулю 2 - то двоичным аддитивным. Как мы с вами выяснили в предыдущем выпуске, с точки зрения надежности шифра все допустимые операции наложения гаммы одинаковы, по этой причине в реальных шифрах используют наиболее просто реализуемую их них. Для двоичных данных таковой является операция побитового суммирования по модулю 2 или побитового исключающего ИЛИ:
Ti' = Ti
Гi.
Кроме того, эта операция является обратной самой себе и по этой причине может использоваться как для зашифрования, так и для расшифрования данных, что позволяет реализовать обе эти процедуры в одном модуле, достигнув тем самым дополнительных преимуществ в экономичности.
Условием стойкости шифра гаммирования является невозможность определить по известному фрагменту гаммы другие ее части или восстановить структуру порождающего ее конечного автомата. Для стороннего наблюдателя, обладающего лишь ограниченными вычислительными возможностями, выработанная гамма должна быть неотличима от случайной последовательности. В заключение рассмотрения темы потоковых шифров отметим, что эта область криптографии целиком базируется на теории конечных автоматов - очень подробно разработанной на сегодняшний день отрасли математики, и по этой причине считается одним из наиболее полно исследованных разделов криптологии. Теперь перейдем к рассмотрению блочных шифров - именно они станут темой нескольких ближайших выпусков. В шифрах этого типа результат зашифрования каждого блока зависит только от его значения, естественно, не считая секретного ключа:
Ti' = EK(Ti).
Как следствие, при зашифровании двух одинаковых блоков данных получатся идентичные блоки шифртекста:
Ti = Tj
Из указанной особенности блочных шифров следует очевидный способ их анализа - статистический. Если известен закон распределения блоков открытого текста, то проанализировав статистику блоков шифртекста, можно установить соответствие между ними. Классическим примером такого криптоанализа является история, описанная Эдгаром По в его известном рассказе "Золотой жук". Для того, чтобы исключить подобную возможность, размер блока должен быть выбран достаточно большим. Например, при размере блока в один байт анализ шифра осуществим вручную, без использования вычислительной техники; при размере блока в 16 бит этот анализ элементарно реализуется на персональной ЭВМ и занимает несколько секунд; при размере блока в 32 бита компьютерный анализ также осуществим, хотя требует больше времени и большего необходимого объема зашифрованных данных. При дальнейшем увеличении размера блока статистический анализ становится все менее осуществимым на практике. Для большинства современных шифров выбрана величина блока в 64 бита, для нее исчерпывающий анализ практически исключен прежде всего из-за невозможности набрать соответствующую статистику шифртекстов. При еще больших размерах блока усложняется не только криптоанализ, усложняется и сам алгоритм шифрования - вот почему неразумно увеличивать его сверх необходимого. Как мы увидим в следующем выпуске, для шифров очень распространенной на сегодняшний день архитектуры, называемой "сбалансированная сеть Файстеля" (balanced Feistel network) условием эффективной реализации в виде программы для ЭВМ является равенство половинного размера блока криптоалгоритма величине машинного слова. Именно поэтому реализация отечественного стандарта шифрования - алгоритма ГОСТ 28147-89, шифра с 64-битовым размером блока, - для 32-битовых процессоров Intel x86 существенно эффективнее реализации этого же алгоритма для 16-битовых процессоров той же серии - естественно, сравнение производилось на одном и том же компьютере. В настоящее время подавляющее количество компьютеров в мире - 32 битовые, и по этой причине выбирать размер блока для упомянутой архитектуры шифров больше 64 бит совершенно бессмысленно, а с точки зрения эффективности реализации - вредно.
Хотя для блочных шифров с достаточно большим размером блока провести исчерпывающий статистический анализ в общем случае невозможно, тем не менее, анализируя зашифрованные данные, легко обнаружить наличие одинаковых блоков в исходных данных, что позволяет выявить стабильные паттерны, имеющиеся в них. Предположим, например, что целиком шифруется магнитный диск с информацией. На таком диске все незанятое пространство обычно заполнено фиксированными кодами, записанными туда при его форматировании. После шифрования на месте этого кода получатся одинаковые блоки шифртекста, что позволит злоумышленнику отличить незанятое пространство диска от пространства, заполненного полезными данными. Иногда это бывает неприемлемым, поэтому перед зашифрованием данных их очень полезно сжимать архиваторами, что существенно снижает избыточность данных и уменьшает вероятность встретить повторяющиеся блоки. В тех случаях, когда данные имеют физическую привязку - как в приведенном примере с шифрованием диска - их рекомендуется рандомизировать - модифицировать с использованием случайных или псевдослучайных.
Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:
Если шифр обладает обоими указанными свойствами в достаточной степени, то любые изменения в блоке открытых данных приводят к тому, что с точки зрения наблюдателя все символы (биты) в зашифрованном блоке получат новые значения, равновероятные в области их определения и независимые друг от друга. Так, если шифр оперирует информацией, представленной в двоичной форме, то инвертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью 1/2 независимо друг от друга так же поменяют свое значение. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. Данное условие является обязательным для шифра рассматриваемого типа, претендующего на то, чтобы считаться хорошим.
Как же создать надежный шифр, соответствующий всем приведенным выше условиям надежности? Шеннон предложил строить его из простых шифров, как большой дом строится из отдельных кирпичиков. Каждый из использованных простых шифров может не обладать рассмотренными выше свойствами, но все вместе они образуют вполне стойкий шифр. О том, как это получается, мы с вами поговорим в следующем выпуске.
[Оглавление] [Предыдущий выпуск] [Следующий выпуск]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]
Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.
