Криптографические средства с древнего времени

Скачать 373.62 Kb.

Название	Криптографические средства с древнего времени
страница	8/8
Дата публикации	16.01.2015
Размер	373.62 Kb.
Тип	Документы

100-bal.ru > Информатика > Документы

1 2 3 4 5 6 7 8

Атака c известным открытым текстом

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

Атака выборочного открытого текста

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

Атака адаптивно-выбранного открытого текста

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

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

Атака выбранного зашифрованного текста

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

Атака выборного шифра

Эта атака не подразумевает, что дешифровальщик может выбирать шифр; это означает, что имеется некоторое знание относительно отношений между различными шифрами - эта - довольно неясная атака и практически не используется.

Метод "резиновой дубинки"

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

Дешифрование шифра простои замены.

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

1) В осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, при этом относительные частоты букв в различных текстах одного языка близки между собой. То же самое можно сказать и о частотах пар, троек букв открытого текста;

2) Любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении не известна.

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

1	а - 0,062	12	л - 0,035	23	ц - 0,004
2	6-0,014	13	м- 0,026	24	ч- 0,012
3	в - 0,038	14	н - 0,053	25	ш - 0,006
4	г -0,013	15	о - 0,090	26	щ - 0,003
5	д - 0,025	16	п - 0,023	27	ы- 0,016
6	е,ё - 0,072	17	р - 0,040	28	ъ,ь- 0,014
7	ж - 0,077	18	с - 0,045	29	э - 0,003
8	3-0,016	19	т - 0,Q53	30	ю - 0,006
9	и - 0,062	20	у -0,021	31	я -0,018
10	и -0,010	21	ф - 0,002	32	- 0,175
11	к - 0,28	22	х - 0,009

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

Если упорядочить буквы по убыванию вероятностей, то мы получим вариационный ряд

О,Е,А,И,Н,Т,С,Р,В,Л,К,М,Д,П,У,Я,3,Ы,Б,Ь,Г,Ч,Й,Х,Ж,Ю,Ш,Ц,Щ,Э,Ф.

Как запомнить первые 10 наиболее частых букв? Помните, как запоминают основные цвета в физике? Надо запомнить фразу Каждый охотник желает знать, где живет фазан. Первые буквы слов фразы указывают на основные цвета. В криптографии надо запомнить слово СЕНОВАЛИТР - в нем все 10 наиболее частых букв.

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

Английский язык	е- 12,75	t-9,25	г -8,50	i - 7,75	h - 7,75	о - 7,50
Французский язык	е- 17,75	а - 8,25	s-8,25	i - 7,25	n - 7,25	r-7,25
Немецкий язык	е- 18,50	п - 1 1.,50	i - 8,00	г - 7,50	s - 7,00	a - 5,00
Арабский язык	а -17,75
Греческий язык	а -14,25
Японский язык	р- 15,75
Латинский язык	а -11,00
Малайский язык	а -20,25
Санскрит	а -31,25

Частоты знаков алфавита зависят не только от языка, но и от характера текста. Так в тексте по криптографии будет повышена вероятность букв Ф, Ш (из-за часто встречающихся слов «шифр», «криптография»). В математическом тексте скорее всего будет завышена частота буквы Ф (из-за слов «функция», «функционал» и т. п.).

В стандартных текстовых файлах наиболее частым был символ «пробел», в ехе-файлах наиболее часто встречается символ 0, в текстах, написанных в текстовом процессоре ChiWriter, удобном для оформления математических текстов, на первое место вышел символ "\" - backslash .

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

.

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

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

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

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

Аналогичная картина наблюдается и для пар соседних букв (биграмм) открытого текста (наиболее частая биграмма русского открытого текста - СТ). Однако для получения устойчивой картины длина последовательности должна быть существенно больше. На сравнительно небольших отрезках открытого текста эта картина как-то смазана. Более устойчивой характеристикой биграмм является отсутствие в осмысленном тексте некоторых биграмм, как говорят, наличие запретных биграмм, имеющих вероятность, равную практически 0.

Видели ли Вы когда-нибудь в открытом тексте биграммы ЪЬ, «гласная» Ь, «пробел» Ь? Знание и использование указанных особенностей открытого текста значительно облегчает дешифрование шифра перестановки и замены.

Дешифрование шифра простой замены! Рассмотрим пример дешифрования шифра простой замены (Учебное пособие «Принципы и методы защиты информации», Проскурин Г.В.). Пусть у нас имеется следующий шифртекст.

ДОЧАЛЬ ИЬЦИО ЛИОЙО ВНЫИЮШ ХЕМВЛНХЕИ ДОСОЛЬ ЧСО ИА ТЬЖАТСР ЬАС АКЕИОЙО ДОКЩОКЗЖАЙО КПЗ РТАЩ ТПЬЧНАР ТДО-ТОУН ХЕМВОРНИЕЗ ЕИМОВЛНЯЕЕ РЮУОВ БВЕД СОЙВНМЕЧАТБОГ ТЕТСАЛЮ ЫНРЕТЕС ОС ОТОУ АИИОТСАГ ЕИМОВЛНЯЕЕ АА ЯАИИ-ОТСЕ Е РОЫЛОЦИОТСАГ РПНКАПШЯАР ДО ЫНЖУСА ТРОАГ ЕИМОВЛНЯЕЕ ДВАЦКА РТАЙО ДОКЧАВБЙАЛ УОПШХОА ВНЫИООУ ВНЫЕА РЕКОР ЫНЖЕЖНАЛОГ ЕИМОВЛНЯАА КОБЬЛАИСНПШИНЗ САПАМОИИНЗ САПАРЕЫЕОИИНЗ БОЛДШЭСАВИНЗ БНЦКЮГ РЕК ЕИМОВЛНЯЕЕ УЛААС ТРОЕ ТДАЯЕМЕЧАТБЕА ОТОУАИИОТСЕ Е ФСБ ОТОЧАИИОТСЕ ТЕПШИО РПЕЗЭС ИН РЮУОВ ЛАСОКОР ХЕМВОРНИЕЗ ЕИМОВЛНЯЕЕ УОПШХОА ЫИНЧАИЕА ЕЛАЭС ОУЪАЛЮ Е СВАУЬАЛНЗ ТБОВОТСШ ДАВАКНЧЕ ХЕМВОРНИИОГ

Работу следует начать с подсчета частот символов в шифрованном тексте.

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

Под ним стоит подписать вариационный ряд вероятностей знаков в открытом тексте.

О Е А И НТСРВЛКМДПУЯЗЫБЬГЧЙХЖЮШЦЩЭФ

При достаточно большой длине шифртекста, для того чтобы из шифрованного текста получить открытый, достаточно заменить bt на О, Ь2 на Е, Ь3 на А и т. д.

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

Что нам остается - угадывать замену. При этом мы должны все-таки учитывать статистические особенности открытого текста. В шифртексте через пробел скорее всего обозначается пробел, через букву О скорее всего обозначена О или А, через Е - О, Е, А, через А - Е, А или И и т.д.

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

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

Таблица не приводится из-за своей громоздкости, она приведена в Приложении 3.

При дешифровании без использования средств автоматизации дальше надо угадывать замену. Если присмотреться к тексту, то сделать это не очень трудно. В тексте есть слово А А из двух часто встречающихся букв. Что это может быть за слово? В русском языке нет слов ОО, ИИ, НН и т. д. Так перебирая возможные слова, мы обнаружим одно слово ЕЕ и прийдем к выводу, что буква Е была заменена на А. Очень часто в шифртексте слова кончаются биграммами ЕЕ. В русском языке типичными окончаниями являются сочетания ЕЕ, ИИ. Учитывая, что замену для буквы Е мы уже угадали, приходим к выводу, что в шифртексте буква И заменена на Е. Теперь всюду в шифртексте можно провести обратную замену. Теперь мы уже можем угадывать отдельные слова. Так, изрядно попотев, мы, как в игре «Поле чудес», в конце концов восстановим весь текст.

В колонках наиболее вероятных замен буквы, отвечающие правильным обратным заменам, должны быть обозначены как заглавные. Прочитавоткрытый текст, Вы убедитесь, что он представляет собой несколько предложений из книги Дориченко С.А. и Ященко В.В. «25 этюдов о шифрах»,М.,1994.

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

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

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