"Ночь — это туннель, — подумала она. — Это дыра в завтра, если только оно наступит, это завтра."
Ф. Херберт. "Дюна".
Вся современная криптография основана на использовании методов хеширования. Метод хеширования позволяет хранить элементы множества А в линейном массиве X. Математически это можно записать:
h: А -> {0,х-1}
Это читается; функция h отображает каждый элемент А в индекс множества X. Поскольку число элементов А, как правило, намного больше X, то функция h наверняка неинъективна.
Однако возможно существование такого интервала на области определения функции, в границах которого она становится инъективной. Это означает, что только для одного элемента А существует индекс х1. Функция будет инъективной и в том случае, если ни один элемент А не отображается на интервал {х1,х2} при условии, что последний не равен нулю. В любом другом случае на каждый индекс множества Х отображается более одного элемента А. Это так называемая коллизия хеш-функции.
Реверс хеш-функции заключается в поиске всех отображаемых на данный индекс элементов. Для любого конечного множества А это разрешимая задача, которая имеет наиболее простое решение на инъективных интервалах хеш-множества.
Давайте остановимся на инъективных интервалах. Невозможно практическое использование хеш-преобразований без понимания их значения. В качестве примера рассмотрим следующую задачу: пусть нам требуется эффективный алгоритм сравнения строк, допустим, для синтаксического анализатора. Простое посимвольное сравнение потребует значительной памяти для хранения образов строк. Представим все возможное множество строк в данной разрядной сетке массивом S, тогда мы можем хеш-преобразованием привести его к множеству b {0,OxFF}. Разумеется, b много меньше S и требует для хранения значительно меньше памяти.
Рассмотрим практическую реализацию для некоторого множества команд IF', THEN', 'BEGIN', 'END'. Выберем простейшую хеш-функцию, посимвольно складывающую элементы строки. Это плохая хеш-функция (ниже мы поясним почему), но для нашего примера ее будет достаточно.
Для начала нужно построить хеш-таблицу значений для всех элементов множества S.
Воспользуемся для этого программой file://CD:SOURCEVChashOO — "хеш-калькулятор". Рассмотрим ее ключевой фрагмент:
BYTE GetHash (CString s0)
(
BYTE hash=0;
for (int a=0; a<s0.GetLength();a++)
hash=hash+s0[a]; // Вычисляем хеш-сумму
return hash;
}
Мы посимвольно складываем элементы множества символов s0, получая в результате некоторый элемент из множества calc {0,OxFF}. Как нетрудно видеть, на каждый элемент множества calc отображается не более чем один элемент S. Таким образом, в заданных рамках функция calc=calc+s0[a] инъективна. Следовательно, для заданного индекса единственным образом определяется элемент S. Этим доказывается корректность работы хеш-анализатора.
Ниже приведен фрагмент реально работающего эмулятора виртуального процессора GetMe01 (file://CD:SOURCEASM_CCRACKmeGetMe01.asm).
LEA SI, Buffer ; Буфер исполнительных команд
start_r:
CALL GetHashe ; Вычисление хеш-суммы очередной команды
CALL CallIt ; Вызов обработчика для данной команды
MOV SI,DI ; Позиционирование указателя команд
CALL Seek ;-//-
JMP short start_r ; — [uncond] -------------------------------------------
GetHashe PROC NEAR
PUSH SI ; Сохраняем виртуальный указатель команд
XOR АХ,АX ; АН == сумматор
gh_Repeat : ; <——------------------------------------------------------
LODSB ; Берем очередной элемент множества s0
ADD AH,AL ; Добавляем в сумматор
XOR AL,':' ; Проверка на конец команды
JNZ gh_Repeat ; —( [SI] <>' : ' }----------------------------------
POP DI ; si—>di; return SI
RETN ; --
ENDP
Seek PROC HEAR
s_repeat: ;---------------------------------------------------------------
LODSB ; Взять "следующий символ
OR AL,AL ; Проверить на равенство нулю
JNZ s_repeat ; —([SI]<>NULL)—--------------------------
RETH ; ~-
ENDP
CallIt Proc NEAR
PUSH SI ; Сохранить SI
LEA SI ,TableOf Range ; Таблица указателей на обработчики
XCHG AХ,ВХ ; ВН == AL
ci_rep: ;-----------------------------------------------------
LODSB ; Читаем очередную хеш-сумму
OR AL,AL ; Конец таблицы?
JZ _err ; --достигнут конец таблицы-~>
СМР AL,BH ;- Хеш найден?
lodsw ; Читаем очередное смещение обработчика
JNZ ci_rep ; —('.Hash)—--------------------------------------
XCHG AХ,ВХ ; ВХ == AX == смещение обрабочика
POP SI ; восстановить SI
CALL ВХ ; Вызвать обработчик данной команды
RET .- —
_err: ; Исключительная ситуация. Неверная команда
MOV АН, 9 ; Печать строки MS-DOS
LEA DX,errr ; Смещение печатаемой строки
IНТ 21h
mov AH,4Ch ; Завершение работы
INT 21h ; --
errr DB 'неизвестная команда', 0Dh,OAh,'$'
ENDP
; //////////////////////////////////////////////////////////////////////////
; // ТАБЛИЦА ПОДДЕРЖИВАЕМЫХ КОМАНД И СООТВЕТСТВУЮЩИХ ИМ ОБРАБОТЧИКОВ
; //—-——-
TableOfRange:
DB 0EFh ; Хеш-сумма команды
DW offset Proc1 ; Обработчик данной команды
DB 0E3h
DW offset Proc2
DB 79h
DW offset РгосЗ
DB 0E6h
DW offset Proc4
DB 01h
DW offset Proc5
DB 0D1h
DW offset Proc7
DB 054h
DW offset Proc8
DB 0ADh
DW offset Proc9
DB 0 ; конец таблицы
Buffer: ; Буфер исполнительных команд
Данный пример хранит восьмибитную хеш-сумму каждой команды. Следовательно, независимо от длины используемых команд для хранения потребуется всего N байт памяти (где N — число команд), что существенно меньше объема, необходимого для полного хранения тех же самых команд. Теоретически восьмибитная хеш-сумма может вместить до OxFF+l команд. Однако практически предложенная реализация при добавлении некоторого числа команд окажется неработоспособной. Это случится, когда двум разным командам будет соответствовать одна и та же хеш-сумма. В таком случае математики говорят о коллизии хеш-функции. Следовательно, на выбранном интервале хеш-функция становится неинъективной и для рассматриваемой задачи непригодной.
Казалось бы, если множество S намного больше X, то любая хеш-функция на полной области определения S окажется неинъективной. На самом деле число элементов S практически всегда много меньше его мощности. Например, множество слов русского языка представляется множеством последовательностей от одного до десяти и более символов, но общее число существующих слов заведомо меньше OxFFFFFFFF. Поэтому возможно существование 32-битной инъективной хеш функции для синтаксического анализатора русского языка.
Рассмотренная нами хеш-функция для этого не годится. Она обладает плохим перемешиванием и не различает соседних аргументов. Необходим поиск более качественных алгоритмов. Поскольку мы заранее не знаем аргументов функции, то мы заинтересованы, чтобы хеш-преобразование по возможности равномерно отображало множество элементов S на хеш-множество X. Предположим, что появление любого элемента из множества S равновероятно, тогда наиболее подходящей окажется функция, приписывающая каждому элементу по возможности одинаковое число ключей.
Наиболее часто используется и хорошо изучен мультипликационный метод отображения. Математически его можно выразить как h(S[x])=C*S[x] mod N, где N — это число элементов хеш-множества или другими словами его мощность. С — любая константа из интервала [О,N). При С=1 эта формула приобретает вид h(S(x])=S[xl mod N и является самостоятельным хеш-преобразованием, называемым методом остатка. Данный алгоритм также широко используется и для генерации псевдослучайных чисел. И неудивительно, ведь генераторы случайных чисел являются ничем иным, как хеш-преобразованием!
К числу наиболее популярных принадлежит также необычайно мощная функция CRC32 (сгс16): cyclic redundancy check (код циклического контроля). Эта функция в первую очередь призвана подтверждать неискаженность выбранной числовой последовательности. Это еще одна область применения хеш-преобразований. А на самом деле здесь осуществляется все то же хеш-сравнение. Конечно, существует определенная вероятность таких искажений, которые не отразятся на хеш-сумме, но она достаточно невелика при условии хорошего рассеяния и чувствительности к незначительным изменениям выбранного хеш-преобразования.
CRC32 — это многократно проверенная, быстродействующая качественная хеш-функция, дающая превосходный результат. Для большинства последовательностей она будет инъективна. Так, например, многие текстовые редакторы реализуют синтаксическую "подсветку" именно на основе CRC32, не вызывая при этом коллизий.
Рассмотрим алгоритм этой функции. Целую беззнаковую 32-х битовую переменную инициализируем значением OFFFFFFFFh. Далее умножаем на 2 аргумент функции и значение CRC. Если старшие биты окажутся не равны, тогда CRC = CRC XOR OxEDB88320, И так до последнего бита аргумента. Если аргумент — строковая (или какая-либо другая) последовательность, то операции проводятся над двойными словами. В каноническом варианте в конце цикла требуется инвертировать все биты CRC, но это важно только для совместимости результатов, полученных разными функциями, и никак не сказывается на качестве. "Магическое число" 0xEDB88320 есть стандартный полином, менять который не следует, так как это ухудшит качество функции.
Может возникнуть такая ситуация, когда требуемое число элементов хеш-множества будет заметно меньше, чем 2^32. Чтобы избежать лишних расходов, умножают результат сам на себя и берут N старших бит так, чтобы 2^N было по возможности близко к требуемому значению. Смысл этой операции в том, чтобы получить битовую последовательность, чувствительную ко всем битам значения CRC.
Рассмотрим теперь применение хеш-преобразований в криптографии. Одной из задач последней является проверка достоверности пароля. Для этого используют особые хеш-функции. Почему поступают так мы поймем, рассмотрев принцип действия криптосистем. Пусть имеется некоторая криптографическая функция F, расшифровывающая паролем р последовательность Ai в последовательность Aj.