Ви є тут

Розробка засобів ефективного вибору та реалізації алгоритмів захисту інформації в комп'ютерних системах.

Автор: 
Акрам Ареф Найеф Мустафа
Тип роботи: 
Дис. канд. наук
Рік: 
2003
Артикул:
3403U000885
129 грн
Додати в кошик

Вміст

ГЛАВА 2.
РАЗРАБОТКА CТРУКТУРНЫХ МЕТОДОВ ПОВЫШЕНИЯ
ЭФФЕК­ТИВНОСТИ ВЫЧИСЛЕНИЯ ХЕШ-АЛГОРИТМОВ
Обеспечение подлинности и аутентичности информации передаваемой по сетям
является одной из важнейших составляющих современных информацион­ных технологий
[15,40]. Анализ структур современных систем обеспечения подлинности и
аутентичности показывает, что уровень их защищенности и производительность в
определяющей степени зависят от используемых в их составе хеш-алгоритмов [36].
В первой главе было показано, что наиболее слабой стороной хеш-алгоритмов всех
типов ( как специализированных типа SHA-1 так и на основе цепочек шифроблоков)
является то, что они, в отличие от блочных алгоритмов шифрования, допускают
только строго последовательную обработку блоков. Это накладывает существенные
ограничения на возможность достижения высо­кой производительности формирования
хеш-сигнатур, резко снижает скорость информационных потоков в сетях,
препятствует использованию средств защиты подлинности информации в системах
реального времени.
Распараллеливание вычисления хеш-сигнатур может быть достигнуто совмещением
операций в рамках формирования отдельной частичной хеш-сигна­туры или
совмещением формирования частичных хеш-сигнатур нескольких блоков сообщения.
2.1. Исследование возможностей распараллеливания вычис-
лений при формировании частичной хеш-сигнатуры
Большинство протоколов и стандартов [6,13,41,76] обеспечения целост­нос­ти
информационных структур в компьютерных системах и сетях ориенти­ро­ваны на
использование хеш-алгоритмов, реализующих рекурсивное вычис­ление систем
булевых функций. Эти хеш-алгоритмы: SHA-1, MD-5, RIPEMD-160, ГОСТ Р.34.10-94 в
плане структуры вычислений весьма близки между собой. Для исследования
возможностей распараллеливания в рамках вычисле­ния частичной хеш-сигнатуры
необходимо проанализировать операции и определить длину критического пути и
суммарную трудоемкость. Ниже в полном объеме изложены такие исследования для
наиболее распространен­ного на практике хеш-алгоритма SHA-1, аналогичные
исследования проведены и для алгоритмов MD-5, RIPEMD-160, ГОСТ Р.34.10-94 и их
результаты приведены в конце параграфа.
Выполнение SHA-1 состоит из 80 подциклов, после каждого из 20-ти выполняется
смена выполняемого функционального преобразования, которые, различаются
сложностью, кроме того, на первых 16-ти циклах используется упрощенная формула
для формирования блока информации - W. Если не учитывать операций выполнения
функционального преобразо­вания и формирования W, то в каждом цикле выполняется
4 операции суммирования по модулю 2, два операции циклического сдвига и 5
пересы­лок информации. Без учета пересылок информации число постоянно
присут­ствующих на каждом цикле операций составляет 6. В табл. 2.1. приведены
данные для анализа суммарной трудоемкости выполнения алгоритма SHA-1.
Таблица 2.1.
Распределение операций, составляющих SHA-1 по циклам
Циклы
К-во
Число опер-ций
Число операций
Число
повторений
формирования W
функц. преобр.
операций
1-18
16
172
19-20
52
21-40
20
220
41-60
20
280
61-80
20
220
Итого:
944
Таким образом, общее число операций, составляющих вычислительную процедуру
алгоритма SHA-1, без учета операций пересылок составляет 944, причем из табл.
2.1. непосредственно следует, что затраты вычислительных ресурсов распределены
неравномерно : наибольшего числа операций требует выполнение циклов с 41-го по
60-й. Поэтому для анализа возмож­ности рас­па­рал­леливания SHA-1 и определения
требуемого числа процессорных элемен­­тов необходимо исследовать наиболее
нагруженные циклы: с 41-го по 60-й.
Операции, выполняемые в рамках одного шага реализуются в такой
последовательности. Сначала осуществляется вычисление значения W путем
суммирования его 4-х составляющих. Очевидно, что начиная с 18-го цикла эти
операции могут выполняться независимо в любое время. Затем к полученному коду W
прибавляется код цикловой константы и эта операция суммирования по модулю 2
также не является критичной по времени. Затем к полученной сумме добавляется
код переменной Е. Однако, если операция выполняется предварительно, за цикл до
вычисления Е, то можно учесть, тот факт, что значение Е формируется как
значение переменной D с предыдущего цикла. Поэтому можно на графе к сумме W и
константы K суммировать по модулю 2 код переменной D при условии, что эта
операция по времени будет выполняться за цикл, до формирования окончательного
значения ТЕМР.
Непосредственно в текущем цикле выполняется суммирование по модулю 2 результата
функционального преобразования и последняя операция – Сум­мирование по модулю 2
сдвинутого значения переменной А. Для того, чтобы реализовать описанный порядок
во времени выполнения операций цикла SHA, необходимо, чтобы нелинейная функция
f3(B,C,D) = BЧC V BЧD V CЧD вычислялась до цикла в котором формируется
результат TEMP. Чтобы выполнить эти условия, необходимым представляется
использование не текущих значений переменных B,C,D, а кодов из которых
формируются указанные переменные алгоритма SHA на предыдущем цикле. Переменная
В за цикл до выполнения совпадает со значением A, то есть Bi= Ai-1, переменная
С за цикл до формирования итоговой операции совпадает со сдвинутой на 30
разрядов циклически влево (на 2 разряда циклически сдвинутой вправо)
перемен­ной В: Сi = Bi-1 <<30. Переменная D за цикл раньше совпадает с
переменной С, то есть Di = Ci-1.
Таким образом, для того, чтобы нелинейное функциональное преобра­зо­вание было
выполнено до начала i-го цикла, можно для формирования функции f3 использовать
следующее выражение:
f3(Bi