Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)
.pdfI
131
должны передать друг другу секретную информацию, то им необходимо зара нее договориться о ключе, причем сделать это нужно так, чтобы ключ был известен только им и больше никому. Для решения этой проблемы в шенно новской модели шифра предусмотрено наличие секретного канала связи, с помощью которого пользователи могут передавать ключи.
Классическая модель криптографической системы.
Алгебраическая модель шифра по К. Шеннону представляет собой (см. параграф 1,3) трехосновную алгебру А=(Х,К,У,1), где Х,К,У - конечные множества, которые названы множеством открытых текстов хеХ, множест
вом ключей К, множеством шифрованых текстов уеУ, соответственно; Г- функция шифрования, Г: ХхК—>У, обладающая свойством: при любом х^К отображение X—>У, Гх(х)=Г(х,х) - инъективно. Последнее условие К. Шен нона отражает возможность однозначного расшифрования шифрованного те кста. Как правило, при таком определении шифра обычно дополнительно считают, что функция Р - сюрьектина. В данной модели считается, что при дешифровании противник знает шифр А=(Х9К9У91)9однако использован ный при зашифровании ключ ему неизвестен. Таким образом, модель
5*
132
Шеннона предназначена для описания шифров с симметричным ключом (ши фров с неизвестным ключом шифрования).
Уравнение шифрования записывается в виде:
Г(х,Х)=У, или Гх(х)=у, или хх=у.
Уравнение расшифрования записывается в виде:
*х'(у)=х, или х''у=х- Достоинством данной модели шифра является ее универсальность.
Она описывает практически все известные шифры с симметричным ключом.
Недостатки математической модели заключаются в следующем.
1)Шифры с ассиметричным ключом (шифры с открытым ключом) этой моделью не покрываются.
2)Даже при моделировании шифров с симметричным ключом отобра
жение Г*'1 задано не вполне корректно. Если элементу не принадлежит мно
жеству Гх(Х)={у: у=Гх(х), хеХ }, то значение Гх''(у) не определено.
3) Затруднительно определить понятия'«истинный» и «ложный» ключ при дешифровании методом тотального перебора ключей. Действительно, ес ли Г(х,х)=Дх,х ), где х - ключ шифрования, а % - опробуемый ключ, то как называть ключ истинным или ложным?
3)Модель не учитывает наличие канала связи с помехами. Если прои зошло искажение передаваемого шифрованного текста у=Г(х,х) и на прием пришло сообщение у', то значение ?х '(У ) может быть не определено по при чине того, что у' не принадлежит Гх(Х), более того: это значение может не принадлежать даже У.
4)Содержательная трактовка множества X в некоторых случаях вызы вает затруднение. По определению, это множество «текстов» х, для которых
определено значение Дх,х) при любом х^К, и они названы открытыми текс тами. Но тексты, которые могут быть зашифрованы, в общем случае делятся, в свою очередь на «содержательные» (это подмножество ХссХ ) и «бессодер жательные» («хаотические», это множество Х\ХС). Критерий истинности де шифрования, например, методом опробования ключей Xе К, обычно строится в проверке условия Гх''(у)еХс (критерий на содержательный текст). Если Х=Хс (шифруются только содержательные текста), то критерий вырождается в кри терий: значение Гх_1(у) определено или нет. Приведенные соображения говорят
о целесообразности наряду с множеством X ввести в модель и его подмножес тво Хс содержательных текстов.
133
Алгебраическая обобщенная модель шифра.
Целью данного пункта является описание новой модели шифра, уточ няющей модели К.Шеннона, Диффи и Хелмана и свободной от указанных выше недостатков. Основная концептуальная идея построения такой модели, на наш взгляд, естественна и очевидна. Она состоит во введении шифра шиф рования и шифра расшифрования, совокупность которых и составляет алгеб раическую модель шифров.
Шифром зашифрования (алгеброй зашифрования) назовем алгебру
АШ=(Х,ХС;КШ,У,УС,Ц, где ХссХ , {: ХхКш-»У - сюрьективное отображение, причем для каждого х^Кш отображение Гх:Х—»У, Гх(х)=Г(х,х) инъективно, а Ус^ХсхКщ). Множество Хс трактуется как подмножество всех содержатель ных текстов из множества «открытых текстов» X. Последнее множество сос тоит из текстов х, которые могут быть зашифрованы шифром, то есть тех х, для которых определено значение Гх(х) для всех %еКш. Введение подмножес тва Хсс:Х, как множества содержательных текстов, позволяет корректно вво дить критерии на содержательные тексты.
Таким образом, шифр зашифрования есть некоторое уточнение моде ли шифра Шеннна А=(Х,КШ,У,Ц.
Шифром расшифрования (алгеброй расшифрования) для Ашназовем алгебру Ар=(У',Кр,Х'Р), где УсУ', ХеХ', Р: У'хКр—>Х' - сюрьективное отоб ражение, для которого выполняются следующие условия:
1)существует биекция ср: Кш—>КР;
2)для любых хеХ, %еКшиз условия Г(х,х)=у вытекает Р(у,ф(х))=х.
При отсутствии искажений в канале связи функция расшифрования Р полностью определена на всем множестве УхКр.
Введение множества V' (а точнее, У'\У) обеспечивает возможность описания реакции приемной стороны на поступление искаженного шифро ванного сообщения у' <2У.
Введение множества Х'\Х обеспечивает возможность описания ре зультата расшифрования приемной стороной искаженного шифрованного со общения у'ёУ.
Отметим, что в определении шифра расшифрования не содержится требований инъективности функции Р по переменной к<Е Кр.
Алгебраической обобщенной моделью шифра назовем тройку (Аш,Ар, ср). Отметим следующие положительные свойства этой модели.
1 кВозможность моделирования шифров с асимметричным ключом. Здесь учитываются следующие соображения:
134
-ключ %еКшнесекретен, а ключ к-ф(х)бКр является секретным;
-определение значения к связано с решением сложных проблем;
-синтез пар ключей (к, х ) проводится достаточно просто.
Заметим, что здесь проявляется возможность классификации шифров по параметру сложности вычисления значения ср(х) ключа расшифрования,
что определяет основной параметр криптографической стойкости шифров с ассиметричным кдючом.
2. Возможность моделирования шифров с симметричным ключом.
Ниже используется как эта обобщенная модель шифра, так и модель шифра по К. Шеннону.
ГЛАВА 2. ДЕШИФРОВАНИЕ ИСТОРИЧЕСКИХ ШИФРОВ
Параграф 2.1 Дешифрование шифра простой замены, переста
новки и некоторых шифров гаммирования (/Про/)
В параграфе 3.2 мы введем математические модели открытых текстов, используемые при криптографичесом анализе шифров, а также укажем неко торые частотные свойства открытых текстов. В следующем пункте мы ис пользуем некоторые из этих свойств и акцентируем внимание на вероятност но-статистических закономерностях, присутствующих в открытом тексте, ко торые используются при дешифровании шифров простой замены и переста новки.
Устойчивые закономерности открытого текста и их использова ние при дешифровании шифров простой замены и перестановки. Воз
можность дешифрования какого либо шифра в значительной мере зависит от того, в какой степени криптографические преобразования разрушают вероят ностно-статистические закономерности, присутствующие в открытом тексте. К наиболее устойчивым закономерностям открытого сообщения относятся следующие.
1) В осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, при этом относительные частоты букв в раз личных текстах одного языка близки между собой. То же самое можно сказать и о частотах пар, троек букв открытого текста;
I
135
2) Любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении не известна.
В приводимой ниже таблицы указаны относительные частоты букв
алфавита русского языка. |
|
|
|
|
|
|
1 |
а - 0,062 |
12 |
л - 0,035 |
23 |
ц - 0,004 |
|
2 |
б - 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 |
з-0,016 |
19 |
т - 0,053 |
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 |
|
|
|
Подобные таблицы приводятся в разных книгах. Они получены на ос нове подсчетов частот на больших объемах открытого текста. Учитывая, что для экспериментов берется различный исходный материал, значения вероят ностей несколько отличаются между собой.
Если упорядочить буквы по убыванию вероятностей, то мы получим вариационный ряд
'0,Е,А,И,Н,Т,С,Р,В,Л,К,М,Д,П,У,Я,3,Ы,Б,Ь,Г,Ч,Й,Х,Ж,Ю,Ш,Ц,Щ,Э,Ф.
Как запомнить первые 10 наиболее частых букв? Помните, как запо минают основные цвета в физике? Надо запомнить фразу Каждый охотник желает знать, где живет фазан. Первые буквы слов фразы указывают на основные цвета. В криптографии надо запомнить слово СЕНОВАЛИТР - в нем все 10 наиболее частых букв.
Частотная диаграмма, конечно, зависит от языка. В нижеследующей таб лице приводятся в процентах относительные частоты наиболее употребляе мых букв некоторых языков.
Английский язык |
е - |
12,75 |
1 - 9,25 |
г -8,50 |
Французский язык |
е - |
17,75 |
а - 8,25 |
5-8,25 |
Немецкий язык |
е - |
18,50 |
п - 11,50 |
1 - 8,00 |
Арабский язык |
а -17,75 |
|
|
|
1 - 7,75
1 - 7,25
1| |
о |
Ъ-. |
|
* |
|
Ь - 7,75
п - 7,25
8 - 7,00
1о |
о |
п |
«п |
г- 7,25
а- 5,00
136
Греческий язык |
а -14,25 |
Японский язык |
р - 15,75 |
Латинский язык |
а - 11,00 |
Малайский язык |
а - 20,25 |
Санскрит |
а -31,25 |
Частоты знаков алфавита зависят не только от языка, но и от характера текста. Так в тексте по криптографии будет повышена вероятность букв Ф, Ш (из-за часто встречающихся слов «шифр», «криптография»), В математиче ском тексте скорее всего будет завышена частота буквы Ф (из-за слов «функ ция», «функционал» и т. п.).
В стандартных текстовых файлах наиболее частым был символ «про бел», в ехе-файлах наиболее часто встречается символ 0, в текстах, написан ных в текстовом процессоре СЫ\Уп1ег, удобном для оформления математи
ческих текстов, на первое место вышел символ “\” - ЪаскзкзЬ .
Частотная диаграмма является устойчивой характеристикой текста. Из теории вероятностей следует, что при достаточно слабых ограничениях на вероятностные свойства случайного процесса справедлив закон больших чи сел, т. е. относительные частоты у к знаков сходятся по вероятности к значе
ниям их вероятностей р :
Р < А ^ ~ Р к \> О — г-Ю .
Это верно для последовательности независимых испытаний, для ко нечной регулярной однородной цепи Маркова. Эксперименты показывают, что это верно и для открытых текстов.
С позиций современной криптографии шифры перестановки и простой замены обладают существенным недостатком - они не полностью разрушают вероятностно-статистические свойства, имеющиеся в открытом сообщении.
При дешифровании текста, зашифрованного шифром простой замены,
'используют частотные характеристики открытого текста. Именно, если под считать частоты встречаемости знаков в шифрованном тексте, упорядочить их по убыванию и сравнить с вариационным рядом вероятностей открытого тек ста, то эти две последовательности будут близки. Скорее всего на первом мес те окажется пробел, далее будут следовать буквы О, Е, А, И.
Конечно, если текст не очень длинный, то не обязательно полное сов падение. Может оказаться на втором месте О, а на третьем Е, но в любом слу чае в первых и вторых рядах одинаковые буквы будут располагаться недале ко друг от друга, и чем ближе к началу (чем больше вероятность знаков), тем меньше будет расстояние между знаками.
137
Аналогичная картина наблюдается и для пар соседних букв (биграмм) открытого текста (наиболее частая биграмма русского открытого текста - СТ). Однако для получения устойчивой картины длина последовательности долж на быть существенно больше. На сравнительно небольших отрезках открыто го текста эта картина как-то смазана. Более устойчивой характеристикой би грамм является отсутствие в осмысленном тексте некоторых биграмм, как го ворят, наличие запретных биграмм, имеющих вероятность, равную практиче ски 0.
Видели ли Вы когда-нибудь в открытом тексте биграммы ЪЬ, «глас ная» Ь, «пробел» Ь? Знание и использование указанных особенностей откры того текста значительно облегчает дешифрование шифра перестановки и за мены.
Дешифрование шифра простой замены. Рассмотрим пример дешифро вания шифра простой замены (Учебное пособие «Принципы и методы защиты информации», Проскурин Г.В.). Пусть у нас имеется следующий шифртекст.
ДОЧАЛЬ ИЬЦИО ЛИОЙО ВНЫИЮШ ХЕМВЛНХЕИ ДОСОЛЬ ЧСО ИА ТЬЖАТСР БАС АКЕИОЙО ДОКЩОКЗЖАЙО КПЗ РТАЩ ТПЬЧНАР ТДОТОУН ХЕМВОРНИЕЗ ЕИМОВЛНЯЕЕ РЮУОВ БВЕД СОЙВНМЕЧАТБОГ ТЕТСДЛЮ ЫНРЕТЕС ОС ОТОУ АИИОТСАГ ЕИМОВЛНЯЕЕ АА ЯАИИОТСЕ Е РОЫЛОЦИОТСАГ РПНКАПШЯАР ДО ЫНЖУСА ТРОАГ ЕИ МОВЛНЯЕЕ ДВАЦКА РТАЙО ДОКЧАВБИАЛ УОПШХОА ВНЫИООУ ВНЫЕА РЕКОР ЫНЖЕЖНАЛОГ ЕИМОВЛНЯАА КОБЬЛАИСНПШИНЗ САПАМОИИНЗ САПАРЕЫЕОИИНЗ БОЛДШЭСАВИНЗ БНЦЮОГ РЕК ЕИМОВЛНЯЕЕ УЛААС ТРОЕ ТДАЯЕМЕЧАТБЕА ОТОУАИИОТСЕ Е ФСБ ОТОЧАИИОТСЕ ТЕПШИО РПЕЗЭС ИН РЮУОВ ЛАСОКОР ХЕМВОРНИЕЗ ЕИМОВЛНЯЕЕ УОПШХОА ЫИНЧАИЕА ЕЛАЭС ОУЪАЛЮ Е СВАУЬАЛНЗ ТБОВОТСШ ДАВАКНЧЕ ХЕМВОРНИИОГ
Работу следует начать с подсчета частот символов в шифрованном тексте. После того как проведен подсчет, упорядочим символы по убыванию
частот.
Ь [ Ь г Ъ з 6 4 6 5 ...............
Под ним стоит подписать вариационный ряд вероятностей знаков в открытом тексте.
О Е А И Н Т С Р В Л К МД П У Я З ЫБ Ь Г Ч Й Х ЖЮШЦ ЩЭ Ф
138
При достаточно большой длине шифртекста, для того чтобы из шиф рованного текста получить открытый, достаточно заменить 61 на О, Ь2 на Е,
Ьзна А и т. д.
По крайней мере такая ситуация будет иметь место для наиболее веро ятных букв. У нас материала недостаточно. Посмотрев на шифртёкст после такой замены, Вы видите, что он не читается, - значит, материала действи тельно мало.
Что нам остается - угадывать замену. При этом мы должны все-таки учитывать статистические особенности открытого текста. В шифртексте через пробел скорее всего обозначается пробел, через букву О скорее всего обрзначена О или А, через Е - О, Е, А, через А - Е, А или И и т.д.
Можно рекомендовать выписать шифртекст, а под ним в колонку наиболее вероятные замены для этих букв. В нашем примере замена подобра на таким образом, что буква алфавита заменена как раз на наиболее вероятное для нее обозначение. Поэтому сам шифртекст в данном примере выписывать нет необходимости. Он совпадает со средней строкой последовательности ко лонок наиболее вероятных замен.
Чем реже встречается буква - тем большей глубины надо брать колон ку, чтобы была уверенность, что в колонке содержится знак открытого тек ста. В нашем случае колонки взяты одинаковой глубиной в 5 символов, но выписаны они только для наиболее частых букв.
Таблица не приводится из-за своей громоздкости, она приведена в Приложении 3.
При дешифровании без использования средств автоматизации дальше надо угадывать замену. Если присмотреться к тексту, то сделать это не очень трудно. В тексте есть слово АА из двух часто встречающихся букв. Что это может быть за слово? В русском языке нет слов ОО, ИИ, НИ и т. д. Так пере бирая возможные слова, мы обнаружим одно слово ЕЕ и прийдем к выводу, что буква Е была заменена на А. Очень часто в шифртексте слова кончаются биграммами ЕЕ. В русском языке типичными окончаниями являются сочета ния ЕЕ; ИИ. Учитывая, что замену для буквы Е мы уже угадали, приходим к выводу, что в шифртексте буква И заменена на Е. Теперь всюду в шифртексте можно провести обратную замену. Теперь мы уже можем угадывать отдель ные слова. Так, изрядно попотев, мы, как в игре «Поле чудес», в конце концов восстановим весь текст.
В колонках наиболее вероятных замен буквы, отвечающие прайильным обратным заменам, должны быть обозначены как заглавные. Прочитав открытый текст, Вы убедитесь, что он представляет собой несколько предло жений из книги Дориченко С.А. и Ященко В.В. «25 этюдов о шифрах», М., 1994.
139
Для дешифрования в автоматизированном режиме прежде всего цадо завести в память компьютера словарь русского языка.
Программа дешифрования должна, просматривая шифртекст, осущес твлять пробные обратные замены, предполагая, что на данном фиксированном месте в открытом тексте находилось проверяемое слово. После каждой заме ны программа частично восстанавливает ключевую подстановку, частично расшифровывает текст и отсеивает вариант подстановки, если в каком-то мес те восстановленного текста оказывается буквосочетание, которое не может бьггь в открытом тексте. После восстановления некоторого числа замен в тек сте появляются участки, в которых определено значительное число букв. Ос тавшиеся буквы подбираются путем перебора словаря и подстановки в текст слов, которые не противоречат восстановленным ранее заменам.
Следует отметить, что практические навыки по дешифрованию шифра простой замены можно получить лишь после проведения самостоятельных опытов по дешифрованию.
Дешифрование шифра перестановки. Для восстановления открыто
го текста шифра перестановки нам необходимо переставить колонки таким образом, чтобы в строках появился осмысленный текст.
Рассмотрим пример дешифрования шифра перестановки восьми столбцов (Учебное пособие «Принципы и методы защиты информации», Про скурин Г.В.). Пусть шифртекст имеет вид
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
п |
а |
я |
|
в |
|
и |
м |
о |
ч |
ш |
г |
|
У |
|
е |
е |
б |
ж |
л |
О |
е |
|
о |
м |
|
ч |
|
т |
о |
я |
|
|
е |
г |
е |
3 |
у |
с |
щ |
|
а |
к |
ь |
а |
т |
т |
|
я |
Р |
е |
|
е |
п |
|
ь |
О |
ю |
3 |
в |
а |
н |
в |
|
й |
а |
в |
е |
ш |
л |
|
|
|
е |
е |
я |
м |
|
п |
н |
ь |
Р |
Р |
н |
3 |
е |
е |
е |
3 |
а |
м |
а |
н |
|
а |
к |
ч |
с |
т |
а |
|
ь |
а |
н |
О |
я |
л |
м |
|
а |
л |
|
О |
ь |
ч |
X |
т |
а |
т |
|
|
|
|
|
140 |
|
|
|
В |
|
е |
0 |
а |
л |
е |
п |
0 |
е |
Р |
м |
т |
ь |
е |
|
Д |
с |
г |
ы |
|
0 |
а |
т |
е |
б |
в |
н |
|
ы |
|
|
|
а |
У |
и |
н |
3 |
н |
л |
|
г |
и |
а |
0 |
к |
к |
Д |
|
а |
0 |
б |
Д |
г |
н |
|
|
ж |
а |
У |
е |
д |
я |
Д |
X |
л |
и |
|
е |
м |
0 |
а |
к |
Р |
т |
д |
|
ь |
0 |
е |
|
ь |
X |
в |
т |
0 |
н |
ю |
Р |
л |
е |
|
е |
д |
а |
|
Р |
|
3 |
е |
в |
|
е |
д |
ш |
|
в |
а |
е |
н |
е |
н |
т |
и |
й |
е |
, в |
|
|
Д |
|
|
в |
|
с |
д |
|
|
Сопоставим перестановке столбцов таблицу 8x8, при этом поставим на пересечении 1-той строки и >ого столбца единицу, если >ая колонка после обратной перестановки должна следовать за 1-ой. Наша задача восстановить
таблицу, отвечающую правильной перестановке столбцов.
Давайте теперь попарно пристраивать один столбец к другому. Если при этом в некоторых строках появляются запретные биграммы, то столбцы не могут в открытом тексте следовать друтза другом, и соответствующая кле точка зачеркиваются. В нашем примере 6-ой столбец не может следовать за
4-ым, т. к. иначе в тексте в первой строке будет подряд два пробела. Посмот рим, например, 6-ую строку. Если бы 4-ый столбец следовал за 1-ым, то в тек
сте были бы слова, начинающиеся с Ь. После просмотра всех строк мы полу
чим таблицу. |
|
|
|
4 |
5 |
|
|
. |
|
1 |
2 |
3 |
6 |
7 |
8 |
||
1 |
X |
X |
|
X |
X |
X |
|
X |
2 |
|
X |
|
X |
|
X |
|
X |
3 |
|
|
X |
|
|
|
|
|
4 |
X |
X |
|
X |
|
X |
X |
X |
5 |
X |
|
|
|
X |
X |
X |
X |
6 |
X |
X |
|
X |
|
X |
X |
|
7 |
X |
|
|
X |
X |
X |
X |
X |
8 |
X |
X |
|
|
X |
X |
X |
X |