1.1.2 Математическая логика в криптографии. Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Общая схема защиты информации представлена на рисунке 2. Этап кодирования от ошибок основан на внесении в передаваемое сообщение избытка информации, достаточного для преодоления помех на линии связи. Например, допустим, передается последовательность символов типа “0” и “1”. При этом в сети связи с некоторой вероятностью могут происходить ошибки приема сигнала “0 “ вместо сигнала “1” или наоборот, тогда кодер на каждый символ ai сообщения передает пятью импульсами 00000, если ai -0 и наоборот. На приемном конце принимаемая последовательность импульсов разбивается по пять импульсов, называемая блоками. Если в принятом блоке содержится 2 и менее импульса 0, то принимается решение о том, что передавался символ ai-1. Таким образом, исходная вероятность ошибки будет значительно снижена. Более элегантные методы кодирования, которые при достаточной надежности позволяют вносить не такой большой избыток информации. Для выражения в информации требуется ввести некоторый алфавит, из которого будет состоять сообщение (конечные упорядоченные множества из этих символов). Обозначим через A – мощность выбранного алфавита. Будем также считать, что все множества информации или , что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять Log2 от числа всевозможных сообщений конечно. Тогда объем информации, падающий на один символ алфавита X=log2a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log2N=Log2As=SX.

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

Общая схема криптосистемы с секретным ключом изображена на рисунке 3. Здесь Х – открытый текст, Y- шифр текста, K – ключ шифра, R – рандомизирующая последовательность.

Рисунок 1 – Общая схема криптосистемы

Теперь рассмотрим несколько наиболее популярных методов шифрования криптосистем с секретным ключом.

Метод перестановки. В общем, виде это метод описывается так: текст разбивается на равные группы по d – символов, и в группах осуществляется одна и та же перестановка символов. Очевидно, что всевозможных ключей будет d!. Перестановку осуществляемую таким образом, иногда называют транспозицией с периодом d.

Пример 1. Пусть исходный текст имеет следующий набор символов x=x1,x2 Пусть d=5 и k=(23154), тогда x=x1x2x3x4x5| x6x7x8x9x10; y=x2x3x3x5x4|x7x6x8x10x9…

Примером такой же простой перестановки является шифр получивший название маршрут Гальмитона.

1.1.3 Математическая логика в программировании. Функция одного аргумента - это правило, ставящее соответствие любому значению, лежащему в области изменения этого аргумента (которая будет и областью определения этой функции), другую величину, лежащую в области значений функции.

Понятие функции было перенесено в языки программирования. В языке программирования, как правило, предусмотрен ряд встроенных функций, например sin, cos, sqrt и т.д. Кроме того, программист имеет возможность определять свои собственные функции. Они могут работать не только с вещественными числами, но и с различными типами данных, включающими обычно integer (целое), real (вещест­венное), boolean (булевское), character (строковое). Они могут также работать со структурами. В языках Паскаль, Алгол=68 и ПЛ/1 имеются, например, типы records (записи), arrays (массивы), lists (списки), files of records (файлы, состоящие из записей), а значениями функций могут быть указатели этих структур. Все это согласовано с понятием области определения, вне которой функция не определена. В языках программирования эта область задана обычно указанием типа данных, который является некоторым множеством величин. Так, в Паскале компилятор должен следить за тем, чтобы никакая функция не применялась к величине неподходящего типа, которая могла бы выйти за пределы области определения функции.

Функция многих аргументов. Теперь нужно обобщить определение, чтобы охватить функции многих аргументов. Для этого соберем n аргументов в упорядоченный набор, который будем рассматривать как один аргумент. Возьмем функцию вычитания diff(x.y). Трактуется ее как отображение пар <х,у> в целые числа. В виде множества упорядоченных пар ее можно записать следующим образом:

diff = {«5,3>, 2>. «6,3>, 3>, «4,5>, -1> .}

Если бы вместо этого у нас была функция четырех аргументов h(x,y,z,w), то использовали бы отображение, определенное на четверках <x,y,z,w>. Этот прием используется и в программировании. Если необходимо уменьшить количество аргументов процедуры или функции (причем все они имеют один и тот же тип), то в Фортране можно записать эти значения в массив и передать в качестве пара­метра этот массив, а не отдельные значения. В более общем случае (например, в Паскале), когда аргументам разрешается иметь различ­ные типы, можно передать в качестве параметра запись и хранить значения в виде отдельных компонент этой записи. В действительнос­ти набор, состоящий из n элементов в математике соответствует записи в программировании. Каждая из ее компонент берется из своей отдельной области, как и в случае записи. Единственное отличие состоит в том, что компонента определяется своим расположением (позицией), а не именем. Реляционная модель данных работает с множествами упорядоченных наборов, которые соответствуют файлам записей, хранящимся в машине. Также математическая логика используется и в других областях информатики – это в разработке в области моделирования и автоматизации интеллектуальных процедур – направление так называемого искусственного интеллекта.

1.2 применение математической логики

Рассмотрим применение математической логики на примере данной функции:

(1)

Эта функции включает в себя 9 действий. Разберем применение математической логики на практическом примере заданной функции на таких операциях, как построение таблицы истинности, построение полинома Жегалкина, приведение функции к конъюнктивной и дизъюнктивной формам, нахождение дифференциала от двух переменных.

1.2.1 Построение таблицы истинности. Всякая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных (то есть всевозможных наборов двоичных векторов длины n), а в правой части приведены значения функции на этих наборах. Функцию (1) можно представлять через таблицу истинности, причем все операции над переменными x и y , а именно – это конъюнкция, дизъюнкция, прямая сумма, импликация можно заменить готовыми значениями булевой функции./2/ Пример преобразования функции к числам 0 и 1 представлен в таблице 1.