Библиографическое описание:

Чернушко М. М. Применение машины Тьюринга для реализации алгоритмов шифрования [Текст] // Технические науки: теория и практика: материалы II междунар. науч. конф. (г. Чита, январь 2014 г.). — Чита: Издательство Молодой ученый, 2014. — С. 19-22.

Введение

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

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

Структура машины Тьюринга

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

Описание: C:\Users\Makcim\Desktop\Рисунки для курсовой\Рисунок 1 лента и автомат.png

Рис. 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

Обсуждение

Социальные комментарии Cackle