Применение машины Тьюринга для реализации алгоритмов шифрования

Чернушко, М. М. Применение машины Тьюринга для реализации алгоритмов шифрования / М. М. Чернушко. — Текст : непосредственный // Технические науки: теория и практика : материалы II Междунар. науч. конф. (г. Чита, январь 2014 г.). — Т. 0. — Чита : Издательство Молодой ученый, 2014. — С. 19-22. — URL: https://moluch.ru/conf/tech/archive/88/4317/ (дата обращения: 26.06.2022).

В 1936 году английским математиком Аланом Мэтисоном Тьюрингом (1912–1954) была представлена абстрактная вычислительная машина, впоследствии названная «Машиной Тьюринга», которую можно считать моделью компьютера общего назначения. Она позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

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

Машина Тьюринга (МТ) состоит из двух частей — ленты и автомата. Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может меняться — в неё можно записать другой символ или стереть находящийся в ней символ.

Рис. 1. Лента и автомат

Для реализации примеров, описанных в статье, используется имитатор детерминированной машины Тьюринга (далее ИМТ), расположенный в сети Интернет по адресу «http://matinf.vsgao.com/simulator/tm.html», исходя из этого, в дальнейшем, для удобства будут использоваться обозначения, принятые в этом ИМТ.

Договоримся пустое содержимое клетки называть символом «пусто» и обозначать знаком «B». Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа «В».

Автомат — это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое; это видимая клетка, а находящийся в ней символ — видимый символ; содержимое соседних и других клеток автомат не видит. Кроме того, в каждый момент автомат находится в одном из состояний, которые будем обозначать буквой «q» с номерами: «q1», «q2» и т. п. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию (например, перемещается направо по ленте, заменяя все символы «b» на «a»), находясь в другом состоянии — другую операцию.

Автомат может выполнять три элементарных действия:

а) записывать в видимую клетку новый символ (менять содержимое других клеток автомат не может);

б) сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток автомат не может);

в) переходить в новое состояние.

Ничего другого делать автомат не умеет, поэтому все более сложные операции так или иначе должны быть сведены к этим трём элементарным действиям. [1]

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

а) записывает некоторый символ «S» в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);

б) сдвигается на одну клетку влево (обозначение — L), либо на одну клетку вправо (обозначение — R), либо остается неподвижным (обозначение — H).

в) переходит в некоторое состояние «q» (в частности, может остаться в прежнем состоянии).

Формально действия одного такта будем записывать в виде тройки: «S [L,R,H]q», где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв «L», «R» или «H». Например, такт «*Lq8» означает запись символа «*» в видимую клетку, сдвиг на одну клетку влево и переход в состояние «q8». [1]

Сама по себе МТ ничего не делает. Для того, чтобы заставить её работать, надо написать для неё программу. Для удобства эта программа записывается в виде следующей таблицы:

Пример программы для МТ в табличной форме

Слева перечисляются все состояния, в которых может находиться автомат, сверху — все символы (в том числе и «B»), которые автомат может видеть на ленте (какие именно символы и состояния указывать в таблице — определяет автор программы). На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ. В целом таблица определяет действия МТ при всех возможных сочетаниях входных символов и состояний автомата и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ — значит предъявить такую таблицу. [1] Однако, в используемом в данной статье ИМТ, программа вводится построчно, где каждая строка представляет собой такт, выполняемый в зависимости от текущего состояния автомата и входящего символа. Например, запись «1q3->2q4L» можно истолковать так: если входящий символ «1» и текущее состояние «q3», то записать в текущую клетку символ «2», перейти в состояние «q3» и сдвинуть автомат влево. При этом последовательность записи роли не играет.

До выполнения программы нужно проделать следующие предварительные действия. Во-первых, надо записать на ленту входное слово, к которому будет применена программа (в используемом ИМТ оно называется «конфигурация»). Входное слово — это конечная последовательность символов, записанных в соседних клетках ленты; внутри входного слова пустых клеток быть не должно, а слева и справа от него должны быть только пустые клетки. Во-вторых, надо установить автомат в состояние «q1» (указанное в таблице первым) и разместить его под первым символом входного слова.

После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой строки (т. к. автомат изначально находится в состоянии «q1») и того столбца, который соответствует первому символу входного слова (это необязательно левый столбец таблицы), и выполняется такт, указанный в этой ячейке. В результате автомат окажется в новой ячейке, соответствующей новому входящему символу и состоянию автомата и выполняется такт из этой ячейки. [1]

В процессе работы автомат будет перескакивать из одной клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние «q0» (в используемом в данной работе ИМТ состояние «q0» обозначается как «STOP»). Эти клетки называются клетками останова. Дойдя до любой такой клетки, МТ прекращает свою работу. [5]

Данный метод состоит в следующем. У нас есть алфавит, состоящий, к примеру, из символов «АБВГДЕ» (при этом важна последовательность символов и они не должны повторяться) и слово, состоящее из символов этого алфавита, например «ГДЕ». Нам необходимо зашифровать слово по некоторому ключу, представляющему собой целое число (для удобства будем брать числа от 1 до 9). Допустим ключ число 2. Тогда каждый символ в слове «ГДЕ» сдвигается на 2 позиции влево относительно соответствующего символа в алфавите и после шифрования представляет собой слово «ЕАБ» (если при смещении символы в алфавите закончились, то отсчет продолжается сначала алфавита). В данном примере, для наглядности, используется небольшой алфавит и однозначный код, но принцип шифрования методом одноалфавитной подстановки полностью соблюдён.

Постановка задачи. У нас есть алфавит, состоящий из символов «antrkid» (для удобства в качестве алфавита используются только значащие символы шифруемого слова, опять же на принцип работы программы это никак не влияет). Нам необходимо написать программу для ИМТ, позволяющую зашифровать слово «antarktida» по ключу 1 или 2. В данном примере входящим словом для ИМТ будет являться «1antarktida» или «2antarktida» в зависимости от ключа шифрования. (Кроме того, допустимыми будут являться любые слова, начинающиеся с 1 или 2 и состоящие из символов алфавита произвольной длинны.) На выходе на ленте мы должны получить только зашифрованное слово (не трудно определить, что это слова «ntrnkirdan» и «trktidkant» для ключей 1 и 2 соответственно).

«12antrkid» будет являться множеством допустимых входящих символов. Теперь определимся с состояниями автомата:

а) q1 — автомат определяет, по какому ключу шифруется слово, и переходит в состояние q2 или q3;

б) q2 — автомат шифрует слово по ключу 1;

в) q3 — автомат шифрует слово по ключу 2.

В табличной форме программа выглядит следующим образом (если ячейка пуста, значит попадание автомата машины в неё невозможно):

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