2.2. Оценка быстродействия существующих алгоритмов блочных шифров

Важным параметром любого криптографического алгоритма, помимо стойкости, является его быстродействие.

Для получения объективной оценки быстродействия необходимо использовать независимые от реализации характеристики алгоритмов шифрования, поскольку оценка быстродействия алгоритма в программной реализации сильно зависит от оптимизации программы и ориентации на работу с определенной архитектурой процессора, операционной системой, длиной блока и т.д. Для сравнительной оценки быстродействия разработанных алгоритмов предлагается использовать методику на основе подсчета количества некоторых элементарных операций, составляющих цикл криптографического преобразования (шифрование 1 блока открытого текста). В результате анализа итеративных блочных шифров в качестве элементарных операций для оценки быстродействия предлагается использовать следующие операции:

• гаммирование (XOR) – g;

• сложение – s;

• умножение – m;

• сдвиг – r;

• табличная подстановка (S-блоки алгоритмов) – t.

Состав используемых для оценки элементарных операций определяется наибольшей распространенностью в существующих блочных шифрах. Для битовой перестановки, встречающейся в некоторых шифрах, в качестве приближенной оценки предлагается использовать операцию сдвига по числу битов перестановки. Операции сложения и умножения выполняются по некоторому модулю, совпадающему с длиной разрядной сетки, необходимой для представления данных, которыми оперирует алгоритм: если алгоритм ориентирован на работу с 16-разрядными данными, то сложение и умножение производится по модулю 2¹⁶, для 32-разрядных – по модулю 2³² и т.д.

В качестве прототипов для сравнения были выбраны алгоритмы DES, NewDES, поскольку для этих алгоритмов известны характеристики стойкости и быстродействия и они являются наиболее исследованными криптографическими алгоритмами. Алгоритм RSA, являющийся несимметричным алгоритмом, требует иного подхода к оценке.

Раунд алгоритма DES с учетом расширяющей и сжимающей табличных подстановок, сложения с ключом и битовой перестановки можно охарактеризовать как:

.

С учетом числа раундов, начальной и завершающей перестановок, получим:

.

Для алгоритма NewDES, состоящего из 17 раундов, раунд можно оценить как:

,

где f – раундовая функция, объединяющая данные и ключ и состоящая из операций гаммирования и подстановки. Тогда полностью алгоритм NewDES можно описать следующим образом:

Полученные оценки числа операций, необходимых для шифрования одного блока открытых данных, можно объединить в таблице 2.1.

Таблица 2.1. Сравнительная характеристика быстродействия алгоритмов существующих блочных шифров в элементарных операциях.

Алгоритм	Быстродействие
DES
NewDES

Для получения сравнительных оценок по быстродействию в единых единицах, в качестве такой характеристики можно использовать число тактов процессора, необходимое для выполнения полного цикла криптографического преобразования. Однако необходимо отметить, что такая оценка является приближенной и не учитывает особенности программной реализации сравниваемых алгоритмов (оптимизации шагов алгоритма, организации структур данных и т.д.). Введенные в качестве элементарных операции характеризуются различной трудоемкостью и, соответственно, разным числом тактов процессора для выполнения в зависимости от типа процессора, размера операндов и их местонахождения. В качестве максимальных характеристик по трудоемкости операций целесообразно использовать следующие характеристики: операции g и s занимают 1 такт, операция умножения m – от 13 до 42 тактов, операция сдвига r – от 1 до 5 тактов, табличная подстановка t (рассматриваемая как операция mov) – от 1 до 7 тактов (основой для таких характеристик служит время выполнения этих операций для процессора i486).

В соответствие с этим рассмотрим влияние каждой из этих операций на быстродействие рассмотренных шифров (рис. 2.1 – 2.3).

Рис. 2.1. Зависимость быстродействия алгоритмов от числа тактов процессора, необходимых для выполнения операции сдвига r (m=13, t=1).

Рис. 2.2. Зависимость быстродействия алгоритмов от числа тактов процессора, необходимых для выполнения операции пересылки t (m=13, r=3).

Рис. 2.3. Зависимость быстродействия алгоритмов от числа тактов процессора, необходимых для выполнения операции умножения m (для t=1, r=3).

Как при шифровании/дешифровании, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.

В практических приложениях для открытого ключа обычно выбирается относительно небольшой показатель, а зачастую группы пользователей используют один и тот же открытый показатель, но каждый с различным модулем. (Если открытый показатель неизменен, вводятся некоторые ограничения на главные делители (факторы) модуля.) При этом шифрование данных идет быстрее, чем расшифровка, а проверка подписи – быстрее, чем подписание. Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым ключом пропорционально второй степени k, количество шагов для операций частного ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.

Методы "быстрого умножения" – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA быстро увеличиваются.

Алгоритм RSA намного медленнее, чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блочного шифрования.