Содержание к диссертации
Введение
1. Анализ задач дискретного логарифмирования и оценки безопасности каскадных шифров 13
1.1. Задача дискретного логарифмирования в конечных полях 13
1.1 1. Постановка задачи дискретного логарифмирования в конечных полях 13
1.1 .2. Особенности применения дискретного логарифмирования в конечных полях 15
1.2. Задача дискретного логарифмирования на эллиптической кривой 19
1.2.1. Постановка задачи дискретного логарифмирования на эллиптической кривой 19
1.2.2. Особенности применения дискретного логарифмирования на эллиптической кривой 21
1.3. Задача анализа безопасности каскадных шифров 25
1.3.1. Каскадные шифры 25
1.3.2. Анализ безопасности каскадных шифров 26
1.3.3. Оценка анализа безопасности каскадных шифров 41
1.4. Выводы 44
2. Разработка параллельных алгоритмов метода согласования и метода "разделяй и побеждай" 45
2.1. Методы согласования и "разделяй и побеждай", и их анализ 45
2.2. Оценка трудоемкости методов 51
2.3. Возможные принципы распараллеливания методов и алгоритмы "распределенных согласований" 52
2.4. Оценка эффективности разработанных алгоритмов 59
2,5 Выводы 63
3. Разработка и оценка эффективности параллельных алгоритмов анализа каскадных классических шифров 64
3.1. Анализ каскадных шифров алгоритмами "распределённых согласований" 64
3.2. Алгоритмы "распределённых согласований" анализа безопасности двойного DES 74
3.3. Оценка эффективности разработанных алгоритмов 78
3.4 Выводы 85
4. Разработка параллельных алгоритмов решения задачи дискретного логарифмирования методом согласования 87
4.1. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования в конечных полях 87
4.2. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования в конечных полях 91
4.3. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой 97
4.4. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой 99
4.5. Оценка эффективности разработанных алгоритмов 101
4.6. Выводы 113
5. Экспериментальное исследование характеристик разработанных алгоритмов 114
5.1. Среда реализации алгоритмов 114
5.2. Описание программы разработанного алгоритма "распределённых согласований" для анализа безопасности двойного DES 115
5.3. Описание программы разработанного алгоритма "распределённых согласований" для задачи дискретного логарифмирования в конечном поле 119
5.4. Экспериментальные оценки разработанных алгоритмов 121
5.5. Выводы 124
Заключение 126
Литература 128
- Постановка задачи дискретного логарифмирования в конечных полях
- Возможные принципы распараллеливания методов и алгоритмы "распределенных согласований"
- Алгоритмы "распределённых согласований" анализа безопасности двойного DES
- Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования в конечных полях
Введение к работе
Актуальность. Широкое применение информационных технологий и повсеместное использование лсктронных ередсів связи в автома і тированных системах обрабоїки информации м управления требует надежной зашшы данных и ресурсов от воіможности несанкционированного доступа, используя специальные средства Среди них одним из наиболее распространенных является преобразование дискретной информации с помощью специально созданных алгоритмов, которые постоянно разрабатываются и модернизируются Возможные пути модернизации заключаются в совершенствовании современных асимметричных алгоритмов (стойкость многих из них основана на задаче дискретною логарифмирования в конечном поле и в группе ючек эллиптической кривой над конечным полем), и усложнении классических алгоршмов созданием каскадных схем При рафаботке и совершенствовании алгоритмов защиты информации необходимо аналакировать их стойкость Стойкость алюритмов разделяют на теоретическую и практческую. Основными количественными мерами практической стойкости алгоритмов защиты дискретной информации служат іак называемые «трудоемкосіь меюіа анализа алюритма» (или вычислительная стойкость) - число операций или количество времени необходимых для получения ключа, и его «надежность» - вероятность дешифрования
Оценка вычислительной стойкости многих алгоритмов защиты информации сводится к решению уравнения вида
Ма,к) = Ь, (1)
где Ф(а,к)- нелинейная функция, секретный ключ keFu, а и b некоторые известные постоянные величины Не малая часть этих уравнений представляет собой уравнение вида
И*') = г(*"). (2)
где у/(к'),у{к")- нелинейные функции, (к',к") = к, k'eF , к"єГ,ь, F х Г„, = Fn В
частности, такие уравнения получаются при анализе стойкости каскадных схем и алгоритмов, основанных на дискретном возведении в степень.
Существуют разнообразные способы решения уравнения (2), однако лить деіерминированньїе методы гарантируют нахождение верного результата, то есть вероятность дешифрования ими равна I. Среди них своей универсальностью выделяются меюды тотальною опробования, согласования и "разделяй и побеждай"
Известными математиками, занимающимися исследованиями в области защиты информации, Грушо Л А , Ростовцевым А Г , Маховенко Е Б , В Диффи, Хеллман М. было показано, чю в среднем трудоемкость меюда согласования состоит из (|<:'| +|A"|J+(|'| + |"|)ln(J'| + |"|) опробований. А трудоемкость метода "разделяй и
побеждай" составляет +І"|/2 опробований Это значительно меньше
|А-')-|А:")/2 метода тотального опробования К тому же Нечаев ВИ установил, что
среди детерминированных меюдов оценки стойкости алюритмов, основанных на дискретном возведении в сіепень, метод согласования является лучшим Таким образом, наиболее перспективными методами ппи анализе стойкости каскадных схем и алгоритмов, основанных на дискретном возве; гіЦОСзЬетедець,! яедяц^ся меюды
"Я**
сої іасования и "разделяй и побеждай" Но они все же, как показано выше, требуют значительных вычислений, а значит и лмчнтельных затрат времени Попробовать сократить эти временные затраты можно при помощи распределенных вычислений, ерелеіва реализации которых постоянно совершенствуются.
Таким образом, исследования ставящие целью повышение производительное і и меююв соїласования и "разделяй и побеждай", являются актуальными и пре іставляют научный и практический иніерес.
Целью работы является повышение производительности мет слов сої іасования и "разделяй и побеждай" д ія опенки вычислительной стойкости зашиты декретной информации при помощи распре тсленных вычислений
В соответствии с поставленной не іью в диссертации решаются следующие основные задачи'
-
Анализ методов согласования и "раз іе іяй и побеждай", использующихся при опенке стойкости современных систем безопасности, основанных на каскадном шифровании или на дискретном возведении в степень.
-
Разработка параллельных алгоритмов па основе методов согласования и "разделяй н побеждай" для анализа оценки стойкости каскадных шифров и методов защиты цифровой информации, основанных на шскретном логарифмировании в конечных полях и в группе точек эллиптической кривой над конечным полем.
-
Получение теоретических оценок эффективности распараллеливания разработанных алгоритмов, характеризующих повышение производительности многопроцессорной системы по сравнению с однопроцессорной системой
-
Разработка программных реализаций предлагаемых параллельных алгоритмов для оценки стойкости двойного DF.S и заначи дискретного логарифмирования в конечных полях.
-
Проведение экспериментальных исследований для подтверждения полученных теоретических оценок эффективности распараллеливания разработанных алгоритмов
Методы исследования данной работы базируются на испочьзовании теории зашиты информации, элементов теории алгоритмов, элементов теории распределенных вычислений, теории конечных полей и эллиптических кривых
Достоверность и обоснованность полученных в диссертационной работе іеорстических результатов и формулируемых на их основе выводов обеспечивается математической корректностью произведенных выкладок, строгостью принятия допущений и введенных ограничений Справедливость выводов относительно сокращения временных затрат предложенными алгоритмами подтверждена результатами проведенных экспериментов
Методы согласования и "разделяй и побеждай" обладают схожей структурой с точки зрения их распараллеливания (способ использования памяти, вид межпроцессорных передач, распределение основной трудоемкости вычислений при независимом переборе двух частей ключа) Имеет смысл в дальнейшем рассмотрении параллельные алгоритмы на основе этих методов объединить одним названием -алгоритмы "распределенных согласований"
Научную новизну диссертационной работы составляют 1 Впервые разработанные параллельные алгоритмы "распределенных согласований", позволяющие на п- мерной системе вычислительной системе решать важные задачи, сводящиеся к решению уравнения вида у/{к') = у(к"). где
i/r(k'),y(k")~ кс шнейные функции, к'вр^, Г'еГ,, (к',к") = к, ktF„,
2. Параллельные алюрнтмы "распределенных согласовании" для анализа каскадных
шифров Полученные оценки эффективности распарлллеливания алгоритмов
(ускорение R = TS>/"„, где T.t — время решения задачи на однопроцессорной
системе, а 7"^ - ирсмя решения той же задачи на и - процессорной системе)
"распределённых согласований" для анализа беюиасности двойного DES
о w
показывают, что л= , где w— количество процессоров
1 + 0,115 w
3. Параллельные алюритмы "распределенных соїласований" для отыскания
дискретного логарифма в конечных полях и в ірупие точек эллиптической кривой
над конечным нолем Полученные теоретические оценки эффективности
распараллеливания алгоритмов "распределённых согласований" для решения
задачи дискретного логарифмирования в конечном ноле показывают, что R ,
например, при и -2 и t = 1700 будет составлять 1,83.
Практическую ценность работы представляют
1 Алгоритмы "распределенных согласований" для анализа каскадных шифров, которые могут быть реализованы на распределенных вычислительных системах
2. Алгоритмы "распределенных согласований" для решения задачи дискретного логарифмирования в конечных полях и в группе точек -эллиптической кривой над конечным полем, которые могут быть реализованы на распределенных вычислительных системах.
3 Оценки эффективности распараллеливания предлагаемых алюритмов "распределенных согласований", которые могут быть использованы при решении соответствующих задач на распределенных вычислительных системах Основные положения, выносимые на защиту:
1. Алгоритмы "распределенных согласований", основанные на детерминированном
методе согласования, которые позволяют на многопроцессорной системе решать
важные задачи, сводящиеся к решению уравнения вида t//(k') = у(к"), где
у/(к'),-/(к")~ нелинейные функции, k'eF^, k"eFIK, (к',к") = к, к с Fa
F xF =F
И, 1>2 П
-
Алгоритмы "распределенных согласований" для анализа безопасности каскадных шифров
-
Алгоритмы "распределённых согласований" для решения задачи дискретного логарифмирования в конечных полях и на эллиптической кривой
-
Теоретические оценки эффективности распараллеливания разработанных алгоритмов
-
Экспериментальное подтверждение теоретических оценок
Апробация работы. Результаты работы докладывались и обсуждались на научно- практических конференциях: VI международной научно-практической конференции «Информационная безопасность» (Таганрог, 2004), VII всероссийской научной конференции молодых ученых и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004), II всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2004), VII всероссийской
научной конференции с международным участием «Новые информационные технолоіии Разрабоїка и аспекты применения» (Таганрог, 2004), I ежегодной научной конференции студенти и аспирантов базовых кафедр Южною научного центра РАН (Ростов. 2005) \ II международной научно-практ пческой конференции «Информационная бсіопасность» (Таганрог, 2005)
Результаты рабо іы использованы в НИИ МВС ТРТУ при выполнении ОКР «Разработка базовою инструментария для параллельно-конвейерной реализации вычислительно ipvuKMKHX фрагментов задач проблемной области в оперативно-приемлемое время при различных условиях применения» в учебном процессе кафедры БИТ TPTY но курсу "Криптографические методы и средства обеспечения информационной безопасности", (что подтверждено соответеївующими актами)
Публикации. По іеме диссертации опубликовано 10 научных работ Программа, полученная в ходе выполнения работы, зареї истрирована в Реестре программ для ЭВМ (сии дстельство об официальной регисірации программы для ЭВМ № 2005611241 от 27 \ия 2005г.)
Структура и объем работы. Материал диссертационной работы изложен на 132 сграницах машинописного текста Работа состоит из введения, пяти разделов, заключения и списка ппературы из 54 наименований
Постановка задачи дискретного логарифмирования в конечных полях
Задача дискретного логарифмирования в конечной группе имеет важные приложения в криптографии. Безопасность ряда криптографических систем и в частности системы, используемые для аутентификации (цифровая подпись) и обмена открытыми ключами напрямую зависят от прогресса в поиске эффективных методов нахождения дискретных логарифмов в конечных полях. Рассмотрим такие системы. Одной из первой опубликованной криптосистемой, стойкость которой зависела от сложности задачи вычисления дискретных логарифмов, явилась схема (протокол) для аутентификации. В большинстве компьютерных систем пароли доступа хранятся в специальном файле, к которому может быть, кем-либо получен доступ и тем самым исполнена роль законного пользователя. В связи с этим этот файл обычно специальным образом защищается средствами операционной системы.
Известно [23], что для исключения этого недостатка достаточно устранить непосредственно само хранение паролей. Для этого используется специальная функция /", которую трудно инвертировать, т.е. такая, что для данного значения у из её области значений нахождение значения х, для которого у = f(x), вычислительно не осуществимо. Затем создаётся файл, содержащий пары {i,f(Pj)), где і- означает имя пользователя (login name), а pt - пароль данного пользователя. Этот файл может быть сделан доступным всем. Безопасность этой схемы целиком зависит от сложности инвертирования функции /.Одним из первых кандидатов на роль такой функции было дискретное возведение в степень. Конечное поле GF(q) и его примитивный элемент g є GF(q) выбирается и делается публичным, а для целого х определяется как f(x) = gx.
Любой желающий получить доступ к системе, представляясь пользователем і, должен найти значение pif зная только значение gPi, т.е. решить дискретный логарифм в конечном поле GF(q).
Диффи и Хеллман в 1976 году [24] предложили систему для безопасного обмена ключами по открытым каналам, базирующуюся на дискретном возведении в степень в конечных полях. В ней выбираются конечное поле GF{p), примитивный элемент g є GF(p) и делаются открытыми. Пользователи А и В, использующие какую либо симметричную криптосистему и не имеющие общего ключа для неё, могут его получить следующим образом. Они выбирают случайным образом целые числа а и Ь, соответственно, такие, что 2 а,Ь р — 2. Дальше А передаёт значение ga пользователю В по открытому каналу, а пользователь В передаёт своё значение g пользователю А. После этого оба они готовы для вычисления общего ключа, значение ga , которого пользователь А получает путём возведения в степень а значения g , а пользователь В- путём возведения в степень Ъ значения ga. Все эти вычисления выполняются в арифметике конечного поля GF(p). Диффи и Хеллман также в [24] выдвинули предположение, что криптоанализ их схемы эквивалентен по сложности вычислению дискретных логарифмов. Это предположение остаётся не доказанным, так что нельзя исключать возможность существования некоторого способа создания gab из ga и gb без вычисления значений а либо Ь. Однако маловероятно, что такой способ существует.
Поскольку (к,р-1) = \, то существует единственное решение сравнения (1.4) по модулю р - I. И это решение пользователю А легко найти, так как он знает а, г и к. Вычисление дискретного логарифма позволяет вычислить секретное число а из открытого значения у. Не найдено никаких других путей для успешного криптоанализа системы ЭльГамаля, кроме как решение задачи по нахождению дискретных логарифмов в конечных полях. Месси и Омура предложили криптографическую систему базирующася на идее Шамира с дискретным возведением в степень [25].
Возможные принципы распараллеливания методов и алгоритмы "распределенных согласований"
В алгоритмах (А-2.1), (Б-2.1) и (С-2.1) методов согласования и "разделяй и побеждай" основной объем работы приходится на вычисление значений функций (и проверку критерия). Причем, эти вычисления для каждого возможного значения неизвестной переменной к (и к") осуществляются не зависимо друг от друга. Следовательно, одновременное выполнение вычислений значений функций (или проверки критерия) для различных значений неизвестных переменных не нарушит целостности алгоритмов. Методы согласования и "разделяй и побеждай", как показано в п.2.2, требуют значительных вычислительных и временных затрат, хоть и намного меньше полного перебора. Для сокращения временных затрат этих методов предлагается организовать параллельное выполнение вычислений значений функций (и проверки критерия) для различных значений перебираемых переменных. Методы согласования и "разделяй и побеждай" обладают схожей структурой с точки зрения их распараллеливания (способ использования памяти, вид межпроцессорных передач, распределение основной трудоемкости вычислений при независимом переборе двух частей ключа). Имеет смысл в дальнейшем рассмотрении параллельные алгоритмы на основе этих методов объединить одним названием — алгоритмы "распределенных согласований".
Распределим перебор значений неизвестных переменных по всем имеющимся процессорам w так, чтобы каждый процессор независимо осуществлял перебор значений своего диапазона.
Пусть min - нижняя, max - верхняя граница значений диапазона перебираемой переменной, myid - собственный номер процессора, w -количество процессоров приложения, п! - нижняя, п2 - верхняя границы диапазона перебираемой переменной для данного процессора. В данной реализации все процессоры должны обменяться полученными значениями S. Чтобы на втором этапе алгоритма все значения S были доступны всем процессорам.
Можно так же все полученные значениями S внести в общую память. Но тогда может возникнуть ситуация, когда к одной и той же ячейке памяти обратятся одновременно несколько процессоров, поэтому нужно для этого случая организовать строгий порядок очереди в соответствии с нумерацией процессоров.
"Быстрая сортировка" — самый известный пример алгоритма, использующего рекурсию, то есть вызывающего самого себя, и самая быстрая из сортировок «на месте», то есть сортировка, использующая только ту память, в которой хранятся элементы сортируемого массива. В нем мы выбираем некоторый барьер - элемент из "текущего" массива и идем к нему слева и справа от концов этого массива. Как только слева попадается элемент, больший барьера, ищем справа элемент, меньший барьера и меняем их местами. Когда встречаемся (идя слева и идя справа), прекращаем и получаем два массива, каждый элемент из первого меньше любого элемента из второго и далее таким же способом сортируем их. Когда остается по одному элементу, получаем полностью отсортированный массив [54]. Доказано, что данную сортировку нельзя выполнить быстрее, чем за n-log2« операций [41], ни в худшем, ни в среднем случаях, и быстрая сортировка достаточно хорошо приближается к этому пределу в среднем случае (2 «-log2n)- Сортировки, достигающие теоретического предела, тоже существуют— это сортировки турнирным выбором и сортировки вставлением в сбалансированные деревья, но для их работы требуется резервирование дополнительной памяти. Так как эффективность самого метода согласования основана на использовании памяти, поэтому целесообразно для сортировки в алгоритме "распределенных согласований" использовать метод quicksort. Так как значения к упорядочены, то их сравнение проводится не всех подряд, а бинарным поиском. По нему поиск всегда начинаем с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Таким образом, в результате каждой проверки мы вдвое сужается область поиска. Двоичный поиск - очень мощный легко реализуемый метод, требующий не более log2 п сравнений [41]. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второго - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений. Кроме поиска бывает нужно вставлять и удалять элементы.
Можно так же все отобранные по критерию значения к внести в общую память. Но тогда может возникнуть ситуация, когда к одной и той же ячейке памяти обратятся одновременно несколько процессоров, поэтому нужно для этого случая организовать строгий порядок очереди в соответствии с нумерацией процессоров. К тому же это приведет к существенным потерям времени. При реализации разработанных алгоритмов "распределённых согласований" может возникнуть ситуация, когда требуемый объем памяти процессора превышает реально существующий. В этом случае для алгоритмов (Б-2.3) и (С-2.3) затруднения можно преодолеть, если модифицировать нужный алгоритм следующим образом: возможные значения неизвестных переменных (ключей) одного процессора перебирать не во всем заданном диапазоне, а разбить его на части. После перебора каждой части будут получаться таблицы с некоторыми значениями- фреймы. Выбирая каждый раз различные части диапазона изменения ключей, выполнять нужный алгоритм "распределённых согласований" (с меньшим количеством переборов за раз). После расчетов очередного фрейма производить синхронизацию всех процессоров. После чего рассылать всем процессорам другие очередные полученные значения S и производить бинарный поиск. После бинарного поиска равных элементов таблиц посылать главному процессору информация о том, найдены ли совпадения. Если совпадения найдены, то главный процессор отправляет всем процессам информацию об остановке работы, если нет, то процедура продолжается. После завершения работы по поиску ключей главный процесс выводит результаты вычислений.
Такая модификация естественно замедлит алгоритм, поэтому ее целесообразно осуществлять только в том случае, когда вновь полученная трудоемкость полученного алгоритма не превышает трудоемкости метода тотального опробования.
Алгоритмы "распределённых согласований" анализа безопасности двойного DES
Затраты на определение ключа двойного DES алгоритмом (А-1.1.2) метода согласования предлагается сократить с помощью следующего алгоритма "распределённых согласований", обозначим его (А-3.1.2). Если известен критерий g, позволяющий при известных X = (xi,...,xn) и У = {у\,—іуп) проверять правильность ключа к1} тогда для определение ключа к = {кх,к2) можно использовать метод "разделяй и побеждай". Чтобы сократить его временные затраты предлагается использовать следующий параллельный алгоритм, обозначим его (С-3.1.2). Вход: Х(х1,х2,Хт ,...,хп),У(уьу2,Уз,...,уп) (открытый и шифрованный тексты). 1. Распределяем перебор значений ключа к\ по всем процессорам. Перебирая значения ключа, проверяем условие: если g(X,Y k\) = 1, тогда к у к±, гдеу - номер процессора, и t(j) = t(j) +1. 2. Распределяем перебор значений ключа к2 по всем процессорам. Перебирая значения ключа для V/ = l,t(j) проверяем условие: если E2{El[X,kljlk2)=Y,?o k = (k{j,k2). ./ = / + 1. Выход: к. 3.3. Оценка эффективности разработанных алгоритмов Исследуем эффективность алгоритма "распределенных согласований" (А-3.1.1) для определения ключа каскадного шифра. Как показано в главе 1 трудоемкость последовательного алгоритма (А-1.1.1) составляет Т = п \С\ ... Сг k \ + cr+i --.- -")+& +(" операций. Все они выполняются параллельно в алгоритме (А-3.1.1). То есть алгоритм обладает идеальным параллелизмом. Для обмена всех процессоров, полученными значениями , необходимо произвести w передач данных длиной л-)/ , А для сбора результатов поиска ключа к нужно произвести w-І передач данных с длинами п /(у), где ] номер процессора, то есть количество передаваемых данных будет п i(j) Значит, общее количество 7=1 h IV-1 передаваемых данных в алгоритме составит tt-fy-w+ л- С/ )- М— j=\ w Если tc— время одной передачи данных по сети, a fy — время выполнения одной операции, то коэффициент пЩ+n-YsKJ) с (й-(ft -...Cr-\k \ + Cr+r...-Ch-\k"\)+\k \ + \k"\)0 Тогда по формуле (2.5) сетевого закона Амдала можно вычислить сетевое ускорение для разработанного алгоритма (А-3.1.1).
Сравнение графиков, изображенных на рисунках 3.13, 3.14, (или таблиц 3.1 и 3.2) и предельных значений позволяет сделать вывод о том, что алгоритмы (А-3.1.2) и (Б-3.1.2) обладают очень близкими по значениям ускорениями. То есть оба алгоритма примерно одинаково могут сократить временные затраты при их использовании. Перед практической реализацией, необходимо проанализировать возможное количество процессоров и их объем памяти для имеющихся вычислительных средств, то есть для одного процесса рассчитать объем памяти необходимый для анализа заданного шифра. Затем сравнить полученные данные с объемом памяти, который требуется для реализации предлагаемых алгоритмов, и выбрать из них оптимальный вариант.
Теперь для конкретного примера оценим ускорение модифицированного алгоритма (Б-3.1.2) для определения ключа двойного DES, оперирующего фреймами. Пусть максимальное количество возможных значений ] в фрейме составляет ІбМключей, то есть 1Х =16-1024-1024; а максимальное количество возможных значений к2 в фрейме составляет ІМключей, то есть /2 =1024-1024, а « = 64 + 56 = 120. И пусть в каждом ключе известно по 32 бита, то есть необходимо подобрать по 24 бита. Тогда коэффициент 120-224. c (l20-1000-(16-10242+10242) + (2-16-10242+ 10242) Лоё2(16-10242)) 120-f 120-139-2"18 1 U c - «0,01356 . 224 10242 (l000-120-17 + 33-24 0 (1000-120-17 + 792)-2,3-10-А сетевое ускорение модифицированного алгоритма (Б-ЗЛ.2) будет Rc и- . И если, например, алгоритм будет выполняться на двух - + 0,01356 W процессорах (-vv = 2), то ускорение составит Rc «1,947. Ускорение в данном случае получается выше за счет того, что в трудоемкости последовательного алгоритма учитывается необходимая (так как для последовательного алгоритма требуется памяти примерно в w/2 раз больше) модернизация при помощи фреймов. Все рассмотренные возможности параллельного решения задачи анализа стойкости каскадных шифров значительно сокращают временные затраты.
Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования в конечных полях
Если имеется два процессора и г велико, то выполнять шаги 3 и 4 в алгоритме (Б-4Л.1) можно одновременно. Сортировку значений z{x), где х є [0;r), естественно проводить наиболее эффективным способом quicksort [41], обозначим ее блоком і ш Xj l. Так как значения z(x), где хє[0;г), теперь уже упорядочены, то их сравнение целесообразно проводить не всех подряд, а, например, бинарным поиском, который дает высокие показатели [41], обозначим его блоком I -z0v ztx/ I, Тогда блок схема такого алгоритма, обозначим его (Б-4.2.1) будет выглядеть так, как показано на рисунке 4.2. начало Блок-схема алгоритма (Б-4.2.1). Так как трудоёмкость шагов 3 и 4 значительно больше других шагов алгоритма, очевидно, что время выполнения полученного алгоритма (Б-4.2.1) будет не менее чем в 1,5 раза меньше.
Если имеется не 2, a w процессоров, то выполнение алгоритма метода согласования можно еще значительно ускорить. Так как каждое умножение производится по mod(/), то фактически каждый раз приходится выполнять не одну арифметическую операцию, а несколько (умножение, деление на /, выделение целой части, умножение на t, вычитание). Предлагается распределить перебор всех значений х по w процессорам и перебор всех значений у тоже по w процессорам так, чтобы каждый процессор независимо осуществлял перебор значений своего диапазона, причем не равномерно, а согласованно со временем вычисления z(i,Q), і є [1, w], и z (j,0), j є [1, и ].
Пусть т - собственный номер процессора, п} — нижняя, л2 - верхняя границы диапазона х, где хє[0;г), для каждого процессора. Тогда можно предположить следующий способ распределения работы по составлению первой таблицы значений z(x), ;сє[0,г — 1] по w процессорам: , \rn-l / = 3Y т-\ 4, n2=nl + hm. А; В последнем процессе W f 1 \ l W f -5 w ґ?\і—1 IV—1 IV IV / -3 - = r. 4. i=\ /=1 i=\\ W-1 \ Ел, ,/" -М / Тогда 1-й процесс осуществляет перебор значений в промежутке [0;Л(), 2-й процессор - [h\ ,k[ + 2), ..., w-й процессор Перебор возможных значений осуществляется аналогичным образом. Тогда /-й процессор будет выполнять алгоритм изображенный на рисунке 4.3. I і-1ґі\к х -at h і n2 := я,+ / I У x = nl, n2 —1 j V z(i,x):=z(itx — l)-c I z(i, x) ;= z(z, x) - \z(i, x) I q\ q і D Рисунок 4,3 - Блок-схема алгоритма работы /-го процессора при переборе значений ряда (4.4) в алгоритме (Б-4.2.2). Z ( / , X ) , где /e[l;w]. При Обозначим этот алгоритм блоком вычислении значений у /-й процессор, где /G[1,IV], будет выполнять алгоритм изображенный на рисунке 4.4. z\i,0):=hbni I tft гт т-е&шя у = ПиП2-\ I z\i,y) z%y-X)-b I 2 (і,у) 2(і,у) У(і,у)/д]д f Рисунок 4.4 - Блок-схема алгоритма работы /-го процессора при переборе значений ряда (4.3) в алгоритме (Б-4.2.2). +) , где ie[l,w]. z%(i y) Обозначим этот алгоритм блоком Передачу значений z\i,y), где ЇЄ[1,УІ ], ОТ /-ГО процессора ко всем остальным процессорам будем обозначать соответствующими стрелками между процессорами. Тогда параллельное выполнение метода согласования для вычисления дискретного логарифма можно организовать по алгоритму, показанному на рисунке 4.5, который назовем алгоритмом "распределенных согласований" и обозначим (Б-4.2.2). / b,a,t,q.w I r:=[tV3]ft Z3I c b r T 4f] z(1,x) X 7U(C/r sort zff,xj T T z(2,xj quick sort Z(w,x) з: owcA sort 7fvv,x) z d.y) z (2,y) zTw.yJ БЛ БП услешен !ІЄТ нет БП z (1,y)=z(1.x) БП z (2,y)=z(1,x) БП Z (1.y)=z(2,x) БП z (2.y)=z(2,x) БП z (2,y)=z(w,x) нет ЄЛ z (w,y)=z(1,x) 5П успешен) г бП успешен нет БП z (w,y)=z(2.x) нет —1 БП z fiv,w=2Cw,x; П успешен; нет т / Иу 1:=1 и ет решен I Рисунок 4.5 - Блок-схема алгоритма "распределенных согласований (Б-4.2.2) вычисления дискретного логарифма. Если в алгоритме (D-4,1.1) для нахождения значений т{ и 1Х использовать алгоритм "распределенных согласований" (Б-4.2.2), то параллельный алгоритм вычисления дискретного логарифма для случая і = Л г2 обозначим его (D-4.2.1), будет выглядеть следующим образом. Вход: b, a, rltr2,q.
Если вычислить все элементы ряда (4.11), то потом, вычисляя элементы ряда (4.10) и сравнивая их с полученными значениями ряда (4.11) можно найти число /. Если имеется w процессоров, то выполнение алгоритма метода согласования для поиска дискретных логарифмов в группе точек эллиптической кривой над конечным полем можно ускорить. Предлагается распределить перебор всех значений х по w процессорам и перебор всех значений у тоже по w процессорам так, чтобы каждый процессор независимо осуществлял перебор значений своего диапазона, например, как в алгоритме (А-3.1.1).
Пусть, например, алгоритм (Б-4.2.2) реализуется в сети с пропускной Q /Г способностью 100 Мбит/с, тогда среднее значение tc =1,39-2 «6,95-10 мс. И пусть вычисления производятся на ЭВМ с процессорами AMD Semptron, тогда t0 = 0,16 мс при длине чисел 1024-2300 бит. Тогда ускорение параллельного алгоритма (Б-4.2.2) при некоторых значения t и w будет выглядеть, как отображено на диаграмме рисунка 4.7. Из этой диаграммы, очевидно, что с ростом значений t и w ускорение увеличивается. Выясним характер увеличения ускорения, то есть равномерно происходит его увеличение или нет.
По графику зависимости ускорения от значения порядка основания логарифма (рисунок 4.8) хорошо видно, что с ростом значений / ускорение постоянно увеличивается, но с каждым разом всё меньше и меньше. Благодаря чему значение ускорения никогда не превысит количество процессоров w (в данном случае 2).
