Алгоритм безопасного хеширования sha

Для использования совместно с алгоритмами ЦП DSA

Для рассмотрения самостоятельно

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

ГОСТ Р.34.11-94 определяет алгоритм и процедуру вычисления h(.) для любых последовательных двоичных символов, применимых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя может быть и использован с другим блочным алгоритмом шифрования – 64-битовым блоком и 256-битным ключом. Данная h(.) формирует 256-битное h-значение.

Функция сжатия:

Hi = f(M_i, H_i-1)

Hi, Mi – 256-битные величины

Определяется следующим образом:

- Генерируется 4 ключа шифрования k_j (j=1..4) путем линейного смешивания M_i, H_i-1, const

- Каждый ключ k_j используется для ­_­шифрования 64-юитных подслов слова H_i-1 в режиме простой замены

64 → h_j → H_i-1

Результирующая последовательность длиной 256 бит запоминается со временной переменной S

S_j = E_kj (h_j) S₄, S₃, S₂, S₁ → S

• Значение H_i является сложной, хотя и линейной функцией смешивания S, M_i, H_i

При вычислении окончательного h-значения сообщения М учитываются значения 3х связанных между собой переменных.

H_n – значение последнего блока сообщения

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

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

Эти 3 переменные и дополнительный последовательный блок М’ объединяются в h-значение следующим образом:

+

H = f(Z M’, f(L, f(M’, H_n)))

Данная h(.) определена российским стандартом для использования с российским стандартом ЭЦП.

Лекция 11

Алгоритмы ецп

Для постановки цифровой подписи (ЦП) для каждого абонента генерируется пара ключей: секретный и открытый.

Секретный хранится абонентом в тайне и используется для формирования ЭЦП.

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

Открытый ключ не позволяет выделить секретный.

Для генерации пары ключей в алгоритме ЭЦП, как и в асинхронных системах шифрования, используются схемы, основанные на применении однонаправленных функций. Схемы делятся на 2 группы. В основе лежат: задача факторизации (разделение на множители) больших чисел – задача дискретного логарифмирования.

Алгоритм цп rsa

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

Вычисляет число E: E <= φ(N), НОД (Е, φ(N)) = 1

Вычисляет число D: D < N, E * D ≡ 1 mod φ(N)

Пара чисел E, N → открытый

D → закрытый

M – сообщение

БС – блок сжатия

ГК – генератор ключей

Если соблюдается условие S^Z mod N = h(M), то получатель признает пару M и S подлинной.

Доказано, что только обладатель секретного кода D может сформировать ЦП. S по документу M, а определить секретной ключ D по открытому E не легче, чем разложить модуль N на множители, кроме того, можно математически доказать, что результат проверки ЦП S будет степени n+p в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу E. Поэтому Е – идентификатор подписывания.

Недостатки:

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

- Для обеспечения криптостойкости RSA ну уровне национальной системы США, необходимо использовать при вычислениях N, D, E целые числа не менее, чем 2²⁵⁶, что требует затрат >20-30% вычислительных затрат других алгоритмов.

- ЭЦП RSA уязвима к мультипликативной атаке, то есть злоумышленник не зная секретного ключа D может сформировать ЦП под теми документами, у которых результат хеширования можно вычислить, как произведение результатов хеширования уже подписанных документов.

Более надежный и удобный алгоритм – Эль Гамаля (EGSA)

Идея основана на использовании более сложной математической задачи, чем задача факторизации, а именно задача дискретного логарифмирования.

Сразу генерируют пару ключей. Для этого берут большие простые числа p и g.

p~2¹⁰²⁴

g < p ~ 2⁵¹²

Отправитель выбирает случайное число Х, (1 <= X <= p-1) и вычисляет Y = G^X mod P – открытый ключ для проверки ЦП и отправителя получателем.

Х – секретное

Для подписи сообщения М отправитель хеширует ее с помощью h-функции

m= h(M) 1 < m < p-1

и генерирует случайное целое число k:

1 < k < p-1,

k, p-1 – взаимопростые

Отправитель вычисляет целое число а:

а = G* mod p

Применяя расширенный алгоритм Евклида вычисляет с помощью секретного ключа Х целое число b из уравнения:

m = X*a + k*b (mod (p-1))

Пара чисел a и b образуют ЦП S, выставляемую под документом М.

M, a, b – передаются получателю

X, k – секретные данные

После приема подписанного сообщения M, a, b, получатель проверяет, соответствует ли подпись сообщения М. Для этого по принятому М вычисляет:

m = h(M)

A = Y^aa^b (mod p)

и признает М подлинным, если А = G^m mod p

то есть Y^aa^b mod p = G^m mod p

Математически равенство выполняется, когда подпись получена с помощью того секретного ключа Х, из которого получен Y. Тем самым удостоверится, что отправителем сообщения М является обладатель секретного ключа Х не раскрывая сам ключ.

Выполнение ЭП по EGSA требует нового значения k. Если k раскрыто, то раскроется X.

Схема ЦП EGSA имеет преимущество перед RSA.

1. При заданном уровне стойкости целые числа имеют длину на четверть короче, следовательно уменьшается сложность вычислений, следовательно уменьшается объем памяти.

2. При выборе модуля p достаточно просто проверить, что оно простое, а (p-1) есть простой сомножитель, то есть 2 просто проверяемых условия.

3. Формирование подписи по EGSA не позволяет вычислить подписи под новыми М без знания ключа.