Стаття присвячена деяким аспектам організації паралельних обчислень і використання технології GPGPU для вирішення завдань дискретного логарифмування в кінцевому полі. Основні розділи присвячені огляду адаптації? -Методу Полларда до паралельних обчислень на пристроях з гетерогенної архітектурою.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Желтов Сергій Олександрович


Adaptation of discrete logarithm problem solution by pollard? -Method to the computing architecture CUDA

The article is devoted to some aspects of organizing parallel computing and the GPGPU technology usage for the discrete logarithm problem solving in a finite field. The main sections are devoted to the review of adaptation Pollard? -Method for parallel computing on devices with heterogeneous architectures.


Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2013


    Журнал: Історія та архіви


    Наукова стаття на тему 'АДАПТАЦІЯ? -Метод Поллард рішення задачі дискретного логарифмування До ОБЧИСЛЮВАЛЬНОЇ АРХІТЕКТУРИ CUDA'

    Текст наукової роботи на тему «АДАПТАЦІЯ? -Метод Поллард рішення задачі дискретного логарифмування До ОБЧИСЛЮВАЛЬНОЇ АРХІТЕКТУРИ CUDA»

    ?моделювання

    С.А. Желтов

    АДАПТАЦІЯ р-МЕТОДУ Поллард рішення задачі дискретного логарифмування До ОБЧИСЛЮВАЛЬНОЇ АРХІТЕКТУРИ Сіба

    Стаття присвячена деяким аспектам організації паралельних обчислень і використання технології орор для вирішення задач дискретного логарифмування в кінцевому полі. Основні розділи присвячені огляду адаптації р-методу Полларда до паралельних обчислень на пристроях з гетерогенної архітектурою.

    Ключові слова: паралельні обчислення, дискретного логарифмування, архітектура Сіба.

    Вступ

    Одним із завдань, складність вирішення якої визначає стійкість цілого ряду асиметричних систем захисту1, є завдання дискретного логарифмування в цілком певних алгебраїчних структурах.

    Формально задачу дискретного логарифмування в кінцевому полі можна сформулювати наступним чином.

    Нехай - кільце відрахувань по простому модулю р.

    Для заданих а, Ь е? Р потрібно знайти х е Гр:

    ах = Ь (тієї р). (1)

    Ціле число х, яке задовольняє (1), називається дискретним логарифмом числа Ь за основою а.

    © Желтов С.А., 2013

    Завдання ставиться до класу NP, і на сьогоднішній день невідомі методи її вирішення полиномиальной складності.

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

    Одним із способів зниження практичних тимчасових витрат на вирішення зазначеного класу обчислювальних задач є вибір ефективної моделі обчислень на існуючих класах архітектур (в тому числі і спеціалізованих) обчислювальних систем, що вимагає відповідної адаптації методів і алгоритмів до обраної моделі вичісленій2. При використанні обчислювальних архітектур в рамках класичної моделі обчислень А. Тьюринга-Дж. Неймана основним напрямком зниження фактичних витрат часу є організація паралельних вичісленій3.

    В даний час все більшого розвитку набуває паралельне програмування на графічних процесорах (GPU).

    I. Технологія GPGPU. архітектура CUDA

    GPGPU (General-purpose graphics processing units) - технологія використання графічного процесора для виконання розрахунків в додатках для загальних обчислень. Це стало можливим завдяки додаванню програмованих шейдерних блоків і більш високою арифметичної точності растрових контейнерів, що дозволяє використовувати потокові процесори для неграфічних обчислень.

    На сьогоднішній день технологія GPGPU реалізована декількома виробниками.

    Khronos Group: OpenCL - мова програмування завдань загального призначення, пов'язаних з обчисленнями на різних графічних і центральних процесорах.

    Microsoft: DirectCompute - інтерфейс програмування додатків, який входить до складу DirectX.

    Advanced Micro Devices: AMD FireStream - технологія GPGPU, що дозволяє реалізовувати обчислювальні алгоритми, що виконуються на графічних процесорах прискорювачів ATI.

    Компанія Nvidia: CUDA - технологія GPGPU, що дозволяє реалізовувати на мові Сі обчислювальні алгоритми, що виконуються на графічних процесорах прискорювачів GeForce восьмого покоління і старше.

    Найбільш зручні засоби для організації паралельних обчислень на графічних прискорювачах пропонує остання технологія.

    Nvidia CUDA (Compute Unified Device Architecture) - це архітектура, т. Е. Сукупність програмних і апаратних засобів, які дозволяють виробляти на графічних процесорах компанії Nvidia, що підтримують технологію GPGPU, обчислення загального назначенія4.

    Особливістю архітектури CUDA є блочно-сіткова організація, незвичайна для багатопоточних додатків. Вона заснована на концепції «одна команда на безліч даних» (Single Instruction Multiple Data) або SIMT (Single Instruction, Multiple Thread).

    Варто відзначити такі особливості використання архітектури CUDA:

    • GPU (device) виступає в ролі співпроцесора для CPU (host) і являє собою масив з окремих обчислювальних ядер;

    • GPU володіє власною пам'яттю (device memory);

    • GPU здатний одночасно обробляти безліч процесів даних (threads) одним і тим же алгоритмом;

    • інтерфейс програмування додатків CUDA заснований на стандартній мові програмування, наприклад Сі, з розширеннями;

    • масштабованість CUDA - код запускається на всіх пристроях, що підтримують технологію CUDA.

    Основні переваги CUDA в порівнянні з іншими реалізаціями GPGPU обумовлені тим, що ця архітектура спроектована для ефективного використання неграфічних обчислень на GPU і використовує мову програмування Сі, не вимагаючи перенесення алгоритмів в зручний для концепції графічного конвеєра вид. Дана технологія використовує пам'ять, що розділяється, недоступну з графічних API (Application Programming Interface), і оптимізований обмін даними між CPU і GPU.

    Вже згадана архітектура не використовує графічні API і позбавлена ​​недоліків, характерних для інших технологій GPGPU.

    II. Адаптація р-методу Полларда до обчислювальної архітектурі CUDA

    Проаналізуємо кожен крок алгоритму р-методу Полларда5 на можливість застосування паралельних обчислень і подальшого скорочення фактичних витрат на час роботи алгоритму при використанні архітектури CUDA. Найбільш зручним для розпаралелювання є крок 2, який слід розбити на незалежні підзадачі, які можливо було б виконати в паралельному режимі. За одну таку підзадачу візьмемо задачу генерації наборів (х, а, в) і (х2, а, в) для фіксованого значення індексу i. Так як алгоритм не вимагає зберігання і використання значень, обчислених на попередніх етапах кроку 2 алгоритму, то немає необхідності обміну даними між різними подзадачами, що також позитивно позначиться на скороченні часу роботи.

    З урахуванням особливостей архітектури CUDA, модифікований для паралельної реалізації алгоритм р-методу Полларда буде виглядати наступним чином:

    Вхідні дані:

    a, b е Fp, p - просте число.

    Вихід: х е Fp, таке, що ax = b (mod p), якщо він існує.

    Крок 1: (виконується на CPU).

    Визначення значення N, завдання початкового параметра i = 1.

    Крок 2: (виконується для значень i, i + 1, i + 2, ..., i + N паралельно на GPU).

    Завдання початкових параметрів а0 = 0, в0 = 0, x0 = 1. _

    Генерація послідовності наборів (х, а, в), гдеj = 1, 2i за правилом:

    якщо 0 < х . <1 p, то а. ^. = А, в. + 1, х, = bx..

    '3 i + 1 i i i + 1 i

    1 2

    якщо -p < x. < - p, то а. ^. = 2а., В- ^ = 2в-, x. ^ T = x2.

    3 r. 3 i + 1 i i + 1 i i + 1 i

    2

    якщо -p < x. < p, то а. ^. = А. + 1, в- ^ = в •, x. ^. = ax..

    3 ^ i i + 1 i 'Z ^ i + 1 ^ V i + 1 i

    Покласти: м = А2. - а (modp- 1), v = в. - в (modp- 1).

    Крок 3: (виконується на CPU).

    Порівняти отримані в результаті кроку 2 значення x. і x2i для значень i, i + 1, i + 2, ..., i + N.

    Якщо x. = X2i, то перейти до кроку 4.

    Якщо x. Ф x, то перейти до кроку 1 і покласти i = i + N.

    Крок 4: (виконується на CPU).

    Якщо V = 0, то алгоритм завершує роботу.

    Якщо V Ф 0, то обчислити НОД d = (v, p - 1) = vv + (p - 1) і.

    Крок 5: (виконується на CPU).

    Обчислити x:

    Якщо d = 1, то x = uv (modp - 1).

    uv + o) (p - 1) --

    Якщо d Ф 1, то x = ---, o = 1, d.

    d

    Число N - це кількість паралельно виконуються подзадач. Це число залежить від конкретного графічного прискорювача і визначається на початковому етапі роботи програми.

    Кількість обчислюваних наборів на кожному наступному етапі другого кроку алгоритму збільшується. У паралельній реалізації всі операції виконуються одночасно, і крок 2 буде завершено, коли обчислити набір з найбільшим індексом. Враховуючи вище викладене, час виконання другого кроку алгоритму одно часу генерації набору з максимальним індексом, т. Е. Для паралельного обчислення до штук наборів з індексами 1, 2, ..., до буде витрачено той же час, що і на генерацію одного набору з індексом до при послідовних обчисленнях. При реалізації на CPU необхідно обчислити до + к2 штук наборів.

    III. експериментальна апробація

    Для проведення чисельних експериментів р-метод Полларда був програмно реалізований в класичному варіанті для послідовного виконання на CPU, на стандартній мові Сі і виконувався на центральних процесорах різних потужностей. Модифікований до архітектури CUDA, паралельний алгоритм р-методу Полларда програмно реалізований на розширенні мови Сі для CUDA і виконувався на різних графічних прискорювачах компанії Nvidia.

    Для проведення чисельних експериментів були задіяні такі технологічні платформи CPU:

    • Intel core i5-2400;

    • Intel Core 2 Duo E7500.

    І GPU компанії Nvidia:

    • GeForce GTX 560;

    • GeForce 9600

    під управлінням операційної системи Windows 7. Результати наведені в табл. 1.

    Таблиця 1

    Результати обчислювальних експериментів

    p біт Час роботи, з.

    Nvidia GeForce 9600 Nvidia GeForce GTX 560 Intel Core 2 Duo Intel core i5-2400

    7 3 0,032 0,041 0,028 0,016

    13 4 0,031 0,040 0,028 0,014

    41 5 0,032 0,047 0,030 0,016

    61 6 0,032 0,042 0,031 0,016

    113 7 0,031 0,042 0,029 0,015

    197 8 0,030 0,041 0,031 0,016

    379 9 0,033 0,038 0,032 0,015

    659 10 0,032 0,045 0,035 0,016

    1153 11 0,032 0,039 0,031 0,016

    2551 12 0,032 0,042 0,046 0,019

    6961 13 0,034 0,040 0,047 0,031

    11719 14 0,033 0,043 0,031 0,031

    23159 15 0,034 0,041 0,047 0,047

    61001 16 0,033 0,045 0,141 0,078

    67651 17 0,032 0,047 0,156 0,109

    921637 20 0,066 0,047 1,453 0,936

    6878407 23 0,132 0,094 11,047 7,110

    88004533 27 0,288 0,203 84,343 50,716

    926403853 30 0,349 0,282 109,265 56,320

    Залежність часу роботи програмних реалізацій для центрального та графічних процесорів від розмірності модуля p представлені на наступних графіках (рис. 1, 2).

    Варто відзначити, що при використанні більш потужних GPU пристроїв або спеціалізованих рішень Nvidia (Quadro і Tesla) слід очікувати подальшого зростання продуктивності в кілька разів і зниження тимчасових витрат ще на кілька порядків.

    Мал. 1. Залежність часу роботи від розмірності модуля (p<17)

    Мал. 2. Залежність часу роботи від розмірності модуля (p>17)

    висновки

    Аналіз обчислювальних операцій р-методу Полларда показав, що алгоритм має виражену властивість паралелізму даних, так як одні й ті ж операції можуть виконуватися відразу над декількома елементами з різних наборів (х, а,?), Ці значення можуть оброблятися незалежно на різних обчислювальних пристроях , що підходить для ефективної паралельної реалізації на архітектурі CUDA і дозволяє скоротити час обчислень.

    Результати числових експериментів показали, що р-метод Полларда допускає ефективну паралельну реалізацію з використанням обчислень на GPGPU компанії Nvidia. Розпаралелювання обчислень при вирішенні задачі дискретного логарифмування р-методом Полларда дає скорочення фактичних витрат часу до двох порядків щодо послідовної реалізації.

    Варто відзначити, що на практиці в системах захисту використовуються ключі не менше 512 біт, а програмні засоби CUDA не мають реалізації бібліотеки для роботи з «великими» числами. Один із способів організації обчислень з «довгими» числами, які виходять за діапазон значень стандартних типів даних сучасних мов програмування, описаний автором в одній з работ6.

    Автор висловлює глибоку подяку проф. А.Е. Барановичу за цінні рекомендації та допомогу при проведенні досліджень.

    Примітки

    Див: Смарт Н. Криптографія. М .: Техносфера, 2006. 528 с. Див .: Баранович А.Є. Введення в предметно орієнтовані аналіз, синтез і оптимізацію елементів архітектур потокових систем обробки даних (Introduction in the object-oriented analysis, synthesis and optimization of elements of architecture data flow processing systems) [Електронний ресурс] 3-е изд., Стереотип., Испр . Електрон. дан. [М., НТЦ «Информрегистр», 2010]. Див .: Воєводін В.В., Воєводін Вл.В. Паралельні обчислення. СПб .: БХВ-Петербург, 2002. 600 с.

    Див .: Боресков А.В., Харламов А.А. Основи роботи з технологією CUDA. М .: ДМК Пресс, 2010. 232 с.

    Див .: Guan D. J. Pollard's Algorithm for Discrete Logarithm [Електронний ресурс] URL: http://guan.cse.nsysu.edu.tw/note/pollard.pdf (дата звернення: 30.04.2013). Желтов С.А. Реалізація арифметичних операцій з «довгими» числами на пристроях GPGPU // Питання захисту інформації. 2012. № 3. С. 2-4.

    3

    4

    5


    Ключові слова: ПАРАЛЕЛЬНІ ОБЧИСЛЕННЯ /PARALLEL COMPUTING /дискретного логарифмування /DISCRETE LOGARITHM /АРХІТЕКТУРА CUDA /ARCHITECTURE CUDA

    Завантажити оригінал статті:

    Завантажити