Введение к работе
Актуальность работы. Асимметричная криптография, выдвинутая Диффи и Хеллманом и независимо Мерклом, за очень короткий срок оказала большое влияние на развитие информационных технологий. Электронная коммерция, электронные платёжные системы, распространение ПО через глобальные сети были бы невозможны без активного использования алгоритмов симметричной и асимметричной криптографии. Криптография и криптоанализ вышли за стены закрытых институтов, и число публикаций по теме достаточно велико.
Стойкость всех алгоритмов асимметричной криптографии базируется на вычислительной сложности решения нескольких фундаментальных задач, таких как задача факторизации (разложения на множители), задача дискретного логарифмирования, задача укладки рюкзака и некоторых других. Объектом исследования в данной работе является задача дискретного логарифмирования, так как решение этой задачи лежит в основе криптоанализа таких алгоритмов шифрования и цифровой подписи, как Эль-Гамаль, ГОСТ Р 34.10-94 и ГОСТ Р 34.10-94. Для произвольной циклической группы G задача формулируется следующим образом: по известным a,beGнайти такой логарифм х, что а' =Ь.
Решение задачи дискретного логарифмирования требует больших вычислительных мощностей, и сложность этой задачи существенно увеличивается при росте размерности исходных данных. Последовательные вычисления с использованием одного процессорного ядра занимают слишком много времени. Например, для нахождения дискретного логарифма методом базы разложения по модулю простого числа длиной 130 бит необходимо 2776 MIPS-года, что составляет около 359 суток (почти год) работы одного ядра процессора Intel Xeon CPU Е5345 с частотой 2.33GHz. Действенным способом ускорения вычислений является использование распределённых многопроцессорных вычислений, с применением современных мощных систем, таких, например, как вычислительные кластеры.
Однако, решить задачу на распределённой вычислительной системе существенно сложнее, чем на обычной, так как необходимо разработать специальные алгоритмы и программы. К тому же, программа может оказаться неэффективной, если потери на обмен данными и синхронизацию в распределённой среде будут велики. Поэтому необходимо исследовать, насколько эффективно применение многопроцессорных вычислительных систем для ускорения решения задач, встающих при криптоанализе алгоритмов, основанных на задаче дискретного логарифмирования.
Имеющиеся в открытой печати статьи в основном описывают некоторые методы решения задач дискретного логарифмирования, такие как решето числового поля, встреча на случайном дереве и т.п. Алгоритмы, реализующие вычислительно сложные этапы этих методов, не приводятся.
Разработка параллельных алгоритмов позволит использовать распределённые вычислительные системы при анализе криптосистем, основанных на задаче дискретного логарифмирования. При этом полученные оценки (в частности, оценки стойкости) будут учитывать рост возможностей современной многопроцессорной вычислительной техники. Кроме того, можно будет выработать рекомендации по выбору параметров алгоритмов для наиболее эффективного использования доступных вычислительных мощностей.
Параллельные алгоритмы, реализующие трудоёмкие этапы методов дискретного логарифмирования, позволят применять современные многопроцессорные вычислительные системы для анализа криптосистем, основанных на этой задаче,
позволяя корректировать оценки стойкости с учётом развития вычислительной техники. В случае, если будут разработаны более эффективные модификации имеющихся методов, их также можно будет ускорить с использованием разработанных алгоритмов, поскольку последние составляют ядро этих методов и охватывают их вычислительно сложные участки.
Таким образом, можно заключить, что задача разработки эффективных параллельных алгоритмов, позволяющих реализовать известные методы дискретного логарифмирования, является актуальной.
Целью работы является разработка и исследование эффективности параллельных алгоритмов, реализующих известные методы дискретного логарифмирования, для применения их при анализе криптосистем.
В соответствии с целью определены следующие задачи исследования: -анализ существующих методов дискретного логарифмирования и их временных затрат, выявление вычислительно сложных участков;
-разработка параллельных алгоритмов, предназначенных для ускорения вычислительно сложных участков выбранных методов дискретного логарифмирования;
-разработка программ, реализующих параллельные алгоритмы дискретного логарифмирования;
-экспериментальные исследования влияния параметров реализаций алгоритмов (размера базиса для субэкспоненциальных методов, размера БД для экспоненциальных и других) и вычислительной системы (числа процессорных ядер, качества передающей среды) на время решения задачи, исследование эффективности распараллеливания, формирование методик по выбору параметров для повышения эффективности вычислений.
Объект исследования - задача дискретного логарифмирования в различных группах
Предмет исследования — параллельные алгоритмы для реализации вычислительно сложных этапов дискретного логарифмирования
Методы исследования
Для достижения поставленной цели и решения сформулированных в диссертационной работе задач использовались методы теории вероятностей, теории чисел, теории групп, теории конечных полей, алгебраической геометрии, а также современные методологии построения программных комплексов и систем. При разработке алгоритмов анализа учитывались особенности применения стандарта передачи сообщений MPI (Message Passing Interface).
Научная новизна работы
Научная новизна работы заключается в разработке и исследовании параллельных алгоритмов, позволяющих эффективно решать задачу дискретного логарифмирования на многопроцессорных вычислительных системах.
Основные научные результаты работы: 1. Разработаны параллельные алгоритмы просеивания и Гауссова исключения для реализации субэкспоненциальных методов ДЛ - базы разложения и решета числового поля, позволяющие получить на многопроцессорной системе значения эффективности 0.9-0.98 для просеивания и 0.5-0.7 для Гауссова исключения. (Эффективностью назовём меру того, насколько хорошо параллельная программа
использует многопроцессорную систему. Она определяется как е=—'—, где Е-
р*т„
эффективность, р-число процессорных ядер, Трвремя выполнения программы на
одном ядре, Тр-время выполнения программы на р ядрах. При Е=1 программа
максимально полно использует процессоры, при Е<1 - имеются потери)
Разработаны параллельные алгоритмы для реализации экспоненциальных методов ДЛ - встречи посередине и встречи на случайном дереве, позволяющие получить на многопроцессорной системе значения эффективности 0.93-0.97.
Проведены исследования влияния параметров реализаций (размера базиса для субэкспоненциальных методов, размера БД для экспоненциальных и других) и вычислительной системы (числа процессорных ядер, качества передающей среды) на время вычислений.
Разработан алгоритм нахождения решения из сравнений вида x = -st'l(modr), s
Модифицирован базовый метод решета числового поля для решения задачи ДЛ в общем случае - при любых образующей а и экспоненте b в выражении a" = b(modp),a< р,Ь< р.
Положения, выносимые на защиту
Разработанные параллельные алгоритмы для ускорения выполнения реализаций субэкспоненциальных и экспоненциальных методов позволяют эффективно решать задачу ДЛ на распределённых вычислительных системах, показывая эффективность 0.9-0.98 на этапе просеивания, 0.93-0.97 на этапе построения БД, и 0.5-0.7 на этапе Гауссова исключения, причём эффективность сохраняется при увеличении числа процессорных ядер..
Результаты экспериментов подтверждают эффективность разработанных алгоритмов и программ.
Модифицированный метод решета числового поля позволяет, в отличие от базового, находить решение при произвольной образующей а и экспоненте b в выражении a' = b(modp),a
Разработанный алгоритм решения сравнений вида xs~st (щойг)^ s
Достоверность полученных результатов подтверждается строгостью математических выкладок, проведёнными вычислительными экспериментами, апробацией основных положений работы на международных, всероссийских и региональных конференциях.
Практическая ценность полученных автором результатов
Разработанные автором параллельные алгоритмы могут применяться для решения
задачи дискретного логарифмирования на широком спектре распределённых
вычислительных машин, а также для обучения специалистов в области
информационной безопасности современным методам дискретного логарифмирования.
Апробация работы
Результаты работы представлялись на региональных, всероссийских и международных конференциях — «Информационная Безопасность-2008», CSIT-2008, РусКрипто-2009 и других. По результатам работы опубликовано 11 печатных работ, среди них 4 тезиса докладов и 7 статей. Две статьи опубликованы в журнале «Известия ТТИ ЮФУ. Технические науки», входящем в перечень изданий, рекомендуемых ВАК. Также получены 4 свидетельства о регистрации программ для ЭВМ.
Внедрение работы
Результаты работы использованы в учебном процессе кафедры БИТ ТТИ ЮФУ, а также при выполнении г/б работы № г.р. 01.2.077 04968 - «Разработка и исследование распределённых методов оценки вычислительной стойкости криптоалгоритмов, основанных на задаче разложения на множители и задаче дискретного логарифмирования» в Институте информатики и проблем регионального управления, г. Нальчик. Имеются соответствующие акты о внедрении.
Состав и структура диссертации
Диссертация состоит из введения, четырёх глав, заключения, списка источников, четырёх приложений. Основной текст диссертации изложен на 141 странице, включая 31 рисунок и 8 таблиц.
