18. Алгоритм sha

Алгоритм безопасного хэшированияSНА(SecureHashAlgorithm) разработан НИСТ и АНБ США в 1992 г.

Рассмотрим подробнее работу алгоритма хэшированияSНА.

Инициализируется пять 32-битовых переменных в виде:

А = 0х67452301 В = 0хЕFСDАВ89 С = 0х98ВАDСFЕ

D = 0x10325476 Е = 0хС3D2Е1F0

Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:

а = А, b = В, с = С, d = D, е = Е

Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.

Блок сообщения преобразуется из шестнадцати 32-битовых слов (М₀...М₁₅) в восемьдесят 32-битовых слов (W₀...W₇₉).

С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:

цикл по t от 0 до 79

ТЕМР = (а <<< 5) + f_t (b, c, d) + е + W_t + К_t

е = d d = с с = (b <<< 30) b = а

а = ТЕМР

конец_цикла

После окончания главного цикла значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D, Е.

18. Отличие md-5 от sha

Отличия SHA от MD5 состоят в следующем:

1. SНА выдает 160-битовое хэш-значение, поэтому он более устойчив к атакам полного перебора и атакам "дня рождения", чем MD5, формирующий 128-битовые хэш-значения.

2. Сжимающая функция SHA состоит из 80 шагов, а не из 64 как в MD5.

3. Расширение входных данных производится не простым их повторение в другом порядке, а рекуррентной формулой.

4. Усложнен процесс перемешивания

22. Российский стандарт хэш-функций

Данный стандарт опред. Ал-тм и процедуру вычисления хэш-функций для любой последовательности двоичных символов.

Базируется на блочном ал-ме шифрования ГОСТ 28147-89, хотя по стр-ре ал-махэширования можно применить любой блочный ал-м шифрования с 64-битовым блоком и 256-битовым ключом. Данная хэш-ф-я генерирует 256 битовое хэш-значение Hi = f (Mi,Hi-1)

Mi и Hi-1 по 256 бит.

Генерируется 4 ключа шифрования Kj, j=1,4 путем линейного смешивания Mi,Hi-1 и некоторых констант Cj/

Каждый ключ Kj используется для шифрования Kjподслов слова Hi-1 в режиме простой замены Sj = Ekj(hj). В результате получаем последовательности S1, S2,S3,S4

Значение Hiявл. Сложной ф-ей от смешивания переменых. Sj, Hi, Hi-1

При вычислении окончательного хэш-значения сообщение M={Mi} учитываются значения всех связанных между собой переменных.

Формула для вычисления окончательного значения

H = f(z(+)M’,f(L,f(M’,Hn)))

Mn – хэш-значение первого блока сообщения

M’ – дополенный последний блок сообщения

L – длина сообщения

z – значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения.

23-24.Алгоритм DSA. Ускоряющие предварительные вычисления

Алгоритм ЦП DSA предложен в 1991 г. NISI США. Для использования в стандарте ЦП DSS.

Отправитель и получатель электронного документа используют при вычислении большие простые целые числа Q,Pдлиннойh; 512 <L< 1024 бит.

Q – простое число длиной 160 бит -> делитель (p-1)/

Числа G,P и Q явл. Открытыми и могут быть общими для всех пользователей сети. Отправитель выбирает случайное число X. X – секретный ключ, используется для формирования ЦП. Рассчитывается значение Y по формуле

Y = G^xmodP.

Y – открытое значение. Используется для проверки подписи отправителя и передается всем получателям документа. Алгоритм предусматривает использование ф-иихэширования. В качестве ф-иихэширвания используется ал-мSHA.

m = h(M);

1 <m<q

Отправитель генерирует случ. Число K , 1 <K<q.

Рассчитывает значение r = (G^Kmodp) modq. Отправитель рассчитывает значение s = ( (m + r*x) ) / kmod

Пара (r,s) – ЦП под документом M/

(M,r,s) – цифровой документ.

Получатель знает значение G,P,q.

Получает (M,r,s)

Получатель документа проверяет выполнение условий

0 <r<q

0 <s<q

Подпись отвергается сразу, если хотя бы одно из неравенство не выполняется.

Если выполняются, рассчитывает w= (1/s) modq

Получает ХЭШ-значение m’ = h/m

Рассчитывает :u1 = (m’*w) modq;

u2 = r*wmodq

Рассчитывает :v = ((g^u1 + y^u2) modp) modq

Проверяет выполнение условия, что v = r

Если условие выполняется, тогда подпись признается подлинной

ЦП <r,s> под документом M, поставленной именно владельцем числа x, при этом именно владелец числа x сгенерировал число y.

Преимущества DSA перед. Эль-гамалем.

При любом допустимом уровне стойкости т.е. при любой паре G и P длиной L, 512 <L< 1024, числа q,X,r,s. Имеют длину 160 бит. Сокращая длину подписи до 320 бит.

Большинство операций с числами k,/\, r,sосущ. по модулю числа q (160 бит). Это сокращает время вычисления подписи.

При проверке большинство операций осущ. с числами u1,u2,v,w,m по модулю q (160 бит). Это сокращает время проверки и объем необх. Памяии.

Недостатком DSAявл. Необходимость выполнять сложные операции деления по модулю, что не позволяет получить максимальное быстродействие системы.

Увеличение быстродействия ал-маDSA можно получить путем реализации некоторых предвычислений. Значение r не зависит от значения сообщения M => от хэш-значения, поэтому можно заранее создать строку случайных заченийk и для каждого из них вычислить для них значение r.

Можно заране произвести расчет значения k-1 и затем при поступлении сообщения M можно рассчитать значение S уже по готовымr и k^-1;