Город: Санкт-Петербург Казань Язык: Русский English

Хэширование и его применение в Криптографии и Блокчейн технологиях
Казань / весна 2018, посмотреть все семестры

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

Хеширование, как программистская техника структурирования в таблицах поиска, хорошо известна широкому кругу специалистов и студентов. Например, Википедия определяет хеширование так. Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция H, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». При изменении исходного текста w даже на один знак, полностью меняется хеш H(w) текста (результат хеш-функции). Однако возможны ситуации, когда разные тексты w, w’ могут порождать одинаковый хеш H(w)=H(w’). В этом случае говорят, что произошла коллизия. Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму.

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

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