Лекции по криптологии / Y16_M01_L09

Лекция 9. Статистический подход к анализу шифров замены и гаммирования.

9.1.Некоторые статистические характеристики естественных языков.

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

Основные характеристики следующие.

1. Словарный состав. Языки отличаются по словарному составу. В письменной речи некоторые слова в разных языках имеют одинаковое написание (но не обязательно один и тот же смысл). Обычно требуется небольшое количество текста, чтобы установить язык переписки.

Заметим, что для ЭВМ задача определения языка на основе короткого текста является достаточно сложной.

2. Частоты встречаемости знаков.

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

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

3. Частоты встречаемости -грамм. На их основе можно построить эффективные критерии автоматического распознавания открытого текста.

4. Статистические особенности в периодических выборках открытых текстов, а также особенности начал и окончаний слов.

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

5. Повторения слов и участков открытого текста. В данном случае важен факт наличия повторения и их взаимное расположение.

6. Статистические особенности в колонках комплекта подписанных друг под другом открытых текстов (т.н. вертикальные -граммы).

9.2. Дешифрование шифра простой замены в случае длинного сообщения.

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

2. Поиск повторяющихся фрагментов текста.

3. Определение наличия знака раздела между словами.

4. Определение языка переписки, составление списка вероятных знаков биграмм, слов. При наличии знака раздела, использовать особенности начал и окончаний слов.

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

6. Попытаться подобрать вероятное слово (стандарт). Например, цифру, артикль или предлог. Разнести вариант по тексту и проконтролировать по сочетаемости -грамм.

Частоты встречаемости знаков английского языка.

Частые Средние Редкие

E	12.31	L	4.03	B	1.62
T	9.59	D	3.65	G	1.61
A	8.05	C	3.20	V	0.93
O	7.94	U	3.10	K	0.52
N	7.19	P	2.29	Q	0.20
I	7.18	F	2.28	X	0.20
S	6.59	M	2.25	J	0.10
R	6.03	W	2.03	Z	0.09
H	5.14	Y	1.88
	70.02		24.71		5.27

9.3. Периодическая и предсказуемая гамма.

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

При периодической гамме и неравновероятном открытом тексте шифр гаммирования становится катастрофически слабым.

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

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

Пример. Пусть открытый текст зашифрован периодической гаммой. Вероятность единицы .

Шифртекст: 1110110011000100000110011010010000001101010100011001010100101110101011001000101100010110011111101111

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

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

Выпишем шифртекст в периодах 7 и 8 и подсчитаем статистику единиц по колонкам, начиная с первой.

Для периода получим значения 3,10,10,3,4,8,11, а для - 7,5,6,6,7,9,4,5. Первый период предпочтительней.

1110110	11101100
0110001	11000100
0000011	00011001
0011010	10100100
0100000	00001101
0110101	01010001
0100011	10010101
0010101	00101110
0010111	10101100
0101011	10001011
0010001	00010110
0110001	01111110
0110011	1111
1111011
11

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

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

9.4. Шифр Вернама (одноразовый шифр-блокнот).

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

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

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

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

На практике применяются последовательности гаммы, по параметрам приближающиеся к требованиям системы Г.Вернама.

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

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

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

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

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