На главную | Содержание | Назад | Вперёд
Наши друзья

 

 

Методы раскрытия шифров

В качестве меры трудоемкости раскрытия таких шифров обычно используют количество элементарных операций (w) некоторого типа,
необходимых для дешифрования сообщения или определения ключа. Под элементарной операцией в различных случаях понимают разное,
но обычно этим термином обозначают операцию, выполняемую на
конкретной аппаратуре за один шаг ее работы. Например, операцию
типа «сложение» для универсальных процессоров или цикл проверки одного ключа для специальных аппаратных схем перебора ключей.
Трудоемкость дешифрования зависит от характера и количества ин­формации, имеющейся в распоряжении аналитика. Обычно различа­ют следующие виды криптоанализа:
- анализ на основе только - у аналитика имеется
только зашифрованное сообщение размером n: w = WGC(n);
- анализ на основе заданного открытого текста — аналитик рас­полагает зашифрованным сообщением размером п и соответствую­щим ему открытым текстом: w
- анализ на основе произвольно выбранного открытого текста — в распоряжении аналитика есть возможность получить результат за­шифрования для произвольно выбранного им массива открытых дан­ных размером n: w = WCP(n);
9 280 257
Павел Даниэль Шрейн
- анализ на основе произвольно выбранного шифротекста - в
распоряжении аналитика есть возможность получить результат рас­шифрования для произвольно выбранного им зашифрованного сооб­щения размером n: w - WCC(n).
что использует наилучший из
доступных ему способов анализа. Конечно, последний вид криптоана­лиза несколько экзотичен, но, тем не менее, в соответствующих об­стоятельствах и он возможен. Очевидно, что между величинами тру­доемкости различных видов криптоанализа выполняются следующие соотношения.
Все рассмотренные характеристики трудоемкости имеют ниж­ние границы:
wxx        inf   WXX(n) .
Очевидно также, что эти границы достигаются при некоторых конечных значениях параметра п, потому что при его неограниченном увеличении трудоемкость анализа, принимающего во внимание все имеющиеся в наличии данные, будет неограниченно возрастать:
wxx   -   WXX fnxx) ,
Таким образом, для каждого вида криптоанализа (XX) сущест­вует свой оптимальный объем необходимых данных (пхх), при возрас­тании объема данных от нуля до этого значения трудоем­кость анализа снижается до своего граничного значения (wxx), а при дальнейшем возрастании — увеличивается. Эти критические объемы данных  и  соответствующие величины трудоемкости анализа и
представляют особый интерес для специалистов-криптографов.
Понятно, что реально трудоемкость анализа зависит не только от объема анализируемых данных, но и от самих этих данных. По этой причине все приведенные выше являются оценочными,
а соответствующие величины считаются заданными с точностью до порядка-двух. Следует различать точное значение показателей трудо­емкости каждого вида анализа WXX (п) и его текущую оценку , осно­ванную на достижениях современного криптоанализа — понятно, что оценка больше оцениваемой величины: и с развитием криптоанализа она постоянно снижается. Истинный интерес, конечно же, представ­ляет сама оцениваемая величина. Однако, как отметил еще Шеннон, не существует способа получить точное значение трудоемкости анали­за, все оценки базируются на проверках устойчивости шифров к изве­стным на текущий момент видам криптоанализа и нет гарантии, что в ближайшем или более отдаленном будущем не будут разработаны но­вые методы анализа, существенно ее снижающие.
Сказанное выше означает, что при текущем положении дел в криптографии стойкость абсолютно всех шифров, за исключением со­вершенных, не может быть доказательно обоснована. Вместо этого она обосновывается эмпирически, как устойчивость к известным на сего­дняшний день видам криптоанализа, но никто не может дать гарантии
того, что завтра не будет изобретен вид криптоанализа, успешный
именно для данного конкретного шифра. Вот почему не стоит дове­рять «новейшим шифрам» — они не прошли проверку временем. По этой же самой причине не является разумным доверять криптоалго­ритмам, которые держатся их авторами в секрете - даже при отсутст­вии злонамеренно оставленных там «люков» нет совершенно никакой гарантии того, что алгоритм был исследован со всей необходимой тща­тельностью. Сказанное не означает, что использование секретных ал­горитмов шифрования вовсе лишено смысла. Оно является допусти­мым и разумным при выполнении двух следующих условий:
— между разработчиками и пользователями алгоритма сущест­вует уровень доверия, исключающий намерение разработчика нанести ущерб пользователю, предоставив ему недостаточно качественный шифр или шифр с оставленными в нем люками;
— специалисты, разработавшие алгоритм, имеют достаточно вы­сокий уровень компетентности в этой области.
Указанные условия выполняются, например, для спецслужб ве­дущих государств, разрабатывающих для «внутреннего собственные шифры. Рассмотрение следующей нашей темы - класси­фикации шифров - начнем с двух требований, предъявляемых к прак­тическим алгоритмам шифрования - они, в общем-то, естественны и понятны:
— шифр должен быть технически применим для закрытия мас­сивов данных произвольного объема;
— шифр должен быть реализуем в виде устройства, имеющего
ограниченный объем памяти, и его реализация должна быть эффек­тивна при этом.
Попытка совместить оба требования неизбежно приводит к
криптоалгоритму, в котором шифрование производится пошагово, порциями — массив данных разбивается на блоки ограниченного раз­мера, и за один шаг шифруется один блок:
Т - Т2, . .     Тп) ,
для всех i от 1 до п ,      N — максимальный размер блока.
От размера шифруемого массива данных в этом случае зависит только количество шагов шифрования, но не сами шаги. Ради удобст­ва реализации размер блока практически всегда полагают постоян­ным, может быть, за исключением последнего блока данных, который может быть меньше.
По соображениям стойкости размер блока не должен значитель­но превышать размер ключа, лучше, если он будет меньше или равен ему.
Существуют два принципиально различающихся подхода к построению шифров с секретным ключом, соответственно им можно выделить два типа шифров - блочные и потоковые шифры:
1. В блочных шифрах результат зашифрования очередного бло­ка зависит только от него самого и не зависит от других блоков шиф­руемого массива данных:
Ti'       I    (Ti) .
Из этого следует, что в результате зашифрования двух одинако­вых блоков открытого текста всегда получаются идентичные блоки шифротекста.
2. В поточных или потоковых шифрах результат зашифрования
очередного блока зависит от него самого и, в общем случае, от всех предыдущих блоков массива данных:
Ti'  = Е   (Tl,  Т2,   ...   ,   Ti) .
Сюда же относится важный частный случай, когда результат за­шифрования очередного блока зависит этого блока и от его номера: Ti1 = Е  (i,Ti) .
По поводу разделения шифров на блочные и потоковые следует добавить, что в современной криптолопш указанные понятия иногда используются в близком, но несколько отличном от сказанного выше смысле - потоковыми называют только такие шифры, в которых шиф­руемый за один шаг блок имеет размер один бит или один символ тек­ста, а шифры с большим размером блока, формально относящиеся к
потоковым, причисляют к блочным.
Потоковые шифры в последнем, практическом значении этого термина, очень хорошо подходят для засекречивания асинхронного информационного потока - поступившая порция данных может быть немедленно зашифрована и отправлена в канал связи, нет необходи­мости ждать, пока наберется полный блок из нескольких битов или символов, как это было бы необходимо для блочных в том же самом
«практическом» смысле термина шифров. Если принять во внимание
требование к реализуемости криптоалгоритма устройством с конеч­ным числом возможных состояний, то наиболее общей моделью пото­ковых шифров является конечный автомат, описываемый множеством состояний входным и выходным алфавитами I и Е и правилами пе­рехода и выхода соответственно.
Множество состояний и алфавиты автомата являются конечны­ми - собственно, именно поэтому автомат и называется конечным, — а правила перехода и выхода могут быть записаны в виде двумерной таблицы и по этой причине иногда называются таблицами переходов и выходов соответственно. Автомат работает следующим образом: каждый символ, поступивший на его вход, вызывает изменение состо­яния автомата и порождение одного выходного символа. В результате входное слово преобразуется в слово точно такой же длины, состав­ленное из символов выходного алфавита.
Работа конечного автомата зависит от его начального состояния: в общем случае два идентичных автомата преобразуют одно и то же входное слово в разные выходные, если начнут свою работу с разных состояний. Для того, чтобы процедура шифрования была обратима, для шифрующего автомата должен существовать обратный ему авто­мат. Один конечный автомат является обратным другому и называет­ся его обращением в том случае, если он преобразует любую выходную
этого автомата в его входную последовательность: преобразует выходную последовательность sls2...sK первого конечно­го автомата (левый, EFA) в его входную последовательность tlt2...tK, и в силу этого является его обращением.
По вполне понятной причине сипхромосылка может передавать­ся только в открытом виде - на момент ее получения автомат расшиф­рования на принимающей стороне не готов к работе. В настоящее вре­мя одним из наиболее популярных видов потоковых шифров являет­ся шифр гаммирования, в котором соответствующий конечный авто­мат является и используется для выработки последова­тельности элементов гаммы. Для наложения гаммы на данные может быть использована любая подходящая бинарная операция. Если это операция аддитивного типа, шифр называется аддитивным, если же используется операция побитового сложения по модулю 2 - то двоич­ным аддитивным. Для двоичных данных таковой является операция побитового суммирования по модулю 2 или побитового исключающе­го ИЛИ. Кроме того, эта операция является обратной самой себе и по этой причине может использоваться как для зашифрования, так и для расшифрования данных, что позволяет реализовать обе эти процедуры в одном модуле, достигнув тем самым дополнительных преиму­ществ в экономичности.
Условием стойкости шифра гаммирования является невозмож­ность определить по известному фрагменту гаммы другие ее части или восстановить структуру порождающего ее конечного автомата. Для стороннего обладающего лишь ограниченными вычис-
лительными возможностями, выработанная гамма должна быть неот­личима от случайной последовательности.
В заключение рассмотрения темы потоковых шифров отметим, что эта область криптографии целиком базируется на теории конеч­ных автоматов - очень подробно разработанной на сегодняшний день
отрасли математики, и по этой причине считается одним из наиболее полно исследованных разделов Теперь перейдем к рас-
смотрению блочных - именно они станут темой нескольких
ближайших выпусков. В шифрах этого типа результат зашифрования каждого блока зависит только от его значения, естественно, не считая секретного ключа: Ti' = EK(Ti) .
Как следствие, при зашифровании двух одинаковых блоков дан­ных получатся идентичные блоки шифротекста. Из указанной особен­ности блочных шифров следует очевидный способ их анализа - ста­тистический. Если известен закон распределения блоков открытого текста, то проанализировав статистику блоков шифротекста, можно установить соответствие между ними. Классическим примером такого криптоанализа является история, описанная Эдгаром По в его извест­ном рассказе «Золотой жук».
Для того, чтобы исключить подобную возможность, размер бло­ка должен быть достаточно большим. Например, при размере блока в один байт анализ шифра осуществим вручную, без использования вы­числительной техники; при размере блока в 6 бит этот анализ элемен­тарно реализуется на персональной ЭВМ и занимает несколько се­кунд; при размере блока в 32 бита компьютерный анализ также осуще­ствим, хотя требует больше времени и большего необходимого объема
зашифрованных данных. При дальнейшем увеличении размера блока
статистический анализ становится все менее осуществимым на прак­тике.
Для большинства современных шифров выбрана величина бло­ка в 64 бита, для нее исчерпывающий анализ практически исключен прежде всего из-за невозможности набрать соответствующую статис­тику При еще больших размерах блока усложняется не
только криптоанализ, усложняется и сам алгоритм шифрования - вот почему неразумно увеличивать его сверх необходимого. Как мы уви­дим в следующем выпуске, для шифров очень распространенной на се­годняшний день архитектуры, называемой «сбалансированная сеть Файстеля» - balanced Feistel network, условием эффективной реали­зации в виде программы для ЭВМ является равенство половинного размера блока криптоалгоритма величине машинного слова. Именно поэтому реализация отечественного стандарта шифрования - алго­ритма ГОСТ 28147-89, шифра с 64-битовым размером блока, - для 32-битовых процессоров Intel х86 существенно эффективнее реализации этого же алгоритма для 16-битовых процессоров той же серии (естест­венно, сравнение производилось на одном и том же компьютере).
В настоящее время количество в ми-
ре - 32-битовые и по этой причине выбирать размер блока для упомя­нутой архитектуры шифров больше 64 бит совершенно бессмысленно, а с точки зрения эффективности реализации - вредно. Хотя для блоч­ных шифров с достаточно большим размером блока провести исчер­пывающий статистический анализ в общем случае невозможно, тем не
анализируя данные, легко
чие одинаковых блоков в исходных данных, что позволяет выявить стабильные паттерны, имеющиеся в них. Предположим, например, что целиком шифруется магнитный диск с информацией. На таком диске все незанятое пространство обычно заполнено фиксированными кода­ми, записанными туда при его форматировании. После шифрования на месте этого кода получатся одинаковые блоки что позволит злоумышленнику отличить незанятое пространство диска от пространства, заполненного полезными данными. Иногда это бывает неприемлемым, поэтому перед данных их очень
лезно сжимать архиваторами, что существенно снижает избыточность данных и уменьшает вероятность встретить повторяющиеся блоки.
В тех случаях, когда данные имеют физическую привязку - как в приведенном примере с шифрованием - их рекомендуется
рандомизировать - модифицировать с использованием случайных
или псевдослучайных. Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории
Такой шифр должен обладать свойствами перемешивания и рас­сеивания: ,
— рассеивание: это свойство шифра, при котором одни символ (бит) исходного текста влияет на несколько символов (битов) лжфро-
текста, оптимально - на все символы в пределах одного блока. Если данное условие выполняется, то при шифровании двух блоков данных с минимальными отличиями между ними должны получаться совер­шенно непохожие друг на друга блоки шифротекста. Точно такая же картина должна иметь место и для зависимости шифротекста от клю­ча один символ (бит) ключа должен влиять на несколько символов (битов) шифротекста;
— перемешивание: это свойство шифра скрывать зависимости между символами исходного текста и шифротекста. Если шифр доста­точно хорошо «перемешивает» биты исходного текста, то соответст­вующий шифротекст не содержит никаких статистических, и, тем бо­лее, функциональных закономерностей - опять же для стороннего на­блюдателя, обладающего лишь ограниченными вычислительными ре­сурсами.
Если шифр обладает обоими указанными свойствами в доста­точной степени, то любые изменения в блоке открытых данных приво­дят к тому, что с точки зрения наблюдателя все символы (биты) в за­шифрованном блоке получат новые значения, равновероятные в об­ласти их определения и независимые друг от друга. Так, если шифр
оперирует информацией, представленной в двоичной форме, то ин­вертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью 1/2 независимо друг от друга также поменяют свое зна­чение. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. Данное условие является обязательным для шифра рассматриваемого типа, претендующего на то, чтобы считаться хорошим.

 

На главную | Содержание | Назад | Вперёд
 
Яндекс.Метрика