Основы информатики_Савельев А.Я_Учебник_2001

9.5 ИаОе-жиость средств защиты информации

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

Правильной отправной точкой в этом случае будет нахождение длины ключевого слова. Обозначим длину ключевого слова буквой «А». Отметим также, что, когда период равен длине ключевого слова, символы текста об­ рабатываются одной буквой ключевого слова. Таким образом, весь шифро­ ванный текст можно разбить на к групп G|,G2,.,.,Gj. Каждая группа начинается с позиции / (1 < / < А) и содержит каждую А-ю букву текста, начиная с /-й буквы. Каждая из этих групп обрабатывается одним символом ключевого слова, что может бьггь представлено шифрованием при помощи одного алфавита.

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

>',.л« = ^i.^t, Ф «•/ при О S У < Af/A,

где >, J», — буква шифрованного текста из группы G,; дс^»+; — буква ис­ ходного текста из i руппы Gj; w, — /-й символ ключевого слова; ^ — номер ншюжеиия ключевого слова; Л^ — длина текста.

Подсчитаем.количество появлений одинаковых букв yj j . ,, в группе G, и, разделив это число на общее количество букв в этой группе (N/k), оп­ ределим частоты букв в группе. Сравнивая полученные частоты с частота­ ми букв русского алфавита, определим предположительные соответствия букв в группе G,. Теперь, используя свойства сложения по модулю 2, мож­ но определить возможные значения г-го символа в ключе:

f^, =>',_4„Фдг,,,„прнО<;<Л'/А.

Подсчитаем максимальное количество одинаковых символов V. при

О < /' < Njk и обозначим это число через a^.

Рхли провести указанные выше вычисления для всех /(1<!<А), то можно определить процент совпадения:

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

225

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

Дальнейшие изменения величины «Ь> должны привести к появлению периодических скачков процента совпадения. Дшна периода таких скачков равна длине ключевого слова.

Естественно, нет необходимости проводить указанные вычисления до значения А = i , если уже при меньших значениях к получены удовлетвори­ тельные результаты и длина ключевого слова найдена. В большигкгве слу­ чаев бывает достаточно обнаружения первого скачка процента совпадения.

Приведем временные оценки обработки шифрованного гекста. Обо­ значим через /^ время на вычисление процента совпадения Р^. Тогда для полной автоматической обработки текста потребуется время

r,-kt,.

Если при шифровании был добавлен циклический сдвиг (шифрование по схеме «ключ—сдвиг»), то время обработки текста и получения наилуч­ шего процента совпадения возрастет:

^«-<,..„ = » * ' * •

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

Найти два места в шифрованном тексте, где две одинаковые буквы идут в том же порядке. Такое гювторение могло произойти гго дв\м причи­ нам. Возможно, различные сочетания букв и соответствующие разные час­ ти ключевого слова случайно выразились в одинаковые сочетания букв luui в исходном тексте были повторения, которые гюпали на одинаковые част ключевого слова, и, таким образом, оказались зашифрованными дважды одним и тем же способом. Во втором случае расстояние между началами повторяющихся сочетаний букв должно быть кратно Д1нше ключевого сло­ ва. Определить, по какой из двух причин произошло гювторение данного сочетания букв, невозможно. Но если в шифрованном тексте повторяются

226

10.Методы логического проектирования

10.1.Числовое и геометрическое представление функций алгебры логики

Часто для упрощения записи функций алгебры логики вместо полного перечисления термов используют номера наборов, для которых функция принимает единичное значение. Например, функция, заданная табли­ цей 2.14, может быть записана в виде / { ^ , , х^, Jj) = v F(3, 4, 6); это означа­ ет, что функция принимает значение 1 на наборах, 1юмера которых равны 3, 4, 6. Такую форму записи называют числовой.

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

228

10 1 '•hicnoeoe и геометрическое представление функций

Р е ш е н и е . В соогветствии с определением выпишем пары соседних термов: / , и / , ; Л и Л ; / , н Л ; / з И / 4 .

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

Ответ

,Ч- .Ti^iJCi

,+Х,ХуХ, ~Х,> Х,ХуХ, + Х.Х.Х.

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

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

Герм максимального ранга принято называть 0-кубом (точкой) и обозиачагь К^.

229

10. Методы логического проектирования

Например, для /(д:,, Х;, л:,) ^ у(0, 4, 7)

/у-^-^

" Ч ^

независимая координата.

Если два 1-куба имеют общую независи­ мую компоненту и различаются только по од­ ной координате, то они образуют 2-куб.

Таким образом, для построения одномерного единичного куба берут два 0-куба (точки) и соединяют отрезком прямой. Двумерный куб (грань) получается, если вершины двух I-кубов соединить параллельными огрезками. Трехмерный куб получается при соединении соответствуюищх вер­ шин двух двумерных кубов отрезками единичной длины. Геометрическое представление будет исг!ользовано при разработке методов минимизации с использованием минимизирующих карт.

10.2. Минимизация логических функций.

Метод неопределенных коэффициентов для базиса И—ИЛИ—НЕ

На основании теоремы Жегалкина лн^ую логическую функцию можно представить в нормальной форме. Например, нусть функция /(л:,, jf^, л:,) записана в виде следующей нормальной дизъюнктивной формы (ЬЩФ):

/(JC|, Х2, Х^) = klx^ +kfx^ +^2^2 +^2^2 +^3^3 +^3^3 +^!2^1'^2 +

+ A-j'j^JfjjCT + kf2XfX2 + ^|""^|^2 + ^|'.1-^1^з +^|'з'^|^1 +k^^x^X2 + kfl^x^x^ +

где /„'"" — неопределенные коэффициенты, принимающие значение О или 1 и подбираемые так, чтобы получающаяся после этого ИДФ была мини­ мальной.

230

if +i; +*! +4' +4' +*2^4У =/з(0,1,1); .

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

!!а основании изложенного можно сформулировать следующий алго­

4.1 ?ереписагь все модифицированные уравнения.

5.Выбрать очередную строку / = ! и вычеркнуть максимально воз­ можное KOiiHMecTBO коэффициентов так, чтобы ранг остающихся членов был минимальным.

Метод пеопределе1Н1Ых коэффициентов наиболее применим для лии>юикгив1юй формы и практически непригоден для конъюнктивной формы.

23 Г

10.3. Метод Квайиа

Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности по­ глощения какой-то переменной:

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

Полученное логическое выражение ие всегда оказывается минималь­ ным. [Ьэтому исследуется возможность дальнейшего упрощения. Для это­ го составляется таблица, в строках которой записываются найденные пер­ вичные импликанты, а в столбцах указываются термы исходного уравнения. Клетки этой таблицы отмечаются в случае, если первичная импликапга входит в состав какого-либо терма. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных HMruiHKaHT, которые гюкрывают все столбцы.

Метод Квайна вьпюлняется в несколько этапов, рассмотрим его при­ менение на конкретном примере.

Пусгь необходимо минимизировать логическую функцию, заданную в

виде

/(X|. .Vj, X-^, Х^) = V(3, 4, 5, 7, 9, 1 1, 12, 13) = Х^Х2Хт^Х^ V Х^Х2ХуХ^ V

Задача реи!ае!ся в несколько этапов.

')тнп I, Нахождение первичных импликант. Прежде всего составляеюя 1аблица {1абл. 10.2) и находятся импликанты четвертого и третьего ранга. I, е. снижается ранг членов, входящих в СНДФ.

Заюм соствляется другая таблица (табл. 10.3), которая включает все lepMbi. не подвергшиеся гюглощению, а также первичные импликанты ipcii.eio painaСос1авлепие таблиц продолжается до тех пор, пока нельзя будет применить правило (10.3). В рассматриваемом примере можно дойти до первичрюй импликанты второго ранга (табл. 10.3)— ^i^^-

Первичные импликанты наименьшего ранга выделены в таблице 10.3. Э гаи 2. Расстановка меток. Составляется таблица, число строк кото­

рой равно числу нолучеипых первичных импликант, а число столбцов совнадпс! с числом минтермов СНДФ. Если в некоторый минтерм СНДФ вхо­ ди! какая-либо из первичных импликант, то на пересечении соо I ветствующего столбца и строки ставится метка (табл. 10.4).

233

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

'I абл н иа И) 3

234