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

кандидата технических наук
Курилкина, Анастасия Михайловна
город
Таганрог
год
2005
специальность ВАК РФ
05.13.19
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Оценка вычислительной стойкости защиты информации алгоритмами "распределенных согласований"»

Автореферат диссертации по теме "Оценка вычислительной стойкости защиты информации алгоритмами "распределенных согласований""

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

Курилкина Анастасия Михайловна

ОЦЕНКА ВЫЧИСЛИТЕЛЬНОЙ СТОЙКОСТИ ЗАЩИТЫ ИНФОРМАЦИИ АЛГОРИТМАМИ «РАСПРЕДЕЛЕННЫХ СОГЛАСОВАНИЙ»

Специальность: 05.13.19. - «Методы и системы защиты информации, информационная безопасность»

АВТОРЕФЕРАТ

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

Таганрог-2005

Работа выполнена в Таганрогском государственном радиотехническом университете на кафедре «Безопасности информационных технологий»

Научный руководитель: доктор технических наук, профессор

Бабенко Людмила Климентьевна

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

1. Аграновский Александр Владимирович, доктор технических наук, < профессор, (ГНУ НИИ «Спецвузавтоматика», г. Ростов-на-Дону)

2. Котепко Владимир Владимирович, кандидат технических наук, доцент кафедры РЭЗиС (ТРТУ, г. Таганрог)

Ведущая организация: Краснодарское высшее военное училище (военный

институт) имени генерала армии С.М. Штеменко, г. Краснодар

Защита состоится « 26 » декабря 2005 года в 14.20 на заседании диссертационного совета ДМ 212.259.06 по техническим наукам Таганрогского государственного радиотехнического университета, по адресу Ростовская область, г. Таганрог, ул. Чехова, 2, ауд. И-425.

Отзывы на автореферат, заверенные печатью учреждения, просьба направлять по адресу: 347928, Ростовская область, г. Таганрог, пер Некрасовский, 44, Таганрогский государственный радиотехнический университет, Ученому секретарю диссертационного совета ДМ 212.259.06. Галуеву Г А.

С диссертацией можно ознакомиться в библиотеке Таганрогского государственного радиотехнического университета, по адресу: 347922, Ростовская область, г. Таганрог, ул. Чехова, 22

Автореферат разослан ноября 2005 года.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

НАШИ

Общая характеристика работы

Актуальность. Широкое применение информационных технологий и повсеместное использование лсктронных средов связи в автомат¡ированных системах обрабо(ки информации и управления требует надежной зашшы данных и ресурсов от возможности несанкционированного доступа, используя специальные средства Среди них одним из наиболее распространенных является преобразование дискретной информации с помощью специально созданных алгоритмов, которые постоянно разрабатываются и модернизируются Возможные пути модернизации заключаются в совершенствовании современных асимметричных алгоритмов (стойкость многих из них основана на задаче дискретною логарифмирования в конечном поле и в группе точек эллиптической кривой над конечным полем), и усложнении классических алгоршмов созданием каскадных схем При ра ¡работке и совершенствовании алгоритмов защиты информации необходимо аналакировать их стойкость Стойкость алюритмов разделяют на теоретическую и прлкшческую. Основными количественными мерами практической стойкости алгоритмов защиты дискретной информации служат /ак называемые «трудоемкое^ чем и анализа алюритма» (или вычислительная стойкость) - число операций или количество времени необходимых для получения ключа, и его «надежность» - вероятность дешифрования

Оценка вычислительной стойкости многих алгоритмов защиты информации сводится к решению уравнения вида

Ф(а,к) = Ь, (1)

где Ф(а,к) - нелинейная функция, секретный ключ Л , а и Ь некоторые известные постоянные величины Не малая часть этих уравнений представляет собой уравнение вида

уу{к') = Г{к"), (2)

где у/(к'),у{к")~ нелинейные функции, (к',к") = к, к'еГщ, к"еГ , Г х Г1Н = В

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

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

Известными математиками, занимающимися исследованиями в области защиты информации, Грушо Л А , Ростовцевым А Г , Маховенко Е Б , В Диффи, Хеллман М. было показано, чю в среднем трудоемкость меюда согласования состоит из |£'|+|^"|)+(|г| + |Г'|)]п(|/1:'| + |/Г|) опробований. А трудоемкость метода "разделяй и

побеждай" составляет \k\jl опробований Это значительно меньше

\к'\-\к"\12 метода тотального опробования К тому же Нечаев В И установил, что

среди детерминированных меюдов оценки стойкости алюритмов, основанных на дискретном возведении в С1епень, метод согласования является лучшим Таким образом, наиболее перспективными методами ппи а^али^е стойкости каскадных схем и алгоритмов, основанных на дискретном возве; ;>ЙОСзЬетеиец(.,! ЯВДЯЦ^С? меюды

ЖГГ»*

С^е-.;,, ург

coi тсования и "разделяй и побеждай" Но они все же, как показано выше, требуют значительных вычислений, а значит и ¡нлчительных затрат времени Попробовать сократить эти временные затраты можно при помощи распределенных вычислений, cpe.iciea реализации которых постоянно совершенствуются.

Таким образом, исследования ставящие целью повышение производительное!и меююв сотласования и "разделяй и побеждай", являются актуальными и прс ютавляют научный и практический ишсрсс.

Целью работы является повышение производительности мет слов coi исования и "разделяй и побеждай" д |я опенки вычислительной стойкости зашиты шскретной информации при помощи распре пленных вычислений

В соответствии с поставленной не н.ю в диссертации решаются следующие основные задачи'

1 Анализ методов согласования и "раз ie 1яй и побеждай", использующихся при опенке стойкости современных систем безопасности, основанных на каскадном шифровании или на дискретном возведении в степень.

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

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

4 Разработка npoi-раммных реализаций предлагаемых параллельных алгоритмов для оценки стойкости двойного DF.S и зачачи дискретного логарифмирования в конечных полях.

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

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

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

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

Научную новизну диссертационной работы составляют 1 Впервые разработанные параллельные алгоритмы "распределенных согласований", позволяющие на п- мерной системе вычислительной системе решать важные задачи, сводящиеся к решению уравнения вида у/{к') = у(к"). где

iff(k'),y(k")~ ne шнейные функции, k'&Fl¡t, к" е Г,, (к',к") = к, ksFn,

Г х F = F

"l "2 "

2. Параллельные алюрнтмы "распределенных согласовании" для анализа каскадных шифров Полученные оценки эффективности распараллеливания алгоритмов (ускорение R = TJ Г, где 7! — время решения задачи на однопроцессорной системе, а Ти - кремя решения той же задачи на и - процессорной системе) "распределённых согласований" для анализа бе (опасности двойного DES

о w

показывают, что И --, где w-количество процессоров

1 + 0,115 и>

3. Параллельные алюритмы "распределенных coi ласований" для отыскания дискретного логарифма в конечных полях и в ipynne точек эллиптической кривой над конечным нолем Полученные теоретические оценки эффективности распараллеливания алгоритмов "распределённых coi ласований" для решения задачи дискретного логарифмирования в конечном ноле показывают, что R , например, при и -2 и t = 1700 будет составлять 1,83.

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

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

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

1. Алгоритмы "распределенных согласований", основанные на детерминированном методе согласования, которые позволяют на многопроцессорной системе решать важные задачи, сводящиеся к решению уравнения вида iy(k') = у(к"), где у/(к'),-/(к")~ нелинейные функции, k'eFi к" еF , (к',к") = к , к с Fa F хF =F

HI ib 11

2. Алгоритмы "распределенных согласований" для анализа безопасности каскадных шифров

3. Алгоритмы "распределённых согласований" для решения задачи дискретного логарифмирования в конечных полях и на эллиптической кривой

4. Теоретические оценки эффективности распараллеливания разработанных алгоритмов

5. Экспериментальное подтверждение теоретических оценок

Апробация работы. Результаты работы докладывались и обсуждались на научно- практических конференциях: VI международной научно-практической конференции «Информационная безопасность» (Таганрог, 2004), VIÍ всероссийской научной конференции молодых ученых и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004), П всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2004), VII всероссийской

научной конференции с международным участием «Ноные информационные технолси ни Рачрабо1ка и аспекты применения» (Таганрог, 2004), I ежегодной научной конференции студен юн и аспирантов базовых кафедр Южною научного центра РАН (Ростов. 2005) \ II международной научно-практической конференции «Информационная бс«опасность» (Таганрог, 2005)

Результаты р.инны использованы в НИИ МВС TPTV при выполнении ОКР «Разработка базовою инструментария для параллельно-конвейерной реализации вычислительно ф\'юсчких фрагментов задач проблемной области в оперативно-приемлемое время при различных условиях применения» в учебном процессе кафедры БИТ TPTY но курсу "Криптографические методы и средства обеспечения информационной безопасности", (что подтверждено соответствующими актами)

Публикации. По 1еме диссертации опубликовано 10 научных работ Программа, полученная в ходе выполнения работы, iapei истрирована в Реестре программ для ЭВМ (свидетельство об официальной регис|рации программы для ЭВМ № 2005611241 or 27 мая 2005г.)

Структура и объем работы. Материал диссертационной работы изложен на 132 сграницах машинописного текста Работа состоит из введения, пяти разделов, заключения и списка ипературы из 54 наименований

ОСНОВНЫЕ ПОЛОЖЕНИЯ РАБОТ Ы Во введении обоснована актуальность темы диссертационного исследования, определено поняше алгоритмов "распределённых согласований", сформулированы цель и задачи рабо<ы, отражены научная новизна и практическая значимость полученных результатов

Первый раз к'л работы посвяшен задаче дискретного логарифмирования в конечных полях и в i pvmie точек эллиптической кривой над конечным полем, а так же анализу стойкости каскадных шифров методами согласования и "разделяй и побеждай"

Лредваритечьно вводятся понятия задач дискретною логарифмирования в конечном поче и в ipynne точек эллиптической кривой над конечным полем и сопутствующие им определения

Пусть О -< С*. 1 > - конечная мультипликативная абслева группа Если

иеС,а*0, то наименьшее натуральное число S с условием а" = 1 называют порядком жмента a i рупны G и обозначают ordа Если a, b е С, l = ord b и

b'=a,0<l<t, (3)

то натуральное число / называют дискретным логарифмом элемента а при основании Ь, обозначают log,, а = / Задачу нахождения решения / уравнения (3) называют

задачей дискретного югарифмирования в группе G

Пусть F - поле из q = р" элементов, где р- простое и пе N. Пусть

эллиптическая кривая E(F^) задана уравнением уг=хг+а х2 +A(modi/) Точки

эллиптической кривой E(F) образуют группу Точку Q называют точкой кратности

к, или прост - кратной точкой эллиптической кривой F\Fq), если для некоторой

точки Р выполнено равенство- Q-P + + Р=кР Если Р е E(Fq),P * О, где

0 = (0!)- нулевая точка, то наименьшее наг>ра ibiioe число п с условием пР - О называют порядком точки Р

Пусть Q е £(£ ) - точка порядка i Тогда задача дискретного югарифмирования в группе точек эгчиптической кривой формулируется следующим образом ,(ля данной точки найти показатель/такой, что P = IQ

Рассмотрено влияние задач дискретною логарифмирования на стойкость MHOi их современных методов зашиты информации

Злюм определяется понятие каскаднош шифрования Пусть даны h шифров E,(X,kt), F2{X\k2),...,Ek(Xh'\kll). В случае каскадного шифрования одного и того же блока открытого текста шифртекст Y = (\\, i ) получается из открытого текста А' = (др ,*„) композицией оюбражений ЕпГ.. , F.h , то есть

Y = Ell(E,i l(,(E2(El(X,k,\k2),k,). .\k,,) Ключ системы представляет ообой век-юр k=(k„k„ где ¿,еЛ",, k2eK2, , k,teKt, К = AT, х К2х. х К,, из h

независимых ключей. Расшифрование происходит применением следующего преобразования X = £~'(£j'( {El\y,kh\kh_^

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

Далее приводится алгоритм метода "разделяй и побеждай" анализа каскадных шифров, обладающих критерием g, который позволяет при известных X = (д,...,хп) и Y = (>',,.. ,уп) проверять правильность первой компоненты k' = {kt,k2,. ,,к1 ), где

1 < г < h , в ключе к = (kl,k!,...,kll). То есть, если

Е'(Х,к') = ЕГ(Е,МФ,Ф2). \k,),E\Z,k") = £,(£,_,(.. {Ejz,k,jk,j..\k,), где к" = (к, .„к, ■,k„),K' = KlxK2x...xK, , K" = K,tixK^2 х...хКЛ, тогда для V/t' с К' функция g(X,Y,k')= 1, если 3k" е К" такой, что E2(El(X,k'\k")= Y, и g(X,Y,k') = 0, если V/Te/T E2{E'{X,k'\k")* Y .

Анализируется структура алгоритма метода "разделяй и побеждай" и делается вывод о возможности его распараллеливания Рассматривается пример применения метода "разделяй и побеждай" для анализа двойного шифра (зашифрованного в режиме СВС) Производится оценка рассмотренных алгоритмов анализа безопасности каскадных шифров. Показано, что трудоемкость двух вариантов метода согласования составляет Т = и (с, ■. ,-cr \k\ + crti . ch •|/t"|)+|A'|+|/t"| и

Г = /| (с,- cr-jfc'l + c,^ • сА + р операций, где с, - трудоемкости вычисления

функций Е1, где t = \,li, ¿-трудоемкость сортировки значений 1-й таблицы, р - обозначим трудоемкость поиска равных элементов в таблицах Это значительно

меньше сг ■ с,^ •. • c.h -|/г'|• операций метода тотального опробования.

Следовательно, алгоритмы двух вариантов метода согласования и метода "разделяй и

побеждай"' эффективнее, чем метод тотальною опробования, но всё же тоже требую) значшельпых затрат времени Поэтому необходимо искать пути сокращения их временных затрат

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

ф(к') = г(к")> И)

где у/{к"\ /<к")~ нелинейные функции, к'с Г . к"еГ , (к\к") = к , к е Г,

II, и, II

Шм1и решение нелинейного уравнения (4) можно с помощью алюршчон метода сш .тасования, который рассмотрен в диссертационной работе.

Затем предполагается, что дополншельно существует критерий позволяющий при известных а и Ъ проверять правильность компоненты к' ь неизвестной переменной к - {к',к") То есть для Ук'еГ функция g(a,b,k')=\ если ЗА" е Рт такой, что Ф(а,(к',к")) = Ь, и g(a,b,kl)-0, если УА"€^Ь Ф(а,(А',А")) * Ь. Тогда найти решение уравнения (4) можно с помощью алтритма метода "ращеляй и побеждай", который так же рассмотрен в работе.

Проведена оценка трудоемкости и анализ структуры рассматриваемых методов Благодаря чему выявлено, что они схожи по структуре и поддаются распараллеливанию.

Далее предложено распределение перебора значений неизвестных переменных по всем имеющимся процессорам и>, и представлены параллельные алгоритмы "распределенных согласований".

Алюритм "распределённых согласований" (А-2 3) выглядит следующим образом

Вход а,Ь.

1 Распределяем перебор возможных значений А'по всем процессорам

Перебирая значения переменной, вычисляем = 5 и я(х)=А'.

2 Распределяем перебор возможных значений к" по всем процессорам

Перебирая значения переменной, вычисляем у(к") = 5 и проверяем- если

/7(5") не пусто, то А = (/7(5'),А")

Выхоб к

Алгоритм "распределённых согласований" (Б-2 3) показан на рисунке 1 В нем где / €[1;и'], обозначен алгоритм, выполняемый /-м процессором

блоком

5 (А")

при переборе значений к'. А блоком -—-— где /е[1;и']> обозначен алюритм,

quick sort S,Ik')

где

выполняемый /-м процессором при переборе значений к" Блок

I е[1; w], означает сортировку возможных значений к' способом quick sort. Сравнение

значений бинарным поиском обозначено блоком

Б Л ,

Sj(k')=S,(k")

где i,j €[l,w]

Произведена оценка ускорения даваемою разработанными алгоритмами

ZLZ

b nun' max nun mux

X

Л, = (inax'~min -l)n I

Л 1 , * ,

i

quick sort quick sor*

Ч/

U- -(max'-min'N !)н

7

<оП успешен>

...W-y

нет

Рисунок I - Блок-схема алгоритма "распределенных согласований" (Б-2 3) для решения уравнения (4)

Ускорение находится по формуле = 2 3) коэффициент сетевой

деградации

, в которой для алгортма (А-вычислений соаавляет

п \к\ + п £/0)

с=ч—/ . ,,-, „л , ,,—¡—-гт—, гче Г - время одной передачи данных но сети,

И^И + М* 1НФ1* |К

/„-время выполнения одной операции, п- размер 5 (и 5"), с, и с2 - трудоемкости вычисления значений функций <р и у соответственно; для алгоритма (Б-2 3)

____'¿Ш_

«•(с,-|*'| + с2-|Г|)+2 |А1 М)

Алгоритм "распределённых согласований" (С-2 3) показан на рисунке 2 В нем алгоритм работы 1-го процессора, где /е[1;м>], при переборе значений к' обозначен

блоком

т

А алгоритм работы у-го процессора при переборе значений к", где Передача найденных, подходящих по

у е [1, и<], обозначен блоком критерию, значений к' от одною процессора другим обозначена соответствующими с грелками между процессорами.

! а, Ь, %, тт'

Т

тах', шт" тах",«<

1

7

\ =(т

п'+1>ц.

т

Л2 =(тах"-т1п"+1)"и>

Рисунок 2 - Блок-схема алгоритма "распределенных согласований" (С-2 3) для решения уравнения (4)

d f>) /

Для алгоритма (С-2 3) в формуле ускорения с =—;—¡-^-г—гт— , где d -

п\т \к'\ + с |Г|) /0

трудоемкость сортировки значений 5 в 1-й таблице, m - трудоемкость проверки критерия g, с - трудоемкость вычисления функции Ф(Л).

При реализации разрабо!анных алгоритмов "распределённых coi ласований" может возникнуть ситуация, ко)да требуемый объем памяти процессора превышает реально существующий В этом случае необходимо модифицировав алгоритмы (Б-2 3) и (С-2 3) разделив возможные значения неизвестных переменных (ключей) одного процессора (перебирать не во всем заданном диапазоне, а разбить ею на части, а получаемые значения сохранять в таблицы- фреймы) Для этого случая произведена коррекция оценок ускорения.

На основании проделанных оценок ускорения разработанных алгоритмов (А-2 3), (Б-2.3) и (С-2.3) делается вывод, что при значительной трудоемкости функций Ф(к), i//(k') и у (к") (что часто встречается на практике) они позволяют существенно сокращать временные затраты

В третьем разделе пре июжены параллельные алгоритмы (А-3 I I), (Б-3 1 1) и (С-3.1 1) анализа каскадных шифров на основе разработанных алгоритмов "распределённых согласований" Рассмотрены алгоритмы "распределённых согласований" (А-3 1 2) и (Б-3 1 2) для частного случая' анализа безопасности двойного DES Получены оценки эффективности распараллеливания предложенных алгоритмов (ускорение).

Для алгоритмов "распределённых согласований" (А-3 1 2) и (Б-Ч 1 2) наглядно проиллюстрирована (рис 3 и рис 4) зависимость ускорения от количества процессоров при конкретных значениях технических параметров (компьютер для шифрования DES алгоритмом требует не менее 1000 тактов; время одной передачи данных по сети /,=1,39 2"'8 мс; время выполнения одной операции /„ = 2,3 10"* мс) Ускорение модифицированного алгоритма (Б-3 1.2), оперирующего фреймами, для этих же

И"

значений параметров составляет R, «- (при w = 2 R -1,947) Так же

' 1 + 0,01356 w '

получены предельные значения ускорения.

Рисунок 3 - График зависимости R алгоритма (А-3.1 2) от количества процессоров

Количество процессоров-«

Рисунок 4 - График зависимости R алгоршма (Б-3 1 2) о г количества процессоров

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

В че1вертом разделе диссертационной работы предложены алгоритмы "распределенных согласований" (Б-4 2 2), (D-4 2 1) и (Б-4 4.1) для дискретного логарифмирования в конечных полях и в группе точек эллиптической кривой над конечным почем, которые используют арифметик) больших чисел. Получены оценки эффективное! и распараллеливания разработанных алгоритмов (ускорение) Ускорение алгоритма Í5-4 2 2) дискретного логарифмирования в конечных нолях:

(8 л/Г-4 + logy,l5V7) w t„

П'2 __ l! t_ i— j

(4 [2/1'2 -lj-t-!og2í'^) t0 ~(8 log2t t.n" И-/,)-

И'

где Л</|- дчина чисел Ускорение алгоритма (Б-4 4 1) дискретного логарифмирования на эллиптической кривой' /?=-

(23■ (4 г-3) + 3•;- log;/-) w t0

(

w 23 (г -1) + 23 13 г

log2

■í„

1 в\\

где ||0||-длина записи произвольной точки О с

Дтя алгоритма "распределенных согласований" (Б-4.2.2) наглядно проиллюстрирована зависимость ускорения от порядка основания логарифма (рис.5) и количества процессоров (рис 6) при конкретных значениях технических параметров (время одной передачи данных по сети = 1.39 2~18 мс, время выполнения одной операции I =0,1 б мс при длине чисел 1024-2300 бит) По графику рис.5 видно, что с ростом значений / ускорение постоянно увеличивается, но с каждым разом всё меньше и меньше Благодаря чему значение ускорения никогда не превысит значение количества процессоров п. По графикам рис б отчетливо видно, что с ростом значений и- ускорение алгоритма (Б-4 2 2) постоянно увеличивается, но чем больше эти значения, тем с меньшей скоростью увеличивается ускорение, не превышая свое! о предельного значения

(lim R-

8 4t - 4+log2Л'

■V7

8 logz; +

+ 4

k/Г-.]

, где

• длина чисел)

§ 2 «

Порядок основания логарифма-!

Рисунок 5 - Т рафик зависимости Л алгоритма (Б-4 2 2) от I при и,=2

Количество процсссорон-л

Рисунок б - График зависимости Я алюритма (Б-4 2 2) от количества процессоров.

Исследования зависимостей ускорения алгоритма "распределенных согласований" (0-4.2.1) показали, что с увеличением порядка основания логарифма г ускорение изменяется не монотонно (рис 7), а зависит от конкретных значений сомножителей /], гг в разложении порядка основания логарифма

Рисунок 7 - График зависимости /? алгоритма (0-4 2.1) от I при w-4

И с уменьшением значения одного из сомножителей /-,,/, ускорение алгоритма

(0-4 2.1) увеличивается К тому же с ростом количества процессоров ускорение алгоритма тоже постоянно увеличивается, не превышая свое! о предельного значения

В пятом разделе диссертационной работы проно л: 1ся описание среды реализации разработанных алгоритмов и программных моделей оптимальных алгоритмов "распределенных согласований" для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном иоде

Разработанные алгоритмы "распределённых согласовании" созданы для систем типа МКМД (множественный поток команд - множественный поток данных) с разделяемой памятью, то есть для многопроцессорных систем с обменом сообщениями Наиболее дешевыми и распространенными снаечами такого типа являются кластерные системы В настоящее время наиболее широко используемым, динамично развивающимся и испытанным средством профаммирования для кластерных систем и компьютеров с распределенной памятью является технология MPI (message passing interface) В связи с этим инструмсшом программирования выбран пакет WMPI 1 3 для среды Windows NT В качестве языка программирования использовался Visual Studio 2003.

Приводя 1ся результаты моделирования разработанных алгоритмов. Для двух процессоров показана возможность существенного сокращения временных затрат при использовании разработанных алгоритмов анализа безопасности двойного DES (Б-3 1.2) (Л>1,6 и зависит от количества произведенных переборов) и решения задачи

дискретного логарифмирования в конечном поле ( R > 1,768 для t > 2770 ).

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

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

При решении поставленных в диссертационной работе задач получены следующие научные результаты:

1 В результате анализа методов согласования и "разделяй и побеждай" выявлена возможность их распараллеливания.

2. Впервые разработаны параллельные алгоритмы "распределенных согласований", позволяющие на п- мерной системе решать важные задачи, сводящиеся к решению уравнения вида у/(к')=у{к"), где у/(к!'),/(к") - нелинейные функции, к' е р^ ,

к" е ^ , (к1,к") = к , к е Р„, ^ х = Р,.

3 Разработаны алгоритмы "распределенных согласований" для анализа стойкости каскадных шифров и отыскания дискретного логарифма в конечных полях и в группе точек эллиптической кривой над конечным полем (для анализа оценки стойкости протоколов защиты цифровой информации, основанных на дискретном логарифмировании)

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

4

4 Получены георсжчсские оценки эффективности распараллеливания разработанных алюршмов "распределенных сопасованин" для анализа стойкости протоколов защи!ы цифровой информации, основанных на каскадном шифровании или дискретом ло) арифмировании Теоретические оценки эффективности алгоритмов "распределенных согласований" для анализа безопасности двойного DES ((А-3 1.2), (Б-3 1 2), модификации (Б-3 1.2)) и решения задачи дискретного логарифмирования в конечном поле ((Б-4.2 2)) проиллюстрированы на конкретных значениях технических параметров Показано, чго ускорение дня (А-3 1 2) и (Б-3.1.2)

будет составлять ---, где iv- количество процессов модифицированного

1 -г 0.11 S и-

W

алгоритма (Б-3 I 2) оперирующего фреймами, будет R «-. для (Б-

1 — 0,01356 w

4 2 2), при w = 2 и ! = I "'00, будет составлять 1,83

5 Созданы программы алгоритмов "распределённых согласований" для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном поле, которые позволяют экспериментально оценивать временные затраты этих алгоритмов при различных значениях параметров (н' и /) В качестве инструментария npoi раммирования использован пакет WMPi 1 3 для среды Windows NT В качестве языка upoi раммирования использовался Visual Studio 2003.

6 Экспериментальные оценки разработанных алгоритмов с помощью созданных программ показали, что ускорение при наличии двух процессоров для модифицированного алгоритма анализа безопасности двойного DES (Б-3 ! 2) будет не менее 1,9 ; для am opin m<j решения задачи дискретного логарифмирования в конечном поле при г = 1700будет ^1,8 Созданные программы подтверждают теоретические оценки ускорения

Список публикаций по теме рабо1ы

1 Бабенко J1K, Нсмова AM Распаршпеливание криптоанапитических методов "встречи в середине атаки" и "разделяй и побеждай" дня многократных шифров// Материалы VI международной научно-практической конференции «Информационная безопасность» - Таганрог' ТРТУ, 2004.

2 Немова А М. Распараллеливание критоаналитических методов для двойного и тройного DES-алгоритмов'/ Тезисы докладов Vil Всероссийской научной конференции молодых ученых и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» - Таганрог ТРТУ 2004.

3 Курилкина A.M Параллелизм в решении задачи криптоанализа тройных алгоритмов// Тезисы докладов II Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» - Таганрог. ТРТУ , 2004

4 Курилкина A M Ал! оритмы решения некоторых классов задач криптоанализа в многопроцессорных системах// Труды VII всероссийской научной конференции с международным участием «Новые информационные технологии Разработка и аспекты применения»,- Taraupoi, 2004

5 Бабенко Л К , Курилкина A M Распараллеливание криптоаналитического метода "разделяй и побеждай" для каскадных шифров//' Материалы XII всероссийской

жал 8216

научно-практической конференции «Проблемы информационной ____

системе высшей школы» - М МИФИ, 2005

6 Курилкина Л М Распараллеливание метода согласования для задачи дискретною логарифмирования в конечных полях / Материалы Пятой межрегиональной научной конференции «Студенческая наука - экономике России».- Ставрополь СевКавГТУ, 2005. йир //\у\у\у псбШ ги

7 Курилкина А М. Параллелизм метода согласования в решении задачи шс кретного логарифмирования в конечных полях для составною порядка основания// Материалы Первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного намного центра РАН.- Ростов, 2005

8 Бабенко Л К, Курилкина А М Параллельный алгоритм «распределенных согласований» решения задачи дискретного логарифмирования в конечных почях// Вопросы защиты информации Москва. 2005 - №2 (69)

9 Бабенко Л.К, Курилкина АМ Распараллеливание решения задачи дискрешого логарифмирования на эллиптической кривой // Материалы VII международной научно-практической конференции «Информационная безопасность»- Т.нанрог 1 РТУ, 2005

10 Курилкина А.М Параллелизм в решении задачи дискретного логарифмирования методом согласования/' Научная работг депонированная в ВИНИТИ (№7"?3-В2005 от 30 05 2005).

Программа, полученная в ходе выполнения диссертационной работы, зарегистрирована в Реестре программ для ЭВМ, свидетельство № 2005611241 от 27 мая 2005г

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем [1] - разработка паралпельного алгоритма метода "встречи в середине атаки" для анализа стойкости многократных шифров, [5] - разработка способа деления диапазонов изменения ключей по процессам, обоснование выбранно! о метода остановки работы процессов в параллельном алгоритме метода "разделяй и побеждай", [8] - обоснование значимости дискретного логарифмирования в конечных полях для задач зашиты информации, разработка блок-схемы алгоритма "распределенных согласований" для вычисления дискретного логарифма в конечных полях, [9] - разработка блок-схемы алгоритма "распределенных согласований" для вычисления дискретного логарифма на э'шигпической кривой

Тип ТРТУ Заказ НгЬск тир /ДЯэкз

2 9 ДЕК 2005

Оглавление автор диссертации — кандидата технических наук Курилкина, Анастасия Михайловна

ВВЕДЕНИЕ.

1. АНАЛИЗ ЗАДАЧ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ И ОЦЕНКИ БЕЗОПАСНОСТИ КАСКАДНЫХ ШИФРОВ.

1.1. Задача дискретного логарифмирования в конечных полях.

1.1.1. Постановка задачи дискретного логарифмирования в конечных полях.

1.1.2. Особенности применения дискретного логарифмирования в конечных полях.

1.2. Задача дискретного логарифмирования на эллиптической кривой.

1.2.1. Постановка задачи дискретного логарифмирования на эллиптической кривой.

1.2.2. Особенности применения дискретного логарифмирования на эллиптической кривой.

1.3. Задача анализа безопасности каскадных шифров.

1.3.1. Каскадные шифры.

1.3.2. Анализ безопасности каскадных шифров.

1.3.3. Оценка анализа безопасности каскадных шифров.

1.4. Выводы.

2. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА СОГЛАСОВАНИЯ И МЕТОДА "РАЗДЕЛЯЙ И ПОБЕЖДАЙ".

2.1. Методы согласования и "разделяй и побеждай", и их анализ.

2.2. Оценка трудоемкости методов.

2.3. Возможные принципы распараллеливания методов и алгоритмы "распределенных согласований".

2.4. Оценка эффективности разработанных алгоритмов.

2.5 Выводы.

3. РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ

АЛГОРИТМОВ АНАЛИЗА КАСКАДНЫХ КЛАССИЧЕСКИХ ШИФРОВ.

3.1. Анализ каскадных шифров алгоритмами "распределённых согласований".

3.2. Алгоритмы "распределённых согласований" анализа безопасности двойного DES.

3.3. Оценка эффективности разработанных алгоритмов.

3.4 Выводы.

4. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ МЕТОДОМ СОГЛАСОВАНИЯ.

4.1. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования в конечных полях.

4.2. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования в конечных полях.

4.3. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой.

4.4. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой.

4.5. Оценка эффективности разработанных алгоритмов.

4.6. Выводы.ИЗ

5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК РАЗРАБОТАННЫХ АЛГОРИТМОВ.

5.1. Среда реализации алгоритмов.

5.2. Описание программы разработанного алгоритма "распределённых согласований" для анализа безопасности двойного DES.

5.3. Описание программы разработанного алгоритма "распределённых согласований" для задачи дискретного логарифмирования в конечном поле.

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

5.5. Выводы.

Введение 2005 год, диссертация по информатике, вычислительной технике и управлению, Курилкина, Анастасия Михайловна

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

разделяют на теоретическую и практическую.

Понятие теоретической стойкости связано с работами К.Шеннона и основано на количественном определении информации через вероятностные характеристики процесса образования данного вида информации. Используя ряд общих результатов теории информации (относящихся к вычислению пропускной способности канала связи) оценивается возможность восстановления сообщения, которое передается через открытый канал связи с шумом, по шифрованному тексту. В качестве теоретической меры секретности используют «надежности открытого сообщения и ключа», которые определяют через условные энтропии вероятностных схем [39].

Понятие практической стойкости связано с книгой Керкхофа «La Cryptographie militare», по которой оценивать стойкость шифра необходимо в предположении, что для противника секретным является лишь ключ. Основными количественными мерами стойкости алгоритмов защиты дискретной информации служат так называемые «трудоемкость метода анализа алгоритма» и его «надежность». Под «надежностью» понимается вероятность дешифрования. А под «трудоемкостью метода анализа алгоритма» понимается число операций (или количество времени) необходимых для получения ключа, то есть оценка вычислительной стойкости алгоритмов защиты информации.

Оценка вычислительной стойкости многих алгоритмов защиты информации сводится к решению уравнения вида

Ф {а,к) = Ь, (1) где Ф(а,к)- нелинейная функция, секретный ключ к е Fn, а и b некоторые известные постоянные величины. Не малая часть этих уравнений представляет собой уравнение вида

Ик') = г(П, (2) где у/{к'),у{к")~ нелинейные функции, {к\к") = к, k'eFni, k"eFn2,

Fn[ х Fni =Fn. В частности, такие уравнения получаются при анализе стойкости каскадных схем и алгоритмов, основанных на дискретном возведении в степень.

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

Известными математиками, занимающимися исследованиями в области защиты информации, Грушо А.А., Ростовцевым А.Г., Маховенко Е.Б., В. Диффи, Хеллман М. было показано, что в среднем трудоемкость метода согласования состоит из (jAr'| + |A:"|)+(jA:'| + |A:"|)ln(jA:'| + |A:"|) опробований. А трудоемкость метода "разделяй и побеждай" составляет |&'|/2 + |&"|/2 опробований. Это значительно меньше \к'\ -|&"|/2 метода тотального опробования. К тому же Нечаев В.И. установил, что среди детерминированных методов оценки стойкости алгоритмов, основанных на дискретном возведении в степень, метод согласования является лучшим.

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

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

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

В соответствии с поставленной целью в диссертации решаются следующие основные задачи:

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

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

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

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

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

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

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

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

Научную новизну диссертационной работы составляют:

1. Впервые разработанные параллельные алгоритмы "распределенных согласований", позволяющие на п- мерной системе решать важные задачи, сводящиеся к решению уравнения вида ^(к') = у(к"), где у/(к'),у(к")~ нелинейные функции, k'eFnx, k"eFn2, (к',к")-к, к е ^п» Рщ х Fn-> = Fn •

2. Параллельные алгоритмы "распределенных согласований" для анализа каскадных шифров. Полученные оценки эффективности распараллеливания алгоритмов (ускорение R = Tl/Tw, где Тх- время решения задачи на однопроцессорной системе, a Tw - время решения той же задачи на w- процессорной системе) "распределённых согласований" для анализа безопасности двойного DES показывают,

D W что R =-, где w—количество процессоров.

1 + 0,115 ■ w

3. Параллельные алгоритмы "распределенных согласований" для отыскания дискретного логарифма в конечных полях и в группе точек эллиптической кривой над конечным полем. Полученные теоретические оценки эффективности распараллеливания алгоритмов "распределённых согласований" для решения задачи дискретного логарифмирования в конечном поле показывают, что R, например, при w = 2 и t = 1700 будет составлять 1,83.

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

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

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

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

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

1. Алгоритмы "распределенных согласований", основанные на детерминированном методе согласования, которые позволяют на многопроцессорной системе решать важные задачи, сводящиеся к решению уравнения вида ч/(к') = у(к"), где у/(к'),у(к")- нелинейные функции, к' е Fm , k" е F„2, (к',к") = к, к eFn Fn{ х Fni = Fn.

2. Алгоритмы "распределённых согласований" для анализа безопасности каскадных шифров.

3. Алгоритмы "распределённых согласований" для решения задачи дискретного логарифмирования в конечных полях и на эллиптической кривой.

4. Теоретические оценки эффективности распараллеливания разработанных алгоритмов.

5. Экспериментальное подтверждение теоретических оценок. Апробация работы. Результаты работы докладывались и обсуждались на научно- практических конференциях: VI международной научно-практической конференции «Информационная безопасность» (Таганрог,

2004), VII всероссийской научной конференции молодых ученых и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004), II всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2004), VII всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004), I ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов, 2005), VII международной научно-практической конференции «Информационная безопасность» (Таганрог,

2005).

Результаты работы использованы в НИИ МВС ТРТУ при выполнении ОКР «Разработка базового инструментария для параллельно-конвейерной реализации вычислительно трудоемких фрагментов задач проблемной области в оперативно-приемлемое время при различных условиях применения»; в учебном процессе кафедры БИТ ТРТУ по курсу

Криптографические методы и средства обеспечения информационной безопасности", (что подтверждено соответствующими актами).

Публикации. По теме диссертации опубликовано 10 научных работ. Программа, полученная в ходе выполнения работы, зарегистрирована в Ы Реестре программ для ЭВМ (свидетельство об официальной регистрации программы для ЭВМ № 2005611241 от 27 мая 2005г.)

Структура и объем работы. Материал диссертационной работы изложен на 132 странице машинописного текста. Работа состоит из введения, пяти разделов, заключения и списка литературы из 54 наименований.

Заключение диссертация на тему "Оценка вычислительной стойкости защиты информации алгоритмами "распределенных согласований""

5.5. Выводы

1. Для среды Windows NT с использованием пакета MPI 1.3 созданы программы алгоритмов "распределённых согласований" (П-1 и П-2) для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном поле, которые позволяют экспериментально оценивать временные затраты этих алгоритмов при различных значениях параметров (w и f), а также ускорение относительно их последовательных аналогов. В качестве языка программирования использовался Visual Studio 2003.

2. Экспериментальное исследование разработанных алгоритмов с помощью созданных программ показало, что ускорение при наличии двух процессоров для алгоритма анализа безопасности двойного DES (Б-3.1.2) будет не менее 1,892; для алгоритма дискретного логарифмирования в конечном поле при />2770 будет более 1,768. Созданные программы подтверждают теоретические оценки ускорения.

126

ЗАКЛЮЧЕНИЕ

В результате анализа детерминированных методов согласования и "разделяй и побеждай" выявлена возможность и необходимость их распараллеливания. Благодаря чему впервые в данной работе на основе этих методов разработаны алгоритмы "распределенных согласований", позволяющие на п- мерной системе решать важные задачи, сводящиеся к решению нелинейного уравнения вида к') = у{к"), где у/{к'\у(к")~ нелинейные функции, к' efni, &"eF„2, (к',к") = к, keFn, F х Fni = Fn; произведена оценка эффективности их распараллеливания (ускорения R).

Разработаны алгоритмы "распределенных согласований" для анализа стойкости каскадных шифров; получены теоретические оценки эффективности их распараллеливания. Полученные оценки эффективности алгоритмов "распределённых согласований" для анализа безопасности двойного DES проиллюстрированы на конкретных значениях технических w параметров. И показано, что R =-, где w - количество

1 + 0,115- w процессоров, а модифицированного алгоритма (Б-3.1.2), оперирующего w фреймами, Rr » г**/ , с

1 + 0,01356-w

Разработаны алгоритмы "распределённых согласований" для анализа стойкости протоколов защиты цифровой информации основанных на дискретном логарифмировании в конечных полях и в группе точек эллиптической кривой над конечным полем; произведены оценки эффективности распараллеливания разработанных алгоритмов и анализ влияния параметров. Полученные теоретические оценки эффективности алгоритмов "распределённых согласований" для дискретного логарифмирования в конечном поле проиллюстрированы на конкретных значениях технических параметров и показывают, что R, например, при и> = 2 и f = 1700 будет составлять 1,83.

Созданы программы алгоритмов "распределённых согласований" для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном поле, которые позволяют экспериментально оценивать временные затраты этих алгоритмов при различных значениях параметров (w и /). В качестве инструментария программирования использован пакет WMPI 1.3 для среды Windows NT. В качестве языка программирования использовался Visual Studio 2003.

Экспериментальные оценки разработанных алгоритмов с помощью созданных программ показали, что ускорение при наличии двух процессоров модифицированного алгоритма "распределённых согласований" (Б-3.1.2) для анализа безопасности двойного DES будет «1,9, для дискретного логарифмирования в конечном поле при t = 1700 будет «1,65. Созданные программы подтверждают теоретические оценки ускорения.

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

128

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

1. Ростовцев А., Маховенко Е. Подпись и шифрование на эллиптической кривой: анализ безопасности и безопасная реализация// Проблемы информационной безопасности. Компьютерные системы. 2003. №1. С.73-83.

2. Ростовцев А., Маховенко Е. Реализация протоколов на эллиптических кривых// Проблемы информационной безопасности. Компьютерные системы. 1999. №4. С.62-67.

3. ГОСТ Р 34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

4. Ростовцев А., Маховенко Е. Введение в криптографию с открытым ключом. СПб.: Мир и семья, Интерлайн, 2001.

5. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.

6. Романцев Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. М.: Радио и связь, 1999.

7. Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов.: Курс лекций.: Йошкар-Ола, 2000.

8. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии./ Москва, МЦНМО, 2003. С. 12-14.

9. Бабенко Л.К., Курилкина A.M. Распараллеливание решения задачи дискретного логарифмирования на эллиптической кривой // Материалы

10. VII международной научно-практической конференции «Информационная безопасность».- Таганрог: ТРТУ, 2005- С. 195-199.

11. Нечаев В.И. Элементы криптографии (Основы теории защиты информации)./Под ред. В.А. Садовничего-М.:Высш.шк.,1999.

12. Maurer U. М. and Massey J.L. Cascade Ciphers: The Importance of Being First. Journal of Cryptology: v.6, n.l, 1993. Pp.55-61.

13. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си. М.:ТРИУМФ:2002. С.401-413.

14. G. В. Purdy, A high security log-in procedure, Comm. ACM 17 (1974), 442445.

15. W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trams. Inform.Theory, IT-22 (1976), 644-654.

16. P. K. S. Wah and M. Z. Wang, Realization and application of the Massey-Omura lock, pp. 175-182 in Proc. Intern. Zurich Seminar, March 6-8, 1984.

17. T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. On Inform. Theory, vol. IT-31, pp. 469-472, July 1985.

18. M. Blum and Micali, How to generate cryptographically strong sequences of pseudo random bits, SIAM J. Computing, 13(4): 850-863, November 1984.28