ДНЕВНИК СТУДЕНТКИ: Криптографическая хэш-функция и ее свойства!


Вчера я посмотрела 18-минутную лекцию Cryptographic Hash Functions в курсе Bitcoin and Cryptocurrency Technologies, чтобы подготовить этот материал, но с фокусировкой было из серии "смотрю в книгу вижу фигу". Ну ничего, сегодня я посмотрела ее еще раз и что-то даже поняла :)

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

Криптографическая хэш-функция H является математической функцией, которая:

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

Свойства безопасности хэш-функции H:

  • стойкость к коллизиям (collision-free)
  • свойство скрытости (hiding property)
  • дружественность к головоломкам? :) (puzzle-friendly)

Далее более подробно об этих свойствах.

Сollision-free

скриншот из лекции

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

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

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

Hiding property

скриншот из лекции

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

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

Вот что русская Википедия говорит:

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

«Commit» — посылку закрытой на ключ коробки (обязательство),
«Reveal» — более поздняя отправка ключа от коробки (значение).

Очень удобно использовать такую функцию H(key | msg), потому что невозможно вычислить значение msg. А имея key любой может "открыть конверт".

Puzzle-friendly

скриншот из лекции

Насколько я поняла, это свойство говорит нам о том, что если ты знаешь y, ты никак не можешь вычислить x, кроме как до бесконечности перебирать варианты :)

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

Подписывайтесь на мой дневник!

@studentka


Comments 0