Хэширование в blockchain.что такое хэш сумма

Оглавление

Какие проблемы это решает?

Пресловутая угадайка: актуален ли файл в кэше?

  • Больше не нужно отправлять запрос и сличать полученные ETags.
  • Даже если файл в кэше вроде как устарел, но хэш совпадает — его можно смело использовать.
  • Чистка кэша как средство решения проблем частично теряет актуальность.

Дилемма: jQuery со своего домена или с CDN?

Владельцам малых сайтов часто приходится выбирать: либо подключать jQuery и/или подобные ей библиотеки с CDN (гугловского, например), или со своего домена.
В первом случае уменьшается время загрузки сайта (в том числе первичной, т.е. при первом заходе посетителя на сайт) за счёт того, что файл с серверов Гугла с большой долей вероятности уже есть в кэше браузера. Но, например, разработчики WordPress придерживаются второго варианта, ставя во главу угла автономность

И в условиях, когда CDN падают, блокируются и т.д., их можно понять.
Теперь от такой проблемы можно будет избавиться навсегда: не всё ли равно, откуда получен файл, если его содержимое — это ровно то, что нужно html-странице, и она это удостоверяет? Можно смело указывать свой домен, и если библиотека есть в кэше (неважно, загруженная с этого сайта, другого «малого» сайта или из какого-нибудь CDN) — она подхватится

Смешанный HTTPS/HTTP-контент

Одна из причин запрета загрузки HTTP-ресурсов на HTTPS-страницах — возможность подмены HTTP-контента. Теперь это больше не преграда: браузер может получить требуемый контент и сверить его хэш с хэшем, переданным по HTTP. Отмена запрета на смешанный контент (при наличии и совпадении хэша) позволит ускорить распространение HTTPS.

Косвенное определение истории по времени загрузки статики

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

Популярные вопросы о хэше

Что такое хэш и хэш-функция?

Хэш-функции — это математические функции, которые преобразуют или «отображают» заданный набор данных в битовую строку фиксированного размера, также известную как «хэш» (хэш кодом, хэш суммой, значением хэша и т.д.).

Как рассчитывается хэш?

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

Для чего используются хэши в блокчейнах?

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

Что такое хешрейт криптовалюты (блокчейна)?

Хешрейт определяет вычислительный потенциал криптодобывающего устройства и общую мощность распределенной сети. Слово «hashrate» происходит от двух английских слов «hash» и «rate». Слово «rate» обозначает скорость, а hash это буквенно-цифровой код фиксированной длины, который используется для передачи зашифрованных данных.

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

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

Это означает, что каждый набор данных будет иметь свой собственный уникальный хеш.

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

Этим термином обозначается и совокупная вычислительная мощность, которая используется для майнинга и обработки транзакций на блокчейне Proof-of-Work, таком как Bitcoin и Ethereum (до обновления 2.0).

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

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

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

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

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

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

3.5. Нахождение коллизий для 7,5-раундовой функции сжатия ГОСТ Р

r2r4Рис. 4. Внутренняя фаза поиска коллизии для 7,5-раундовой функции сжатия ГОСТ Р

3.5.1. Внутренняя субфаза 1

  • Начинаем с разности в 8 байтах в первом столбце R3 и продвигаемся в обратном направлении к R2S.
  • Для каждой разности в 8 байтах в первом столбце R1P продвигаемся вперед до R2. Поскольку различных значений разности в R1P всего 264, мы можем получить 264 разностей для R2. После поиска соответствия данные разности приводят примерно к 264 действительным значениям. Однако, мы можем выполнять поиск соответствия для каждой строки независимо и получать 28 действительных значений для строки. Следовательно, трудоемкость генерации 264 действительных значений, соответствующих дифференциальному пути, составляет всего 28 раундовых преобразований.

964R2SR5

3.5.2. Внутренняя субфаза 2

R2SR564R2S64R5k3k4k564LPR2SR2LXk5-1Xk5PSTP-1L-1R5R2SR5Рис. 5. Внутренняя субфаза 2 атаки по нахождению коллизии для 7,5-раундовой функции сжатия ГОСТ РR2LR4SR2*T64R2SR564R2*T64R2*R2S64TR5R2*T96564R3*

  • Поскольку разность в R3* известна, для выбранного значения первой строки R3* вычисляем в прямом направлении значения первой строки R3L и разность для первой строки R4.
  • После выполнения поиска соответствия для разности первой строки R4 и R4S мы рассчитываем найти решение для первой строки R4. Поскольку первая строка значений R3L нам известна, мы можем далее вычислить значение первой строки k4.
  • Вычисляем первые строки для k3*, R2*, R4S и T. Поскольку для первой строки как R2*, так и R4S мы имеем около 264 значений, мы рассчитываем найти соответствие между ними. Другими словами, мы теперь соединили и значения, и разности для первой строки.

R2*T64k3*6464R2*T64128166412812812864R364R4SR3R4S64192

Что в будущем?

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

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

Как появилось понятие хэш?

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

Дата (год) Хронология событий
1953 Известный математик и программист Дональд Кнут авторитетно считает, что именно в этот промежуток времени сотрудник IBM Ханс Питер Лун впервые предложил идею хеширования.
1956 Арнольд Думи явил миру такой принцип хеширования, какой знают его подавляющее большинство современных программистов. Именно эта «светлая голова» предложила считать хэш-кодом остаток деления на любое простое число. Кроме этого, исследователь видел идеальное хеширование инструментов для позитивной реализации «Проблемы словаря».
1957 Статья Уэсли Питерсона, опубликованная в «Journal of Research and Development», впервые серьезно затронула поиск информации в больших файлах, определив открытую адресацию и ухудшение производительности при ликвидации.
1963 Опубликован труд Вернера Бухгольца, где было представлено доскональное исследование хэш-функции.
1967 В труде «Принципы цифровых вычислительных систем» авторства Херберта Хеллермана впервые упомянута современная модель хеширования.
1968 Внушительный обзор Роберта Морриса, опубликованный в «Communications of the ACM», считается точкой отсчета появления в научном мире понятия хеширования и термина «хэш».

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

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

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

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

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

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

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

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

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

Зачем шифровать данные в блокчейне

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

В традиционной архитектуре «клиент-сервер» за безопасность отвечает сервер. Он выполняет следующие функции:

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

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

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

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

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

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

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

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

Вероятность ошибки и почему это всё вообще работает

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

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в \(O(n^2)\) различных случайных значений в промежутке \([0, m)\). Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать \(m\), чтобы не бояться такого?

MD5 — пример хеширования

Python

import hashlib

hash_object = hashlib.md5(b’Hello World’)
print(hash_object.hexdigest())

1
2
3
4

importhashlib

hash_object=hashlib.md5(b’Hello World’)

print(hash_object.hexdigest())

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

Итак, если вам нужно принять какой-то ввод с консоли и хешировать его, не забудьте закодировать строку в последовательности байтов:

Python

import hashlib

mystring = input(‘Enter String to hash: ‘)

# Предположительно по умолчанию UTF-8
hash_object = hashlib.md5(mystring.encode())
print(hash_object.hexdigest())

1
2
3
4
5
6
7

importhashlib

mystring=input(‘Enter String to hash: ‘)

 
# Предположительно по умолчанию UTF-8

hash_object=hashlib.md5(mystring.encode())

print(hash_object.hexdigest())

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

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

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

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

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

Облачный майнинг — оптимальный вариант добычи биткоина на 2021 год

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

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

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

Рейтинг ТОП-5 сервисов облачного майнинга (с актуальными оценками на декабрь 2020 года)

Сервис Оценка Подробный обзор
IQ Mining (выбор редакции!) 9.5 Читать обзор
ECOS 7.2 Читать обзор
YoBit VMining 7.0 Читать обзор
BitDeer 6.4 Читать обзор
HashFlare 6.3 Читать обзор

Критерии по которым выставляется оценка в нашем рейтинге:

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

Самые последние новости криптовалютного рынка и майнинга:

Исследование Fidelity: 52% крупнейших инвесторов уже владеют криптовалютой

«Народная партия» Канады выступила с критикой Центробанка и поддержала биткоин

Эмитенты стейблкоинов обязаны обеспечить свободную конвертацию токенов в фиат

Создатель биткоина Сатоши Накамото увековечен в виде бронзовой статуи в Венгрии

Как изменилась комиссия за транзакции в сети Ethereum после обновления London?

The following two tabs change content below.

Mining-Cryptocurrency.ru

Материал подготовлен редакцией сайта «Майнинг Криптовалюты», в составе: Главный редактор — Антон Сизов, Журналисты — Игорь Лосев, Виталий Воронов, Дмитрий Марков, Елена Карпина. Мы предоставляем самую актуальную информацию о рынке криптовалют, майнинге и технологии блокчейн.
Отказ от ответственности: все материалы на сайте Mining-Cryptocurrency.ru имеют исключительно информативные цели и не являются торговой рекомендацией или публичной офертой к покупке каких-либо криптовалют или осуществлению любых иных инвестиций и финансовых операций.

Новости Mining-Cryptocurrency.ru

  • Исследование Fidelity: 52% крупнейших инвесторов уже владеют криптовалютой — 18.09.2021
  • «Народная партия» Канады выступила с критикой Центробанка и поддержала биткоин — 18.09.2021
  • Эмитенты стейблкоинов обязаны обеспечить свободную конвертацию токенов в фиат — 18.09.2021
  • Создатель биткоина Сатоши Накамото увековечен в виде бронзовой статуи в Венгрии — 18.09.2021
  • Как изменилась комиссия за транзакции в сети Ethereum после обновления London? — 18.09.2021

Хэш подстроки и его быстрое вычисление

Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S.

По определению имеем:

H  =  S  +  S * P  +  S * P^2  +  ...  + S * P^(J-I)

откуда:

H * P  =  S * P  +  ...  +  S * P,
H * P  =  H  -  H

Полученное свойство является очень важным.

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

Единственная возникающая проблема — это то, что нужно уметь делить на P. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент.

Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени.

Допустим, даны два хэша: один умноженный на P, а другой — на P. Если I < J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки:

string s;  int i1, i2, len; // входные данные

// считаем все степени p
const int p = 31;
vector<long long> p_pow (s.length());
p_pow = 1;
for (size_t i=1; i<p_pow.size(); ++i)
	p_pow = p_pow * p;

// считаем хэши от всех префиксов
vector<long long> h (s.length());
for (size_t i=0; i<s.length(); ++i)
{
	h = (s - 'a' + 1) * p_pow;
	if (i)  h += h;
}

// получаем хэши двух подстрок
long long h1 = h;
if (i1)  h1 -= h;
long long h2 = h;
if (i2)  h2 -= h;

// сравниваем их
if (i1 < i2 && h1 * p_pow == h2 ||
	i1 > i2 && h1 == h2 * p_pow)
	cout << "equal";
else
	cout << "different";

Общие сведения

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

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

Для идеальной хеш-функции выполняются следующие условия:

а) хеш-функция является детерминированной, то есть одно и то же сообщение приводит к одному и тому же хеш-значениюb) значение хеш-функции быстро вычисляется для любого сообщенияc) невозможно найти сообщение, которое дает заданное хеш-значениеd) невозможно найти два разных сообщения с одинаковым хеш-значениемe) небольшое изменение в сообщении изменяет хеш настолько сильно, что новое и старое значения кажутся некоррелирующими

Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.

Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.

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

Любой заинтересованный читатель задаст себе вопрос: «А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?»

Ответ таков: на выходе получим все те же 256 бит!Дело в том, что 256 бит — это соответствий, то есть различных входов имеют свой уникальный хеш.Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:

Надеюсь, теперь нет сомнений в том, что это очень внушительное число!

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

Алгоритм MD5 и его подверженность взлому

MD5 hash — один из первых стандартов алгоритма, который применялся в целях проверки целостности файлов (контрольных сумм). Также с его помощью хранили пароли в базах данных web-приложений. Функциональность относительно проста — алгоритм выводит для каждого ввода данных фиксированную 128-битную строку, задействуя для вычисления детерминированного результата однонаправленные тривиальные операции в нескольких раундах. Особенность — простота операций и короткая выходная длина, в результате чего MD5 является относительно легким для взлома. А еще он обладает низкой степенью защиты к атаке типа «дня рождения».

Атака дня рождения

Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.

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

Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.

Результаты

Оценка скорости работы

Рассмотрим скорость работы (количество операций в миллисекунду) для различных имплементаций в зависимости от длины входных строк.

В диапазоне от двух до восьми символов:

Диаграмма

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

В диапазоне от 16 до 256 символов:

Диаграмма

Функция murmur2 явный фаворит, ей немного уступает murmur;  crc16 и sdbm остались в аутсайдерах и на этой выборке.

Оценка распределения результатов

Рассмотрим таблицу результатов соответствия критерию Пирсона

Видно, что имплементации crc16, murmur2, murmur3 удовлетворяют критерию Пирсона о равномерном распределении практически на всех выборках. 

Рассмотрим гистограммы относительных частот, в разрезе разных выборок.

На гистограммах ниже, для loseLose, Djb2, Sdbm, не прошедших тест, видно, что  распределение далеко от равномерного и больше похоже на геометрическое:

ДиаграммаДиаграммаДиаграмма

Для проваливших тест Fnv1 и Fnv1a ситуация похожа, распределения отдалённо напоминают нормальное:

ДиаграммаДиаграмма

Смотрим на тройку победителей:

ДиаграммаДиаграммаДиаграмма

За исключением некоторых всплесков, crc16, murmur2, murmur3 удовлетворяют критерию Пирсона, что согласуется с характеристиками их гистограмм относительных частот.

Выводы

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

Скорость работы. Функции  murmur2/murmur3 имеют лучшее время работы для входных строк длиной больше 8 символов. 

Удовлетворение гипотезы о равномерном распределении. Можем выделить три функции, для которых гипотеза принимается для большинства наборов данных: crc16, murmur2/murmur3. Графики распределения гистограмм относительных частот подтверждают вид равномерного распределения для функций crc16, murmur2/murmur3.