Triangulations comparison by means of hash function.pdf Триангуляция часто применяется в различных задачахмашинной графики, вычислительной геометрии, методахконечных элементов, геоинформатике, различных инженер-ных задачах.По модели триангуляции часто выполняется построениеизолиний, профилей по поверхности, расчёт объёмов зем-ляных работ и пр. При больших объёмах исходных данныхнекоторые алгоритмы решения указанных задач являютсядостаточно трудоёмкими [1 - 3]. Во многих программныхпродуктах после изменения исходных данных вызываетсясоответствующий алгоритм для повторного вычисленияизолиний, объёмов работ и т.д. Однако в некоторых случаяхэтого можно избежать, например, если вновь построеннаятриангуляция в области наших интересов (в месте, где стро-ятся изолинии и считаются объёмы работ) эквивалентнапредыдущей.Таким образом, возникает задача сравнения двух триан-гуляций. При этом возможны два класса вопросов: 1) сов-падают ли две данные триангуляции по ряду параметров;2) различаются ли две данные триангуляции по ряду пара-метров. Внешне эти два вопроса являются дополнительны-ми друг к другу, однако они имеют существенно различныйсмысл в контексте предлагаемого в настоящей работе веродля каждого треугольника - ссылки на образующиеузлы. Кроме того, для всех узлов и треугольников за-дан некоторый набор вспомогательных признаков.Требуется установить, различаются ли две триангуля-ции как геометрическое место точек и по набору со-ответствующих признаков элементов триангуляции.При решении этой задачи кроме топологии и ко-ординат узлов триангуляции нам потребуется учестьсоответствующие признаки элементов. Поскольку по-рядок задания элементов в триангуляции T1 и T2 мо-жет отличаться, необходимо при сохранении в потокпризнаков элементов учитывать эту особенность. Длярешения поставленной задачи предлагается использо-вать нумерацию элементов триангуляции, котораяприменялась при решении предыдущей задачи. Вэтом случае можно будет последовательно сохранятьв поток интересующие признаки триангуляции. Присохранении признаков можно применять два подхода:1. Сохранять в поток последовательно в порядкевозрастания номера только тех элементов триангуля-ции, которые соответствуют требуемому признаку(эффективно, когда количество таких элементов неве-лико).2. При сохранении координат (для узлов) или ин-дексов образующих треугольник узлов (для треуголь-ников) так же сохранять в поток и сам признак (эф-фективно, когда «вес» признака мал).Для решения поставленных задач требуется алго-ритм нумерации узлов и треугольников, не зависящийот их порядка в структуре триангуляции. Для этогопредлагается отсортировать все узлы триангуляции поих X-координатам, а узлы, имеющие равные X-коор-динаты, дополнительно отсортировать по Y-координа-там. Аналогичным образом сортируются все треуголь-ники, при этом в качестве сравнивающихся координатиспользуются координаты центров треугольников. Врезультате для двух эквивалентных триангуляций, раз-личающихся только порядком составляющих её эле-ментов, мы получим одинаковые индексы элементов.В целом поток, в который последовательно запи-саны координаты узлов триангуляции, индексы обра-зующих треугольники узлов и, возможно, дополни-тельная информация об узлах и треугольниках, могбы быть использован для однозначной идентифика-ции триангуляции. То есть, в принципе, для сравне-ния двух триангуляций T1 и T2 можно было бы, сохра-нив их в соответствующие потоки S1 и S2, сравнить побайтам содержимое потоков и по результату сравне-ния потоков сделать выводы об эквивалентности три-ангуляций, но такой подход нерационален в смыслеиспользования памяти и неудобен на практике.Поэтому после того, как триангуляция была со-хранена в поток, предлагается применить к потоку вцелом какую-либо хеш-функцию и для сравнения три-ангуляций сравнивать только значения хеш-функций,вычисленных на данных потоках. Это позволяет хра-нить в триангуляции только однажды вычисленноехеш-значение, не генерируя поток данных триангуля-ции для каждой операции сравнения. В случае, еслиодна из триангуляций зафиксирована и меняется ред-ко, то такой подход позволяет в 2 раза уменьшитьобъем временно используемой памяти для храненияпотока данных триангуляций.Кроме того, рассмотрим такой пример. Пустьсравниваемые триангуляции - это по сути одна и таже модель, но построенная в разное время. Например,набор исходных данных был изменен (изменены ко-ординаты существующих или добавлены дополни-тельные объекты), в результате, после построения но-вой триангуляции, необходимо принять решение онеобходимости перестроения изолиний, трёхмерноймодели и пр. Тогда для сравнения потоков двух три-ангуляций (бывшей и текущей) необходимо было быхранить поток данных от старой триангуляции, чтоочень невыгодно по затратам памяти. В этом смыслесохранение только одного хеш-значения для старойтриангуляции даёт существенный выигрыш.ВЫБОР ХЕШ-ФУНКЦИИПри выборе хеш-функции следует обратить вни-мание на её статистическую независимость. Посколь-ку для различных триангуляций результаты хеш-функции потенциально могут оказаться одинаковыми[5], то существует вероятность того, что после срав-нения может быть выдан ошибочный результат о сов-падении двух различающихся триангуляций. Поэтомуважно (это скорее необходимое, но не достаточноеусловие), чтобы результаты хеш-функций были рас-пределены равномерно на множестве их возможныхзначений для всех возможных триангуляций. В каче-стве хеш-функций в данной работе предлагается ис-пользовать следующие варианты:А. Применение операции «Исключающее ИЛИ»для всех данных из полученного потока, который рас-сматривается как последовательность 64-битных це-лых чисел. Далее в настоящей работе этот метод бу-дем называть XOR.Б. Применение операции «Исключающее ИЛИ»для всех данных из полученного потока, который рас-сматривается как последовательность 64-битных це-лых чисел, со сдвигом результата каждой операциивлево на n бит. Следует заметить, что для полученияболее равномерного распределения значений хеш-функции в качестве n лучше брать небольшое простоечисло, например 3, 5 или 7 (этот результат чисто эм-пирический, не обоснованный теоретически, однакопроверенный авторами на практике при эксперимен-тальной оценке различных алгоритмов). Далее в рабо-те этот метод будем называть XOR*.В. Использование функций Microsoft CryptoAPI сприменением одного из алгоритмов хеширования,стандартно встроенных в операционную систему MicrosoftWindows 9x/Me/NT/2000/XP: MD2, MD4, MD5или SHA [6 - 8]. Далее в работе эти методы будем на-зывать соответственно MD2, MD4, MD5, SHA,Сравнение алгоритмов MD2, MD4, MD5, SHAВ криптографии хеширование часто применяетсядля цифровой подписи сообщений [6,8,9], при этом вхеш-функцию в качестве входных параметров переда-ётся, помимо исходных данных, ключ (приватный илипубличный). Тогда данные ключа используются привычислении значения хеш-функции. В нашем случаеможно обойтись алгоритмами, не требующими клю-чей для вычисления хеш-значений.Ниже перечислены несколько алгоритмов, исполь-зуемых для вычисления хеш-функций, не требующихдля работы ключей. Все эти алгоритмы поддержива-ются Microsoft RSA Base Cryptographic Provider, стан-дартно поставляемым со всеми операционными сис-темами Microsoft.Семейство алгоритмов RSA для вычисления хе-ширующих значений использует стандартную мето-дику RSA при работе с публичными и приватнымиключами. При этом заранее (при разработке програм-мы хеширования) создаётся некоторый предопреде-ленный ключ, с помощью которого производится ге-нерация хеш-значения. Именно поэтому статистиче-ские параметры получаемого хеш-значения опреде-ляются свойствами самого алгоритма RSA, который внастоящее время достаточно полно исследован. В ча-стности, количество различных получаемых хеш-значений пропорционально величине публичного илиприватного ключа в алгоритме RSA. В различныхреализациях алгоритма RSA обычно используютсяключи длиной не менее 512 бит, при этом после усе-чения сгенерированного хеш-значения до 128 или160 бит (в реализациях, поставляемых Microsoft) по-лученные хеш-значения оказываются распределеныравномерно на всем диапазоне возможных 128 или160-битных значений соответственно.Кратко опишем конкретные поставляемые Microsoftреализации метода RSA.MD2 - хеширующий алгоритм, генерирующий128-битное хеш-значение. Алгоритм оптимизировандля 8-битных компьютеров, поэтому на практике ра-ботает достаточно медленно.MD4 и MD5 - хеширующие алгоритмы, генери-рующие 128-битное хеш-значение. Эти два алгоритмаоптимизированы для 32-битных компьютеров. Скоро-сти и качество работы этих алгоритмов практическине отличаются.SHA - хеширующий алгоритм, генерирующий160-битное хеш-значение. Разработан совместно На-циональным институтом стандартов и технологий(NIST, США) и Агентством национальной безопасно-сти (NSA, США).Все перечисленные криптографические хеш-функ-ции должны выдавать статистически независимые ре-зультаты на различных входных данных, даже еслиони отличаются на такую ничтожно малую величину,как один бит.Хеширующие алгоритмы MD2, MD4 и MD5 былиразработаны в корпорации RSA Data Security, Inc.Среди перечисленных алгоритмов Microsoft рекомен-дует использовать MD5, как наиболее новый и быст-рый алгоритм хеширования.ЭКСПЕРИМЕНТАвторами было проведено экспериментальное мо-делирование работы предложенных алгоритмов напримерах сгенерированных триангуляций на различ-ных наборах случайных точек. Для всех триангуляцийбыло вычислено значение хеш-функций по предло-женным алгоритмам. Для оценки распределения ре-зультатов хеш-функций в эксперименте использова-лись упрощённые функции, возвращающие 8-битноезначение, поскольку для проверки гипотезы о равно-мерном распределении 128-битных значений на прак-тике потребуется огромное количество тестов (не ме-нее 5⋅2128 ) [10], выполнить которые за разумное вре-мя невозможно. Для сведения 64-, 128- и 160-битныхзначений к 8-битным к ним была применена побайтнооперация «исключающее ИЛИ».На рис. 1 представлены графики распределениярезультатов хеш-функций, вычисленных на 100000триангуляций, построенных на 5000 равномерно рас-пределённых в единичном квадрате точках.абвгдеРис. 1. Графики распределения результатов различных хеш-функций: а) алгоритм MD2; б) алгоритм MD4; в) алгоритмMD5; г) алгоритм SHA; д) алгоритм XOR; е) алгоритм XOR*Приведённые результаты были оценены на соот-ветствие равномерному распределению поχ2-критерию [10]. При уровне значимости ƒ = 0,05 всемеры отклонения ƒ2 истинного распределения от рав-номерного меньше критического 2ƒƒ = 292,97, вычис-ленного для данного случая, что не даёт повода со-мневаться в правильности предположения о равно-мерном распределении результатов хеш-функций намножестве её возможных значений:25520(i i)i iM np= np−ƒ = ƒ ,где Mi - число значений хеш-функций, равныхi = 0, 255 , n - объём выборки значений хеш-функций(количество испытаний), pi - «теоретическая вероят-ность» того, что результат хеш-функции будет равен i(при 8-битном значении хеш-функции все 1/ pi = 256 ).Следует, однако, отметить, что при использова-нии простой 64-битной хеш-функции (не криптогра-фической), такой, как XOR, распределение её резуль-татов может несколько ухудшиться по сравнению сравномерным распределением. Такая ситуация можетвозникать при вычислении значения хеш-функцииXOR(T) по триангуляции, построенной на регулярноммножестве точек. Поскольку в поток сохраняются ко-ординаты узлов триангуляции и целочисленные ин-дексы её элементов, в некоторых случаях XOR(T) бу-дет содержать большое количество нулевых бит. Прииспользовании криптографических алгоритмов хеши-рования данный эффект проявляться не будет.В табл. 1 приведены результаты тестированияпредложенных в данной работе хеширующих функ-ций. Из таблицы видно, что все предложенные хеш-функции имеют равномерное распределение резуль-татов на множестве их возможных значений. Среднеевремя работы алгоритмов указано в абстрактных еди-ницах времени и может использоваться для качест-венного сравнения их скорости работы. Сравнивая ал-горитмы по скорости, можно сделать вывод, что наи-более выгодным с точки зрения оценки скорости ра-боты функций представляется использование хеш-функции, работающей по алгоритму MD5.Т а б л и ц а 1Результаты тестирования хеширующих алгоритмовХеширующийалгоритм Значение ƒ2 Среднее времяработы, у.е.MD2 262,75 637MD4 248,14 32MD5 256,29 31SHA 255,90 50XOR 273,76 90XOR* 270,57 93Также был проведён следующий эксперимент: бы-ла построена триангуляция T1 на 10000 случайных то-чек, равномерно распределённых в единичном квад-рате. По триангуляции T1 было вычислено 128-битноезначения хеш-функции H1, работающей по алгоритмуMD5. После этого триангуляция T1 была зафиксиро-вана, и с неё была получена её точная копия T2. Былопроведено 100000 незначительных модификаций три-ангуляции T2, изменяющих её по одному из следую-щих параметров: 1) незначительное изменение коор-динат одного из узлов триангуляции; 2) изменениезначения одного признака случайного узла триангу-ляции; 3) перестроение пары соседних треугольников(переброска ребра); 4) изменение одного признакаслучайного треугольника. Для каждой модификациипо такому же алгоритму вычислялось 128-битное зна-чение хеш-функции H2. Ни одно значение H2 не сов-пало с исходным значением H1, что даёт основаниесделать вывод о достаточной надёжности предложен-ного метода.ЗАКЛЮЧЕНИЕВ заключение вернемся к поставленным в началеработы и возникающим при сравнении триангуляцийдвум вопросам. С помощью предложенного методахеширующих функций мы можем уверенно сделатьвывод только о различности двух исходных триангу-ляций, если мы получили различные хеш-значения. Вслучае, если хеш-значения совпали, то мы можемлишь утверждать, что, скорее всего, триангуляциитакже совпадают, причём с большой степенью уве-ренности (вероятность ошибки составляет ƒ(2−n ) , гдеn - длина сгенерированного хеш-значения в битах).Предложенный в данной работе метод сравнениятриангуляций реализован на практике и внедрен всистему автоматизированного проектирования Indor-CAD и геоинформационную систему IndorGIS, разра-ботанные в ООО «ИндорСофт», г. Томск.

Скачать электронную версию публикации