Описание алгоритма

Одна итерация алгоритма SHA1

SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока M_i равен h_i = f(M_i,h_{i − 1}). Хеш-значением всего сообщения является выход последнего блока.

Инициализация

Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1, а потом нули, чтобы длина блока стала равной (512 - 64 = 448) бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах. Если последний блок имеет длину более 448, но менее 512 бит, дополнение выполняется следующим образом: сначала добавляется 1, затем нули вплоть до конца 512-битного блока; после этого создается ещё один 512-битный блок, который заполняется вплоть до 448 бит нулями, после чего в оставшиеся 64 бита записывается длина исходного сообщения в битах. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину.

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

A = a = 0x67452301

B = b = 0xEFCDAB89

C = c = 0x98BADCFE

D = d = 0x10325476

E = e = 0xC3D2E1F0

Определяются четыре нелинейные операции и четыре константы.

	Kt = 0x5A8279 99	0≤t≤19
	Kt = 0x6ED9EBA1	20≤t≤39
	Kt = 0x8F1BBCDC	40≤t≤59
	Kt = 0xCA62C1D6	60≤t≤79

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов M_i в 80 32-битовых слов W_j по следующему правилу:

W_t = M_t при 0≤t≤15 W_t = (W_t-3 W_t-8 W_t-14 W_t-16) << 1 при 16≤t≤79

здесь << — это циклический сдвиг влево

для t от 0 до 79 temp = (a<<5) + F_t(b,c,d) + e + W_t + K_t e = d d = c c = b<<30 b = a a = temp

После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая итерация.

Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение.

15. Хеш-функция MD5

16. Электронная цифровая подпись

17. Эцп на основе алгоритма rsa

ЭЦП на основе алгоритма RSA

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа Р и Q, затем находит их произведение N = Р * Q и значение функции (N) = (Р-1)(Q-1)

Далее отправитель вычисляет число Е из условий:

Е  (N), НОД (Е, (N)) =1

и число D из условий: D < N, Е * D  1 (mod (N)).

Пара чисел (Е, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.

Обобщенная схема формирования и проверки цифровой подписи RSА показана на рис.5.

Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции h() в целое число m:

m = h(М).

Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D:

S = m^D (mod N).

Пара (М, S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

После приема пары (М, S) получатель вычисляет хэш-значение сообидения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа Е:

m' = S^E (mod N).

Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h():m = h(М).

Если соблюдается равенство вычисленных значений, т.е.

S^E (mod N) = h(М),

то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители.

Недостатки алгоритма цифровой подписи RSА.

1. При вычислении модуля N. ключей Е и D для системы цифровой подписи RSА необходимо проверять большое количество дополнительнмх условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.

2. Для обеспечения криптостойкости цифровой подписи RSА по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10¹⁸, необходимо использовать при вычислениях N, D и Е целые числа не менее 2⁵¹² (или около 10¹⁵⁴) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

3. Цифровая подпись RSА уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSА позволяет злоумышленнику без знания секретного кпюча D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.