Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.5 RIPE-MD Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.3 MD5   Содержание   Предметный указатель

5.2.4 SECURE HASH ALGORITHM (SHA)

В 1993 году Национальный институт стандартов и технологий (NIST) США совместно с Агентством национальной безопасности США выпустил "Стандарт стойкой хэш-функции" (Secure Hash Standard [NBS2], [NBS3]), частью которого и является алгоритм SHA. Предложенная процедура вырабатывает хэш-код длиной 160 битов для произвольного текста длиной менее $ 2^{64}$ битов. Разработчики считают, что для SHA невозможно предложить алгоритм, имеющий разумную трудоемкость, который строил бы два различных сообщения, дающих один и тот же хэш-код. SHA основан на тех же самых принципах, которые использовал Ривест при разработке MD4, более того, алгоритмическая структура SHA очень похожа на структуру MD4.

Процедура дополнения хэшируемого текста до кратного 512 битам полностью совпадает с процедурой дополнения алгоритма MD5.

Инициализируются 5 переменных по 32 бита (в алгоритме MD5 таких переменных было 4):

    \begin{tabular}{r@{}l}
$A={}$&\texttt{67 45 23 01};\\
$B={}$&\texttt{EF CD AB 8...
...\
$D={}$&\texttt{10 32 54 76};\\
$E={}$&\texttt{C3 D2 E1 F0}.\\
\end{tabular}

Далее, аналогично MD5, создаются копии $ AA$, $ BB$, $ CC$, $ DD$, $ EE$ инициализированных переменных и для каждого блока текста размером 512 битов выполняется основной цикл, состоящий из 4 раундов. В отличие от MD5 каждый раунд состоит из 20 операторов (в MD5 -- 16 операторов).

Аналогично MD5, каждый оператор состоит из функции от 3 переменных (в случае SHA это $ B$, $ C$ и $ D$), циклического сдвига и суммирования. Набор используемых в SHA функций выглядит следующим образом.

В первом раунде ($ t\in 0,19$) действует функция $ f_t(X,Y,Z)=XY\lor(\qopname\relax o{not}X)Z$.

Во втором раунде ( $ t\in 20,39$) действует функция $ f_t(X,Y,Z)=X\oplus Y\oplus Z$.

В третьем раунде ( $ t\in 40,59$) действует функция $ f_t(X,Y,Z)=XZ\lor XY\lor ZY$.

В четвертом раунде ( $ t\in 60,79$) действует функция $ f_t(X,Y,Z)=X\oplus Y\oplus Z$.

Здесь и далее $ t\in0,79$ обозначает номер оператора в основном цикле. Для каждого раунда определена одна константа, которая суммируется с очередным подблоком:

    в первом раунде ($ t\in 0,19$):      $ K_t=\hbox{\ttfamily 5A827999}$;
    во втором раунде ( $ t\in 20,39$):      $ K_t=\hbox{\ttfamily 6ED9EBA1}$;
    в третьем раунде ( $ t\in 40,59$):      $ K_t=\hbox{\ttfamily 8F1BBCDC}$;
    в четвертом раунде ( $ t\in 60,79$):      $ K_t=\hbox{\ttfamily CA62C1D1}$.

В начале основного цикла блок хэшируемого текста расширяется до 80 слов по 32 бита по правилу: для $ t\in
0,15$ слово $ W_t$ совпадает с $ t$-тым подблоком $ M_t$ исходного блока; для $ t\in16,79$ полагают $ W_t=W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}$, где $ W_t$ -- промежуточные значения слов.

Каждый из 80 операторов основного цикла имеет следующий вид:

    $ \{$TEMP$ {}=(A\ll5)+f_t(B,C,D)+E+W_t+K_t$;

    $ E=D$;

    $ D=C$;

    $ C=(B\ll30)$;

    $ A={}$TEMP$ \}$;

Здесь, как и прежде, символ "$ \ll$" обозначает циклический сдвиг. Основной цикл завершается суммированием $ A$, $ D$, $ C$, $ D$, $ E$ и $ AA$, $ BB$, $ CC$, $ DD$, $ EE$. Выходом алгоритма является конкатенация $ A$, $ B$, $ C$, $ D$, $ E$.


Известные результаты анализа


SHA скорее является модификацией MD4, нежели новой разработкой. В отличие от Ривеста, который аргументирует вносимые им изменения в MD4 при разработке MD5, авторы SHA такой аргументации не приводят. Ниже сравниваются изменения MD4, внесенные Ривестом при разработке MD5, и изменения, внесенные в MD4 при разработке SHA.


1. Как в MD5, так и в SHA, добавлен 4-й раунд. Однако, в SHA в 4-м раунде используется та же самая функция, что и во 2-м раунде (в MD5 функции различны).

2. SHA наследует от MD4 принцип использования в каждом операторе одного раунда одной аддитивной константы (в MD5 константа каждого оператора уникальна).

3. Функция второго раунда в MD5 изменена с целью сделать ее менее симметричной, а SHA использует ту же функцию, что и в MD4.

4. Как в SHA, так и в MD5, результат каждого шага суммируется с результатом предыдущих шагов, что позволяет усилить эффект распространения ошибки. Однако, в SHA добавлена 5-я переменная по которой идет "зацепление", что приводит к тому, что метод ден Бура -- Босселэра, эффективный для MD5, перестает работать в случае SHA.

5. В отличие от MD5, в котором изменен порядок считывания слов во втором и третьем раундах для того, чтобы они меньше походили друг на друга, в SHA входные слова считываются в соответствии с правилом, получаемым на основе кода, исправляющего ошибки.

6. Если в MD5 величина циклического сдвига различается от раунда к раунду и от оператора к оператору, то SHA использует постоянные циклические сдвиги. Как и в MD4, величины этих сдвигов взаимно просты с длиной слова.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.5 RIPE-MD Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.3 MD5   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   

TopList Rambler's Top100