http://financialcouns.livejournal.com/51688.html
Ar tem
май 2016.
16247

Что такое хэширование и зачем оно нужно?

Ответить
Ответить
Комментировать
0
Подписаться
2
2 ответа
Поделиться

Это термин из ИТ. Обычному пользователю совершенно незачем задумываться о смысле хэширования. Хэширование представляет интерес только для программистов (и, возможно, математиков).

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

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

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

1. Одни и те же данные должны давать всегда один и тот же хэш. Это обязательное условие.

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

Хорошая хэш-функция ведёт себя следующим образом:

1. Весь доступный диапазон хэшей используется по максимуму. То есть, если на хэш отведено 32 байта, то разные данные дают максимально разнообразный хэш, который может являться совершенно любой комбинацией битов. То есть, диапазон хэшей не "простаивает".

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

Для чего нужен хэш. Допустим, у вас есть массив из миллиона разных (неодинаковых) строк. В каждой строке миллион символов (то есть, всего у вас 1 терабайт = 1000 гигабайт данных). Вам приходит такое указание: добавьте строку, которая содержит "тото-сёто-пятое-десятое-и-ещё-миллион-символов", в ваш массив, но только в том случае, если такой строки там ещё нет.

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

Но если перед записью вы имеете (вычислили их ранее) хэши эти строк, то ваша задача превращается в сравнение 32 символов вместо миллиона символов (32 мегабайта данных на весь массив). Если вы обнаружили, что у вас в списке есть точно такой же хэш, то для полной надёжности, вы можете сравнить посимвольно только эту строку. Гораздо меньше затрат, чем проверять терабайт целиком, не так ли? (На самом деле, даже 32 мегабайта хэшей проверять не потребуется, поскольку по теории вероятностей, лишь 1-2 первых символа хэшей будут совпадать, да и то очень редко, а 3 одинаковых символа подряд, возможно, не найдутся во всём миллионе хэшей. И это при том, что изначальные данные могли быть очень похожими.)

Хэш также может использоваться для проверки целостности данных при передаче. Вы передали гигабайт данных. А затем передали 32-байтный хэш. Получатель на своей стороне захешировал этот гигабайт тем же способом (той же хэш-функцией) и получил тот же самый хэш. Теперь он уверен, что он имеет точно те же данные, что и отправитель (вероятность случайной ошибки примерно около 1e-70, поэтому ей можно пренебречь; на самом деле, вероятность, скорее всего, ещё меньше, потому что хорошая хэш-функция не даст такой же хэш на похожих данных).

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

14
0

то есть, всего у вас 1 терабайт = 1000 гигабайт данных

для человека, представляющегося как программист, непростительная ошибка

-1
Ответить

Я действительно программист, и с довольно большим опытом работы. Я знаю, когда нужно говорить точно, а когда нужно говорить просто и понятно. Аудитория the Question - это не коллеги, не тематический форум и не собеседование. Если вы искренне считаете отклонение в 2,4% непростительной ошибкой, вы можете написать свой собственный ответ. Хотя мне кажется более правдоподобной версия, что вы просто захотели блеснуть знанием. "Для человека, представляющегося" и прямо "непростительная" говорят в эту пользу. Ведь могли бы просто поправить меня без ярких фраз. Или, может быть, вы недавно программируете и вам нравится чувствовать себя программистом. 1024 - это так аутентично :)

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

+7
Ответить

Намеренные ошибки, чтобы другие поняли - это странно. Что насчет меня, я вообще гуманитарий.

0
Ответить
Ещё 4 комментария

Если уж говорить совсем строго, то моя фраза как раз верна на 100%.

Цитата из Вики: "По пояснениям Международной электротехнической комиссии, название «терабайт» общепринято, но неверно, так как приставка тера- в международной системе единиц означает умножение на 1000000000000".

То есть "1 терабайт = 1000 гигабайт" - это и есть самая правильная фраза. Другая правильная фраза: "1 тебибайт = 1024 гибибайт". "Гибибайты" почему-то не прижились, поэтому почти все говорят неправильно.

А теперь немного оффтопа.

> Намеренные ошибки, чтобы другие поняли - это странно.

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

Например, вы не сможете объяснить школьнику настоящую суть физического термина "температура" (вроде бы просто? на самом деле - нет). Не сможете объяснить устройство атома. Не сможете объяснить, как возникает электрический ток. Не сможете объяснить суть закона всемирного тяготения - а, стало быть, и астрономию нет смысла преподавать.

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

+3
Ответить

Отличное объяснение, спасибо.

+1
Ответить

Так это "ваша логика" виновата в том, что на моей флешке с 4 Гб памяти всего 3,76??!!! :D великие округлители, блин))

-1
Ответить

На всякий случай поясню, что я знаю истинную причину подобных "неточностей", так что не надо объяснять, просто понравилась статья, а тут дискуссия забавная. Ворвался, так сказать))

0
Ответить
Прокомментировать
АВТОР ВОПРОСА ОДОБРИЛ ЭТОТ ОТВЕТ

ALEXANDER OVCHARENKO дал очень хороший ответ, но хочется добавить, что хэширование очень и очень часто используется в безопасности. Хэш имеет для этого очень важную особенность. Из A всегда можно получить только B, но зная B нельзя вычислить A (Есть некоторые способы, но если безопасностью занят нормальный человек, то он исключит такой вариант)

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

Ответ очень прост.

Когда вы регистрируетесь на сайте, то он не сохраняет ваш пароль. Он хранит хэш пароля(A->B) . Когда вы входите на сайт, то ваш пароль хэшируется и проверяется с хэшем(A`->B`, проверка равенства B` и B), но сам пароль НИГДЕ не хранится. Поэтому, когда сливают базу данных, то хакеры получают ХЭШ и не могут войти в аккаунт человека т.к. (B->C, C не равно B)

Также, когда вы даете запрет на хранение ваших данных (или компания его не просит), но компания очень хочет вести статистику данных, то никто не мешает хранить ХЭШ. А дальше обрабатывать ХЭШ, но это другая история :)

6
0

> Из A всегда можно получить только B, но зная B нельзя вычислить A

Для читателей.

С точки зрения практики, Levan Kvirkvelia, действительно, сделал полезное дополнение. Но с точки зрения теории стоит сделать уточнение, что описанное не относится к хэшированию напрямую.

Для такого класса задач (задачи безопасности) разрабатываются специальные криптографические ("шифровальные") хэш-функции, которые отличаются тем, что они производят необратимые преобразования. Как раз вот это: "зная B нельзя вычислить A".

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

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

+1
Ответить
Прокомментировать
Ответить