Разработка и исследование алгоритмов хэширования и генерации псевдослучайных последовательностей

Актуальность проблемы. Одной из особенностей нашего времени является грандиозный бум информационных технологий. Использование вычислительных систем становится повсеместным, качество их неуклонно возрастает (постоянный рост производительности микропроцессоров, объемов и быстродействия оперативной и внешней памяти) — стоимость всех вычислительных ресурсов неизменно снижается, а число пользователей увеличивается — вот лишь несколько основных признаков этого информационного взрыва. Естественным следствием происходящих процессов является: постоянное увеличение объемов информации, хранимой на носителях (магнитных, оптических и др.) и передаваемой по каналам связи, что ужесточает требования к процедурам контроля целостности данных — последние должны выявлять как можно большее число искажений в информационных последовательностях, обеспечивая при этом максимальную производительностьпоявление нового программного обеспечения (ПО) и постоянное совершенствование уже выпущенных продуктов требует ускорения процессов их тестирования и отладки без снижения качества тестированиянеизменное совершенствование элементной базы компьютеров и сокращение размеров элементов предъявляет жесткие требования к средствам их тестового диагностирования, которые должны обеспечивать высокую достоверность контроля, иметь высокое быстродействие, регулярную структуру, высокую надежность и низкую стоимостьрост объемов информации, хранимой в базах данных, требует высокопроизводительных средств добавления, поиска и удаления элементов.

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

В настоящее время известно немало различных алгоритмов хэширования и генерации псевдослучайных последовательностей. Недостатком большинства из них является отсутствие эффективных методов наращивания разрядности. Эта проблема становится особенно острой сейчас, когда происходит переход на 64-х разрядную обработку данных, а большинство существующих алгоритмов, реализованных программно, — 32-х разрядные. Алгоритмы сигнатурного анализа, отличающиеся высокой достоверностью контроля и широко применяемые при контроле цифровых устройств, оказываются неэффективными при тестировании ПО вследствие неудобства их программной реализации.

Предлагаемые в настоящей работе алгоритмы хэширования и генерации ПСП свободны от этих недостатков. Достоверность разработанных алгоритмов хэширования аналогична алгоритмам сигнатурного анализа или алгоритмам CRC (циклические избыточные коды), а производительность оказывается существенно большей (см. далее). Предлагаемые алгоритмы генерации ПСП характерны хорошими статистическими характеристиками и удобны как для программных, так и для аппаратных приложений.

Целью диссертационной работы является разработка и исследование новых алгоритмов хэширования и генерации ПСП для задач контроля и обработки таблиц, которые позволяли бы создание генераторов ПСП и хэш-функций, с заданными характеристиками (период генерируемой последовательности, число коллизий), характеризовались высокопроизводительной программной реализацией, допускали легкую, недорогую и надежную аппаратную реализацию, выгодно отличаясь от используемых ныне аналогов.

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

Научная новизна. Разработаны и описаны в виде рекуррентных соотношений и блок-схем три класса алгоритмов хэширования и генерации ПСПпредложенные алгоритмы автор подразделяет на базовые и производные. Выявлен ряд свойств разработанных алгоритмов, в частности, доказано, что доля обнаруживаемых ошибок во входных последовательностях для предложенных алгоритмов соответствует таковой для алгоритмов сигнатурного анализа и алгоритмов CRC, получена зависимость периода последовательности, порождаемой генераторами базового класса от разрядности и ряда параметров алгоритма генерации, исследованы статистические характеристики генерируемых последовательностей. Показано, что трудоемкость программной реализации разработанных алгоритмов характеризуется линейной зависимостью от разрядности обрабатываемых последовательностей и параметров алгоритма. Также показаны преимущества предлагаемых алгоритмов перед аналогами в различных областях применения. Основными положениями работы, выносимыми на защиту, являются:

1. Три класса алгоритмов хэширования и генерации последовательностей.

2. Исследование хэш-функций, реализующих разработанные алгоритмы.

3. Исследование периода и статистических характеристик генерируемых последовательностей.

4. Прикладные аспекты (исследование трудоемкости программной реализации, методики проектирования хэш-функций для контроля целостности и обработки таблиц, методика тестирования ПО).

Практическая значимость работы. Предложено два способа программной реализации разработанных алгоритмов хэширования и генерации ПСП (приведены примеры кода на языках Паскаль, С и Ассемблер). Разработана методика тестирования программного обеспечения, основанная на применении предлагаемых алгоритмов генерации и хэширования. В рамках гранта Российского фонда фундаментальных исследований написана программа для контроля целостности файлов SIGNER.EXE. Предложена методика проектирования устройств, реализующих разработанные алгоритмы хэширования и генерации, которые по сравнению с аналогами имеют меньшую стоимость, большее быстродействие и простоту наращивания разрядностиустройства, реализующие некоторые алгоритмы хэширования, защищены патентом России на изобретение № 2 087 030. Также предложена логическая схема многофункционального секционируемого устройства для систем тестового диагностирования цифровых устройств.

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

Реализация результатов исследования. Исследования проводились в рамках ряда научно-исследовательских работ по разработке алгоритмов хэширования и генерации ПСП для контроля, выполняемых на кафедре «Компьютерные системы и технологии» МИФИ и в Центре новых информационных технологий МИФИ.

Некоторые алгоритмы хэширования и генерации ПСП были приняты к использованию Особым конструкторским бюро систем автоматизированного проектирования (ОКБ САПР) для применения в подсистемах контроля целостности. С конца 1997 гг. предложенные алгоритмы используются в некоторых разработках АОЗТ «Всесоюзный институт волоконно-оптических систем связи и обработки информации». Кроме того, ряд положений работы был использован в учебном процессе кафедры «Компьютерные системы и технологии» МИФИ по курсам «Надежность, контроль и диагностика ЭВМ», «Системы ввода-вывода ЭВМ» .

Апробация. Отдельные результаты диссертационной работы излагались на следующих научных конференциях: Студенческая научная осень-94 (1994 г.), Микроэлектроника и информатика (1995 г.), Международный конгресс студентов, аспирантов и молодых ученых «Молодежь и наука — третье тысячелетие» (УЭТМ-Эб) (1996 г.), Научная сессия МИФИ — 98 (1998 г.). Несколько докладов были удостоены различных дипломов и премий, в том числе диплома первой степени и премии конгресса УвТМ-Эб. Также некоторые положения работы обсуждались на научных семинарах, проводимых на кафедре 12 МИФИ.

Научные публикации. По теме диссертации автор имеет 5 печатных работ, результаты исследований отражены в 2 отчетах по НИР.

Структура и объем работы. Диссертационная работа включает введение, четыре главы, заключение, список литературы и два приложения, помещенные во втором томе работы. Общий объем работы: первый том — 143 листа, второй — 96 листов. Работа содержит 34 рисунка, 17 таблиц и 74 наименований библиографии.

Основные результаты работы можно сформулировать следующим образом:

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

2. Введено множество Уп, эквивалентное множеству всех информационных последовательностей разрядности п, определен ряд операций на данном множестве, выявлены свойства введенного множества и доказано, что существует слабая форма деления его элементов.

3. Разработаны и описаны в виде рекуррентных соотношений и блок-схем три класса (базовый и два производных) алгоритмов хэширования и генерации ПСП, обрабатывающие элементы введенного множества.

4. Доказано, что разработанные алгоритмы хэширования базового класса выполняют деление входной информационной последовательности на элемент множества Уп, однозначно определяемый алгоритмом и не зависящий от вида входной последовательности.

5. Доказано, что хэш-функции, реализующие алгоритмы хэширования базового класса, имеют минимально возможное число коллизий.

6. Показано, что алгоритмы хэширования производных классов характерны трудностью подбора таких разных входных последовательностей, результаты обработки которых будут одинаковы.

7. Определена аналитическая зависимость периода последовательности, порождаемой генераторами базового класса от разрядности последовательности и ряда параметров алгоритма.

8. Показано, что период последовательностей, порождаемых генераторами производных классов, существенно превышает период последовательностей, генерируемых по базовым алгоритмам.

9. Разработана методика анализа статистических характеристик набора чисел и оценки степени их соответствия характеристикам набора случайных чисел.

10. С помощью разработанной методики проведен анализ последовательностей, генерируемых в соответствии с разработанными алгоритмами, дан ряд рекомендаций по проектирования генераторов ПСП для конкретных приложений.

11. Показано, что зависимость трудоемкости программной реализации разработанных алгоритмов от разрядности обрабатываемых последовательностей и параметров алгоритма является линейной.

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

13. Предложена методика использования разработанных алгоритмов хэширования и генерации ПСП для тестирования программного обеспечения.

14. Разработана программа для контроля целостности файлов, реализующая разработанные алгоритмы хэширования.

15. Разработана логическая схема многофункционального секционируемого устройства, которое может быть использовано как для генерации тес.

138 тов, так и для сжатия реакций объектов контроля в задачах тестового диагностирования цифровых устройств.

Устройства, реализующие некоторые алгоритмы хэширования из разработанных, защищены патентом России на изобретение № 2 087 030. Различные аспекты работы отражены в работах [1−4, 6−8].

Заключение

.

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

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