Частотные характеристики открытых сообщений.

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

Для установления статистических закономерностей про­водилась большая серия экспериментов по оценке вероятностей появления в открытом тексте фиксированных m -грамм (для небольших значений т). Суть экспериментов состоит в подсчете чисел вхождений каждой из пm возможных m -грамм в достаточно длинных открытых текстах Т = t1t ₂... tl, составленных из букв алфавита { а1, a₂,...,a_n}. При этом просматриваются подряд идущие т- граммы текста: t1t2 t3...tm, t2t3 t4...tm+1,......tl-m+1tl-m+2...tl.

Если Q — число появлений m -граммы, в тексте T, a L — общее число подсчитанных т- грамм, то опыт показывает, что при достаточно больших L частоты Q/L дл я данной m -граммы мало отличаются друг от друга. В силу этого относительную частоту Q/L считают приближением ве­роятности P появления данной m- граммы в слу­чайно выбранном месте текста (такой подход принят при ста­тистическом определении вероятности).

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

Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов. Неравновероятность m -грамм (и даже слов) тесно связана с характерной особенностью открытого текста — наличием в нем большого числа повторений от­дельных фрагментов текста: корней, окончаний, суффиксов, слов и фраз. Так, для русского языка такими привычными фрагментами являются наиболее частые биграммы и три­граммы: СТ, НО, ЕН, ТО, НА, 0В, НИ, РА, ВО, КО, СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА.

Полезной является информация о сочетаемости букв, то есть о предпочтительных связях букв друг с другом, которую легко извлечь из таблиц частот биграмм. При анализе сочетаемости букв друг с другом следует иметь в виду зависимость появления букв в открытом тексте от значительного числа предшествующих букв. Для анализа этих закономерностей используют понятие условной вероят­ности. Наблюдения над открытыми текстами показывают, что для условных вероятностей выполняются неравенства Р(a _i1) ≠ Р(a _i1/ a _i2 ), Р(a _i1/ a _i2 ) ≠ Р(a _i1/ a _i2 a _i3 ), …..

Систематически вопрос о зависимости букв алфавита в открытом тексте от предыдущих букв исследовался извест­ным русским математиком А.А.Марковым (1856 — 1922). Он доказал, что появления букв в открытом тексте нельзя считать независимыми друг от друга. В связи с этим А. А. Марковым отмечена еще одна устойчивая закономер­ность открытых текстов, связанная с чередованием гласных и согласных букв. После Маркова зависимость появления букв текста вслед за несколькими предыдущими исследовал методами теории информации К. Шеннон. Фактически им было показа­но, в частности, что такая зависимость ощутима на глубину приблизительно в 30 знаков, после чего она практически от­сутствует.

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

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

5. Критерии на открытые сообщения.

см. вопрос 3

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

Итак, открытый текст представляет собой реализацию независимых испытаний слу­чайной величины, значениями которой являются буквы алфа­вита А = {a_l,...,a_n}, появляющиеся в соответствии с распре­делением вероятностей Р(А) = (p(a₁),…p(a_n)). Требу­ется определить, является ли случайная последовательность c₁,с₂...с_l, букв алфавита А открытым текстом или нет.

Пусть Н₀ — гипотеза, состоящая в том, что данная по­следовательность — открытый текст, Н₁ — альтернативная гипотеза. В простейшем случае последовательность c₁,с₂...с_l, можно рассматривать при гипотезе Н₁, как случайную и рав­новероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается "бессмысленная" по­следовательность знаков. В более общем случае можно счи­тать, что при гипотезе Н1, последовательность c₁,с₂...с_l пред­ставляет собой реализацию независимых испытаний некото­рой случайной величины, значениями которой являются бук­вы алфавита А = {a_l,...,a_n}, появляющиеся в соответствии с распределением вероятностей Q (А) = (q (a₁),…q(a_n)). При таких договоренностях можно применить, например, наиболее мощный критерий различения двух простых гипотез, который дает лемма Неймана-Пирсона.

В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может при­нять открытый текст за случайный набор знаков. Такая ошиб­ка обычно называется ошибкой первого рода, ее вероятность равна ά = p {Н1/Н₀}. Аналогично вводится ошибка второго рода и ее вероятность β = p {Н₀/Н1}. Эти ошибки опреде­ляют качество работы критерия. В криптографических иссле­дованиях естественно минимизировать вероятность ошибки первого рода, чтобы не "пропустить" открытый текст. Лемма Неймана—Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.

Критерии на открытый текст, использующие запретные сочетания знаков, например k -граммы подряд идущих букв, называются критериями запретных k-грамм. Они уст­роены чрезвычайно просто. Отбирается некоторое число s редких k -грамм, которые объявляются запретными. Теперь, просматривая последовательно k -грамму за k -граммой ана­лизируемой последовательности c₁,с₂...с_l, мы объявляем ее случайной, как только в ней встретится одна из запретных k -грамм, и открытым текстом в противном случае. Такие кри­терии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных k- грамм являются эффективными.

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

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

Блочный шифр состоит из двух взаимосвязанных алгоритмов: алгоритм шифрования E и алгоритм расшифрованияE−1. Входными данными служат блок размером n бит и k-битный ключ. На выходе получается n-битный зашифрованный блок. Для любого фиксированного ключа функция расшифрования является обратной к функции шифрования для любого блока M и ключа K.

Блочные шифры – последовательность возможность с повторением и чередованием основных методов, применяя к блоку/части шифротекста (как правила 8 или 16 байт). Отличается высокой криптостойкостью.

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

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

Дата добавления: 2015-12-01