Содержание к диссертации
Введение
Глава 1. Постановка задачи исследования . 21
1.1. Вычислительные задачи информационной безопасности: краткий обзор 21
1.2. Стойкость систем защиты и способы ее оценки 24
1.3. Задачи факторизации целых чисел и дискретного логарифмирования в конечном поле 27
Выводы 29
Глава 2. Параллельные вычисления в архитектуре CUDA . 31
2.1. Обзор параллельных вычислительных систем 31
2.2. Обзор технологий GPGPU 38
2.3. Архитектура CUDA 42
2.4. Обзор методов и способов организации параллельных вычислений 46
Выводы 50
Глава 3. Алгоритмы решения задач факторизации и дискретного логарифмирования . 52
3.1. Основные методы и алгоритмы факторизации целых чисел. Метод Ш. Лемана 52
3.2. Параллельный алгоритм Ш. Лемана, адаптированный к вычислениям на GPGPU с архитектурой CUDA.
Асимптотические оценки сложности 55
3.3. Основные методы и алгоритмы дискретного логарифмирования. -метод Полларда 63
3.4. Параллельный алгоритм -метода Полларда, адаптированный к вычислениям на GPGPU с архитектурой CUDA 68
Выводы 75
Глава 4. Компьютерное моделирование метода Лемана и -метода Полларда 76
4.1. Экспериментальная апробация параллельного алгоритма Ш. Лемана 76
4.2. Экспериментальная апробация параллельного алгоритма -метода Полларда 79
4.3. Оценки эффективности использования параллельных вычислений в архитектуре CUDA 84
4.4. Реализация арифметических операций с «длинными» числами на устройствах GPGPU с архитектурой CUDA 94
Выводы 98
Заключение . 101
Список сокращений . 105
Список литературы 106
- Стойкость систем защиты и способы ее оценки
- Обзор методов и способов организации параллельных вычислений
- Параллельный алгоритм -метода Полларда, адаптированный к вычислениям на GPGPU с архитектурой CUDA
- Реализация арифметических операций с «длинными» числами на устройствах GPGPU с архитектурой CUDA
Стойкость систем защиты и способы ее оценки
Согласно доктрине информационной безопасности Российской Федерации [39], информационная безопасность (ИБ) является неотъемлемой частью на-циональной безопасности государства. Информатизация российского общества, идущая все большими темпами [81], с каждым годом увеличивает значение ин-формационной безопасности в вопросе обеспечения общей безопасности госу-дарства.
Под информационной безопасностью понимается защищенность инфор-мации и поддерживающей инфраструктуры от случайных или преднамеренных воздействий естественного или искусственного характера, чреватых нанесени-ем ущерба владельцам или пользователям информации и поддерживающей ин-фраструктуры. Сущность информационной безопасности основывается на трех базовых принципах [36]: целостность данных; конфиденциальность информации; доступность информации для всех авторизованных пользователей.
Под целостностью данных подразумевается достоверность и полнота ин-формации и методов ее обработки, т. е. защита от сбоев, ведущих к потере ин-формации, а также защита от неавторизованного создания или уничтожения данных. Конфиденциальность трактуется как возможность доступа к информа-ции только авторизованных пользователей. Доступность – есть обеспечение свободного доступа к информации и связанными с ней активами авторизован-ных пользователей по мере необходимости.
Защита информации (ЗИ) – деятельность, направленная на предотвраще-ние утечки защищаемой информации, несанкционированных и непреднамерен-ных воздействий на защищаемую информацию. К основным видам ЗИ относят-ся: правовая, физическая, техническая и криптографическая [3, 37]. С помощью реализации совокупности мер по ЗИ обеспечивается информационная безопас-ность.
ИБ является одним из важнейших аспектов интегральной безопасности, на каком бы уровне не рассматривалась последняя — национальном, отрасле-вом, корпоративном или персональном. При анализе проблематики, связанной с информационной безопасностью, необходимо учитывать ее специфику, со-стоящую в том, что ИБ есть составная часть предметной области информаци-онно-коммуникационных технологий, динамика развития которой характеризу-ется беспрецедентно высокими темпами роста. До недавнего времени рост ос-новных показателей вычислительной техники характеризовался законом Мура [50], т. е. декларируемый уровень мощности вычислительных устройств увели-чивался в два раза за каждые два года. В настоящий момент многие эксперты в области вычислительных технологий считают, что развитие отрасли идет опе-режающими закон Мура темпами, т. е. увеличение происходит быстрее, чем за два года, а именно за полтора. Однако уже сейчас (в ближайшем будущем) можно считать, что персональные ЭВМ на базе архитектуры фон Неймана практически достигли предела вычислительной мощности, который не может быть преодолен из-за физических ограничений используемой технологии про-изводства центральных процессоров. Согласно закону Мура, размеры элемен-тов микросхемы к 2060 году (самый поздний срок прогноза) должны будут стать размерами с одиночный атом. С другой стороны, все более широкое рас-пространение средств вычислительной техники и коммуникации в рамках об-щедоступных вычислительных сетей оказывают в современных условиях суще-ственное влияние на общий порог совокупной вычислительной мощности госу-дарства и социума. По данным Internet World Stats число пользователей сети Интернет в 2011 году превысило , что дает общее представление о реаль-ном количестве потенциально доступных вычислительных устройств массового пользования [113].
Наряду с основными угрозами информационной безопасности, сущест-венный рост вычислительных мощностей сверх определенного уровня также представляет угрозу информации, обрабатываемой и хранимой средствами вы-числительной техники, в частности, в отношении снижения уровня защищен-ности ряда асимметричных систем защиты, практическая стойкость которых базируется на сложности решения некоторых фундаментальных трудноразре-шимых вычислительных задач (здесь и далее под трудноразрешимыми или вы-числительно сложными задачами подразумеваются задачи, для которых не из-вестны алгоритмы их решения полиномиальной сложности на модели детерми-нированной машины Тьюринга).
Основой определения угроз для конкретной информационной системы является выявление потенциальных нарушителей, прогнозирование их возмож-ностей, намерений и тактики действий.
К числу наиболее распространенных средств защиты информации в IT-сфере относятся система RSA, открытая система PGP, DarkCryptTC, схема вы-работки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля и другие [13, 88, 91, 93]. Практическая (вычислительная) стойкость указанных систем базируется на одной из следующих задач класса NP [79]: факторизации целых чисел (RSA), дискретного логарифмирования в конечном поле (схема выработки ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптографи-ческая система Мэсси-Омуры), дискретного логарифмирования в группе точек эллиптической кривой (протокол обмена ключей Диффи-Хеллмана, цифровая подпись Эль-Гамаля, криптосистема Мэсси-Омуры с реализацией вычислений в группе точек эллиптической кривой), задачи «об укладке ранца» и ее модификации.
Для рассматриваемых систем защиты одной из важнейших характеристик модели нарушителя является уровень технической подготовленности (осна-щенности). Определение вычислительных возможностей потенциального на-рушителя позволяет оценить степень его способности практической реализации угроз.
В диссертации исследованы задачи факторизации целых чисел и дискрет-ного логарифмирования в конечном поле в отношении возможности снижения фактических временных затрат на их решение при использовании параллель-ных вычислений на графических процессорах nVidia с технологией GPGPU и архитектурой CUDA.
Обзор методов и способов организации параллельных вычислений
Стойкость большинства систем защиты информации, разработанных в последние годы, как правило, оценивается на основании теории вычислитель-ной сложности, а не на классической теории информации. Основное отличие такой оценки заключается в том, что если в соответствии с теорией информа-ции система является стойкой при отсутствии у противника возможности полу-чения необходимого количества информации для восстановления зашифрован-ного сообщения, то в соответствии с теорией вычислительной сложности, даже при наличии всей необходимой информации, противник не может восстановить сообщение в заданный срок из-за большого объема вычислений.
Другой практический подход, связанный с вычислительной защищенно-стью, состоит в том, чтобы свести вскрытие системы к решению хорошо изу-ченных (как правило, математических) задач. В этом случае системы называют доказуемо стойкими.
Решение задачи вскрытия криптосистемы RSA сводится, в частности, к разложению на простые множители числа n, , .
Теорема 1.2.1. ([63]) Задача факторизации числа n=pq ( , p, q – про-стые) и задача вычисления функции Эйлера полиномиально эквивалентны Значение функции Эйлера , где , есть количество натуральных чисел, меньших n и взаимно простых с n [2]. Теорема 1.2.2. ([63]) Задача вычисления секретного показателя , где , сводится с полиномиальной сложно-стью к задаче вычисления функции . Факторизация самого числа n сразу дает возможность вычисления функ-ции .
На сегодняшний день не известны методы разложения числа на простые множители полиномиальной сложности. До начала 90-х годов XX века самым быстрым из общих методов считался метод квадратичного решета. Его операционная сложность составляет , где c – некоторая константа, за-висящая от типа поля, например, от его характеристик и . Наиболее приемлемым методом на сегодняшний день является метод квадратичного решета в числовом поле, сложность которо-го равна , где с – некоторая константа, не зависящая от разлагаемого числа n.
Вскрытие протокола генерации общего ключа Диффи-Хеллмана, схемы электронной подписи Эль-Гамаля и криптосистемы Мэсси-Омуры сводятся к одной из следующих задач [55, 79]: проблеме дискретного логарифмирования (F – конечное поле): для дан-ных найти x такой, что ; задаче Диффи-Хелмана: для , и найти ; проблеме выбора Диффи-Хелмана: для , , и тре-буется определить, является ли z произведением . Данные задачи являются эквивалентными по сложности решения. Теорема 1.2.3. ([79]) В любой конечной абелевой группе G задача Диф-фи-Хелмана не сложнее проблемы дискретного логарифмирования. Теорема 1.2.4. ([79]) Проблема выбора Диффи-Хелмана в любой конеч-ной группе G не сложнее задачи Диффи-Хелмана. Вообще говоря, проблема выбора Диффи-Хелмана самая легкая из трех описанных проблем, далее по сложности следует задача Диффи-Хелмана и за-дача вычисления дискретного логарифма.
Стоит отметить, что сложность решения задачи дискретного логарифми-рования сильно зависит от типа алгебраической структуры. Например, для группы целых чисел относительно сложения по модулю целого числа n эта за-дача тривиальна. Наибольшую сложность задача дискретного логарифмирова-ния имеет в группе точек эллиптической кривой [15].
Наряду с разработкой новых эффективных методов и алгоритмов, общим магистральным направлением снижения практических временных затрат на решение указанных классов задач остается выбор эффективной модели вычис-лений на существующих классах архитектур вычислительных систем, что тре-бует соответствующей адаптации синтезируемых методов и алгоритмов к вы-бранной модели вычислений [9]. В рамках классической модели вычислений А. Тьюринга - Дж. Неймана основным направлением снижения временных затрат является распределение требуемого объема информационно-вычислительной работы по совокупности параллельно работающих вычислителей.
Типичной задачей такого рода, помимо исследованных в работе, являют-ся задачи тотального перебора. В первую очередь рост производительности вы-числительных систем нарушителя порождает угрозы ИБ для парольных систем защиты. Их стойкость обусловлена невозможностью эффективной реализации метода грубой силы и недостаточностью вычислительных средств у потенци-ального нарушителя. Использование параллельных вычислений на базе графи-ческих процессоров nVidia может существенно повысить эффективность атак методом полного перебора [57]. В настоящее время использование ресурсов GPU с архитектурой CUDA для взлома паролей методом перебора делает уяз-вимым практически любой пароль, состоящий из менее 12 символов.
Параллельный алгоритм -метода Полларда, адаптированный к вычислениям на GPGPU с архитектурой CUDA
Оценка третьего шага (Step3), состоящего из операции извлечения квадратного корня, составит O(t2).
Четвертый шаг (Step4) аналогично шагу два можно оценить как максимальное время выполнения одной параллельной ветви. Если – время выполнения i-ой нити, то – оценка четвертого шага. В свою очередь, время складывается из времени операций (1) и цикла (2). Для выполнения (1) надо выполнить деление, сложность O(t2), извлечение квадратного корня – O(t2), сложение – O(t) и присваивание – O(1). Таким образом, согласно правилу сумм, имеем оценку O(t2).
Общее время выполнения цикла (2) равно сумме временных затрат каждой итерации. Как видно из приведенного алгоритма, одна итерация состоит из последовательных команд, сложность которых оценивается как O(t2), операций присваивания – O(1) и операций ветвления. Время работы оператора if состоит из времени выполнения условно исполняемых операторов и вычисления логического условия. Оценка оператора (4) равна времени выполнения операторов (5), (6) и вычислению логического условия, т. е. времени двух операций умножения – O(t2+t2)=O(t2), вычитания – O(t) и нахождения остатка от деления – O(t2), т. е. O(t2). Сложность оператора (5) равна сложности сложения O(t), присваивания – O(1), перехода – O(1) и сложности вычисления логического условия, т. е. сложности сложения O(t), нахождения НОД, сложность последнего составит , если НОД находить с помощью бинарного алгоритма Евклида [72], и проверке самого логического условия – O(1). Таким образом, сложность оператора (5) равна O(t+1+1+t+ +1)= . Аналогичную оценку имеет и оператор (6). Следовательно, для оператора (4) имеем оценку O(t2+ +n)= . Тогда одну итерацию цикла можно оценить как O(t2). Оценка выполнения цикла – это произведение сложности одной итерации на количество повторений , т. е. O(gt2)= = . В результате оценка для одной параллельной нити четвертого шага будет равна = = . Соответственно, итоговая оценка данного шага равна O( )= .
Оценка заключительного этапа (Step5) равна О(1). Согласно правилам анализа времени работы алгоритмов, общая оценка операционной сходимости данной реализации алгоритма в терминах арифметических операций и извлечения корня составит . Оценки и результаты, опубликованные в работе [45], после научной дис-куссии были скорректированы и доработаны.
Все методы дискетного логарифмирования можно разделить на две кате-гории: общие алгоритмы, применяемые в любой конечной абелевой группе, и специальные, разработанные для специальных групп.
В настоящее время не известен алгоритм, который решает задачу за по-линомиальное время. Существующие методы являются субэкспоненциальны-ми, либо экспоненциальными [63, 79]. Алгоритмы первой группы имеют слож-ность , где c=const, . Алгоритм Адлемана впервые упо-минается в 1979 году, сложность , где с – некоторая константа, на практике не достаточно эффективен [98]. Алгоритм COS разработан математи-ками Копперсмитом, Одлыжко, Шреппелем в 1986 году, c=1, d=1/2 [18]. С по-мощью данного алгоритма и его модификаций успешно решена задача дис-кретного логарифмирования для и , при эффективней решета числового поля. Последний предложен Гордоном в 1993 году, имеет оценку , где , [104]. Существует много модифика-ций решета числового поля. Отдельные шаги метода, например, поиск гладких экспонент, можно выполнять в параллельном режиме, но подготовительный этап достаточно трудоемкий.
Ко второй группе относится алгоритм Шенкса (большой – малый шаг), который был предложен в 1971 году [122], сложность , где r – порядок группы, при этом объем необходимой памяти оценивается как . Данный метод имеет возможность распараллеливания, но он более подходит для реше-ния задачи в группе точек эллиптической кривой. Анализ параллельных алго-ритмов дискретного логарифмирования в указанной группе можно найти в ра-ботах Сидорова И. Д. [77, 78]. Алгоритм Сильвера-Полига-Хеллмана опублико-ван в 1978 году, известен так же как метод Гельфонда, требуется знать разло-жение на простые множители , трудоемкость составляет , эффективен, если множители числа p-1 достаточно малы [67]. -метод Полларда имеет эвристическую оценку [118].
Классический вариант -метода Полларда решения задачи дискретного логарифмирования в конечном поле обладает выраженным свойством паралле-лизма данных, так как одни и те же операции могут выполняться сразу над не-сколькими элементами из различных наборов [79]. В этом случае различные значения могут обрабатываться независимо на разных вычислитель-ных устройствах, что соответствует классу SIMD. Таким образом, -метод Пол-ларда может быть эффективно адаптирован и отображен на архитектуру графи-ческих процессоров nVidia CUDA. При этом не требуется дополнительных временных затрат на пересылку данных по сети в отличие от параллельного -метода Полларда [79], который рассчитан на распределенные вычисления в се-ти и подразумевает пересылку большого объема сообщений каждым из задей-ствованных компьютером на общий сервер, который должен их хранить, что делает метод неэффективным.
Впервые -метод Полларда решения задачи дискретного логарифмирова-ния в кольце вычетов по простому модулю был описан в работе [118]. Алго-ритм осуществляет случайный поиск дискретных логарифмов [18, 79, 109]. Строится псевдослучайная последовательность, в которой находятся совпа-дающие элементы, а затем на основании полученной величины вычисляется искомый дискретный логарифм. Используемая для рекурсивных вычислений функция является циклической, начиная с некоторого индекса (номера) элемен-та псевдослучайной последовательности. Этот метод имеет экспоненциальную оценку сложности. Он требует небольшого объема памяти для хранения дан-ных и допускает организацию параллельных вычислений на нескольких этапах, поэтому он предпочтительней для адаптации к архитектуре CUDA.
Реализация арифметических операций с «длинными» числами на устройствах GPGPU с архитектурой CUDA
В ряде прикладных задачах ИБ требуется выполнять вычислительные операции над «длинными» целыми числами, т. е. которые нельзя хранить в пе-ременных стандартных типов данных языков программирования. Для хранения таких чисел можно использовать различные способы, например, хранить число в виде строки, считая отдельный символ строки соответствующим разрядом числа. Наиболее часто для хранения чисел используют массивы, при этом, как правило, в одну ячейку записывается сразу несколько разрядов числа и даль-нейшие операции реализуются над массивом поэлементно. Такое представле-ние требует дополнительных действий для получения результата вычислитель-ных операций.
С учетом особенностей архитектуры CUDA одним из наиболее удобных способов представления «длинных» чисел является использование массивов [16, 44]. При этом в одну ячейку массива будем записывать только один разряд числа. Данное представление может быть более неудобным при вводе числа, но, как правило, операции ввода-вывода разовые и не оказывают существенно-го влияния на время работы алгоритма. С учетом выше сказанного для хране-ния десятичного числа из n разрядов необходим массив из t элементов по во-семь бит каждый, т.е. для хранения такого числа требуется 8t бит памяти. Для реализации арифметических операций на графическом устройстве (GPU) с ар-хитектурой CUDA необходимо в его памяти поместить два числа, т. е. 2t байт. В настоящее время в прикладных задачах защиты информации используют числа от 768 до 2048 бит, т. е. от 233 до 620 десятичных разрядов. Для хранения числа записанного в двоичной системе с помощью 1024 бит требуется массив из 310 элементов, т. е. 310 байт памяти, для хранения числа из 2048 бит доста-точно использовать массив из 620 байт. Самые простые из современных видео-карт имеют объем памяти 512 Мбайт и выше, соответственно, на них без про-блем могут быть реализованы операции с большими числами, представленны-ми в таком виде.
Будем считать, что два числа, над которыми требуется выполнить опера-цию сложения, представлены в виде загруженных в память GPU массивов из t+1 элементов, t= , где и – количество разрядов первого и второго числа соответственно. Пусть первое число записано в массив a, второе в массив b. Младший разряд хранится в нулевой ячейке массива, старший в t-1 ячейке. Последние элементы массивов проинициализированы нулями, они предназна-чены для записи единицы в случае увеличения разрядности чисел в результате сложения. Проинициализируем флаг переноса f нулевым значением. Восполь-зуемся известным алгоритмом сложения «в столбик», т. е. поэлементно сложим массивы, что можно выполнить в параллельном режиме сразу для всех t эле-ментов. Результат операции будем записывать в массив a. Остается только учесть переносы из разряда в разряд. Будем записывать в i-ю ячейку массива b и переменную f единицу, если a[i]+b[i] 10, в противном случае запишем ноль в соответствующую ячейку массива b. Для вычисления окончательного резуль-тата достаточно выполнить еще одну операцию поэлементного сложения мас-сивов a и b, перед которой флаг переноса обнуляем. Если значение f=0, то ал-горитм закончил работу, иначе выполняем его с первого шага. Формально вы-шеописанный алгоритм можно записать следующим образом.
Сложность операции сложения «длинных» чисел, реализуемая в гетеро-генных вычислительных системах на базе графических процессоров с архитек-турой CUDA с достаточным количеством GPU-вычислителей, равна О(t), где t – максимальное количество разрядов складываемых чисел Доказательство. Оценка общего времени работы алгоритма складывается из оценок времени работы трех его шагов [5]. Третий шаг состоит из одного ус-ловия и единственной операции присваивания, выполняемых на CPU. Операция присваивания имеет оценку сложности О(1), как и операция проверки условия, следовательно, данный шаг можно оценить как О(1). Для получения асимпто-тических оценок первых двух шагов, выполняемых параллельно на GPU, необ-ходимо оценить время выполнения одной параллельной ветви (нити, в терми-нологии CUDA). В общем случае разные ветви могут иметь различное время выполнения. Т. к. синхронизация параллельных вычислений на устройствах CUDA выполняется после завершения работы всех нитей, то общая оценка бу-дет равна , где – время выполнения i-ой нити. Для реализации одной параллельной нити первого шага требуется выполнить одну операцию сложе-ния, вычитания, присваивания и проверку логического условия. Сложность по-следнего, как и операции присваивания, равна О(1). Сложность сложения в об-щем случае имеет оценку О(1). Таким образом, для первого шага алгоритма число арифметических операций можно оценить О(1+1+1+1)=О(1). Аналогич-но оценка второго шага составит О(1+1)=О(1). Максимальное число повторе-ний алгоритма с учетом всех возможных переносов равно t. Тогда оценка слож-ности операции сложения «длинных» чисел, реализуемая на GPU с архитекту-рой CUDA, равна О(t) Операцию умножения двух чисел а и b можно реализовать через b после-довательных сложений числа a с самим собой. Как было показано выше, слож-ность операции сложения составляет О(t), в этом случае сложность операции умножения равна О(bt)=O(b )= . Данную оценку можно улучшить, используя параллельный вариант алгоритма умножения в столбик. Будем счи-тать, что множители имеют одинаковое количество разрядов – t. Для реализа-ции потребуется t операций умножения t-разрядного числа на одноразрядное (каждую из которых можно выполнять параллельно) и сложение полученных результатов. Умножение числа на цифру можно выполнить как сложение числа a с самим собой, при этом может потребоваться максимум девять сложений. Таким образом, операция умножения на цифру имеет сложность O(9t)=O(t). Для сложения результатов умножений может потребоваться t операций сложе-ния t-разрядных чисел, следовательно, итоговая сложность составит O(t2).
