Сравнение данных с помощью хэш функции
Заключение
- System.Security.Cryptography
- System.Text
Проверка хэша
Проверку целостности данных можно производить на основании сравнения их с хэш-кодом. Обычно данные хэшируются в некоторый момент времени, а затем их хэш-код защищается каким-либо образом. Позже можно снова хэшировать эти данные и результат сравнивать с защищенным хэш-кодом. Если хэш-коды совпадают, значит, данные не изменялись. Несовпадение хэш-кодов свидетельствует о том, что данные были повреждены. Чтобы такой механизм был работоспособен, защищенный хэш должен быть зашифрован или являться недоступным для всех лиц, не имеющих достаточного доверия.
В примере ниже ранее полученный хэш-код строки сравнивается с ее новым хэш-кодом. В этом примере реализован цикл, производящий побайтовое сравнение хэш-кодов.
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm
Хэш-код является численным значением фиксированной длины, которое однозначно идентифицирует данные. Хэш-коды представляют большие объемы данных в виде намного меньших по объему числовых значений, поэтому они используются с цифровыми подписями. Хэш-код можно подписать более эффективно, чем значение большего размера. Хэш-коды также могут использоваться для проверки целостности данных, пересылаемых по незащищенным каналам. Хэш-код полученных данных можно сравнить с хэш-кодом этих же данных, вычисленным перед их передачей, и на основании этого определить, подвергались ли данные изменениям.
В этом разделе описываются способы создания и проверки хэш-кодов с помощью классов пространства имен System.Security.Cryptography.
Вступление
Данная статья будет повествовать о том, что такое хэширование и какие алгоритмы хэширования используются в плагине crypto, а также будет приведена сравнительная таблица, в которой можно будет увидеть и сравнить характеристики тех или иных алгоритмов хэширования, поддерживаемых данным плагином.
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.
• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.
Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:
Способность противостоять атакам злоумышленников
• Производительность и стоимость
Вычислительная эффективность алгоритма и требования к оперативной памяти для программных реализаций, а также количество элементов для аппаратных реализаций
• Гибкость и простота дизайна
Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности
В финальный тур попали всего 5 алгоритмов:
Победителем и новым SHA-3 стал алгоритм Keccak.
Давайте рассмотрим Keccak более подробно.
Создание хэша
Управляемые классы, реализующие хэширование, можно использовать для хэширования либо байтового массива, либо управляемого объекта потока. В примере ниже хэш-алгоритм SHA1 используется для создания хэш-кода строки. В примере класс UnicodeEncoding используется для преобразования строки в массив байтов, которые хэшируются с помощью класса SHA256. После этого хэш-код выводится на консоль.
Этот код выводит на консоль следующую строку:
185 203 236 22 3 228 27 130 87 23 244 15 87 88 14 43 37 61 106 224 81 172 224 211 104 85 194 197 194 25 120 217
Сравнение двух хэш-значений
Цель создания хэша из исходных данных:
- Предоставление способа проверить, изменились ли данные с течением времени.
- Сравнение двух значений без работы с фактическими значениями.
В любом случае необходимо сравнить два вычисляемых хэши. Это легко, если они хранятся в виде шестнадцатеричных строк (как на последнем шаге выше). Но возможно, что они оба будут иметь вид массивов байтов. В следующем коде, который продолжается из кода, созданного в предыдущем разделе, показано, как сравнить два массива байтов.
Сразу после создания шестнадцатеричной строки создайте новое хэш-значение на основе новых исходных данных.
Самый простой способ сравнить два массива байтов — выполнить циклический проход по массивам, сравнивая каждый отдельный элемент с его аналогом из второго значения. Если какие-либо элементы отличаются или два массива имеют разный размер, эти два значения не равны.
Сохраните и запустите проект, чтобы просмотреть шестнадцатеричные строки, созданные на основе первого хэш-значения. Узнайте, равен ли новый хэш исходному.
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
- обычная функция трансляции, которая сопоставляет биту бит ,
где - длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
Полный список кода
Общие сведения
Криптографическая хеш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Для идеальной хеш-функции выполняются следующие условия:
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:
Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
Keccak
Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.
Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где
перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где
В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов
Далее будем рассматривать
Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.
Строка состояния представляет собой строку длины 1600 бит, которая делится на и части, которые называются скоростью и ёмкостью состояния соотвественно.
Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256
В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.
Алгоритм получения хеш-функции можно разделить на несколько этапов:
• Строка P делится на n блоков длины
• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.
• «Отжимание»: пока длина результата меньше чем , где - количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:
Pre-image resistance
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
Содержание
Ссылки
Что такое и с какой целью необходимо использовать хэширование? Основные виды хэширования.
Вычисление хэш-значения
Вы можете легко создавать и сравнивать хэш-значения с помощью криптографических ресурсов, содержащихся в пространстве System.Security.Cryptography имен. Так как все хэш-функции Byte[] принимают входные данные типа, перед хэшированием источника может потребоваться преобразовать его в массив байтов. Чтобы создать хэш для строкового значения, выполните следующие действия.
Используйте директиву using в пространствах System имен и System.Security.Cryptography пространствах имен, System.Text чтобы позже в коде не было необходимости уточнять объявления из этих пространств имен. Эти инструкции должны использоваться перед любыми другими объявлениями.
Объявите строковую переменную для хранения исходных данных и два байтовых массива (неопределенного размера) для хранения исходных байтов и результирующего хэш-значения.
Используйте метод GetBytes() класса для System.Text.ASCIIEncoding преобразования исходной строки в массив байтов (требуется в качестве входных данных для функции хэширования).
Вычислите хэш MD5 для исходных данных ComputeHash , вызвав экземпляр MD5CryptoServiceProvider класса.
Чтобы вычислить другое хэш-значение, необходимо создать другой экземпляр класса.
Сохраните и запустите код, чтобы увидеть результирующую шестнадцатеричные строки для исходного значения.
Раздел 1: Что такое хэширование и плагин crypto
Хэш (хеш) — это криптографическая функция, которая представляет собой математический алгоритм, преобразующий произвольный массив данных (информацию) в строку фиксированной длины, состоящую из цифр и букв.
Как работает процесс хэширования:
Вначале определяют, целостность каких файлов нужно контролировать. Для каждого файла производится вычисления значения его хэша по специальному алгоритму с сохранением результата. Через необходимое время производится аналогичный расчет и сравниваются результаты. Если значения отличаются, значит информация содержащаяся в файле была изменена.
Основная особенность хэш-функций — это то, что их нельзя расхэшировать, невозможно вернуть единожды хэшированную строку данных в обратный читабельный вид.
Где используется:
Анализ при помощи хэш-функций часто используется для контроля целостности и сверки уникальности важных файлов операционной системы, программ, а также с целью защиты личных данных на просторах сети Интернет, таких как пароль, ключ или иное значение, которое не требует обратной расшифровки, но требует контроля/сравнения значений.
Какими характеристиками должна обладать хэш-функция:
Должна уметь выполнять преобразования данных произвольной длины в фиксированную.
Должна иметь открытый алгоритм, чтобы можно было исследовать её криптостойкость.
Должна быть односторонней, то есть не должно быть математической возможности по результату определить исходные данные.
Должна "сопротивляться" коллизиям, т.е. не должна выдавать одинаковых значений при разных входных данных.
Не должна требовать больших вычислительных ресурсов.
При малейшем изменении входных данных результат должен существенно изменяться.
Чтобы рассмотреть процесс хэширование во всей его красе, мы будем использовать сопутствующий плагин для фреймворка Flutter:
crypto — сборник криптографических хэш-функций, написанный на чистом языке Dart, поддерживает такие платформы как Android, iOS, Linux, macOS, Windows, Web.
Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.
Введение
Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p 2 s2 +… + p n-1 sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i] ).
Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Конечно, чтобы сравнить 2 строки, мы можем написать подобную функцию (будем считать, что длины строк s и t совпадают и равны n):
Однако в худшем случае эта функция обязана проверить все символы, что дает асимптотику O(n).
Сравнение строк с помощью хешей
Теперь посмотрим, как справляются с этой задачей хеши. Так как хеш — это всего лишь число, для их сравнения нам потребуется O(1) времени. Правда, для того, чтобы посчитать хеш одной подстроки наивным способом, требуется O(n) времени. Поэтому потребуется немного повозиться с математическими формулами и научиться находить за O(n) хеши сразу всех подстрок. Давайте сравним подстроки sL..R и tX..Y (одинаковой длины). Пользуясь определением хеша, мы можем записать:
Проведем небольшие преобразования в левой части (в правой части все будет происходить аналогично). Запишем хеш подстроки s0..R, он нам понадобится:
Разобьем это выражение на две части…
… и вынесем из второй скобки множитель p L :
Выражение в первой скобке есть не что иное, как хеш подстроки s0..L-1, а во второй — хеш нужной нам подстроки sL..R. Итак, мы получили, что:
Отсюда вытекает следующая формула для hash(sL..R):
Аналогично, для второй нашей подстроки будет выполнено равенство hash(tX..Y) = (1 / p X )(hash(t0..Y) — hash(t0..X-1)).
Внимательно глядя на эти формулы, можно заметить, что для вычисления хеша любой подстроки нам необходимо знать лишь хеши префиксов этой строки s0..0, s0..1, . s0..n-2, s0..n-1. А, так как хеш каждого следующего префикса выражается через хеш предыдущего, их несложно посчитать линейным проходом по строке. Все сразу за O(n) времени. Степени числа p тоже надо заранее предпросчитать и сохранить в массиве.
- Замечание первое: L (или X) может оказаться равным нулю, и при вычислении hs[L - 1] произойдет выход за границы массива. Однако если L равно нулю, то интересующий нас хеш подстроки sL..R хранится в точности в hs[R] . Поэтому правильнее вместо hs[L - 1] писать так:
. - Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 2 64 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!). Число p для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2 64 , т.е. оно должно быть нечетным). Почему так, я здесь рассказывать не буду — об этом можно почитать в книжках по алгебре. Конечно, неизбежно появляется вероятность коллизии, но она крайне мала, поэтому при решении олимпиадных задач можно ей просто пренебречь.
- Замечание третье: так как все операции мы теперь выполняем по модулю, деление для нас недоступно (точнее, доступно, но писать это довольно неэффективно). Поэтому от него надо избавляться. Делается это довольно просто, способом, который в школе называют «пропорцией»: выражение приводится к общему знаменателю, и вместо деления используется умножение:
Задачи, решаемые с помощью хешей
1. Сравнение подстрок
Первое, и главное, применение, как уже было сказано, это быстрое сравнение двух подстрок — на нем основываются все остальные алгоритмы с хешами. Код в прошлом разделе довольно громоздкий, поэтому я напишу более удобный код, который будет использоваться в дальнейшем.
Следующая функция вычисляет хеш подстроки sL..R, умноженный на p L :
Теперь сравнение двух подстрок мы выполняем следующей строчкой:
Умножение на степени числа p можно назвать «приведением к одной степени». Первый хеш был умножен на p L , а второй — на p X — значит, чтобы сравнение происходило корректно, их надо домножить на недостающий множитель.
Примечание: имеет смысл сначала проверить, совпадают ли длины подстрок. Если нет, то строки в принципе не могут быть равны, и тогда можно не проверять вышезаписанное условие.
2. Поиск подстроки в строке за O(n + m)
Хеши позволяют искать подстроку в строке за асимптотически минимальное время. Это делает так называемый алгоритм Рабина-Карпа.
Пусть есть строка s длины n, в которой мы хотим найти все вхождения строки t длины m. Найдем хеш строки t (всей строки целиком) и хеши всех префиксов строки s, а затем будем двигаться по строке s окном длины m, сравнивая подстроки si..i+m-1.
Код:
3. Нахождение z-функции за O(n log n)
Z-функцией строки s называется массив z, i-ый элемент которого равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке s, который одновременно является и префиксом всей строки s. Значение z-функции в нулевой позиции будем считать равным длине строки s, хотя некоторые источники принимают его за ноль (но это не критично).
Конечно, есть алгоритм нахождения z-функции за O(n). Но когда его не знаешь или не помнишь (а алгоритм довольно громоздкий), на помощь приходят хеши.
Идея следующая: для каждого i = 0, 1, . n-1 будем искать zi бинарным поиском, т.е. на каждой итерации сокращая интервал возможных значений вдвое. Это корректно, потому что равенство s0..k-1 = si..i+k-1 обязательно выполняется для всех k, меньших zi, и обязательно не выполняется для больших k.
4. Поиск лексикографически минимального циклического сдвига строки за O(n log n).
Существует алгоритм Дюваля, который позволяет решать эту задачу за O(n), однако я знаю некоторых довольно сильных олимпиадных программистов, которые так и не разобрались в нем. Пока они будут в нем разбираться, мы снова применим хеши.
Алгоритм следующий. Сначала примем саму строку s за лучший (лексикографически минимальный) ответ. Затем для каждого циклического сдвига с помощью бинарного поиска найдем длину максимального общего префикса этого сдвига и текущего лучшего ответа. После этого достаточно сравнить следующие за этим префиксом символы и, если надо, обновить ответ.
Еще заметим, что для удобства здесь рекомендуется приписать строку s к самой себе — не придется делать операции взятия по модулю при обращениям к символам строки s. Будем считать, что это уже сделано.
Примечание: по сути, внутри цикла for написан компаратор, сравнивающий лексикографически два циклических сдвига. Используя его, можно за O(n log 2 n) отсортировать все циклические сдвиги.
5. Поиск всех палиндромов в строке за O(n log n).
Опять же, существует решение этой задачи за O(n). И опять мы будем решать ее с помощью хешей.
Подстрока sL..R называется палиндромом, если sL = sR, sL+1 = sR-1, и т.д. Если выражаться русским языком, то это означает, что она читается одинаково как слева направо, так и справа налево.
Возможно, вы уже знаете или догадались, при чем тут хеши. Помимо массива h[] , содержащего хеши для подстрок s0..0, s0..1, . s0..n-2, s0..n-1, посчитаем второй массив rh[] (для «перевернутой» строки), который будем обходить справа налево. Он будет содержать соответственно хеши s0..n-1, s1..n-1, . sn-2..n-1, sn-1..n-1:
Должно уже быть понятно, как за O(1) определять, является ли строка палиндромом. Я напишу функцию getRevHash(), аналогичную getHash(), а потом приведу необходимое условие сравнения. Вы можете самостоятельно убедиться в правильности этого выражения, проделав математические выкладки, подобные тем, что приводились в начале статьи.
Теперь рассмотрим позицию i в строке. Пусть существует палиндром нечетной длины d с центром в позиции i (в случае четной длины — с центром между позициями i-1 и i). Если обрезать с его краев по одному символу, он останется палиндромом. И так можно продолжать, пока его длина не станет равной нулю.
Таким образом, нам достаточно для каждой позиции хранить 2 значения: сколько существует палиндромов нечетной длины с центром в позиции i, и сколько существует палиндромов четной длины с центром между позициями i-1 и i. Обратите внимание, что эти 2 значения абсолютно независимы друг от друга, и обрабатывать их надо отдельно.
Применим, как и ранее, бинарный поиск:
Теперь можно, к примеру, найти общее количество всех палиндромов в строке, или длину максимального палиндрома. Длина максимального нечетного палиндрома с центром в позиции i считается как 2 * oddCount[i] - 1 , а максимального четного палиндрома — 2 * evenCount[i] .
Еще раз напомню, что нужно быть внимательнее с палиндромами четной и нечетной длины — как правило, их надо обрабатывать независимо друг от друга.
Хеши в матрицах
Наконец, рассмотрим более изощренные применения хешей. Теперь наше пространство будет двумерным, и сравнивать мы будем подматрицы. К счастью, хеши очень хорошо обобщаются на двумерный случай (трехмерных и более я не встречал).
Теперь вместо числа p и массива pow у нас будут два различных числа p, q и два массива pow1 , pow2 : по одному числу и по одному массиву в каждом направлении: по вертикали и горизонтали.
Хешем матрицы a0..n-1, 0..m-1 будем называть сумму по всем i = 0, . n-1, j = 0. m-1 величин p i q j aij.
Теперь научимся считать хеши подматриц, содержащих левый верхний элемент a00. Очевидно, что hash(a0..0, 0..0) = a00. Почти так же очевидно, что для всех j = 1. m-1 hash(a0..0, 0..j) = hash(a0..0, 0..j-1) + q j a0j, для всех i = 1. n-1 hash(a0..i, 0..0) = hash(a0..i-1, 0..0) + p i ai0. Это напрямую вытекает из одномерного случая.
Как посчитать хеш подматрицы a0..i, 0..j? Можно догадаться, что hash(a0..i, 0..j) = hash(a0..i-1, 0..j) + hash(a0..i, 0..j-1) — hash(a0..i-1, 0..j-1) + p i q j aij. Эту формулу можно получить из следующих соображений: сложим все слагаемые (хеш, напомню, это сумма нескольких слагаемых), составляющие хеш подматриц a0..i-1, 0..j и a0..i, 0..j-1. При этом мы два раза учли слагаемые, составляющие подматрицу a0..i-1, 0..j-1, так что вычтем их, чтобы они учитывались один раз. Теперь не хватает только элемента aij, умноженного на соответствующие степени p и q.
Примерно из тех же соображений, что и в первой части статьи (вы уже заметили причастность формулы включений-исключений?) строится функция для вычисления хеша произвольной подматрицы ax1..x2, y1..y2:
Эта функция возвращает хеш подматрицы ax1..x2, y1..y2, умноженный на величину p x1 q y1 .
А сравнение двух подматриц aax1..ax2, ay1..ay2 и abx1..bx2, by1..by2 выполняется с помощью следующего выражения:
Хешами также можно решать задачи, связанные с нахождением самой большой симметричной подматрицы и похожие на них. Причем я не знаю сравнимых с хешами по скорости и простоте алгоритмов, выполняющих эту работу. Здесь используются те же принципы, что и при поиске палиндромов в одномерном случае (т.е. считать «реверснутые» хеши справа налево и снизу вверх, проводить бинпоиск отдельно для подматриц четной и нечетной длины). Предлагаю попробовать решить эту задачу самостоятельно — эта статья вам поможет!
Заключение
Итак, в нашем распоряжении есть довольно неплохой аппарат, позволяющий делать многие вещи либо с лучшей возможной асимптотикой, либо лишь чуть-чуть (в логарифм раз) медленнее, чем специализированные алгоритмы. Неплохо, не так ли?
Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Читайте также: