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

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. Периодическая и предсказуемая гамма.

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

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

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

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

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