Криптографический алгоритм DersCrypt

Sergey Derevyago, Minsk, Belarus

LVEE 2016

An original block symmetric cryptography algorithm DersCrypt is presented. Specifics of implementation is discussed, as far as reference and production implementations.

DersCrypt — это блочный симметричный криптографический алгоритм, построенный на не использовавшихся ранее принципах. Суть работы алгоритма состоит в переводе числа из одной системы счисления в другую, перестановке “цифр” и обратном переводе в исходную систему счисления.

DersCrypt обладает следующими достоинствами:

Нет ограничений на длину ключа;
Криптоалгоритм предельно прост для понимания и реализации;
Криптоалгоритм является открытым и свободным для использования.

Впервые криптоалгоритм был представлен в феврале 2004 года в виде сообщения в профильные ньюсгруппы UseNet¹. Наиболее ценное обсуждение произошло в конференции fido7.ru.crypt сети FidoNet. В апреле 2005 года увидела свет первая версия DersCrypt, заметно отличавшаяся от того, что было представлено в самом начале². Текущей является версия алгоритма 1.1.

Особенности алгоритма

Базовый алгоритм DersCrypt состоит из следующих шагов:

Текст для шифрования рассматривается как неотрицательное число $\textstyle A_1$ в некоторой системе счисления $\textstyle S_1$ по основанию $\textstyle B_1$ .
Число $\textstyle A_1$ переводится в другую систему счисления $\textstyle S_2$ по основанию $\textstyle B_2$ . Число $\textstyle B_2$ является ключом.
Цифры числа $\textstyle A_1$ в системе счисления $\textstyle S_2$ переставляются, в результате чего получается число $\textstyle A_2$ . Перестановка задается значением ключа.
Число $\textstyle A_2$ переводится в исходную систему счисления $\textstyle S_1$ .
Число $\textstyle A_2$ в системе счисления $\textstyle S_1$ и является результатом шифрования.

Сам по себе базовый алгоритм DersCrypt непригоден к практическому применению в силу существования следующих эффективных способов атаки:

Если зашифровать два числа, отличающихся только значением младшего бита, то разность зашифрованных чисел, очевидно, будет равна $\textstyle B_{2}^n$ для некоторого $\textstyle n$ .
Существует и более эффективный способ атаки: Max Alekseyev указал на то, что имея число $\textstyle A_1$ в системе счисления по основанию $\textstyle B_2$ и число $\textstyle A_2$ , полученное из $\textstyle A_1$ произвольной перестановкой цифр, разность $\textstyle A_1 - A_2$ всегда делится на $\textstyle B_2 - 1$ .

Таким образом, DersCrypt не должен сводиться к простой перестановке цифр в некоторой системе счисления. Решение достаточно очевидно: перед применением базового алгоритма, число $\textstyle A_1$ превращается в некоторое число $\textstyle A'_1$ посредством приписывания к $\textstyle A_1$ некоторого количества случайных байт слева и справа. После дешифрования приписанные байты достаточно просто отбросить, получив исходное число $\textstyle A_1$ .

В силу того, что действительно случайные байты довольно сложно получить на практике, в DersCrypt используется предварительное шифрование числа $\textstyle A_1$ базовым алгоритмом и извлечение из полученного числа $\textstyle A_2$ последовательности бит нужной длины. На самом деле, для учета значения предыдущего зашифрованного блока текста, процедура формирования псевдослучайной битовой последовательности чуть более усложнена. Ознакомиться с ней можно непосредственно по коду эталонной реализации DersCrypt, которая, благодаря детальным комментариям³, определяет сам алгоритм и предназначена для практического исследования его свойств.

Реализации алгоритма

Языком эталонной реализации выбрана Java, а исходный код оформлен исходя из упрощения понимания, а не производительности и/или простоты включения во внешние проекты.

Также имеются реализации на Java⁴ и С++⁵, предназначенные для практического использования. Об их сравнительной производительности можно судить по следующей таблице, в которой приведена скорость шифрования в килобайтах в секунду на 256-битном ключе для двух компьютеров разной архитектуры:

	Эталонная реализация	Java-реализация	C++-реализация универсальная	C++-реализация оптимизированная
Pentium4	52.5 K/s	74.2 K/s	351.8 K/s	612.7 K/s
Athlon	86.4 K/s	127.2 K/s	1149.2 K/s	1404.6 K/s

Как можно видеть, оптимизированная C++ реализация в 8-11 раз быстрее Java реализации, которая, в свою очередь, на 40-50 процентов быстрее эталонной. Судя по всему, неприемлемой производительностью Java реализации обязаны стандартному классу java.math.BigInteger, чей код никак нельзя признать оптимальным.

Исходный код реализаций алгоритма свободно распространяется с правом копирования, использования, модификации, продажи и распространения при условии сохранения сведений об авторе⁴ ⁵.