Хеширование

имеет удвоенный объем

Решение – сообщение перед подписыванием преобразуется в короткую

цепочку данных

(to hash – рубить, перемалывать).
Результат хеширования h, т.е. хеш,

является хеш-функцией h = h (M) сообщения M. Он имеет фиксированную длину, не зависящую от размера аргумента, к которому применена хеш-функция.
Поскольку длинных различных последовательностей больше, чем коротких, рассматриваемое преобразование не обладает свойством взаимной однозначности: одному хешу может соответствовать не один, а множество аргументов.
Применение простого хеширования обладает очевидным недостатком: любая пара сообщений M и M, имеющая общий хеш, дает и одинаковую цифровую подпись.

обладающее следующими свойствами:
При известном сообщении M вычисление h = h (M) должно быть

простым, причем без использования какого-либо ключа. Это означает, что процедура хеширования может быть выполнена любым пользователем. Применяемые при этом хеш-функции называются бесключевыми (бесключевое хеширование).
По известному хешу h должно быть трудно найти сообщение M такое, чтобы h = h (M), т.е. вычисление обратной функции должно быть сложным.
По заданному сообщению M должно быть трудно найти другое такое сообщение M  (M  M ), чтобы h (M) = h (M ).
Должно быть трудно найти любую пару таких сообщений M и M, для которых h (M ) = h (M ).

цифровую подпись, использующую хеш-функцию. Эта атака, основана на так называемом

парадоксе дней рождения.

что, по крайней мере, два человека в группе имеют один

и тот же день рождения. Оказывается, что если m  23, то вероятность такого события не меньше, чем 1/2.
Более формально:
Пусть имеется n мест и m предметов, которые случайно размещаются на этих местах. Вероятность события, состоящего в том, что на любом из n мест окажется более одного предмета при равна

возможных вариантов хеша равно 2L. Основываясь на концепции дней рождения,

видим, что достаточно перебрать 2L / 2 сообщений и хотя бы для одной пары сообщений M и M с вероятностью близкой к единице найдется общий хеш. При использования хеш-функции для получения цифровой подписи это означает, что при случайном выборе сообщений, где L – длина хеша, хотя бы одна пара из них будет иметь общий хеш и, следовательно, одну и ту же цифровую подпись.

h(M) , т.е. 512 бит

+ SHA-256)