Для чего нужны хэш функции. Что это такое? Определение хэша и его вычисление

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

Очень краткая история цифровых денег

Биткойн – новый подход к предыдущим экспериментам с цифровыми деньгами. В 1990-х это была горячая, но спекулятивная тема. Даже Алан Гринспен в своей речи в 1996 г. сказал:

Мы предвидим в близком будущем предложения эмитентам электронных платёжных обязательств, таких как карты с хранимой стоимостью или «цифровые деньги», создать специализированные эмиссионные корпорации с сильными балансовыми отчетами и публичными кредитными рейтингами

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

Когда Гринспен произносил свою речь, шифропанки уже экспериментировали с цифровыми валютами с явным намерением дестабилизировать банки. В числе их экспериментов, существовавших до Биткойна, были Hashcash Адама Бэка, BitGold Ника Сабо, B-Money Вэй Дая и RPOW Хэла Финни. Все они использовали возможности криптографических хеш-функций, и вместе они образуют гигантские плечи, на которых сегодня стоит Биткойн.

История

В январе 1953 года Ханс Петер Лун (нем. Hans Peter Luhn) (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую

идею «хеширования».

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation

» первым описал идею «хеширования» такой, какой её знает большинство программистов сейчас. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса»
остаток от деления на простое число
[1].

В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья Уэсли Питерсона (англ. W. Wesley Peterson) о поиске текста в больших файлах

. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой было проведено
обширное
исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, однако никаких значимых работ не публиковалось.

В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем

»[2]. В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в журнале «
Communications of the ACM
» большой
обзор
по «хешированию». Эта работа считается «
ключевой
» публикацией, вводящей понятие о «хешировании» в
научный
оборот, и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).







До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а для «коллизий» использовался термин «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных

» 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: «окрошка». Однако
ни один
из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование»[3].

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

Криптографическая хеш-функция берёт данные и, по сути, переводит их в строку букв и цифр. Вы когда-нибудь пользовались URL-сокращалками типа Bitly или TinyURL? Это нечто похожее. Вы вводите что-то длинное, а на выходе получается что-то короткое, олицетворяющее то длинное. Только в случае криптографических хеш-функций ввод не обязательно должен быть длинным. Это может быть что-то очень короткое (например, слово «пёс») или почти бесконечно длинное (например, весь текст «Повести о двух городах»), и на выходе вы получите уникальную строку установленной длины. Кроме того, в отличие от сокращателей ссылок, хеш-функции, применяемые в Биткойне, действуют только в одном направлении. Хотя одни и те же данные всегда дадут один и тот же хеш, воспроизвести изначальные данные по полученному из них хешу невозможно.

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

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

Определение количества различных подстрок

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

Для решения переберём по очереди длину подстроки: L = 1 .. N.

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

Реализация:

String s, // входная строка int n = (int) s.length(), // считаем все степени p const int p = 31, vector p_pow (s.length()), p_pow = 1, for (size_t i=1, iH (s.length()), for (size_t i=0, i hs (n-l+1), for (int i=0, i 12 мая 2010 в 01:28

  • Информационная безопасность

Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.

О себе

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

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

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

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







Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x 1 , x 2)

двух переменных, где
x 1
,
x 2
и
y
— двоичные векторы длины
m
,
n
и
n
соответственно, причем
n
— длина свертки, а
m
— длина блока сообщения. Для получения значения
h(M)
сообщение сначала разбивается на блоки длины
m
(при этом, если длина сообщения не кратна
m
то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам
M 1 , M 2 ,.., M N
применяют следующую последовательную процедуру вычисления свертки:























H o = v, H i = f(M i ,H i-1), i = 1,.., N, h(M) = H N

Здесь 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

.

В следующей статье

Обзор алгоритмов MD (MD4, MD5, MD6).

Пример

Хеш фразы:

Это было самое прекрасное время, это было самое злосчастное время, – век мудрости, век безумия, дни веры, дни безверия, пора света, пора тьмы, весна надежд, стужа отчаяния, у нас было всё впереди, у нас впереди ничего не было, мы то витали в небесах, то вдруг обрушивались в преисподнюю, – словом, время это было очень похоже на нынешнее, и самые горластые его представители уже и тогда требовали, чтобы о нём – будь то в хорошем или в дурном смысле – говорили не иначе, как в превосходной степени:

df0a199c7fef0a53d9a4144bc9122441b94510c13faf424ca26b65aa5035048f

Тогда как хеш слова «пёс»:

cd6357efdd966de8c0cb2f876cc89ec74ce35f0968e11743987084bd42fb8944

Что такое хэш в криптовалюте

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

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

Как хеш-функции применяются в блокчейне

Чтобы блокчейн работал, он должен обновляться. Подобно банку, он должен вести актуальные записи всех транзакций и активов (например, биткойнов), имеющихся у каждого участника сети. Именно при обновлении транзакционной информации любая аутентифицирующая система уязвима для атаки. Банк сглаживает этот риск благодаря наличию строгой централизованной иерархии, гарантирующей подлинность на свой собственный риск. Так как блокчейну удаётся обновляться, оставаясь децентрализованным? Он использует криптографическую вероятностную хеш-игру, называемую «доказательство выполнения работы» (Proof of Work).

Как используют показатели мегахеша майнеры

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

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

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

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

Хешрейт отражается в фиксированных показателях:

  • Хеш в секунду H/s,
  • Килохеш в секунду KH/s,
  • Мегахеш в секунду MH/s,
  • Гигахэш в секунду GH/s,
  • Терахэш в секунду TH/s,
  • Петахэш в секунду PH/s.

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

Мегахэш — это фактически отражение того, сколько различных хешей вычислительная техника может сгенерировать за одну секунду, например, 1000 мегахешей.

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

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

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

Подсчет мегахеш

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

Криптография обеспечивает консенсус

Чтобы продолжать функционировать, блокчейн должен создавать новые блоки. Так как блокчейны – это децентрализованные системы, новые блоки должны создаваться не единственным аутентифицирующим субъектом, а сетью в целом. Чтобы решить, каким будет новый блок, сеть должна достичь консенсуса. Чтобы достичь консенсуса, майнеры предлагают определённые блоки, блоки верифицируются, и, наконец, сеть выбирает единственный блок, который будет следующей частью реестра. Однако очень много майнеров предлагают идентичные блоки, проходящие верификацию. Так каким образом конкретный блок выбирается, чтобы стать следующим в цепи?

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

Помните хакеров из фильмов, использующих программу, угадывающую миллион паролей в минуту, чтобы взломать компьютер? Это что-то вроде этого. Все майнеры мира одновременно используют похожую программу-угадайку, ищущую правильный нонс, который при добавлении к данным блокчейна и вводе в хеш-функцию SHA-256 даст рандомный хеш, который сам блокчейн «определил» как «решение» задачи. Компьютеры, в каком-то смысле, работают совместно, так как каждый предложенный хеш не может быть предложен снова. Компьютер, первым отгадавший правильное число, выигрывает право на создание следующего блока и получает 12,5 биткойна, что сейчас равно примерно $50 000.

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

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

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

Понравилась статья? Поделиться с друзьями:
Добавить комментарий