хэш код что это
Разбираемся с hashCode() и equals()
Что такое хеш-код?
Если очень просто, то хеш-код — это число. На самом деле просто, не так ли? Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины (википедия).
Пример №1
Выполним следующий код:
Вторая часть объяснения гласит:
полученная из массива произвольной длины.
В итоге, в терминах Java, хеш-код — это целочисленный результат работы метода, которому в качестве входного параметра передан объект.
Подведём итог:
Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.
Понятие эквивалентности. Метод equals()
Начнем с того, что в java, каждый вызов оператора new порождает новый объект в памяти. Для иллюстрации создадим какой-нибудь класс, пускай он будет называться “BlackBox”.
Пример №2
Выполним следующий код:
Во втором примере, в памяти создастся два объекта.
Эквивалентность и хеш-код тесно связанны между собой, поскольку хеш-код вычисляется на основании содержимого объекта (значения полей) и если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые (см. правило 2).
Класс Object
При сравнение объектов, операция “ == ” вернет true лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
Заглянем в исходный код метода hashCode() в классе Object :
При вычислении хэш-кода для объектов класса Object по умолчанию используется Park-Miller RNG алгоритм. В основу работы данного алгоритма положен генератор случайных чисел. Это означает, что при каждом запуске программы у объекта будет разный хэш-код.
Но, как мы помним, должно выполняться правило: “если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые ”. Поэтому, при создании пользовательского класса, принято переопределять методы hashCode() и equals() таким образом, что бы учитывались поля объекта.
Это можно сделать вручную либо воспользовавшись средствами генерации исходного кода в IDE. Например, в Eclipse это Source → Generate hashCode() and equals().
В итоге, класс BlackBox приобретает вид:
Теперь методы hashCode() и equals() работают корректно и учитывают содержимое полей объекта:
Кому интересно переопределение в ручную, можно почитать Effective Java — Joshua Bloch, chapter 3, item 8,9.
Алгоритм хеширования данных: просто о сложном
Криптографические хэш-функции распространены очень широко. Они используются для хранения паролей при аутентификации, для защиты данных в системах проверки файлов, для обнаружения вредоносного программного обеспечения, для кодирования информации в блокчейне (блок — основной примитив, обрабатываемый Биткойном и Эфириумом). В этой статье пойдет разговор об алгоритмах хеширования: что это, какие типы бывают, какими свойствами обладают.
В наши дни существует много криптографических алгоритмов. Они бывают разные и отличаются по сложности, разрядности, криптографической надежности, особенностям работы. Алгоритмы хеширования — идея не новая. Они появилась более полувека назад, причем за много лет с принципиальной точки зрения мало что изменилось. Но в результате своего развития хеширование данных приобрело много новых свойств, поэтому его применение в сфере информационных технологий стало уже повсеместным.
Что такое хеш (хэш, hash)?
Хеш или хэш — это криптографическая функция хеширования (function), которую обычно называют просто хэшем. Хеш-функция представляет собой математический алгоритм, который может преобразовать произвольный массив данных в строку фиксированной длины, состоящую из цифр и букв.
Основная идея используемых в данном случае функций — применение детерминированного алгоритма. Речь идет об алгоритмическом процессе, выдающем уникальный и предопределенный результат при получении входных данных. То есть при приеме одних и тех же входных данных будет создаваться та же самая строка фиксированной длины (использование одинакового ввода каждый раз приводит к одинаковому результату). Детерминизм — важное свойство этого алгоритма. И если во входных данных изменить хотя бы один символ, будет создан совершенно другой хэш.
Убедиться в этом можно на любом онлайн-генераторе. Набрав слово «Otus» и воспользовавшись алгоритмом sha1 (Secure Hashing Algorithm), мы получим хеш 7576750f9d76fab50762b5987739c18d99d2aff7. При изменении любой буквы изменится и результат, причем изменится полностью. Мало того, если просто поменять регистр хотя бы одной буквы, итог тоже будет совершенно иным: если написать «otus», алгоритм хэш-функции отработает со следующим результатом: 1bbd70dc1b6fc84e5617ca8703c72c744b3b4fc1. Хотя общие моменты все же есть: строка всегда состоит из сорока символов.
В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.
Криптостойкость функций хеширования
Говоря о криптостойкости, предполагают выполнение ряда требований. То есть хороший алгоритм обладает несколькими свойствами: — при изменении одного бита во входных данных, должно наблюдаться изменение всего хэша; — алгоритм должен быть устойчив к коллизиям; — алгоритм должен быть устойчив к восстановлению хешируемых данных, то есть должна обеспечиваться высокая сложность нахождения прообраза, а вычисление хэша не должно быть простым.
Проблемы хэшей
Одна из проблем криптографических функций хеширования — неизбежность коллизий. Раз речь идет о строке фиксированной длины, значит, существует вероятность, что для каждого ввода возможно наличие и других входов, способных привести к тому же самому хешу. В результате хакер может создать коллизию, позволяющую передать вредоносные данные под видом правильного хэша.
Цель хороших криптографических функций — максимально усложнить вероятность нахождения способов генерации входных данных, хешируемых с одинаковым значением. Как уже было сказано ранее, вычисление хэша не должно быть простым, а сам алгоритм должен быть устойчив к «атакам нахождения прообраза». Необходимо, чтобы на практике было чрезвычайно сложно (а лучше — невозможно) вычислить обратные детерминированные шаги, которые предприняты для воспроизведения созданного хешем значения.
Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.
Алгоритм MD5 и его подверженность взлому
MD5 hash — один из первых стандартов алгоритма, который применялся в целях проверки целостности файлов (контрольных сумм). Также с его помощью хранили пароли в базах данных web-приложений. Функциональность относительно проста — алгоритм выводит для каждого ввода данных фиксированную 128-битную строку, задействуя для вычисления детерминированного результата однонаправленные тривиальные операции в нескольких раундах. Особенность — простота операций и короткая выходная длина, в результате чего MD5 является относительно легким для взлома. А еще он обладает низкой степенью защиты к атаке типа «дня рождения».
Атака дня рождения
Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.
Вывод прост: если есть фиксированные ограничения на выход, значит, есть и фиксированная степень перестановок, на которых существует возможность обнаружить коллизию.
Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.
SHA1, SHA2, SHA3
Secure Hashing Algorithm (SHA1) — алгоритм, созданный Агентством национальной безопасности (NSA). Он создает 160-битные выходные данные фиксированной длины. На деле SHA1 лишь улучшил MD5 и увеличил длину вывода, а также увеличил число однонаправленных операций и их сложность. Однако каких-нибудь фундаментальных улучшений не произошло, особенно когда разговор шел о противодействии более мощным вычислительным машинам. Со временем появилась альтернатива — SHA2, а потом и SHA3. Последний алгоритм уже принципиально отличается по архитектуре и является частью большой схемы алгоритмов хеширования (известен как KECCAK — «Кетч-Ак»). Несмотря на схожесть названия, SHA3 имеет другой внутренний механизм, в котором используются случайные перестановки при обработке данных — «Впитывание» и «Выжимание» (конструкция «губки»).
Что в будущем?
Вне зависимости от того, какие технологии шифрования и криптографические новинки будут использоваться в этом направлении, все сводится к решению одной из двух задач: 1) увеличению сложности внутренних операций хэширования; 2) увеличению длины hash-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.
И, несмотря на появление в будущем квантовых компьютеров, специалисты уверены, что правильные инструменты (то же хэширование) способны выдержать испытания временем, ведь ни что не стоит на месте. Дело в том, что с увеличением вычислительных мощностей снижается математическая формализация структуры внутренних алгоритмических хэш-конструкций. А квантовые вычисления наиболее эффективны лишь в отношении к вещам, имеющим строгую математическую структуру.
Что такое Хэширование? Под капотом блокчейна
Так что же такое хэширование?
Простыми словами, хэширование означает ввод информации любой длины и размера в исходной строке и выдачу результата фиксированной длины заданной алгоритмом функции хэширования. В контексте криптовалют, таких как Биткоин, транзакции после хэширования на выходе выглядят как набор символов определённой алгоритмом длины (Биткоин использует SHA-256).
Input- вводимые данные, hash- хэш
Посмотрим, как работает процесс хэширования. Мы собираемся внести определенные данные. Для этого, мы будем использовать SHA-256 (безопасный алгоритм хэширования из семейства SHA-2, размером 256 бит).
Как видите, в случае SHA-256, независимо от того, насколько объёмные ваши вводимые данные (input), вывод всегда будет иметь фиксированную 256-битную длину. Это крайне необходимо, когда вы имеете дело с огромным количеством данных и транзакций. Таким образом, вместо того, чтобы помнить вводимые данные, которые могут быть огромными, вы можете просто запомнить хэш и отслеживать его. Прежде чем продолжать, необходимо познакомиться с различными свойствами функций хэширования и тем, как они реализуются в блокчейн.
Криптографические хэш-функции
Криптографическая хэш-функция — это специальный класс хэш-функций, который имеет различные свойства, необходимые для криптографии. Существуют определенные свойства, которые должна иметь криптографическая хэш-функция, чтобы считаться безопасной. Давайте разберемся с ними по очереди.
Свойство 1: Детерминированние
Это означает, что независимо от того, сколько раз вы анализируете определенный вход через хэш-функцию, вы всегда получите тот же результат. Это важно, потому что если вы будете получать разные хэши каждый раз, будет невозможно отслеживать ввод.
Свойство 2: Быстрое вычисление
Хэш-функция должна быть способна быстро возвращать хэш-вход. Если процесс не достаточно быстрый, система просто не будет эффективна.
Свойство 3: Сложность обратного вычисления
Сложность обратного вычисления означает, что с учетом H (A) невозможно определить A, где A – вводимые данные и H(А) – хэш. Обратите внимание на использование слова “невозможно” вместо слова “неосуществимо”. Мы уже знаем, что определить исходные данные по их хэш-значению можно. Возьмем пример.
Предположим, вы играете в кости, а итоговое число — это хэш числа, которое появляется из кости. Как вы сможете определить, что такое исходный номер? Просто все, что вам нужно сделать, — это найти хэши всех чисел от 1 до 6 и сравнить. Поскольку хэш-функции детерминированы, хэш конкретного номера всегда будет одним и тем же, поэтому вы можете просто сравнить хэши и узнать исходный номер.
Но это работает только тогда, когда данный объем данных очень мал. Что происходит, когда у вас есть огромный объем данных? Предположим, вы имеете дело с 128-битным хэшем. Единственный метод, с помощью которого вы должны найти исходные данные, — это метод «грубой силы». Метод «грубой силы» означает, что вам нужно выбрать случайный ввод, хэшировать его, а затем сравнить результат с исследуемым хэшем и повторить, пока не найдете совпадение.
Итак, что произойдет, если вы используете этот метод?
Свойство 4: Небольшие изменения в вводимых данных изменяют хэш
Даже если вы внесете небольшие изменения в исходные данные, изменения, которые будут отражены в хэше, будут огромными. Давайте проверим с помощью SHA-256:
Видите? Даже если вы только что изменили регистр первой буквы, обратите внимание, насколько это повлияло на выходной хэш. Это необходимая функция, так как свойство хэширования приводит к одному из основных качеств блокчейна – его неизменности (подробнее об этом позже).
Свойство 5: Коллизионная устойчивость
Учитывая два разных типа исходных данных A и B, где H (A) и H (B) являются их соответствующими хэшами, для H (A) не может быть равен H (B). Это означает, что, по большей части, каждый вход будет иметь свой собственный уникальный хэш. Почему мы сказали «по большей части»? Давайте поговорим об интересной концепции под названием «Парадокс дня рождения».
Что такое парадокс дня рождения?
Если вы случайно встречаете незнакомца на улице, шанс, что у вас совпадут даты дней рождений, очень мал. Фактически, если предположить, что все дни года имеют такую же вероятность дня рождения, шансы другого человека, разделяющего ваш день рождения, составляют 1/365 или 0,27%. Другими словами, он действительно низкий.
Однако, к примеру, если собрать 20-30 человек в одной комнате, шансы двух людей, разделяющих тот же день, резко вырастает. На самом деле, шанс для 2 человек 50-50, разделяющих тот же день рождения при таком раскладе.
Как это применяется в хэшировании?
Предположим, у вас есть 128-битный хэш, который имеет 2 ^ 128 различных вероятностей. Используя парадокс дня рождения, у вас есть 50% шанс разбить коллизионную устойчивость sqrt (2 ^ 128) = 2 ^ 64.
Как вы заметили, намного легче разрушить коллизионную устойчивость, нежели найти обратное вычисление хэша. Для этого обычно требуется много времени. Итак, если вы используете такую функцию, как SHA-256, можно с уверенностью предположить, что если H (A) = H (B), то A = B.
Свойство 6: Головоломка
Свойства Головоломки имеет сильнейшее воздействие на темы касающиеся криптовалют (об этом позже, когда мы углубимся в крипто схемы). Сначала давайте определим свойство, после чего мы подробно рассмотрим каждый термин.
Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вводные данные x такие, что H (k | x) = Y.
Вероятно, это, выше вашего понимания! Но все в порядке, давайте теперь разберемся с этим определением.
В чем смысл «высокой мин-энтропии»?
Это означает, что распределение, из которого выбрано значение, рассредоточено так, что мы выбираем случайное значение, имеющее незначительную вероятность. В принципе, если вам сказали выбрать число от 1 до 5, это низкое распределение мин-энтропии. Однако, если бы вы выбрали число от 1 до бесконечности, это — высокое распределение мин-энтропии.
Что значит «к|х»?
«|» обозначает конкатенацию. Конкатенация означает объединение двух строк. Например. Если бы я объединила «голубое» и «небо», то результатом было бы «голубоенебо».
Итак, давайте вернемся к определению.
Предположим, у вас есть выходное значение «Y». Если вы выбираете случайное значение «К», невозможно найти значение X, такое, что хэш конкатенации из K и X, выдаст в результате Y.
Еще раз обратите внимание на слово «невозможно», но не исключено, потому что люди занимаются этим постоянно. На самом деле весь процесс майнинга работает на этом (подробнее позже).
Примеры криптографических хэш-функций:
1. Указатели
2. Связанные списки
Указатели
В программировании указатели — это переменные, в которых хранится адрес другой переменной, независимо от используемого языка программирования.
Например, запись int a = 10 означает, что существует некая переменная «a», хранящая в себе целочисленное значение равное 10. Так выглядит стандартная переменная.
Однако, вместо сохранения значений, указатели хранят в себе адреса других переменных. Именно поэтому они и получили свое название, потому как буквально указывают на расположение других переменных.
Связанные списки
Связанный список является одним из наиболее важных элементов в структурах данных. Структура связанного списка выглядит следующим образом:
*Head – заголовок; Data – данные; Pointer – указатель; Record – запись; Null – ноль
Это последовательность блоков, каждый из которых содержит данные, связанные со следующим с помощью указателя. Переменная указателя в данном случае содержит адрес следующего узла, благодаря чему выполняется соединение. Как показано на схеме, последний узел отмечен нулевым указателем, что означает, что он не имеет значения.
Важно отметить, что указатель внутри каждого блока содержит адрес предыдущего. Так формируется цепочка. Возникает вопрос, что это значит для первого блока в списке и где находится его указатель?
Первый блок называется «блоком генезиса», а его указатель находится в самой системе. Выглядит это следующим образом:
*H ( ) – Хэшированные указатели изображаются таким образом
Если вам интересно, что означает «хэш-указатель», то мы с радостью поясним.
Как вы уже поняли, именно на этом основана структура блокчейна. Цепочка блоков представляет собой связанный список. Рассмотрим, как устроена структура блокчейна:
* Hash of previous block header – хэш предыдущего заголовка блока; Merkle Root – Корень Меркла; Transactions – транзакции; Simplified Bitcoin Blockchain – Упрощенный блокчейн Биткоина.
Блокчейн представляет собой связанный список, содержащий данные, а так же указатель хэширования, указывающий на предыдущий блок, создавая таким образов связную цепочку. Что такое хэш-указатель? Он похож на обычный указатель, но вместо того, чтобы просто содержать адрес предыдущего блока, он также содержит хэш данных, находящихся внутри предыдущего блока. Именно эта небольшая настройка делает блокчейн настолько надежным. Представим на секунду, что хакер атакует блок 3 и пытается изменить данные. Из-за свойств хэш-функций даже небольшое изменение в данных сильно изменит хэш. Это означает, что любые незначительные изменения, произведенные в блоке 3, изменят хэш, хранящийся в блоке 2, что, в свою очередь, изменит данные и хэш блока 2, а это приведет к изменениям в блоке 1 и так далее. Цепочка будет полностью изменена, а это невозможно. Но как же выглядит заголовок блока?
* Prev_Hash – предыдущий хэш; Tx – транзакция; Tx_Root – корень транзакции; Timestamp – временная отметка; Nonce – уникальный символ.
Заголовок блока состоит из следующих компонентов:
· Версия: номер версии блока
· Время: текущая временная метка
· Текущая сложная цель (См. ниже)
· Хэш предыдущего блока
· Уникальный символ (См. ниже)
· Хэш корня Меркла
Прямо сейчас, давайте сосредоточимся на том, что из себя представляет хэш корня Меркла. Но до этого нам необходимо разобраться с понятием Дерева Меркла.
Что такое Дерево Меркла?
Источник: Wikipedia
На приведенной выше диаграмме показано, как выглядит дерево Меркла. В дереве Меркла каждый нелистовой узел является хэшем значений их дочерних узлов.
Листовой узел: Листовые узлы являются узлами в самом нижнем ярусе дерева. Поэтому, следуя приведенной выше схеме, листовыми будут считаться узлы L1, L2, L3 и L4.
Дочерние узлы: Для узла все узлы, находящиеся ниже его уровня и которые входят в него, являются его дочерними узлами. На диаграмме узлы с надписью «Hash 0-0» и «Hash 0-1» являются дочерними узлами узла с надписью «Hash 0».
Корневой узел: единственный узел, находящийся на самом высоком уровне, с надписью «Top Hash» является корневым.
Так какое же отношение Дерево Меркла имеет к блокчейну?
Каждый блок содержит большое количество транзакций. Будет очень неэффективно хранить все данные внутри каждого блока в виде серии. Это сделает поиск какой-либо конкретной операции крайне громоздким и займет много времени. Но время, необходимое для выяснения, на принадлежность конкретной транзакции к этому блоку или нет, значительно сокращается, если Вы используете дерево Меркла.
Давайте посмотрим на пример на следующем Хэш-дереве:
Изображение предоставлено проектом: Coursera
Теперь предположим, я хочу узнать, принадлежат ли эти данные блоку или нет:
Вместо того, чтобы проходить через сложный процесс просматривания каждого отдельного процесса хэша, а также видеть принадлежит ли он данным или нет, я просто могу отследить след хэша, ведущий к данным:
Это значительно сокращает время.
Хэширование в майнинге: крипто-головоломки.
Когда мы говорим «майнинг», в основном, это означает поиск нового блока, который будет добавлен в блокчейн. Майнеры всего мира постоянно работают над тем, чтобы убедиться, что цепочка продолжает расти. Раньше людям было проще работать, используя для майнинга лишь свои ноутбуки, но со временем они начали формировать «пулы», объединяя при этом мощность компьютеров и майнеров, что может стать проблемой. Существуют ограничения для каждой криптовалюты, например, для биткоина они составляют 21 миллион. Между созданием каждого блока должен быть определенный временной интервал заданный протоколом. Для биткоина время между созданием блока занимает всего 10 минут. Если бы блокам было разрешено создаваться быстрее, это привело бы к:
Процесс Майнинга
Примечание: в этом разделе мы будем говорить о выработке биткоинов.
Когда протокол Биткоина хочет добавить новый блок в цепочку, майнинг – это процедура, которой он следует. Всякий раз, когда появляется новый блок, все их содержимое сначала хэшируется. Если подобранный хэш больше или равен, установленному протоколом уровню сложности, он добавляется в блокчейн, а все в сообществе признают новый блок.
Однако, это не так просто. Вам должно очень повезти, чтобы получить новый блок таким образом. Так как, именно здесь присваивается уникальный символ. Уникальный символ (nonce) — это одноразовый код, который объединен с хэшем блока. Затем эта строка вновь меняется и сравнивается с уровнем сложности. Если она соответствует уровню сложности, то случайный код изменяется. Это повторяется миллион раз до тех пор, пока требования не будут наконец выполнены. Когда же это происходит, то блок добавляется в цепочку блоков.
• Выполняется хэш содержимого нового блока.
• К хэшу добавляется nonce (специальный символ).
• Новая строка снова хэшируется.
• Конечный хэш сравнивается с уровнем сложности, чтобы проверить меньше он его или нет
• Если нет, то nonce изменяется, и процесс повторяется снова.
• Если да, то блок добавляется в цепочку, а общедоступная книга (блокчейн) обновляется и сообщает нодам о присоединении нового блока.
• Майнеры, ответственные за данный процесс, награждаются биткоинами.
Помните номер свойства 6 хэш-функций? Удобство использования задачи?
Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вход x таким образом, H (k | x) = Y.
Так что, когда дело доходит до майнинга биткоинов:
• К = Уникальный символ
• x = хэш блока
• Y = цель проблемы
Весь процесс абсолютно случайный, основанный на генерации случайных чисел, следующий протоколу Proof Of Work и означающий: