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

Введение

В 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]

Программа для машины Тьюринга

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

Таблица 1

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

S1	…	Si	…	Sn	B
q1
…
qj	S [L,R,H]q
…
qm

Слева перечисляются все состояния, в которых может находиться автомат, сверху — все символы (в том числе и «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.

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

Таблица 2

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

Состо­яние	Входящие символы
	1	2	a	n	t	r	k	i	d	B
q1	Bq2R	Bq3R
q2	nq2R	tq2R	rq2R	kq2R	iq2R	dq2R	aq2R	BSTOPL
q3	tq3R	rq3R	kq3R	iq3R	dq3R	aq3R	nq3R	BSTOPL

Обратите внимание, что после завершения работы машины, автомат будет указывать на последний символ уже зашифрованного слова (такт «STOPL»), а не на пустую клетку, сделано это исключительно из эстетических соображений. Проверить работу программы можно в ИМТ, внеся в него следующие команды: 1q1->Bq2R, 2q1->Bq3R, aq2->nq2R, nq2->tq2R, tq2->rq2R, rq2->kq2R, kq2->iq2R, iq2->dq2R, dq2->aq2R, Bq2->BSTOPL, aq3->tq3R, nq3->rq3R, tq3->kq3R, rq3->iq3R, kq3->dq3R, iq3->aq3R, dq3->nq3R, Bq3->BSTOPL.

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

Описание алгоритма симметричного шифрования методом перестановки

Данный алгоритм заключается в следующем. У нас есть слово, которое необходимо зашифровать по некоторому ключу. Ключ представляет собой последовательность чисел, первое из которых показывает, какой из символов в исходном слове является первым в зашифрованном, второй показывает, какой из символов в исходном слове является вторым в зашифрованном и т. д. Из этого следует, что длина ключа равна количеству символов в слове. К примеру, у нас есть слово «Привет», которое необходимо зашифровать по ключу «356142». Тогда зашифрованное слово примет вид «иетПвр».

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

Постановка задачи. У нас есть слово «home» его необходимо зашифровать по ключу «3421». Работа МТ выглядит при этом следующим образом. Входным словом является ключ, при этом не обязательно «3421», машина должна работать при любом сочетании этих чисел. По завершении работы на ленте должно остаться только зашифрованное слово (в данном случае слово «meoh»). При этом следует учитывать, что на пути у автомата могут встречаться уже напечатанные символы, которые следует пропускать.

Рассмотрим состояния автомата:

а) q1 — автомат определяет, какой символ необходимо напечатать, либо прекращает свою работу, если все символы напечатаны (не осталось символов, составляющих ключ);

б) q2–q5 автомат печатает соответствующий символ;

в) q6 — автомат возвращается в начало слова.

В табличной форме программа представлена в таблице 4.

Таблица 3

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

Состо­яние	Входящие символы
	1	2	3	4	h	o	m	e	B
q1	Bq2R	Bq3R	Bq4R	Bq5R	hSTOPH	oSTOPH	mSTOPH	eSTOPH
q2	2q2R	3q2R	4q2R	oq2R	mq2R	eq2R	hq6L
q3	1q3R	3q3R	4q3R	hq3R	mq3R	eq3R	oq6L
q4	1q4R	2q4R	4q4R	hq4R	oq4R	eq4R	mq6L
q5	1q5R	2q5R	3q5R	hq5R	oq5R	mq5R	eq6L
q6	1q6L	2q6L	3q6L	4q6L	hq6L	oq6L	mq6L	eq6L	Bq1R

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

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

Заключение

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

Литература:

1.                  Пильщиков В. Н., Абрамов В. Г., Вылиток А. А., Горячая И. В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) — М.: МГУ, 2006. — 47 с.

2.                  http://ru.wikipedia.org

3.                  http://www.mobi.ru

4.                  http://matinf.vsgao.com/simulator/tm.html

5.                  http://inf.1september.ru/articlef.php?ID=200600802