Биткоин. Криптографические хеш-функции

Криптографические хэш-функции — это крайне важный базовый элемент, используемый во множестве криптографических алгоритмов и протоколов. Они широко применяются в сфере обеспечения информационной безопасности. В число наиболее известных алгоритмов преобразования или криптографических функций входят MD5 и его предыдущая версия MD4, а также SHA-256, которому предшествовал алгоритм SHA-1 и так далее. Есть и другие алгоритмы, может быть вы о них знаете, хотя они менее распространенные, это RIPEMD, Блэйк, Скайн и другие. В общем, криптографические хэш-функции имеют широкую область применения. Например, первое прикладное применение, ставшее широко распространенным и наиболее известным — это электронная подпись. Сейчас электронная подпись широко применяется повсюду. Криптографические хэш-функции применяются во множестве коммерческих операций. Кроме того, они используется при эмиссии биткоинов. Криптографические хэш-функции применяются и в протоколах аутентификации сообщений, в генерации псевдослучайных чисел, в защитах с использованием паролей и при шифровании. Помимо электронной подписи, хэш-функции имеют и другое применение в протоколе биткоин. Давайте подробнее рассмотрим, что такое криптографические хэш-функции. Во-первых, исходя из названия, это хэш-функции. Или функции свёртки. Это математическая функция преобразования массива данных. Она берет входные данные, назовем эти входные данные — сообщение. Оно может быть произвольного объема. И хэш-функция преобразует входные данные, причем это может быть сделано в несколько этапов, чтобы получить на выходе код, который обычно называют дайджестом или сводкой сообщения. Хотя иногда могут назвать тэг или хэш, или хэш-код. Но чаще всего дайджест. Кстати, MD5 — одна из первых хэш-функций, означает «Дайджест сообщений 5». MD4 — это дайджест сообщений 4. Как уже говорилось, сообщение может быть любого размера. Хотите — короткое, хотите — длинное. Но на выходе вы получаете дайджест стандартного размера, фиксированной длины. Например, хэш-функция SHA-256 преобразует любое сообщение в дайджест, размер которого составляет в точности 256 битов. То есть фиксированная длина на выходе и произвольный размер на входе. Есть еще один аспект хэш-функций, о котором нужно упомянуть. Это детерминированные функции. Я имею в виду, что для одного и того же сообщения вы всегда будете получать один и тот же дайджест. Не может возникнуть ситуации, при которой на выходе получаются несколько вариантов дайджеста или хэш-кода. Хэш-функции широко используются во многих компьютерных приложениях. Например, вы наверняка знаете о так называемых хэш-таблицах. Это структура данных, в которой используются хэш-функции. Но это не обязательно криптографические хэш-функции. Определение «криптографические» крайне важно. Это означает, что данные функции должны соответствовать ряду требований для выполнения своих специфических задач. Чтобы функция могла использоваться в различных криптографических приложениях для защиты данных. В тех областях, где нужно обеспечить безопасность, конфиденциальность или аутентификацию. Во-первых, одно из важнейших требований, которому должна удовлетворять хорошая хэш-функция — она должна быстро вычисляться. Запишем: быстро вычисляется. Я имею в виду, что на получение хэш-кода из данного сообщения не должно затрачиваться слишком много времени. Если имеются некие данные, которые необходимо преобразовать и получить код или дайджест, то преобразование не должно отнимать много времени, надолго загружая компьютер. Оно должно происходить относительно быстро. Это само собой разумеющееся свойство, но я посчитал нужным о нем упомянуть. Некоторые создают весьма неэффективные в этом отношении функции. Такие функции не могут использоваться, скажем, в криптографических приложениях. Второе свойство, которое особенно важно в криптографии, скажем, при формировании электронной подписи. Важно избегать ситуаций, когда два разных сообщения преобразуются в одинаковый код. Такая ситуация называется коллизией хэш-функций. Так что, второе свойство или требование — это стойкость к коллизиям. То есть, должно быть непросто найти другое сообщение, преобразующееся в тот же хэш-код. Например, есть сообщение М₁ и сообщение М₂. После преобразования при помощи хэш-функции не должен получиться одинаковый дайджест. То есть, в результате применения хэш-функции ко входным данным М₁ и М₂, на выходе не должны получаться одинаковые хэш-коды. Или дайджесты. Они всегда должны получаться разные. Конечно, на практике, учитывая, что сообщения могут быть произвольного размера, а код на выходе должен быть фиксированной длины, математически невозможно гарантировать, что из разных сообщений всегда будут получаться разные коды. Так что, нам нужно не то чтобы исключить такую возможность, но сделать так, чтобы было непросто найти сообщение, подходящее для того же кода. Известно, что такие сообщения могут существовать, их число бесконечно. А вот число небольших кодов или дайджестов, невелико, в сравнении с числом возможных сообщений. Мы стараемся обеспечить, чтобы на подбор другого такого сообщения потребовалось много времени. Я имею в виду, астрономически много. На то, чтобы нашлось другое сообщение, которое дало бы тот же код на выходе. И третье требование, которому должна удовлетворять хорошая хэш-функция, это невозможность восстановления исходных данных по коду. Нужно скрыть информацию. По дайджесту сообщения должно быть невозможно получить какое-либо представление об исходном сообщении, восстановить хоть какие-то детали. Даже такие, как является ли сообщение числом и каким, четным или нечетным. Должно быть невозможно восстановить или как-то догадаться о сути или форме сообщения. И четвертое требование. Код или дайджест, должен выглядеть бессвязным. Как будто вы подбрасывали монеты. И код формировался абсолютно случайным образом. Как будто бы вы зашифровали данные, подбрасывая монеты. Код должен выглядеть случайным и бессвязным. Можно назвать криптографические хэш-функции математическим аналогом мясорубки. То есть, мы берем данные, применяем преобразования и получаем на выходе дайджест, который абсолютно никак не связан с исходным сообщением. Хочу заметить, что эти свойства взаимосвязаны. Например, если хэш-код, по-видимому, абсолютно никак не связан с входными данными и выглядит бессвязно, то при этом повышается и стойкость к коллизиям. Потому что тот факт, что хэш-код выглядит бессмысленно и никак не связан с сообщением, позволяет предположить, что вряд ли два разных сообщения будут преобразованы в одинаковый код. Но иногда одно требование удовлетворяется за счет другого. Я хочу сказать, что на практике, при построении этих алгоритмов, можно только надеяться, что эти требования выполняются. Например, вполне возможно, что вы разработали хэш-функцию и полагаете, что исключили вероятность коллизий, а потом, может через год, кто-то находит хитрый способ организации коллизий. Может быть, кто-то придумает способ, позволяющий избежать простого перебора вариантов. Оказывается, пока что не удалось разработать способа, который позволил бы обходить все, или хотя бы некоторые из этих ограничений. Так что часто мы вынуждены просто верить, что эти алгоритмы дают должную степень защиты. И, напоследок, хочу заметить, что то, что я рассказал вам о хэш-функциях и их свойствах, это лишь приблизительное описание, оно не отличается высокой точностью. Особенно в том, что касается математики. Но надеюсь, вы получили хотя бы общее представление о том, что такое криптографические хэш-функции. Subtitles by the Amara.org community