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

На правах рукописи

п

1 Г В вХЬЛлЬЕВ НИКОЛАЙ ПЕТРОВИЧ

I 7 ОКТ 1998

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ХЭШИРОВАНИЯ И ГЕНЕРАЦИИ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

05.13.11,- Математическое и программное

обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Автор:

Москва, 1998 г.

Работа выполнена в Московском государственном инженерно-физическом институте (техническом университете).

Научный руководитель:

доктор технических наук, профессор Чернышев Ю.А. - доктор технических наук, профессор Александров В.М.

Официальные оппоненты:

кандидат технических наук

Ведущая организация:

Матвеев А.Е., АОЗТ "Всесоюзный институт волоконно-оптической связи и передачи информации"

Защита диссертации состоите 1998

года

в аудитории в мае. мин. на заседании диссертационного совета Д053.03.04 в МИФИ по адресу:

115409, Москва. Каширское шоссе, д.31. Тел. 324-84-98; 323-91-67

С диссертацией можно ознакомиться в библиотеке МИФИ. Автореферат разослан " " 1998 т.

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

Ученый секретарь диссертационного совета

д.т.н., профессор В.З. Вольфенгаген

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

высокой достоверностью контроля и широко применяемые при контроле цифссвы/ ♦

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

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

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

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

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

Основными положениями работы, выносимыми на защиту, являются:

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

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

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

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

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

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

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

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

-S-

"Компьютерные системы и технологии" МИФИ по курсам "Надежность, контроль и диагностика ЭВМ", "Системы ввода-вывода ЭВМ".

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

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

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

СОДЕРЖАНИЕРАБОТЫ

Хэш-функцией называется функция К принимающая не более некоторого М различных значений; для всех своих аргументов, именуемых ключами, О<,к{к)<М. Другими словами, хзш-функция отображает множество аргументов мощности Р, на множество значений мощности Рг,~ причем Р, г/*. Таким образом, возможен случай, когда Эк, :Ь(к,)=к(кг); данная ситуация именуется коллизией. Алгоритм, реализуемый хэш-функцией именуется алгоритмом хэширования. Под псевдослучайной последовательностью понимается такой набор чисел, статистические характеристики которого соответствуют таковым для набора случайных чисел, но в отличие от последнего формируемый по определенному правилу, именуемому алгоритмом генерации ПСП.

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

По мнению автора, основной причиной низкой эффективности программной реализации алгоритмов, основанных на теории конечных палей (к таковым стносят-

-6-

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

Под информационным символом (ИС) будем понимать целое число без знака, для представления которого необходимо конечное число двоичных разрядов. Количество последних будем называть разрядностью ИС. Информационной последовательностью (ИП) именуется такой набор информационных символов одинаковой разрядности, в котором каждому ИС однозначно соответствует уни-хальный порядковый целочисленный номер. Максимальный порядковый номер ИС в ИП определяет длину последней. Множество информационных символов S, образуют целочисленные элементы 0,1,2,. ..,2" -1, где натуральное число п - разрядность информационных символов. Множество У, образуют полиномы вида

р . _

FP(x) = ¿,//лг '• Р € |0,+оо), V/ = О, Р е ; степень полинома будем обозначать

degA(x) либо указывать в обозначении полинома: (*), где g = deg-4(jr). Множество У, содержит подмножество Ä., образованное всеми полиномами множества Ут, у которых коэффициент при старшей степени равен 1:

. ч-1 . _

Я„сУя: VHä(x) = xd + ^ h,x' ,d e(0,+®),Vi = 0,rf-l => Hä(x)e Д„.

Теорема 1. Множество V, эквивалентно множеству всех информационных последовательностей разрядности п.

Над элементами множества У. определим следующие операции: Сложение, задаваемое следующим образом: для любых полиномов А(х) степени I

/ m

вида /1(д:)= ^а,--*' и В(х) . ¿тепени m вида Щх) = ^¿¡х', принадлежащих

i=o ;=о

множеству У,, существует полином С(х) степени max(l,m), также принадлежащий

mu((,m)r | .

данному множеству и имеющий вид C(jc) = £ |(af +6, )mod2" je1.

о

Умножение, задаваемое таким образом: для любых полиномов А(х) степени I вида

I m

• А(х) = и 8(х) степени m вида В(х) = ^Ь}х', принадлежащих множеству V,,

(=0 1=0

существует полином D(x) степени )+т вида 1Цх) = £ ^[(«,éy )mod 2" , также

i=0j=t>

принадлежащий множеству V..

Свойства множества V,. Множество И. :

1. Является абелевой группой относительно операции сложения.

2. Представляет собой кольцо относительно сложения и умножения, которое ^коммутативно по умножению, имеет единичный элемент относительно операции умножения и содержит элементы, для которых не существует обратных относительно умножения элементов.

3. Не является полем.

Следствием данных свойств является то, то строгого деления на множества У, ие существует. Тем не менее, имеет место слабая форма деления (с остатком), описываемая следующей теоремой.

»

Теорема 2. (Алгоритм деления элементов VJ. V/i(x)~ eV„,m е|0,<») и

■ ■ . ¿-О '

УВ(х) = хр + ^ bjXJ бЯя,/>б(0,<х>) существует единственная пара многочленов

Q(x) и R(x), принадлежащих , таких что= Д(*)0(л)+

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

Разработанные алгоритмы хэширования и генерации ПСП. обрабатывающие элементы множества И. разделены на базовые и производные алгоритмы, последние подразделяются на алгоритмы с несколькими порождающими полиномами и алгоритмы с несколькими порождающими полиномами и сдвигом переменных Базовые алгоритмы. Рассмотрим полином, принадлежащий множеству Я„. вида

ФЛ (дг)= xs +...+а,х' +...+a,x+l: N е N,VJ = 1,Л'-1 oj е {(>,)} (1)

Назовём полиномы вида (1) порождающими. Введем N элементов хранения д ■ -»Jt'.v • каждого из которых должно быть достаточно для хранения одного

информационного символа разрядности п, т.е. V/ = ¡¡Т/У .у у е ,... ,2" -1}. Для

каждой пары ¡п.Ы}, связанного с ней набора элементов хранения у1 ,}>2<---<У.\ . Для

которых задано начальное состояние =0,^5 =0,...,/дг =0, и порождающего

м

полинома вида (1), базовый алгоритм хэширования полинома Вм(х)=

1=0

описывается системой рекуррентных соотношений вида:

- У { =

Уг^у'Г'+'лг-гУл*

ДЛ . (2) . ■

где V/ = Г,уу-1 я у есть коэффициенты данного ПП, у'к обозначает состояние переменной ук в цикле итерации с номером ¡, а знак "+" обозначает операцию сложения

N-1

по модулю 2". Результат хэширования С/у., (-) = С,-х' е У„, формируется как

¡=о

С( V/ = 0,/V — I, т.е. символами полинома-результата преобразования яв-

ляются состояния переменных У1>У2*-*Ул после обработки последнего символа исходной последовательности.

Генерация последовательности осуществляется по аналогичным формулам, при условии, что входной последовательности нет (т.е. отсутствует слагаемое />,).

начальное состояние переменных У^Уг,■■■,)>% такое что хотя бы одна из них не содержит нулевого значения, и в качестве текущего символа порождаемой последовательности используется текущее состояние переменной (можно использовать и произвольную линейную комбинацию состояний всех или некоторых переменных УнУгг-чУн)-

Алгоритмы с несколькими порождающими полиномами. Основная идея - использование не одного, как в базовом методе, а нескольких порождающих многочленов (ПП) и одного и того же набора переменных.

Пусть разрядность информационной последовательности равна л, имеется множество порождающих полиномов вида (1) С с Л.: С ** ^(д:)^, и набор пере* менных где ЛГ = т*х {^Ф*(х)|, у/ = 1,Л'^е|),1.....2"-1}. Введем

функцию Р[>), принимающую значения следующим образом:

*-« Г а 1»

У/еЫ 1+ ^^Ф^ООк З/^Ф'Ч*) о /»(/)=* е {|,2,...,Л}

и=® С ] ж=1

где де%Ф°(х)=1.

Алгоритм хэширования преобразует элемент множества У. (соответствующий

' • .'-.-■•■ и ■ '

входной информационной последовательности) вида 0И (х)= е Уя в поли-

К-1

ном Сн_,(х)= 2) С,х1 е Уя по формулам:

/»в •. -

У1 - УЩРЮ) +Ь!-1

„I _ „4-1, „Р(0 „1-1 —

„I _ „1-1 . „«0„1-1

^ЛГ(ЖО) -/лг(Л«))-1 +в1

где V/=I, N -1,1 е 10,+ю) в ^ есть коэффициенты текущего порождающего

полинома Ф«п(х). - степень этого полинома, ^

обозначает состоя«« переменной в цикле итерации с номером 1, а "+" обозначает операцио сложения по модулю 2". Начальное состояние переменных У°.Уг* :Уя Должно быть нулевым. Алгоритм генерации отличается от алгоритма хэширования отсутствием входной последовательности, ненулевым вектором начального состояния и тем, что текущее выходное состояние формируется как содержимое переменной .

"Физический смысгГ функцт Р||) заключается в следующем: в течение первых ¿скФ'(х) циклов итерации при вычислениях используются коэффициенты пер-

вого порождающего полинома, в течение следующих deg<J>5(*) циклов - коэффициенты второго ПП, продолжаем, пока не переберем все ПП, после чего вновь в течение циклов используем коэффициенты первого ПП - и так далее. В итоге вычисления оказываются ненамного сложнее используемых в базовых алгоритмах. Алгоритмы с несколькими порождающими полиномами и сдвигом переменных. В алгоритмах этого класса используются уже два набора переменных и два множества порождающих полиномов. Пусть разрядность информационной последовательности равна п, имеется множество основных порождающих полиномов

шада (1) GcR„:G = ^(■*)}/„!, набор основных переменных УцУг,...,Ул. гДв

N=max peg®*(jf)j, V/=1JV у, е — If Также дзкы множество вспомога-

ьй

тельных порождающих полиномов вида (1) Н c.R„tH * {^(дг)]^, и набор вспомогательных переменных 2|где 1. => ma* peg^(x)/. Введем функции P(i) и '■ k'UT

Q(i), принимающие значения следующим образом:

*-1 Г s 1 * ,

VieN £deg<D"4x)<;/mod 1 + ii Я(/) = Л е {ГЛ,...,^},

т=О L т«= I J

1+ ¿deg <рт(х)

/

т-1

т—о

где degO°(x) = l.

Тогда хэширование в соответствие с данным алгоритмом полинома

м S-1

еИ, в полином C№.|(*)=JC|* еСя осуществляется по 1=0 1=0

формулам:

у\ "Уп}р(1))+Ь1

„» „ „'-1 . „W) „¿-I

_ „¿-I . ,,»-«

yNM)) - УЩ1М)У1 +el w»

k = 2,N(P0))

В случае, если /*(/) # />(i -1) дополнительно вычисляется: (4)

** - 4-1

после чего происходит циклический сдвиг влево (вправо) переменной /¿г на \Л/

разрядов. ^

По окончании обработки всех элементов входной последовательности

определяются коэффициенты полинома-результата Обозна-

чения: V/ = 1,ЛГ —1, / е (0,-ыо) есть коэффициенты текущего основного порождающего полинома Ф^'Ч*). Л'(Я('')) ¿ейФ^'^х) - степень этого полинома, ^ (г,) обозначает состояниэ переменной у„ (г,) а цикле итерации с номером ¡, а "+" обозначает операцию сложения» по модугео 2". Начальное состояние основных переменных .у? должно быть нулевым, а среди вспомогательных

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

V»! = 1,£-1,1* е(0,+оо) {¡§М относятся к текущему вспомогательному полиному

степень которого ¿((2(/)) = <1е$;?>С{|)(.*). Переменные и и \Л/ принимают значения, определяемые состоянием некоторых вспомогательных переменных и определяемые из условия итах = Л', \У„=я. Например, при N=32 и п=8 в качестве и можно использовать число, соответствующее состоянию 5 младших разрядов переменной г,, а УУ - 3 старших разряда этой же переменной.

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

Таким образом, данные алгоритмы в дополнение к смене порождающего полинома используют генератор с несколькими ПП, вырабатывающий величины, опре-

деляющче какая переменная и на сколько бит сдвигается циклически влево либо вправо.

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

Тогда независимо от вида исходной информационной последовательности при ее хэшировании происходит деление (в соответствие с Теоремой 2) полинома, соответствующего данной последовательности, на некоторый полином Ч'(л-)

• /v—1

Причем полином ЧЧ*) имеет вид: Ч»(дг) = х" + -о,-)**-' +{2Я - I), . (5)

' ¡=1

где aj е {о,1} - соответствующие коэффициенты порождающего полинома для данного алгоритма, а коэффициенты полинома-остатка от деления хранятся во внутренних переменных, используемых базовым алгоритмом, и коэффициент при более старшей степени хранится в переменной с более старшим номером. Теорема 3. Пусть п - разрядность символов исходной и результирующей после, довательносгей, т и N - количество символов з исходной и результирующей последовательностях соответственно. Хэшировании исходной последовательности в результирующую осуществляется базовым алгоритмом в соответствии с формулами (2). Тогда все входные последовательности, отличающиеся между собой только одним информационным символом всегда дадут разный результат хэширования, а для всех прочих входных последовательностей число коллизий равно:

а) 0. если т.V ,

б) 2»(т-л') если (п>д. (6)

(Отметим, что полученное значение, как доказано в работе, является минимально возможным, т е для любой хэш-функции число коллизий не может быть меньше (6)) Следствие Доля обнаруживаемых ошибок составляет: 1 для таких ошибок, когда искажен только один информационный символ входной информационной ' последовательности: 1 для любых ошибок в последовательности длины, меньшей

2п{т- /v > _|

либо равной степени порождающего полинома и 1 - для прочих ошибок

гпт -1

При т А' зависимость от длины преобразуемой последовательности исчезает, и последняя формула принимает вид

1 -2"ЛГ (7)

Метод сигнатурного анализа и алгоритмы СЙС. обеспечивают точно такой же результат Отметим, что полученные соотношения справедливь! для таких искажений, вероятность возникновения которых есть величина случайная. Такие ошибки харахтер-

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

Производные алгоритмы хэширования позволяют значительно усложнить подбор необнаруживаемых искажений. Рассмотрим алгоритм с несколькими порождающими полиномами. Как следует из его описания, порождающий полином сменяется через каждые ЛГ/ тактов работы, где ¡-номер а - степень текущего ПП. Очевидно

4

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

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

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

Раии=2»-1(2№-1), (8)

где п - разрядность генерируемой последовательности, N - степень порождаемого полинома.

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

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

» со степенью достоверности 0.99 можно утверждать, что вероятность того, что последовательности, порожденные предлагаемыми алгоритмам генерации при случайном выборе порождающих (и вспомогательных) полиномов, будут случайными. равна 0.5541 для базовых алгоритмов. 0,5738 для алгоритмов с несколькими пороздающими полиномами. 0.5927 для алгоритмов с несколькими порождающими полиномами и сдвигом переменных. В Приложении 2 диссертации дан перечень ряда полиномов, выбор которых позволяет генерировать последовательности. проходящие все тесты. • найдено, что для всех разработанных алгоритмов генерации, порождаемые последовательности наиболее чувствительны к 3-м тестам (в порядке убывания чувствительности): тесту собирателя купонов, проверке комбинаций анализу последовательной корреляции

Отметим одну из важнейших особенностей всех разработанных алгоритмов: несмотря на наличие в описании алгоритмов операций сложения по модулю 2" , при программкой реализации операций взятия по данному модулю не потребуется, если число п такое, что для обработки переменной, необходимой для хранения информационных символов разрядности п, как целого без знака требуется одна

операция (инструкция) сложения. 8 таком случае сложение по модулю 2" реали-

зуется данной инструкцией е условиях отсутствия анализа переполнения. Это условие выполняется для современных вычислительных машин при п=8,16,32.

В работе рассмотрено два различных способа программной реализации предложенных алгоритмов. Первый заключается а программировании алгоритма хэширования и/или генерации ПСП в общем виде - т.е. в соответствии с формулами (2)-{4); другой способ - программирование конкретного алгоритма, по жестко заданным полиномам. В первом случае удобно реализовыаать алгоритм хэширования/генерации на языке высокого уровня типа Object Pascal, С++ или Java, Пользуясь t

всеми преимуществами объектного программирования. При программировании конкретного алгоритма можно воспользоваться языком низкого уровня, что позволит достичь более высокого быстродействия. Например, реализация базового алгоритма „

генерации при порождающем полиноме Ф(х) = х* +х3 +1 на Ассемблере IBM PC потребует 4 ячейки памяти, емкость которых равна разрядности обрабатываемых символов и 6 инструкций сложения и пересылки типа «регистр-память». Базовый алгоритм хэширования реализуется с теми же затратами памяти и требует на одну инструкцию пересылки больше. Показано, что зависимости расходов памяти и необходимого числа элементарных операций от сложности алгоритмов при программной реализации последних обоими вышеописанными способами являются ' для базовых линейными, а для производных - почти линейными.

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

• разбить множества входных и выходных переменных тестируемого ПО (модуля либо системы) на подмножества и таким образом, чтобы разрядность переменных в пределах каждого подмножества была одинаковой,

• разработать для каждого подмножества входных переменных процедуру-генератор, причем разрядность генерируемых символов должна быть большей либо равной разрядности переменных в пределах данного подмножества;

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

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

Процесс тестирования включает следующие этапы.

1. генерация одного символа каждым из генераторов. Каждый символ есть тест, подаваемый на все переменные в пределах каждого подмножества входных переменных объекта контроля (модуля или системы);

2. программный объект контроля обрабатывает входное состояние, сформированное на шаге 1, и вырабатывает новое состояние выходных переменных;

3. состояние всех выходных переменных в пределах одного подмнсжества последовательно поступают на вход соответствующей хэш-функции. Шаги 1-3 выполняются до тех пор, пока не будут поданы ьсе i есты;

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

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

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

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

unsigned long CRC32 (unsigned char *buf, int ¿en, unsigned long 'tableJ {// формирования содержимого массива table ив показано register unsigned long crc « OxfffffffffL; mt p;

unsigned long index « 0; f or ip w 0; p < len; p++) i

index я OxfT £ ( (crc » 24) " buf Ip) ) ; crc » OxFFFFFFTFL « ((его « В) A table [ (int) index]) ; ) ___

)

Реализация алгоритма с 4-мя переменными разрядности в, порождающий полином которого имеет вид х4 + х3 +1:

unsigned long bhashl(unsigned char *bu£, int len)

{ • •

int cnt;

register unsigned char у 1"0,ylo~0,y2»0,y3«0, y4«0 ;

for (cnt»0;cnt<len;-H-cnt) <

yl»y4+buf[cnt); y4"y4+y3; y3«y2; y2"ylo; ylo-yl;

' return ( ((unsigned long) y4«24) t ((unsigned long) y3«16) | ( (unsigned

long)y2«8) |yl) ; ] .

С другой стороны, можно использовать алгоритм с 2-мя переменными разрядности 16 и полиномом Ф(х) -х2 +х + \, тогда получим такую хэш-функцию:

unsigned long bhash2 (unsigned int *buf, int len) {

int cnt;

register unsigned int yl»0 ,ylo»0,y2«0; f or (cnt»0; cnt<len; ++cnt) (

yl=y2+builent]; y2=«y2+ylo; ylo«y 1;

) . . , return (((unsigned long)у2«16) |yl) ;

>

Согласно формуле (7), доля обнаруживаемых ошибок для разработанных

алгоритмов в данном случае равна 1-2'31, что соответствует известному значению аналогичной величины для алгоритмов CRC-32. Результаты экспериментальных исследований временных характеристик приведены в следующих двух таблицах (а строках - количество обработанных последовательностей, в столбцах - длина последовательности в байтах, в ячейках - отношение производительности первой и второй хзш-функции соответственно к производительности хэш-функции CRC-32).

10 50 200 1024 5120

50000 2,454545 2,648148 2,626794 2,698276 2,711509

200000 2,2 2,557078 2,679612 2,714662 2,718409

500000 2,124088 2,540984 2,67183 2,713108 2,71833

1500000 2,133495 2,570111 2,687722 2,585037 2,597975

10 50 200 1024 5120

50000 4,5 6,5 5,545455 5,578218 5,588655

200000 5,5 5,333333 5,506234 5,60663 5,598118

500000 4,409091 5,406977] 5,492537 5,596758 5,595928

1500000 4,656354 5,36457 5,527243 5,600857 5,603514

Таблица 2.

При проведении эксперимента использовались: ПЭВМ с процессором Pentium-ll (тактовая частота 266 МГц), операционная система MS-DOS 6.22, компилятор

Borland С++ v.3.1. Тестовые программы приведены в Приложении 1 диссертационной работы. Как видно из табл.1 и 2 производительность первой из рассмотренных хэш-функций выше производительности CRC-32 о среднем в 2.5 раза, а второй - в 5.5 раза. Однако, вторая хэш-функция предполагает, что входная последовательность имеет разрядность 16 (слово), а не 8 (байт), что может потребовать дополнительных. преобразований в приложениях

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

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

Основные результаты работы

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

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

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

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

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

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

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

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

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

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

цифроаых устройств, t

Устройства, реализующие некоторые алгоритмы хэширования из разработанных,

защищен^ патентом России на изобретение №2087030. ~~

По материалам диссертации опубликованы следующие работы:

1. Васильев Н.П., Чернышев (O.A. Программа защиты результатов фундаментальных исследований «Сейф Ученого». - В сб.:Научная сессия МИФИ-98. Сборник научных трудов. В 11 частях. Ч. 5. - М.'.МИФИ, 1998. - с. 70-72.

2. Васильев Н.П., Иванов М.А., Тышкевич В.Г., Чернышев Ю.А. Многоканальный сигнатурный анализатор. - Описание изобретения к патенту Российской Федерации №2087030 кл. 6 06 F 11/00, бюллетень №22. - М.:Роспатент, 1997. "

3. Н. Васильев. Класс алгоритмов хэширования для решения задач контроля и защиты информации. - В c6.:YSTM'96: Молодежь и наука - третье тысячелетие. Труды международного конгресса. Том 1,- М.:НТА «АПФН», 1997. - с. И-48 - II-50.

4. Васильев Н.П. Последовательностью машины нового класса и их применение для контроля и обработки информации. - В сб.: Материалы Московской конференции «Студенческая научная осень-94». В 4-х частях Часть 4. Компьютерные науки. Студенческие идеи, проекты, предложения. - М..МИФИ, 1995. — с. 17-21. '

5. Васильев Н.П. Новый метод контроля информации и криптографической защиты данных. - В сб.: Межвузовская научно-техническая конференция «Микроэлектроника и информатика». Тезисы докладов. -М.:МГИЭТ, 1995. - с. 219-220.

Подписано в печать jL 9. 'Л .Заказ . Тираж 100 экз.

Типография МИФИ. Москва. Каширское шоссе. 31

1.1. Классификация алгоритмов генерации псевдослучайных последовательностей.

1.2. Алгоритмы генерации ПСП, основанные на методах современной алгебры.

1.2.1. Генераторы на основе теории конечных полей.

1.2.2. Линейные конгруэнтные генераторы.

1.3. Эвристические алгоритмы генерации ПСП.

1.3.1. Алгоритмы генерации ПСП общего назначения.

1.3.2. Криптографические алгоритмы генерации ПСП.

1.4. Классификация алгоритмов хэширования.

1.5. Алгоритмы хэширования, основанные наделении полиномов.

1.5.1. Алгоритмы сигнатурного анализа.

1.5.2. ОЗС-алгоритмы.

1.6. Эвристические алгоритмы хэширования.

1.6.1 Алгоритмы хэширования для обработки таблиц.

1.6.2. Криптографические алгоритмы хэширования.

1.7. Выводы.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМОВ ХЭШИРОВАНИЯ И ГЕНЕРАЦИИ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

2.1. Математический аппарат для разработки алгоритмов хэширования и генерации ПСП

2.1.1. Информационные символы и информационные последовательности.

2.1.2. Множество ¥п, эквивалентное множеству информационных последовательностей разрядности п.

2.1.3. Сложение и умножение на множестве Уп.

2.1.4. Свойства множества Уп.

2.1.5. Деление элементов множества ¥п.

2.2. Проектирование классов алгоритмов хэширования и генерации ПСП, обрабатывающих элементы кольца ¥п.

2.2.1. Базовые алгоритмы.

2.2.2. Алгоритмы с несколькими порождающими полиномами.

2.2.3. Алгоритмы с несколькими порождающими полиномами и сдвигом элементов хранения.

2.3. Выводы.

ГЛАВА 3. АНАЛИЗ КАЧЕСТВА РАЗРАБОТАННЫХ АЛГОРИТМОВ.

3.1. Оценка качества хэширования.

3.1.1. Предельное число коллизий для произвольной хэш-функции.

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

3.1.3. Обнаружение искажений с помощью разработанных алгоритмов хэширования.

3.2. Оценка основных показателей алгоритмов генерации псевдослучайных последовательностей.

3.2.1. Оценка периода генерируемых последовательностей.

3.2.2. Анализ случайности генерируемых последовательностей.

3.2.2.1. Критерии оценки случайности набора чисел.

3.2.2.2. Статистические тесты и методика тестирования.

3.2.2.3. Испытания последовательностей, генерируемых на основе предлагаемых алгоритмов, и их результаты.

3.3. Выводы.

ГЛАВА 4. РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ ХЭШИРОВАНИЯ И ГЕНЕРАЦИИ ПСН.

4.1. Программная реализация разработанных алгоритмов хэширования и генерации ПСП

4.1.1. Трудоемкость программной реализации разработанных алгоритмов.

4.1.2. Обработка таблиц и разработанные алгоритмы хэширования.

4.1.2.1 Быстрая хэш-функция для обработки слов естественного языка.

4.1.2.2. 32-х разрядная хэш-функция для обработки последовательностей байт и сравнение ее с хэш-функцией Дженкинса.

4.1.3. Использование разработанных алгоритмов при программном контроле.

4.1.4. Сравнение эффективности программной реализации базовых алгоритмов хэширования и алгоритмов CRC.

4.1.4.1. Алгоритм CRC-32.

4.1.4.2. Базовый алгоритм хэширования с 4-мя переменными разрядности 8.

4.1.4.3. Базовый алгоритм хэширования с 2-мя переменными разрядности 16.

4.1.4.4. Оценка производительности работы.

4.1.5. Программа контроля целостности файлов SIGNER.EXE.

4.1.5.1. Интерфейс пользователя и работа с программой.

4.1.5.2. Алгоритмы контроля и скорость обработки файлов.

4.2. Аспекты аппаратной реализации предлагаемых алгоритмов.

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

4.2.2. Преимущества устройств, реализующих разработанные алгоритмы, перед аналогами.

4.2.3. Многофункциональное секционируемое устройство.

4.4. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые алгоритмы хэширования и генерации ПСП были приняты к использованию Особым конструкторским бюро систем автоматизированного проектирования (ОКБ САПР) для применения в подсистемах контроля целостности. С конца 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 тов, так и для сжатия реакций объектов контроля в задачах тестового диагностирования цифровых устройств.

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

Заключение

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

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

1. Васильев Н.П., Чернышев Ю.А. Программа защиты результатовфундаментальных исследований «Сейф Ученого». В сб.:Научная сессия МИФИ-98. Сборник научных трудов. В 11 частях. Ч. 5. -М.:МИФИ, 1998.-с. 70-72.

2. Васильев Н.П., Иванов М.А., Тышкевич В.Г., Чернышев Ю.А. Многоканальный сигнатурный анализатор. Описание изобретения к патенту Российской Федерации №2087030 кл. G 06 F 11/00, бюллетень №22. - М.Роспатент, 1997.

3. Н. Васильев. Класс алгоритмов хэширования для решения задач контроля и защиты информации. В c6.:YSTM'96: Молодежь и наука - третье тысячелетие. Труды международного конгресса. Том 1-М.:НТА «АПФН», 1997. - с. II-48 - II-50.

4. Чернышев Ю.А., Васильев Н.П. Отчет по гранту Российского фонда фундаментальных исследований №97-07-90220.

5. Жельников В. Криптография от папируса до компьютера. M.:ABF, 1996.-336с.

6. Чернышев Ю.А., Тышкевич В.Г., Иванов М.А., Васильев Н.П. Отчет по теме 218, номер 0191.00.16304, инвентарный номер 02960 000013

7. Васильев Н.П. Новый метод контроля информации и криптографической защиты данных. В сб.: Межвузовская научно-техническая конференция «Микроэлектроника и информатика». Тезисы докладов. - М.:МГИЭТ, 1995. - с. 219-220.

8. Масфик С. Механизмы защиты в сетях ЭВМ. М.:Мир, 1993.

9. Спесивцев A.B. и др. Защита информации в персональных ЭВМ. -М.Радио и связь, 1993.

10. Бородич Ю.С. Разработка программных систем на языке Паскаль: Справ. Пособие. Минск:Вышэйшая школа, 1992. - 143 с.

11. Методические указания к выполнению лабораторного практикума «Техническая диагностика микропроцессорных систем». М.:МИФИ, 1990.-40 с.

12. Толковый словарь по вычислительным системам/Под ред. В. Ил-лингуорта и др.: Пер с англ.; Под ред. Е.К. Масловского. М.: Машиностроение, 1989. - 568 с.

13. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. - 448 с.

14. Иванов М.А., Кпарин А.П. Генераторы псевдослучайных последовательностей. Уч. пособие. М.:МИФИ, 1987. - 40 с.

15. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986. - 576 с.

16. Иванов М.А., Кларин А.П. Сигнатурный анализ в задачах контроля и диагностики цифровых устройств. Уч. пособие. М.:МИФИ, 1986. - 28 с.

17. Липаев В.В. Тестирование программ. М.: Радио и связь, 1986 г. -296 с.

18. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытания и контроля /Под ред. П.М. Чеголина. Минск: Наука и техника, 1986. 200 с.

19. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 4. Ок-Сло М.: Сов. энциклопедия, 1984. - 1216 стб.

20. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 4. Слу-Я М.: Сов. энциклопедия, 1984. - 1248 стб.

21. Математическая теория планирования эксперимента /Под ред. С.М. Ермакова. М.: Наука, 1983. - 392 с.

22. Майерс Г. Искусство тестирования программ /Пер. с англ. под ред. Б.А. Позина. М.: Финансы и статистика, 1982. - 176 с.

23. Поллард Дж. Справочник по вычислительным методам статистики /Пер. с англ. М.: Финансы и статистика, 1982. - 344 с.

24. Майерс Г. Надежность программного обеспечения /Пер. с англ. М.: Мир, 1980.-363 с.

25. Применение цифровой обработки сигналов. Под ред. Оппенгейма Э.- М.:Мир, 1980.-552 с.

26. Информационный обмен в вычислительных сетях. М.:Наука, 1980. -270 с.

27. Хоффман Л. Современные методы защиты информации: Пер. с англ. /Под ред. В.А. Герасименко. М.:Сов. Радио, 1980. - 264 с.

28. Мартин Дж. Организация баз данных в вычислительных системах /Пер. с англ. 2-е изд., доп. - М.:Мир, 1980. - 662 с.

29. Игнатов Б.А. Теория информации и передачи сигналов. М.:Сов. Радио, 1979.-280 с.

30. Ахо А., Ульман Дж. Построение и анализ вычислительных алгоритмов/Пер. с англ. М.:Мир, 1979, - 539 с.

31. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 2. Д-Коо- М.: Сов. энциклопедия, 1979. 1104 стб.

32. Касами Т. и др. Теория кодирования/Пер. с японского; под ред. B.C. Цыбанова и С.И. Гельфанда. М:Мир, 1978. - 576 с.

33. Ахо А., Ульман Дж. и др. Теория синтаксического анализа, перевода и компиляции: В 2-х т. Т.1. Синтаксический анализ. М.:Мир, 1978. -619 с.

34. Ахо А., Ульман Дж. и др. Теория синтаксического анализа, перевода и компиляции: В 2-х т. Т.2. Компиляция. М.:Мир, 1978. -491 с.

35. Кнут Д. Искусство программирования для ЭВМ: В 7-ми т. Т.З. Сортировка и поиск/Пер с англ. М.:Мир, 1978. - 849 с.

36. Гордон и др. Локализация неисправностей в микропроцессорных системах при помощи шестнадцатеричных ключевых кодов. -Электроника, 1977, №5, с. 23-33.

37. Советов Б.Я. Теория информации. Теоретические основы передачи информации в АСУ. Л.:Изд-во ЛГУ, 1977. -184 с.

38. Кнут Д. Искусство программирования для ЭВМ: В 7-ми т. Т.2. Получисленные алгоритмы/Пер с англ. М.:Мир, 1977. - 729 с.

39. Математическая энциклопедия: Гл. ред. И.М. Виноградов, т. 1. А-Г-М.: Сов. энциклопедия, 1977. 1152 стб.

40. Макуильямс О.Дж., Слоан Н.Дж.А. Псевдослучайные последовательности и таблицы. ТИИЭР, 1976, т.64, №12, с. 80-95.

41. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.:Мир, 1976.

42. Кнут Д. Искусство программирования для ЭВМ: В 7-ми т. Т.1 Основные алгоритмы/Пер с англ. М.:Мир, 1976. - 739 с.

43. Крамер Г. Математические методы статистики /Пер. с англ. 2-е изд. -М.:Мир, 1975.-651 с.

44. Доценко В.И. и др. Свойства последовательностей максимальной длины с р-уровнями. Автоматика и телемеханика, № 8, 1971. - с. 189-194.

45. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.

46. Гмурман В.Е. Теория вероятностей и математическая статистика. Изд. 4-е, доп. Учебное пособие для вузов. М.:ВШ, 1972.

47. Алексеев А.И. и др. Теория и применение псевдослучайных сигналов. М.: Наука, 1969.-371 с.

48. Соболев В.И. Лекции по дополнительным главам математического анализа. М.: Наука, 1968. - 291 с.

49. Метод статистических испытаний (метод Монте-Карло) /Под ред. Ю.А. Шрейдера. М.:Физматгиз, 1962. - 335 с.

50. Н. Dobbertin. "Cryptanalysis of MD4. In Proceedings of the 3rd Workshop on Fast Software Encryption", Cambridge, U.K., pages 53-70, Lecture Notes in Computer Science 1039, Springer-Verlag, 1996.

51. RSA Laboratories Bulletin no. 1, January 22,1996.

52. RSA Laboratories Bulletin no. 2, January 23,1996.

53. RSA Laboratories Bulletin no. 3, January 25, 1996.

54. RSA Laboratories Bulletin no. 4, November 12,1996.

55. National Institute of Standards and Technology, Secure Hash Standard", FIPS 186-1, US Department of Commerce, April 1995.

56. P. Rogaway, "Bucket Hashing and its Application to Fast Message Authentication", Proceedings of CRYPTO '95, 1995.

57. Colin Plumb, "Truly Random Numbers", Dr. Dobb's Journal, November 1994.

58. ANSI X9.31-1, "American National Standard, Public-Key Cryptography Using Reversible Algorithms for the Financial Services Industry", 1993.

59. RSA Laboratories. PKCS #1: RSA Encryption Standard. Version 1.5,1. November 1993.

60. Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, MIT and RSA Data Security, Inc, April 1992.

61. National Institute of Standards and Technology, "Secure Hash Standard", FIPS 186, US Department of Commerce, January 1992.

62. E. Fox, L. Heath, Q. Chen, and A. Daoud, "Practical Minimal Perfect Hash Functions for Large Databases", Communications of the ACM, vol. 35, January 1992, pp. 105-121.

63. S. Lloyd, "Counting Binary Functions with Certain Cryptographic Properties", Journal of Cryptology, vol. 5, 1992, pp. 107-131.

64. Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology CRYPTO '90 Proceedings, pp. 303-311, Springer-Verlag, 1991.

65. G. Marsaglia, "A New Class of Random Number Generators", The Annals of Applied Probability, vol. 1,1991, pp. 462-480.

66. RJ. Anderson, "The Classification of Hash Functions", in "Codes and Ciphers", proceedings of Fourth IMA Conference on Cryptography and Coding, 1990, pp. 83-93.

67. R.C. Merkle, "A Fast Software One-Way Hash Function", Journal of Cryptology, vol. 3 no 1,1990, pp. 43-58.

68. P. Flajolet, A. M. Odlyzko, "Random mapping statistics", Lecture Notes in Computer Science, vol. 434, 1990, pp. 329-354.

69. P. Pearson, "Fast Hashing of Variable Length Text Strings", Communications of the ACM, vol. 33, June 1990, pp. 677-680.

70. I. Damgerd. "A design principle for hash functions", Advances in Cryptology — Crypto '89, Springer-Verlag, 1990, pp. 416-427.

71. J. Campbell, "C Programmer's Guide to Serial Communications", Howard W.Sams & Company, 1987.

72. J.L. Carter and M. Wegman, "Universal Classes of Hash Functions", Journal of Computer and System Sciences, vol. 18, (1979) pp. 143-154.

73. A. L. Zobrist, "A new hashing method with application for game playing", U. Wisconsin CS Department, no. 88, April 1970.2