Хешування даних.

Слово хеш походить від англійського «hash», яке можна перекласти як "плутанина", "мішанина", "фарш". Часто ще про сам процес говорять «хешування», від англійського "hashing" (рубати, подрібнювати).

З'явився цей термін в середині минулого століття серед людей, які займались обробкою масивів даних. Спеціальна хеш-функція дозволяла привести будь-який масив даних до числа заданої довжини.

Наприклад, якщо байти з послідовністі байт будь-якої довжини скласти, і від отриманої суми взяти залишок від ділення на 256, то цей залишок від ділення можна буде називати хешем. Для різних початкових байт залишок від ділення буде відрізнятись.

Але для різної послідовності байт по вищенаведеному алгоритму ми можемо отримати однаковий результат. Наприклад, якщо ми в результаті роботи хеш-функції отримали 1, то початкова послідовність довжиною 2 байти може бути одною з наступних:

0001, 0100, 02FF, 03FE, 04FD, ...  FE03, FF02

Тобто для послідовності з 2 байт результат роботи хеш-функції буде однаковим у 256 випадках. І нескладним і відносно невитратним перебором можна отримати усі послідовності з 2 байт від яких хеш-функція видає однаковий результат.

Ситуації, коли хеш-функція видає однаковий результат для різних вхідних даних, називають колізіями.

Хеш-функція — функція, що перетворює вхідні дані будь-якого (як правило великого) розміру в дані фіксованого розміру.

Наведений вище приклад хеш-функції — це суто видуманий автором приклад щоб продемонструвати принцип. Хеш-функції бувають різні, головне щоб результат їх виконання відповідав певним умовам:

функция повинна вміти приводити будь-який об'єм цифрових даних до числа заданої довжини (по суті — стискання даних до бітової послідовності заданої довжини хитрим способом).
найменша зміна (хоча б на один біт) вхідних даних має призводити до повної зміни хеша.
функція повинна бути стійкою у зворотній операції — ймовірність відновлення початкових даних по хешу повинна бути досить низькою.
функція повинна мати якомога нижчу ймовірність виникнення колізій.
хороша хеш-функція не повинна сильно навантажувати обчислювальні потужності. Тут часто важливим є компроміс між швидкістю роботи і якістю результата. Але існують випадки, де від хеш-функції якраз і "вимагається" складність і ресурсозатратність.
алгоритм роботи функції має бути відкритим, щоб кожен бажаючий міг бы оцінити її стійкість, тобто ймовірність відновлення початкових данихх по результату її роботи.

Де і як використовують хешування

Здавалося б, навіщо нам такий "фарш"? Ви можливо будете здивовані, але у наш час без хешування практично неможливо багато речей, наприклад, робота в Інтернет.

Передача даних по комп'ютерним мережам

Прості хеш-функції (ненадійні, але які просто і головне швидко обчислюються) застосовують для перевірки цілістності передачі пакетів по мережевому протоколу TCP/IP та інших для виявлення апаратних помилок — так зване "надлишкове кодування". Якщо хеш отриманого пакета даних співпадає з відправленим разом з пакетом даних (так званою "контрольною сумою), то це може означати, що втрати чи помилок при передачі пакета даних по мережі не сталось. Якщо ж хеші не співпадають, то можливо при передачі пакета відбулась втрата даних, у такому разі пакет пересилається знову. У даному випадку використовується проста хеш-функція, тому що при передачі даних важлива швидкість.

Перевірка цілістності даних

Певно при завантаженні файлів з Інтернет ви стикались з тим, що там наводять деякі числа, які називають або хешем, або контрольною сумою, наприклад такі:

CRC32: 7438E546
MD5: DE3BAC46D80E77ADCE8E379F682332EB
SHA-1: 332B317FB97126B0F79F7AF5786EBC51E5CC82CF

Ці набори символів — не що інше, як результат роботи різних хеш-функцій (їх назви наведено перед числами), які застосували для усього вмісту файла. Ви за допомогою спеціалізованого програмного забезпечення обчислюєте хеш завантаженого файла і порівнюєте його з тим, що було наведено на сайті. Якщо хеші збігаються — файл завантажено без помилок.

Криптографія

Великі по складності хеш-функції використовують у криптографії. Головна умова для них — неможливість по кінцевому результату (хешу) обчислити початковий масив даних. Ще одна головна умова — стійкість до колізій, тобто низька ймовірність отримати два однакових хеша з двох різних масивів даних при обробці їх такою функцією. Розрахунки по таким алгоритмам складні і ресурсовитратні, але тут вже головне не швидкість, а надійність.

Для доступа до сайтів та серверів по логіну і паролю часто використовують хешування. Зберігати паролі у відкритому вигляді для подальшої звірки тими, що ввів користувач, досить ненадійно з точки зору можливості їх викрадення. Тому зберігають хеші усіх паролів. Користувач вводить пароль, миттєво розраховується його хеш і звіряється з тим, що є у базі даних. Надійно і дуже просто. Як правило для такого типу хешування використовують складні функції з дуже високою криптостійкістю, щоб по хешу було неможливим відновити пароль.

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

Блокчейн

Хеш-функції використовуються в технології блокчейн, де хеш є гарантією цілістності ланцюжка транзакції (платежів) і захищає її від несанкціонованих змін. Завдяки хешу і розподіленим обчислюванням зламати блокчен дуже складно, на основі блокчейна існує багато криптовалют. Сама популярна — біткоін — існує з 2009 року, і до цього часу її не було зломано.