Здравствуйте, дорогие жители ! В этой публикации (а, скорее всего, и цикле) я расскажу о моей реализации одного из алгоритмов шифрования. Почему о реализации? Потому что идея не нова, и утверждать то, что задумка принадлежит именно мне, нельзя. Но способ достаточно интересный, поэтому узнать о нём стоит.
В этой части я достаточно кратко опишу принцип работы самого алгоритма и мою реализацию.
Суть работы
В этом разделе будет описан алгоритм шифрования. Для его описания ответим на некоторые вопросы:
- Что мы шифруем? (входные данные)
Будем шифровать строки, а точнее каждый отдельный символ. Хотя с таким же успехом кодированию поддаются все целые числа. Можно шифровать и дробные, но из-за их особого представления в компьютере временно отбросим их.
- Что будем возвращать? (выходные данные)
Обработав входную строку, мы вернём её в зашифрованном виде. При этом длинна и кодировка строки остаются неизменными, что достаточно удобно.
А что происходит внутри? Это самое интересное! Каждый символ входной строки мы скармливаем элементарному клеточному автомату! Почему он?
- Это просто. Алгоритм работы элементарного клеточного автомата прост для понимания и реализации.
- Это быстро. Даже моя (не самая удачная) реализация работает достаточно быстро (убедимся в этом, закончив работу).
Как это происходит? Да очень просто!
- Разбиваем входную строку на символы
- Код каждого символа разбиваем на двоичные разряды
- Записываем эту вереницу единиц и нулей в поле клеточного автомата
- Просчитываем эволюцию клеточного автомата с помощью правила перехода состояний и в какой-то момент возвращаем вызывающей стороне текущее состояние поля
- Преобразуем это состояние обратно в код символа
- «Запихиваем» символ в выходную строку
Действия 2-6 повторяем для каждого символа и выходная строка готова, возвращаем её.
Реализация
Ссылку на GitHub дам в конце описания.
Для осуществления моей идеи был использован объектно-ориентированный язык программирования C++. Для наглядности и удобства все сущности, выделенные в первой части, были реализованы в виде отдельных классов. Они получили логичные названия — Field и Rule.
Класс Rule
Это вспомогательный класс, который хранит в себе информацию о правиле перехода состояний и содержит функции для работы с правилом.
Данные
Каждый экземпляр имеет лишь состояния клеток, хранящиеся в std::vector в соответствии с каждым случаем окрестности. Почему std::vector? Потому что для типа bool имеется специализация этого контейнера. При этом под каждый элемент отводится лишь 1 бит, вместо целого байта. За счёт этого количество занимаемой памяти уменьшается в 8 раз.
Функции
- Конструктор. На вход поступает константное беззнаковое целое число типа size_t. Это число проверяется на принадлежность числовому отрезку [0;255]. Если проверка пройдена успешно, то оно разбивается на двоичные разряды, сохраняемые во внутренний вектор типа bool. Иначе генерируется исключение out_of_range.
- Оператор взятия индекса. Он принимает целое беззнаковое число типа size_t. Если число входит в числовой отрезок [0;7], то возвращается элемент вектора типа bool находящийся по данному индексу. Иначе снова генерируем исключение out_of_range. Данное число есть окрестность клетки. Этой окрестности правило перехода сопоставляет состояние клетки посередине в будущем поколении.
Класс прост в использовании и понимании. Но и тут найдётся тема для дискуссий. Раз он используется только в связке с экземпляром класса Field, так почему бы не сделать его внутренним? Чёткого ответа на данный вопрос у меня не имеется. И правда, почему бы и нет? Можно сделать его приватным, так, чтобы объекты конструировались по мере необходимости. Заманчиво, но на данный момент я считаю, что он достаточно самостоятелен. Ведь можно определить заранее несколько отдельных правил перехода и кодировать с их помощью строки, которые требуют различных способов шифрования. Я не хочу лишать программистов такого удобства, поэтому в моей реализации тип Rule объявлен отдельно от типа Field.
Класс Field
Это основной тип, в котором и определены функции, непосредственно выполняющие кодирование.
Данные
- Правило перехода состояний. Экземпляр класса Rule, хранящий правило перехода состояний. Интерфейс класса описан выше.
- Текущее состояние поля. Экземпляр класса std::vector<bool>, хранящий текущее состояние всех клеток поля. Вектор инициализируется двоичными разрядами кодируемого символа в конструкторе и изменяется при вызове оператора (), в котором и происходит кодирование.
- Вспомогательное поле. Вспомогательный экземпляр класса std::vector<bool>, хранящий состояние всех клеток поля. Используется при просчёте следующего поколения клеток. Можно было бы определять его прямо в операторе (), но этот оператор используется довольно часто, поэтому практичней определить вектор отдельно.
- Размер поля. Константа типа size_t, хранящая размер поля клеточного автомата, равна 8, так как на данный момент поддерживается лишь кодировка ASCII.
Функции
- Конструктор. Принимает константную ссылку на объект типа Rule и константу типа unsigned char. Так как конструктор класса Rule не объявлен explicit, мы можем передавать вместо ссылки целое число — номер правила перехода, записанный в виде кода Вольфрама (см. ссылку в начале). Переданный символ разбивается на двоичные разряды, записываемые по порядку в вектор, который хранит текущее состояние поля.
- Оператор (). Здесь и происходит кодирование символа. Просчитывается следующее поколение (для каждой клетки смотрим её окрестность и с помощью правила перехода узнаём состояние клетки посередине в следующем поколении). Поле замкнуто в кольцо, поэтому отдельно считаем состояние клеток по краям поля. После этого поле обратно переводится в десятичную систему счисления, при этом мы получаем код символа, который и возвращаем из функции.
Немного тестов
Проверить работоспособность программы самостоятельно вы сможете по ссылке ниже. Здесь же я приведу некоторые факты о производительности, показавшиеся мне интересными. Помните, они характеризуют лишь данную программу, но ни в коем случае не сам алгоритм. Начнём!
Для зашифровки всех символов кодировки Unicode с использованием правила 110 понадобилось на моей системе 645 000 тиков или приблизительно 0.645 секунды (средние значения для 10 запусков).
Для зашифровки одного символа кодировки Unicode с использованием правила 110 понадобилось 80 тиков или приблизительно 0.00008 секунды (средние значения для 10 запусков).
Все символы Unicode с использованием всех 256 правил были зашифрованы за 133500000 тиков или приблизительно 134 секунды (средние значения для 10 запусков).
Но самое странное, что выдаются верные результаты! Проверял вручную, лично зашифровав некоторые числа.
Заключение
По моему, получилось достаточно хорошо и наглядно. От ошибок никуда не деться, но кто не без греха. Реализация работает верно, выполняет свою работу. Использовать её, конечно, ещё рано, многое не реализовано до конца, но я подкинул вам пищу для размышлений и надеюсь, что вскоре появятся ещё и ваши попытки реализовать данный алгоритм.
Автор: chistobaevAndrey
