С чего всё началось и зачем оно надо

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

Актуальность темы шифрования и расшифровки данных с помощью хеш-функции обусловлена постоянным ростом объёмов информации и требований к её безопасности в современных компьютерных системах. В цифровую эпоху защита данных стала критически важной для обеспечения конфиденциальности, целостности и подлинности информации. Хеш-функции, как неотъемлемая часть многих криптографических алгоритмов, обеспечивают быстрое и эффективное преобразование больших объёмов данных в короткие хеш-значения, используемые для проверки целостности, создания цифровых подписей и аутентификации. Особенно актуальны хеш-функции в условиях быстрого развития технологий Интернета вещей (IoT), облачных вычислений, блокчейна и криптовалют. Рост количества кибератак и нарушений конфиденциальности данных также подчёркивает необходимость надёжных алгоритмов хеширования и шифрования для защиты информационных систем.

Базовая теория и немного Википедии

Шифрование — это процесс преобразования открытой информации (plaintext) в зашифрованную (ciphertext) с использованием алгоритма и ключа. Цель — защита данных от посторонних лиц без доступа к ключу.

Основные методы шифрования:

1. Симметричное — используется один ключ для шифрования и расшифровки. Примеры: AES, DES. Преимущество — высокая скорость, но есть риск утечки ключа.

2. Асимметричное — используется пара ключей: открытый (для шифрования) и закрытый (для расшифровки). Примеры: RSA, ECC. Обеспечивает большую безопасность, но работает медленней.  

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

Шифрование и расшифровка обеспечивают:

• Конфиденциальность — защита от несанкционированного доступа.

• Целостность — данные не изменены при передаче или хранении.

• Аутентичность — подтверждение личности отправителя/получателя.

• Анонимность — скрытие личности и данных пользователя.

Свойства хеш-функций

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

1. Детерминированность — одинаковый ввод → одинаковый хеш.

2. Фиксированная длина — независимо от объёма входа.

3. Быстрота вычислений — для работы с большими данными.

4. Устойчивость к коллизиям — трудно найти разные данные с одним хешем.

5. Односторонность — невозможно восстановить исходные данные по хешу.

6. Эффект лавины — малое изменение входа сильно меняет хеш.

Работа хеш-функции:

1. Получает данные (текст, файл, пароль и т. д.).

2. Обрабатывает их через математические операции.

3. Выдаёт фиксированное хеш-значение, представляющее входные данные.

Описания работы алгоритма

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

Основная идея

Основная идея шифрования базируется на нахождении такого хеша, который при соединении с частью открытого ключа и повторном хешировании даст новый хеш, который будет в определённом месте иметь часть открытых данных. В данном случае это будет начало хеша. Это значит, что нам сначала нужно сгенерировать случайный набор данных, длина которого будет равна длине сообщения, которое будет открытым ключом или шифротекстом и которое можно открыто передавать. Дальше мы должны найти список хешей, который будет закрытым ключом, в количестве, равном длине сообщения — на каждый символ текста свой хеш, который при расшифровке сообщения будет соединяться с определённой частью шифротекста. Каждый символ можно представить в байтовом виде — числом от 0 до 255, то есть 00–ff, если в hex-формате. Поэтому каждый символ (байт) шифруется двумя хешами — так наиболее быстро.

Выбор хеш-функции

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

Шифрование

Итак, перед нами текст, который нужно зашифровать, пусть это будет строка "Secret data". Для начала нужно сгенерировать случайную последовательность такой же длины, пусть это будет строка "Yuh6Gfhh8jC", причём в ней могут быть как числа, так и буквы верхнего и нижнего регистра. Дальше обе строки нужно представить в шестнадцатеричном формате (0xFF), дальше — hex, переводим и получаем следующее: "Secret data" → "5365637265742064617461", "Yuh6Gfhh8jC" → "5975683647666868386a43". Эту строку уже можно передавать — она является открытой частью шифрования. Дальше — самое интересное: нужно найти хеши. Для этого будем генерировать случайный набор из 8 байт, так как каждый байт в hex-формате представляется двумя символами, то на выходе получаем случайную hex-строку длиной 16 символов. Генерация строки для хеширования более 8 байт может привести к снижению производительности, с одной стороны, с другой — к повышению криптостойкости, так как у нас получается больший набор вариантов строк, которые можно использовать для генерации хешей, но пока для иллюстрации этого достаточно. Итак, берём первый символ из нашей строки шифротекста "5" и соединяем со случайно сгенерированными 8 байтами в hex-формате (пусть это будет следующая строка c135dc43589da553) — получается 5c135dc43589da553. Хешируем алгоритмом, выбранным ранее (xxHash), и получаем следующий хеш этой строки: 87a0552aa9ee4789. Видим, что на первом месте стоит 8, а нам нужно, чтобы было 5 (первый символ из 5365637265742064617461), поэтому продолжаем дальше генерировать байты и искать нужный хеш — по моим наблюдениям, в среднем для этого нужно около 10 попыток. Когда мы нашли нужный хеш, в нашем случае это будет daa41b6a5a06a744. Дальше возьмём следующий символ из строки 5975683647666868386a43 — это 9, нужный хеш 6d6adcbc4d769946 и так далее. На этом этапе мы зашифровали первую букву из нашего секретного сообщения Secret data, поскольку, напоминаю, что мы переводили байтовую строку в hex, а символ S в таком формате будет выглядеть как 53. Дальше по аналогии делаем это со всеми остальными символами. На выходе получим такой список хешей (секретный ключ).

Эту часть нужно держать в секрете — публичный ключ: Yuh6Gfhh8jC. Готово! Мы зашифровали сообщение "Secret data".

Разшифрование

Эта часть будет уже проще. Всё, что нам нужно сделать — это поочерёдно брать символы открытого ключа, соединять с соответствующим хешем из закрытого ключа, повторно хешировать и получить зашифрованное сообщение. Приступим. Первый символ открытого ключа — Y, но помним, что он кодируется в hex, поэтому будет 59. Нам нужна 5, первый хеш — daa41b6a5a06a744. Получаем входную строку для хеша: daa41b6a5a06a7445 (добавляем 5 в конец), хешируем и получаем вот такой выходной хеш: 5c5fb79952915a32. Видим, что на первом месте стоит символ 5 — хорошо! Давайте сделаем то же с 9 и хешем 6d6adcbc4d769946: добавляем 9 в конец — 6d6adcbc4d7699469 и также хешируем. Получаем: 3f8f00ac6fb63a2b, первый символ — 3. Итак, у нас есть строка "53", или символ S, если перевести её из байтового представления — это то, что мы и хотели получить: первая буква нашего зашифрованного сообщения Secret data! Поздравляю, всё получилось! Остальную работу пусть проделает уже бездушная машина.

Тестирование

А что по скорости?

Что ж, наверняка вас интересует скорость работы такого метода. Что ж, давайте проверим. Ссылку на код оставлю внизу, но для начала давайте немного улучшим код. Во-первых, сделаем хеш-таблицу и сжатие данных. Первое нужно для кеширования ранее найденных результатов, сохранения их и повторного использования. Второе — это сжатие данных: сжимать данные нужно, чтобы уменьшить длину сообщения и, соответственно, не только сократить время выполнения шифрования, но и уменьшить размер ключей. Чем короче сообщение — тем меньше нужно будет хешей. Для сжатия возьмём также быстрый алгоритм LZ4 и библиотеку для Python — py-lz4framed. RSA нам не конкурент, поэтому сразу возьмём быструю симметричную классику в виде AES и DES. Шифровать будем случайные байты, сгенерированные с помощью модуля os и функции urandom, размером 1 КБ, 100 КБ, 1 МБ, 20 МБ, 100 МБ. Запускаю я это всё на своём домашнем компьютере на Windows 10 с процессором Intel Core i7-11700F. Тестирование будет проходить со сжатием и без — для моего алгоритма — и с выводом следующей информации: название алгоритма и режим (только для моего), общее время в секундах, скорость обработки данных в МБ/сек и размер данных тоже в МБ.

И что мы видим? AES и DES значительно быстрее — оно и не удивительно. Средняя скорость моего алгоритма — 4.5 МБ/с, что при сжатии, что без него. Но это и понятно, поскольку данные не сжимаются. Также обратите внимание, что на выходе получается всегда в два раза больший файл — как уже говорил, это связано с тем, что каждый байт шифруется двумя хешами. Но ещё есть шанс на данных, которые хорошо сжимаются. Кто-то может посчитать, что это нечестно, так как для AES и DES сжатие не применяется. Возможно, в какой-то мере это и так, но всё же у них нет встроенного сжатия, а у моего алгоритма оно есть — и это плюс. Теперь возьмём строку, например, "Hello World" и повторим её миллион раз — посмотрим, какие будут результаты теперь.

Другое дело — добились при определённых данных скорости шифрования в 800 МБ/с, или 6.4 Гбит/с (для крутости звучания), и обогнали как AES, так и DES. На другие строчки не смотрим — они в рекламные заголовки всё равно не попадут. Так что да, именно так и работает маркетинг и реклама. А если серьёзно, то видно, что можно шифровать этим алгоритмом данные, которые хорошо сжимаются, или использовать его там, где скорость не критична.

Это вообще безопасно?

Да, и на это есть две причины. Первая — это то, что хеши являются закрытым ключом. Открытая часть — это, по сути, случайный набор байт, никак не связанный с шифруемыми данными. Вторая — это очень низкая вероятность подбора при условии, что сообщение достаточно длинное (хотя бы 100 байт). Поскольку взломать хеш невозможно, остаётся только подбор, но даже при этом непонятно, какой именно из полученных ответов правильный. Из потенциальных уязвимостей можно выделить то, что злоумышленнику видна длина сообщения. Но это также можно частично решить, генерируя в публичном ключе дополнительную последовательность случайной длины — что, кстати, уже реализовано.

Какие есть минусы?

Конечно, как и у любого алгоритма, не обходится без минусов. Первый — это очень большой размер ключей, особенно секретного: он по размеру минимум равен длине шифруемого сообщения, что может создавать неудобства. Второй — это не слишком высокая скорость: для скоростного шифрования трафика алгоритм не подойдёт, хоть он и хорошо параллелится. Также интересный факт — основное время тратится не на поиск хешей, а на прохождение по данным и создание секретного ключа.

Перспективы

Если немного доработать алгоритм так, чтобы открытым ключом были хеши, он станет более универсальным — но это не главное. Что действительно важно — так это то, что поиск хешей, как минимум теоретически, можно перенести на GPU. Как показал майнинг, это может быть очень эффективно. Если кто-то сумеет реализовать это, то скорости шифрования могут многократно возрасти — и, думаю, без проблем обгонят AES и DES.

Заключение

Итак, идея алгоритма показана и рассказана, протестировали скорость, сделали выводы (каждый для себя) — и на этом можно расходиться.

Код