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

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

Для получения объективной оценки быстродействия необходимо использовать независимые от реализации характеристики алгоритмов шифрования, поскольку оценка быстродействия алгоритма в программной реализации сильно зависит от оптимизации программы и ориентации на работу с определенной архитектурой процессора, операционной системой, длиной блока и т.д. Для сравнительной оценки быстродействия разработанных алгоритмов предлагается использовать методику на основе подсчета количества некоторых элементарных операций, составляющих цикл криптографического преобразования (шифрование 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, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блочного шифрования.

Выводы.

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

К преимуществам алгоритма DES следует отнести его существенно большее быстродействие. Как и все блочные алгоритмы, он работает в реальном времени, что позволяет применять их при шифровании данных «на лету» - прозрачно для пользователя. Быстродействие алгоритма позволяет реализовывать подсистемы шифрования данных, которые смогут обеспечить шифрование объемов данных, соответствующих максимальной пропускной способности канала связи. Даже сравнительно простая реализация алгоритма обеспечивает скорость шифрования/дешифрования до 1 Мб/ сек.

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

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

Говоря об устойчивости к взлому алгоритма RSA, отметим, что в настоящий момент существует несколько способов взлома RSA. Наиболее эффективная атака: найти секретный (private) ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым (public) ключом и подделывать подписи.

Фактически, задача восстановления секретного (private) ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M**e*(mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный (private) ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

Разумеется, существуют и атаки, нацеленные не на криптосистему непосредственно, а на уязвимые места всей системы коммуникаций в целом; такие атаки не могут рассматриваться как взлом RSA, так как говорят не о слабости алгоритма RSA, а скорее об уязвимости его конкретной реализации.

Например, нападающий может завладеть секретным (private) ключом, если тот хранится без должных предосторожностей. Необходимо подчеркнуть, что для полной защиты недостаточно защитить выполнение алгоритма RSA и принять меры вычислительной безопасности, то есть использовать ключ достаточной длины. На практике же наибольший успех имеют атаки на незащищенные этапы управления ключами системы RSA.

К одним из наиболее существенных недостатков использования алгоритма RSA является его существенная трудоемкость. Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании Zaxus (Racal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. Столь широкое распространение позволяет сделать вывод о перспективности использования данного алгоритма для шифрования данных, передаваемых по сети.

Литература

1. Б. Ю. Анин Защита компьютерной информации – СПб.: БХВ-Санкт-Петербург, 2000

2. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си – М: Издательство Триумф, 2002.

3. Алферов А.П., Зубов А.Ю, Кузьмин А. С., Черемушкин А. В. Основы криптографии: учебное пособие, 2-е изд. – М.: Гелиос АРВ, 2002.

Дата добавления: 2018-02-15; просмотров: 1148; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 23

Мы поможем в написании ваших работ!