Szabad szoftvert használók és fejlesztők nemzetközi konferenciája

Криптографический алгоритм 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 года в виде сообщения в профильные ньюсгруппы UseNet1. Наиболее ценное обсуждение произошло в конференции fido7.ru.crypt сети FidoNet. В апреле 2005 года увидела свет первая версия DersCrypt, заметно отличавшаяся от того, что было представлено в самом начале2. Текущей является версия алгоритма 1.1.

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

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

  1. Текст для шифрования рассматривается как неотрицательное число в некоторой системе счисления по основанию .
  2. Число переводится в другую систему счисления по основанию . Число является ключом.
  3. Цифры числа в системе счисления переставляются, в результате чего получается число . Перестановка задается значением ключа.
  4. Число переводится в исходную систему счисления .
  5. Число в системе счисления и является результатом шифрования.

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

  1. Если зашифровать два числа, отличающихся только значением младшего бита, то разность зашифрованных чисел, очевидно, будет равна для некоторого .
  2. Существует и более эффективный способ атаки: Max Alekseyev указал на то, что имея число в системе счисления по основанию и число , полученное из произвольной перестановкой цифр, разность всегда делится на .

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

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

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

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

Также имеются реализации на Java4 и С++5, предназначенные для практического использования. Об их сравнительной производительности можно судить по следующей таблице, в которой приведена скорость шифрования в килобайтах в секунду на 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, чей код никак нельзя признать оптимальным.

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

Ссылки

1 Анонс алгоритма

2 С. Деревяго. Криптографический алгоритм DersCrypt

3 Комментарии к эталонной реализации алгоритма

4 Java-реализация алгоритма

5 Реализация алгоритма на С++

Abstract licensed under Creative Commons Attribution-ShareAlike 4.0 license

Vissza