Идеальный алгоритм шифрования? HASH-CRYPT
Под конец школы я стал увлекаться информационной безопасностью, шифрованием, и всем подобным. Стал изучать существующие алгоритмы шифрования, начиная с шифра Цезаря и заканчивая роторами Энигмы. Узнал, что большинство алгоритмов перестановки — полная фигня, потому что частотный анализ позволяет с лёгкостью опознать исходные данные, и я захотел придумать что-то своё, что может бороться с частотным анализом, при этом являясь алгоритмом перестановки. Не знаю, зачем, не знаю, для какой цели. Никто бы не стал его использовать, да и криптостойкость наверняка была бы ужасна. Просто хочется быть радостным, что смог что-то придумать сам. Ну и на уроке английского придумал алгоритм, где на матрице надо найти соответствующую букву или байт, и определённым способом сместиться по этой матрице, выбрав другую букву или байт. После каждой буквы или байта — смещаться нужно было уже по-другому. Получилась некая Энигма. Из плюсов — одинаковый набор символов или байтов подряд (например: FFFFFFFF или 00000000) кодировались во множество непредсказуемых символов (A7105261 или 9321FDC7), а так же у алгоритма была особенность — у него были режим шифрования и расшифровки, что, в теории, усложняло определение ключа и исходных данных (потому что «дешифровка» на исходные данные тоже являлась шифрованием), иначе говоря — у алгоритма была направленность. Ещё, алгоритм можно было усложнять и изменять под свои нужны при помощи изменения выбора символа или самой таблицы. Из минусов — очень медленная скорость работы, и если данные повторяются слишком часто (например — 256 мегабайт нулей, начало .wav файла или просто структурированные данные), то становились явными повторения.
Это проблема «длины ключа». Если она не больше, чем шифруемые данные — избежать повторений не выйдет, только отсрочить за счёт усложнения алгоритма. И недавно, когда я рассказывал про этот алгоритм своему знакомому, вспоминал детали, плюсы и минусы — в голову пришла мысль:, а что, если попытаться решить и эту проблему? Сделать ключ равным длине данных? А разве такое возможно?
Я тут же догадался применять хэш-функции. Пускай она генерирует в зависимости от места в данных ещё один хэш для этого места. Тогда получается бесконечный набор хэшей — их можно использовать как ключ шифрования, явно превышающий почти любой не бесконечный набор данных!
Я начал продумывать этот новый алгоритм, и вскоре придумал это:
На вход подаётся парольная фраза и данные в виде байтов. Данные разбиваются на чанки, равные размеру хэша (У SHA-256 это 32 байта). Для каждого чанка формируется свой хэш: (Парольная фраза или хэш парольной фразы)+(Номер чанка) Затем, чанк делает XOR с этим хэшем.
Такая модель позволяет распараллеливать процесс «обработки» (из-за XOR не совсем неправильно называть процесс шифрованием или дешифрованием, поэтому я называю его «обработкой»). Например — седьмой поток процессора может обрабатывать каждый седьмой чанк из количества потоков, четвёртый поток — каждый четвёртый из количества потоков. Ещё, для ускорения, можно использовать аппаратные ускорители вычисления хэшей.
У алгоритма нет повторений в зашифрованных данных. Проверено на файле весом 2 гигабайта, полностью состоящем из букв «А». (Я даже не вижу здесь возможных вариантов с зацикливанием хэша, он тут невозможен).
Скорость шифрования, возможно, оставляет желать лучшего — 1 гигабайт за 55 секунд на одном потоке процессора с частотой 2.5 GHz, но опять же — её можно существенно ускорить, добавляя многопоточность, выбирая другие алгоритмы (SHA-128 быстрее, но требует больше чанков) и уменьшая затраты на передачу данных между основной программой и функцией.
Чтобы доказать хорошую криптостойкость алгоритма — нужно покопаться в возможных математических бэкдорах хэш-алгоритмов, потому что остальных слабых мест я пока что не вижу. Размышления о том, как можно расшифровать зашифрованные данные без знания ключа довольно сложны… В теории, если взять один чанк, перебирать XOR’ы, и получить более-менее правдивые данные, таким образом примерно узнав хэш чанка, а затем попытаться провести обратный хэш-алгоритм на этот хэш (практически невозможно, если не составить огромную таблицу для перебранных байтов), и попытаться получить что-то типа исходной строки «что-то + номер чанка», то можно узнать это «что-то», добавить другой номер чанка, хэшировать, и проверить на другом чанке. Но в теории, благодаря хэш-коллизям, совпадения можно оправдывать случайным совпадением, так как, в теории, возможен такой «основной ключ», который при обработке каждого зашифрованного чанка выдаст любой желаемый результат той же длины. (Пускай вероятность и меньше, чем что-либо в этой вселенной, но не равна нулю).
Для наглядной демонстрации, я написал программу на чистом Си и выложил в своём репозитории. Пока что написана только для Linux (лень ставить винду и настраивать всё для компиляции и тестов), требует наличие библиотеки IUP (Не понял как собрать static версию, памагите).
Разумеется, этот алгоритм очень напоминает современные алгоритмы, проверенные временем, и более быстрые, так что я не претендую на то, что этот алгоритм стоит использовать. Скорее — просто изучить ради интереса. Кстати, возможно, такой алгоритм уже существует и даже где-то используется, так что я не претендую на первооткрывательство. Я просто придумал его сам для себя, и решил написать статью об этом для людей, которые могут заинтересоваться подобным.
Если кому-то интересно — пишите, как можно улучшить или ухудшить алгоритм и реализации.
Habrahabr.ru прочитано 3309 раз
