Насколько безопасна цифровая подпись?

Question

Цифровая подпись, если я правильно понял, означает отправку сообщения в чистом виде вместе с хешем сообщения, который зашифрован с использованием личного ключа.

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

Насколько это безопасно?Я имею в виду, вы можете легко получить хеш сообщения, и у вас также есть зашифрованный хеш.Насколько легко найти закрытый ключ, используемый для создания Encrypted_hash?

Пример:

Message            Hash    Encrypted_hash
-----------------------------------------
Hello world!       1234    abcd
Hi there           5678    xyzt
Bla bla            0987    gsdj
...

С учетом значений Hash и Encrypted_hash и достаточного количества этих сообщений, насколько просто / сложноэто узнать секретный ключ?

Answer 1

Из-за алгоритмов, используемых для генерации ключей (типичным является RSA), ответ по существу «невозможен в любое разумное количество времени», если предположить, что ключ имеет достаточную длину в битах.Пока закрытый ключ не украден или не передан, вы не сможете расшифровать его, используя только открытый ключ и сообщение, которое было хешировано с помощью закрытого ключа.

Как указано в @HenkОтвет Холтермана: алгоритм RSA основан на том факте, что вычисления, необходимые для дешифрования закрытого ключа - одной из них является простая факторизация, - являются сложными проблемами, которые не могут быть решены в разумные сроки (о которых мы знаем в настоящее время).Другими словами, основная проблема (первичная факторизация) - это проблема NP , означающая, что она не может быть решена за полиномиальное время (взломать закрытый ключ), но может быть проверено за полиномиальное время (расшифровка с использованием открытого ключа).

Answer 2

Шифры, разработанные до того, как электронные компьютеры часто становились уязвимыми для атаки «известного простого текста», что, по сути, является тем, что описано здесь: если у злоумышленника был зашифрованный текст и соответствующего простого текста,мог бы найти ключ.Коды эпохи Второй мировой войны иногда нарушались, угадываясь в зашифрованных текстовых словах, таких как места сражений, званий, приветствий или погодных условий.

Однако алгоритм RSA, наиболее часто используемый дляцифровые подписи неуязвимы даже для «выбранной атаки с открытым текстом» при использовании правильного заполнения (например, OAEP ).Выбранный простой текст означает, что злоумышленник может выбрать сообщение и заставить жертву зашифровать его;обычно это даже более опасно, чем известная атака с открытым текстом.

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

Answer 3

Цифровая подпись ничего не говорит о том, как передается фактическое сообщение.Может быть открытым текстом или зашифрованным.

А текущие асимметричные алгоритмы (открытый + закрытый ключ) очень безопасны, насколько безопасность зависит от размера ключа.

Злоумышленник имеет достаточно информации, чтобы взломать ее.Но это часть «доказательства» асимметричного шифрования, которое занимает непрактичное количество процессорного времени: метод безопасен в вычислительном отношении.

Answer 4

То, о чем вы говорите, называется атакой "известным открытым текстом".С любым достаточно безопасным современным алгоритмом шифрования известный открытый текст по существу не поможет при атаке.При разработке алгоритма шифрования вы предполагаете, что злоумышленник будет иметь доступ к произвольному количеству известного открытого текста;если это помогает злоумышленнику, алгоритм считается полностью нарушенным в соответствии с действующими стандартами.

Фактически, вы обычно принимаете как должное, что злоумышленник будет иметь доступ не только к произвольному количеству известного открытого текста, но даже к произвольномуколичество выбранного открытого текста (т. е. они могут выбрать какой-то текст, каким-то образом заставить вас зашифровать его и сравнить результат с оригиналом. Опять же, любой современный алгоритм должен быть защищен от этого, чтобы считаться безопасным.

Answer 5

Учитывая значения Hash и Encrypted_hash и достаточное количество этих сообщений, насколько легко / сложно найти закрытый ключ?

Это сценарий Атаки по известному тексту : вам выдается много текстовых сообщений (хэш) и соответствующих зашифрованных текстов (зашифрованный хэш), и вы хотите узнать ключ шифрования.

Современные криптографические алгоритмы предназначены для противостояния такого рода атакам, как алгоритм RSA , который является одним из алгоритмов, используемых в настоящее время для цифровых подписей.

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

Для более детального и полного понимания криптографии, посмотрите литературу, например, страницы Википедии или Прикладная криптография Брюса Шнайера .

Answer 6

Для идеально разработанного хэша это невозможно (или, скорее, нет более простого способа, чем пробовать все возможные клавиши ввода)