В этой части я достаточно кратко опишу принцип работы самого алгоритма и мою реализацию.
Суть работы
В этом разделе будет описан алгоритм шифрования. Для его описания ответим на некоторые вопросы:
- Что мы шифруем? (входные данные)
Будем шифровать строки, а точнее каждый отдельный символ. Хотя с таким же успехом кодированию поддаются все целые числа. Можно шифровать и дробные, но из-за их особого представления в компьютере временно отбросим их.
- Что будем возвращать? (выходные данные)
Обработав входную строку, мы вернём её в зашифрованном виде. При этом длинна и кодировка строки остаются неизменными, что достаточно удобно.
А что происходит внутри? Это самое интересное! Каждый символ входной строки мы скармливаем элементарному клеточному автомату! Почему он?
- Это просто. Алгоритм работы элементарного клеточного автомата прост для понимания и реализации.
- Это быстро. Даже моя (не самая удачная) реализация работает достаточно быстро (убедимся в этом, закончив работу).
Как это происходит? Да очень просто!
- Разбиваем входную строку на символы
- Код каждого символа разбиваем на двоичные разряды
- Записываем эту вереницу единиц и нулей в поле клеточного автомата
- Просчитываем эволюцию клеточного автомата с помощью правила перехода состояний и в какой-то момент возвращаем вызывающей стороне текущее состояние поля
- Преобразуем это состояние обратно в код символа
- «Запихиваем» символ в выходную строку
Действия 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 запусков).
Но самое странное, что выдаются верные результаты! Проверял вручную, лично зашифровав некоторые числа.
Заключение
По моему, получилось достаточно хорошо и наглядно. От ошибок никуда не деться, но кто не без греха. Реализация работает верно, выполняет свою работу. Использовать её, конечно, ещё рано, многое не реализовано до конца, но я подкинул вам пищу для размышлений и надеюсь, что вскоре появятся ещё и ваши попытки реализовать данный алгоритм.
Комментарии (18)
miksoft
06.03.2017 13:34правила перехода состояний
Не увидел, а какие именно правила используются?
chistobaevAndrey
06.03.2017 16:11И вам спасибо за комментарий!
Оператор [] класса Rule вызывается в операторе () класса Field. Можете посмотреть реализацию по ссылке, ведь это и есть моя работа, которую я кратко описал в публикации. Но всё же объясню, как смогу.
Правило перехода состояний я реализовал в виде класса Rule. В его конструктор (прошу заметить, что не explicit) передаётся целое число от 0 до 255 включительно. В двоичных разрядах этого числа хранится информация о том, как изменится в следующем поколении клетка посередине при некотором случае окрестности (погуглите про Код Вольфрама, возможно и я ошибаюсь). Вот число разбивается на двоичные разряды, которые записываются во внутренний вектор класса. При этом каждый экземпляр класса Field включает свой экземпляр класса Rule, имеющий определение оператора []. Этот оператор используется в операторе () класса Field, в котором просчитывается следующее поколение клеточного автомата. При этом ему передаётся окрестность клетки, преобразованная в десятичное число. Вот так примерно Rule и используется.
Но только после написания комментария я осознал, что, возможно, нет необходимости в классе Rule. Можно заменить его ещё одним вектором в классе Field, а вышеописанные преобразования числа выполнять в конструкторе Field. Это ещё раз говорит о том, что реализация находится на стадии разработки и требует некоторых изменений и дополнений. Но она имеет право на существование, так как других попыток реализации я не нашёл. Возможно, у вас получится намного лучше, это лишь пример и его краткое описание. Хотя могли бы и почитать код, там лишь 60 строк. Ещё раз спасибо)
ppikS
06.03.2017 15:55Добавьте пожалуйста пример работы, входные параметры, данные и результат работы.
А то малость непонятно в чём профит.chistobaevAndrey
06.03.2017 16:22Я давал ссылку на github и думал, что люди протестят сами, если заинтересуются. Понял, что был не прав, в скором времени дополню публикацию небольшими тестами)
chistobaevAndrey
06.03.2017 18:19Программа находится на стадии активной разработки, поэтому описание может не совпадать с действительностью. Например, было удалено кидание исключений в классе Rule.
Прошу отнестись с пониманием.
chistobaevAndrey
06.03.2017 23:05-1Написал один комментарий, потом другой и втянулся…
Каюсь за моё невежество относительно основных терминов криптографии. Завтра перепишу текст.
haoNoQ
07.03.2017 14:38Хмм. То есть Вы шифруете строчку, применяя к ней несколько раз Wolfram rule номер такое-то.
Почти все правила необратимы. Вы не сможете расшифровать своё сообщение, даже зная правило, которым оно зашифровано. Кроме редких случаев навроде Rule 90, которое унылый XOR соседей (это где точка разбегается как треугольник Серпинского).
Более того, неясно, сколько будет коллизий (интуиция game of life подсказывает, что очень много), и насколько они будут равномерно встречаться, если мы хотим просто использовать этот алгоритм как хэш.
Если бы даже
у нас не кончился порохэтих проблем не было, правил всего 256, и перебрать их будет очень легко. Нужно будет либо прогонять очень много поколений, либо использовать правила с большим числом соседей — это к вопросу о быстродействии алгоритма.
Но за интерес к клеточным автоматам — спасибо! >_<
chistobaevAndrey
07.03.2017 14:52Дело в том, что с таким их использованием я не был знаком раньше и решил поэкспериментировать.
Насчёт необратимости знаю, но и такие алгоритмы используются.
И в вопросе о коллизиях вы правы, можно даже подсчитать, в каком правиле они реже встречаются. То есть простор для экспериментов огромный, многое можно проверить и выбрать оптимальный вариант.
Вам тоже спасибо за интерес)
HKA
15.03.2017 14:30При этом длинна и кодировка строки остаются неизменными
Вы уверены, что если я подам на вход, к примеру, UTF-8, то на выходе получу валидный UTF-8?
Но самое странное, что выдаются верные результаты
Как вы определили это, пробовали расшифровать? Как справедливо заметили выше, шифрование != хэширование. Да и хэш, длина которого совпадает с длиной исходной строки, выглядит сомнительно.chistobaevAndrey
15.03.2017 16:231) Какой тип в используете для хранения UTF-8 символа?
2) Я лично просчитал эволюцию клеточного автомата для одного из входных символов на бумаге. Потом вбил свои данные в программу и получил такой же результат.
А так же элементарные клеточные автоматы, которые на данный момент используются, необратимы. Из этого ясно, что без словаря расшифровать шифротекст не получится.HKA
15.03.2017 18:25Дело не в типе, а в том, что не любые последовательности байтов считаются валидными символами UTF-8.
Необратимо утраченные данные невозможно восстановить с помощью словаря. Шифрование: 1 -> 55, 2 -> 55. Расшифровка: 55 ->?chistobaevAndrey
15.03.2017 19:101) Похоже, что поддерживается только UTF-16 и то не точно, ведь тип unsigned char, который я использовал может иметь размер более 2 байтов (но не менее). Тогда стоит представлять символ в виде char*. Спасибо.
2) Показанные вами повторения очень часто встречаются в данном алгоритме, но из-за использования элементарных клеточных автоматов избавиться от них полностью не удастся, можно лишь подобрать номер правила перехода, когда количество совпадений будет минимальным. Поэтому, чтобы избавиться от этих ограничений, я решил использовать обратимые бинарные одномерные клеточные автоматы. Попытаюсь произвести замену так скоро, как только смогу.
ov7a
" реализация работает достаточно быстро (убедимся в этом, закончив работу)." — Где?
Хэш-функция — не алгоритм шифрования.
Вместо простыни с описанием классов из серии капитан очевидность лучше бы написали, чем ваша работа отличается от других.
На гитхабе могли бы и оставить нормальные расширения файлов.
chistobaevAndrey
Спасибо за критику!
Убрал расширения, потому что подумал, что так удобнее.
Описание классов есть описание моей реализации. Другую реализацию после длительных поисков в интернете я так и не нашёл, поэтому сравнивать мне не с чем. Можно протестить программу и сравнить с другими алгоритмами.
Не откажусь от вашей помощи.
chistobaevAndrey
Проверку добавлю, как и расширения. Извиняюсь за неудобства, ведь я не подумал о подсветке синтаксиса. Спасибо.
chistobaevAndrey
Расширения добавлены!
chistobaevAndrey
Добавил немного строк о быстродействии.