Криптографические хэш-функции. Хеш функция требования

Июл 23, 2019 Законы
  • Необратимость или стойкость к восстановлению прообраза: для заданного значения хэш-функции m должно быть вычислительно невозможно найти блок данных X , для которого H(X)=m .
  • Обратимая функция нестойка к коллизиям первого и второго рода.
  • В общем случае, в основе построения хэш-функции лежит итеративная последовательная схема (Структура Меркля-Дамгарда). Ядром алгоритма является сжимающая функция — преобразование k входных в n выходных бит, где n — разрядность хэш-функции, а k — произвольное число большее n . При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

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

    Сжимающая функция на основе симметричного блочного алгоритма

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

    Применения

    Электронная цифровая подпись

  • Повышение криптостойкости. Криптоаналитик не может, используя открытый ключ, подобрать подпись под сообщение, а только под его хэш.
  • Обеспечение совместимости. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хэш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.
  • Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хэш-функции H(pass,R2), где R2 — псевдослучайное, заранее выбранное, число. Клиент посылает запрос (name, R1), где R1 — псевдослучайное, каждый раз новое, число. В ответ сервер посылает значение R2. Клиент вычисляет значение хэш-функции H(R1,H(pass,R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1,H(pass,R2)) и сверяет его с полученным. Если значения совпадают — аутентификация верна.

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

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

    Атака на основе парадокса дней рождений

    Существует длинный перечень криптографических хеш-функций, хотя многие из них были признаны уязвимыми и не должны быть использованы. Даже если хэш-функция никогда не была взломана, успешная атака против ослабленного варианта может подорвать доверие экспертов и привести к отказу от хэш-функции. Например, в августе 2004 года были найдены слаюости в ряде хэш-функций , которые были популярны в то время, в том числе SHA-0, RIPEMD и MD5. Это поставило под сомнение долгосрочную безопасность более поздних алгоритмов, которые являются производными от этих хеш-функций — в частности, SHA-1 ( усиленный вариант SHA-0 ), RIPEMD- 128 , и RIPEMD-160 (оба усиленные версии RIPEMD ). Ни SHA-0 , ни RIPEMD широко не используются, так как они были заменены на более усиленные версии. По состоянию на 2009, двумя наиболее часто используемыми криптографическими хэш-функциями являются MD5 и SHA-1. Тем не менее, MD5 была взломана, атака против него была также использована для взлома SSL в 2008. Функции SHA-0 и SHA-1 были разработаны в АНБ. В феврале 2005 года сообщалось, что проведена успешная атака на SHA-1, найдены коллизии за, примерно, 2 69 операций хэширования, а не в 2 80 , которые ожидаются для 160-битной хэш-функции. В августе 2005 года сообщалось, об еще одном успешном нападении на SHA-1: нахождение коллизии за 2 63 операций. Новые приложения могут избежать этих проблем с безопасностью функции SHA-1 с помощью более продвинутых членов семьи SHA , например, SHA-2. Тем не менее, для обеспечения долгосрочной надежности приложений, использующих хэш-функций, был устроен конкурс на лучший проект — замену SHA-2. 2 октября 2012 года, Keccak был выбран в победителем в конкурсе, устроенном NIST. Версия этого алгоритма как ожидается, станет стандартным FIPS в 2014 году под названием SHA-3. Некоторые из следующих алгоритмов часто используется в приложениях криптографии.Обратите внимание, что этот список не включает кандидатов в текущем конкурсе NIST.

    Хеш функция требования

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

    1. на вход хэш-функции подается сообщение произвольной длины;
    2. на выходе хэш-функции формируется блок данных фиксированной длины;
    3. значения на выходе хэш-функции распределены по равномерному закону;
    4. при изменении одного бита на входе хэш-функции существенно изменяется выход.

    Кроме того, для обеспечения устойчивости хэш-функции к атакам она должна удовлетворять следующим требованиям:

  • если мы знаем значение хэш-функции h, то задача нахождения сообщения M такого, что Н(М) = h, должна быть вычислительно трудной;
  • при заданном сообщении M задача нахождения другого сообщения M’, такого, что Н(М) = H(M’), должна быть вычислительно трудной.
  • Если хэш-функция будет удовлетворять перечисленным свойствам, то формируемое ею значение будет уникально идентифицировать сообщения, и всякая попытка изменения сообщения при передаче будет обнаружена путем выполнения хэширования на принимающей стороне и сравнением с дайджестом, полученным на передающей стороне.

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

    Хэш-функции строятся по итеративной схеме, когда исходное сообщение разбивается на блоки определенного размера, и над ними выполняются ряд преобразований с использованием как обратимых, так и необратимых операций. Как правило, в состав хэширующего преобразования включается сжимающая функция, поскольку его выходзачастую по размеру меньше блока, подаваемого на вход. На вход каждого цикла хэширования подаетсявыход предыдущего цикла, а также очередной блок сообщения. Таким образом, на каждом цикле выход хэш-функции hi представляет собой хэш первых i блоков.

    Если вспомнить, насколько рандомизируют входное сообщение блочные шифры, можно в качестве функции хэш-преобразования использовать какой-нибудь блочный шифр. То, что блочные шифры являются обратимыми преобразованиями, не противоречит свойствам хэш-функции, поскольку блочный шифр необратим по ключу шифрования, и, если в качестве ключа шифрования использовать выход предыдущего шага хэш-преобразования, а в качестве шифруемого сообщения очередной блок сообщения (или наоборот), то можно получить хэш-функцию с хорошими криптографическими характеристиками. Такой подход использован, например, в российском стандарте хэширования – ГОСТ Р 34.11-94. Эта хэш-функция формирует 256-битное выходное значение, используя в качестве преобразующей операции блочный шифр ГОСТ 28147-89 (рис.2.17). Функция хэширования H получает на вход хэш, полученный на предыдущем шаге (значение h произвольное начальное число), а также очередной блок сообщения mi. Ее внутренняя структура представлена на рис.2.18. Здесь в блоке шифрующего преобразования для модификации hi в si используется блочный шифр ГОСТ 28147-89. Перемешивающее преобразование представляет собой модифицированную перестановку Фейштеля. Для последнего блока mN (N – общее количество блоков сообщения) выполняется набивка до размера 256 бит с добавлением истинной длины сообщения.Параллельно подсчитывается контрольная суммасообщения ? и суммарная длина L, которые участвуют в финальной функции сжатия.

    Основным недостатком хэш-функций на основе блочных шифров является невысокая скорость их работы. Поэтому были спроектированы ряд специализированных алгоритмов, которые, обеспечивая аналогичную стойкость к атакам, выполняют гораздо меньшее количество операций над входными данными и обеспечивают большую скорость работы. Примерами подобного рода алгоритмов являются: MD2, MD4, MD5, RIPEMD – 160, SHA. Рассмотрим подробнее структуру алгоритма хэширования SHA (Secure Hash Algorithm), который описан в стандарте SHS и обеспечивает безопасность электронной цифровой подписи DSA, формируя 160-битный дайджест сообщения.

    Сначала сообщение разбивается на блоки длиной 512 бит. Если длина сообщения не кратна 512, к последнему блоку приписывается справа 1, после чего он дополняется нулями до 512 бит. В конец последнего блока записывается код длины сообщения. В результате сообщение приобретает вид n 512-разрядных блоков M1, M2, …, Mn.

    Алгоритм SHA использует 80 логических функций f, f1, …, f79, которые производят операции над тремя 32-разрядными словами (B,C,D):

    ft(B, C, D) = (B ? C) ? ((¬B) ? D) для 0 ? t ? 19
    ft(B, C, D) = B ? C ? D для 20 ? t ? 39
    ft(B, C, D) = (B ? C) ? (B ? D) ? (C ? D) для 40 ? t ? 59
    ft(B, C, D) = B ? C ? D для 60 ? t ? 79

    В алгоритме используются также специальным образом инициализированные 4 константы Ki и 5 начальных значений Hi.

    Делим массив M на группы из 16 слов W, W1,…,W15 (W самое левое слово).
    Для t = 16 — 79 Wt = S 1 (Wt-3 ? Wt-8 ? Wt-14 ? Wt-16)
    S k означает операцию циклического сдвига влево на k разрядов.
    Пусть теперь A = H, B = H1, C = H2, D = H3, E = H4.
    for t = 0 to 79 do
    TEMP = S 5 (A) + f t (B, C, D) + E + Wt + Ki.
    E = D; D = C; C = S 30 (B); B = A; A = TEMP;
    Пусть H = H + A; H1 = H1 + B; H2 = H2 + C; H3 = H3 + D; H4 = H4 + E.

    Графически один цикл SHA представлен на рис.2.19.

    В результате обработки массива М будет получено 5 слов H, H1, H2, H3, H4 с общей длиной 160 бит, которые и образуют дайджест сообщения.

    Из приведенных данных ясно, что сложность американского стандарта хэширования ниже, чем у российского. Российский стандарт предполагает выполнение четырех шифрований за один цикл выработки хэша, или в общей сложности 128 раундов. Каждый раунд шифрования требует примерно полтора десятка элементарных машинных операций, что существенно увеличивает затраты машинного времени на выполнение линейных перемешивающих операций. Один раунд выработки хэша SHA гораздо проще: он весь может быть реализован примерно за 15-20 команд, общее количество раундов всего 80, и за один цикл выработки хэша обрабатывается вдвое больше исходных данных — 512 против 256 в ГОСТ P34.ll — 94. Таким образом, можно предположить, что быстродействие программных реализаций SHA будет примерно в 3-6 раз быстрее, чем у отечественного стандарта.

    Основная задача хэш-функций – генерация дайджестов, уникальных для конкретного документа. Если для двух различных входных блоков хэш-функция дает одинаковый дайджест, такая ситуация называется хэш-коллизией. Из теоремы, носящей название «парадокс дней рождения», следует, что для n-битного хэш-значения необходимо в среднем 2 n/2 различных входных сообщений, чтобы возникла коллизия. Это делает практически невозможным изменение документа при его подписи с помощью, например, алгоритма SHА путем простого подбора, поскольку при таком подходе потребуется сгенерировать около 2 80 различных сообщений, чтобы получить аналогичное подменяемому по получаемому дайджесту. Эта цифра недостижима для современного уровня технологий.

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

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

    Contents

    Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, дли- ны (называемую значением хэш-функции). В качестве простой хэшфункции можно рассматривать функцию, которая получает прообраз и возвращает байт, представляющий собой XOR всех входных байтов. Смысл хэш-функции состоит в получении характерного признака, прообраза-значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш-функция представляет собой соотношение «многие к одному», невозможно со всей деленностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности. Однонаправленная хэш-функция – это хэш-функция, которая работает только в одном направлении. Легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленными: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такой вариант невозможен. Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функции заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа. Изменение одного бита прообраза приводит к изменению (в среднем) половины битов значения хэш-функции, что известно также как лавинный эффект. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш-функции

    Требования

    Для того, чтобы хэш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хэш-функций в криптографии:

  • Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений (M, M’) , имеющих одинаковый хэш.
  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.
  • Следует отметить, что не доказано существование необратимых хэш-функций, для которых вычисление какого-либо прообраза заданного значения хэш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей.

    Атака «дней рождения» позволяет находить коллизии для хэш-функции с длиной значений n битов в среднем за примерно 2 n/2 вычислений хэш-функции. Поэтому n – битная хэш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2 n/2 .

    Принципы построения

    Входной поток разбивается на блоки по (k-n) бит. Алгоритм использует временную переменную размером в n бит, в качестве начального значения которой берется некое произвольное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хэш-функции являются выходные n бит последней итерации. Каждый бит выходного значения хэш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.

    Таким образом, мы получаем 64 варианта построения сжимающей функции. Большинство из них являются либо тривиальными, либо небезопасными. Ниже изображены четыре наиболее безопасные схемы при всех видах атак.

    В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хэш-значения. Xранение самих паролей нецелесообразно, так как в случае несанкционированного доступа к файлу с паролями злоумышленник получает их в открытом и сразу готовом к использованию виде, а при хранении хэш-значений он узнает лишь хэши, которые не обратимы в исходные данные. В ходе процедуры аутентификации вычисляется хэш-значение введённого пароля, и сравнивается с хранимым.

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

    Случайный оракул

    Предположим, что функция хэширования h действительно является случайным оракулом. В атаке по методу квадратного корня (атака на основе парадокса дней раждения) предполагается, что для обнаружения коллизий с ненулевой вероятностью достаточно выполнить 2 в степени |h|/2 случайных вычислений значения функции хэширования. Для организации атаки на основе парадокса дней рождений атакующий должен сгенерировать пары «сообщение-хэшированное значение», пока не обнаружаться два сообщения m и m`, удовлетворяющие условиям m не равно m`, h(m)=h(m`). Такая пара сообщений называется коллизией(collision) функции хэширования h. Например, для функции хэшироания SHA-1 выполняется условие |h|=160, а значит его стойкость на основе парадокса дней рождения оценивается величиной 2 80 .

    Сравнительная характеристика наиболее известных функций

    Хэш-алгоритмы

    О себе

    Студент кафедры информационной безопасности.

    О хэшировании

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

    Хэш-функцией называется всякая функция h:X -> Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X — множество всех сообщений, Y — множество двоичных векторов фиксированной длины.

    Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x1, x2) двух переменных, где x1, x2 и y — двоичные векторы длины m, n и n соответственно, причем n — длина свертки, а m — длина блока сообщения.
    Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M2. MN применяют следующую последовательную процедуру вычисления свертки:

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

    Выделяют два важных вида криптографических хэш-функций — ключевые и бесключевые. Ключевые хэш-функции называют кодами аутентификации сообщений. Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.
    Бесключевые хэш-функции называются кодами обнаружения ошибок. Они дают возможность с помощью дополнительных средств (шифрования, например) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями.

    О статистических свойствах и требованиях

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

    К ключевым функциям хэширования предъявляются следующие требования:
    — невозможность фабрикации,
    — невозможность модификации.

    Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.

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

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

    Это была теоретическая часть, которая пригодится нам в дальнейшем…

    О популярных хэш-алгоритмах

    Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).

    Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
    Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
    Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

    Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

    Российский стандарт — ГОСТ 34.11-94.

    Постановка задачи

  • Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N , для которого H(N)=H(M) .
  • Данные требования не являются независимыми:

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

    Итеративная последовательная схема

    При проектировании хэш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен (k-n) . Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.

    Обычно при построении хэш-функции используют более сложную систему. Обобщенная схема симметричного блочного алгоритма шифрования изображена на рис.2

    Основным недостатком хэш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хэширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них — MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

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

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

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

    Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows. В них хранятся лишь хэш-значения парольных фраз из учётных записей пользователей.

    Хеш-функция

    Понятие и роль хеш-функции

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

    В качестве исходных данных может служить сколь угодно большая последовательность букв и цифр. Результат хеширования всегда будет иметь неизменную длину. По сути, хеш-функция представляет собой калькулятор, по сложной формуле вычисляющий сумму всех исходных данных. Ее можно уподобить некоему черному ящику, используемому для шифрования информации. Неподготовленному человеку может показаться невероятным, чтобы практически бесконечное число символов можно было преобразовать в уникальную строку, которая состоит всего из нескольких сотен бит. Однако именно это делают хеш-функции. Используя данную технологию, можно преобразовать целый толстый том в одну строку из 64 символов. Получить исходные данные из результата вычислений невозможно. Но если знать алгоритм вычисления, то на основе одних и тех же исходных данных путем повторных расчетов всегда будет получен одинаковый хеш. Хеширование используется в криптовалютах и в любых блокчейнах. Именно оно обеспечивает защиту блокчейнов, сохранность денежных средств и возможность осуществлять обменные операции между владельцами криптовалют.

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

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

  • CRC – контрольная сумма. Эта хеш-функция отличается простотой и имеет множество вариантов в зависимости от требуемой выходной длины дайджеста сообщения. Однако ввиду ее простоты она не относится к криптографическим.
  • MD5 – весьма популярная криптографическая функция свертки. Длина хеша равна 128 бит.
  • SHA-1 – также весьма распространенная криптографическая функция свертки. Длина дайджеста сообщения равна 160 бит.
  • ГОСТ Р 34.11-94 – российский криптографический стандарт хеширования. Длина дайджеста сообщения составляет 256 бит.
  • Любая хеш-функция должна отвечать следующим требованиям:

    • преобразовывать исходные данные произвольного размера в строку фиксированной длины;
    • иметь открытый алгоритм для обеспечения возможности исследовать ее криптоустойчивость;
    • отсутствие необходимости использования значительных вычислительных ресурсов.
    • В биткойне используется хеш-функция SHA-256. Она работает на основе чрезвычайно сложной формулы, которая связана с отражением светового излучения от эллипсов. Результатом вычислений данной функции являются дайджесты сообщений длиной 64 символа или 256 бит.

      Основные требования к криптографическим хеш-функциям

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

    • Необратимость. Это означает, что для определенного значения функции свертки k должно быть невозможно вычислить блок данных Y, для которого H(Y) = k.
    • Устойчивость к коллизиям первого рода. Это значит, что для заданного сообщения M нельзя путем вычислений найти другое сообщение K, для которого H(K) = H(M).
    • Устойчивость к коллизиям второго рода. Под эти понимается невозможность путем вычислений найти пару сообщений (M, M’) с одинаковым дайджестом сообщения.

    Указанные требования являются зависимыми друг от друга:

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

    Будьте в курсе всех важных событий United Traders — подписывайтесь на наш телеграм-канал

По admin

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *