Прообраз находить не нужно. Задана криптографическая хеш-функция $h(\cdot).$ Для заверения вычисляем и затем на основании формируем значение ЭЦП. Зачем нам прообраз, когда известно по построению? ЭЦП можно фальсифицировать только тогда, когда известно некоторое $x´\neq x,$ такое, что А это и есть коллизия. Более того, асимптотическая оценка вычислительной трудоемкости нахождения коллизии для произвольной хеш-функции $O(\sqrt{N}),$ где $N=2^\ell$ для $\ell$ -разрядной хеш-функции. И эта оценка ниже аналогичной оценки для нахождения прообраза, а именно $x=h^{-1}(y).$

-1

nin-jin 5 авг 2022 в 16:58

x' - это и есть прообраз. Причём для взлома цифровой подписи нужно не абы какой прообраз найти, а соответствующий заданному валидному шаблону, содержащему подложные данные.

А поиск коллизий - это просто генерация таких x1 и x2, хеши которых совпадают. К конкретной цифровой подписи они не имеют никакого отношения.

AndrChm 5 авг 2022 в 18:12

x' - это и есть прообраз. Причём для взлома цифровой подписи нужно не абы какой прообраз найти, а соответствующий заданному валидному шаблону, содержащему подложные данные.

Подозревал, что терминология хромает. Для функции прообразом (preimage) в математической литературе принято назвать аргумент а образом (image) значение функции И не следует вводить собственные интерпретации, вы ведь не Рамануджан, который полностью игнорировал стандартные обозначения и толкования.

Теперь про атаки на цифровую подпись. Процитирую самого себя. «Злоумышленник способен навязать заверителю множество различных сообщений и вынудить сформировать для них ЭЦП. Распространенной практикой следует считать доказательство криптостойкости схемы ЭЦП в фокусе модели экзистенциальной фальсификации/подлога при атаке с подбором сообщений. Особенность модели в том, что сообщение изменяется/выбирается произвольным образом, без сохранения смыслового содержания в соответствии с принципом «атака ради атаки». Криптостойкость трактуется как неспособность злоумышленника при неизвестном секретном ключе, располагающего полиномиально-ограниченными ресурсами, как вычислительными, так и памяти, сформировать ЭЦП для некоторого сообщения с использованием множества заверенных ЭЦП произвольных сообщений, такую, что для сообщения, которое не принадлежит упомянутому множеству, при проверке на валидность булевская переменная принимает истинное значение.» Так что рассуждения про «валидный шаблон» — это частный случай экзистенциальной атаки с подбором сообщений. Иными слова, если схема ЭЦП уязвима в плане такой атаки, то её просто выбрасывают в мусорную корзину. И этот ваш «валидный шаблон» никакого смысла не имеет. Вы бы как-то теорию подтянули что-ли…

-1

nin-jin 5 авг 2022 в 21:23

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

AndrChm 5 авг 2022 в 21:26

Ай-я-яй! Как грубо-то! И ведь у вас есть имя и фамилия, которые известны. А ваша грубость — это проявление слабости. Подумайте об этом.

-1

AndrChm 5 авг 2022 в 16:52

Просто коллизия - это 50к баксов выкинутые на ветер.

Я вот тут интересуюсь, а почему 50К баксов на ветер, а не скажем 100К или наоборот меньше 50К?

Не перестаю удивляться «компетентности» и апломбу участников…

nin-jin 5 авг 2022 в 17:19

Тут речь идёт о 75..120 килобаксах. За 5 лет ситуация думаю улучшилась.

AndrChm 5 авг 2022 в 18:25

Вы хоть понимаете, что значит силовая атака с целью нахождения коллизии для SHA256, например? Это в худшем случае приблизительно $2^{128}$ опробований. Вот вам несколько цифр для отрезвления. Число атомов Вселенной $10^{77}(2^{256}).$ Число атомов нашей галактики $10^{67}(2^{223}).$ Число атомов Солнца $10^{57}(2^{190})$ и так далее. Вы о каком улучшении толкуете? Вы сможете сделать то, о чём так безответственно заявляете, за пару сотен тысяч баксов? Не смешите…

-1

nin-jin 5 авг 2022 в 21:35

И при чём тут SHA256? В статье описывается алгоритм со сложностью 2^63 для SHA-1 и приводятся расчёты стоимости поиска коллизии. Довольно бесполезной для целей взлома цифровой подписи.

AndrChm 5 авг 2022 в 21:40

Только коллизии и полезны для фальсификации ЭЦП. Кстати, они всегда существуют. Вопрос только в том, как их найти. И ещё раз. Нет никакого смысла обсуждать SHA-1. Эта хеш-функция скомпрометирована. Как минимум для ЭЦП. Так же как нет никакого смысла обсуждать DES, например, на смену которому пришёл стандарт AES. Всё развивается. Прошу прощения за очередной высер. Уж будьте великодушны, не судите строго. Да, и побольше минусов, конечно.

-1

nin-jin 5 авг 2022 в 22:11

Оставлю для вас место для ссылки на "компрометацию":

AndrChm 5 авг 2022 в 22:32

Сложная семантика. Вот не догоняю своим умишком-то. Но уловил щедрое предложение оставить место. Это дивно! И… больше минусов, хороших и разных!

-1

AndrChm 5 авг 2022 в 18:57

Про SHA-1 речь уже давно не идёт. Это всё не интересно. Никто для ЭЦП не использует. Пройденный этап.

-1

ReadOnlySadUser 4 авг 2022 в 00:25

Стоит ли говорить, что уже давно приехали алгоритмы SHA-3?)

nin-jin 4 авг 2022 в 01:24

Которые минимум в 3 раза медленнее и выдают в полтора раза больший дайджест?

AndrChm 5 авг 2022 в 19:39

минимум в 3 раза медленнее и выдают в полтора раза больший дайджест

Вы вот рассуждаете как программист, но при этом почему-то забываете, что в контексте ЭЦП разрядность значения хеш-функции (тот самый образ или дайджест) если и имеет смысл, то только с точки зрения криптостойкости. Ведь это значение вычисляется при формировании и проверке ЭЦП и не сохраняется в долговременной памяти в течение всего срока жизни заверенного ЭЦП документа. В отличие от самой цифровой подписи, которая должна храниться вместе с документом. Вот её разрядность уже имеет смысл. Но для современных схем ЭЦП на эллиптических кривых эта разрядность редко превышает 512 бит. Так что интересна только криптостойкость, которую может гарантировать хеш-функция в составе схемы ЭЦП. Остальные параметры вторичны, хотя разработчики хеш-функций их тоже имеют в виду, конечно.

-1