VII Международная студенческая научная конференция Студенческий научный форум - 2015

Аннотация. Статья посвящена актуальной тематике - параллельным вычислениям, с использованием ресурсов видеоплат. Направление вычислений эволюционирует от «централизованной обработки данных» на центральном процессоре до «совместной обработки» на CPU и GPU. Для реализации новой вычислительной парадигмы компания NVIDIA изобрела архитектуру параллельных вычислений CUDA, на данный момент представленную в графических процессорах GeForce, ION, Quadro и Tesla и обеспечивающую необходимую базу разработчикам ПО. Эту технологию можно использовать для параллельного шифрования блоков.

Ключевые слова: шифр Хилла,централизованная обработка, совместная обработка, параллельные вычисления.

Abstract. Article is devoted to the subject - parallel computing using graphics cards resources. The direction of computing is evolving from "central processing" on the CPU to "co-processing" on the CPU and GPU. For the implementation of a new computing paradigm, NVIDIA invented parallel computing architecture CUDA, currently represented by the GPU GeForce, ION, Quadro and Tesla, and provides the necessary framework for software developers. This technology can be used for parallel encryption blocks.

Keywords: Hill сipher,centralized processing, co-processing, parallel computing.

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре [1]. Лестер С. Хилл изобрел этот шифр в 1929, и это был первый шифр, который позволял на практике (хотя и с трудом) оперировать более чем с тремя символами за раз.

Каждой букве сперва сопоставляется число. Для латинского алфавита часто используется простейшая схема: A = 0, B =1, ..., Z=25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается на n × n матрицу по модулю 26. (Если в качестве основания модуля используется число большее 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации.) Матрица целиком является ключом шифра. Матрица должна быть обратима в Z26n, чтобы была возможна операция расшифрования.

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

A		C	D	E	F	G	H	I	J	K	L	M		O		Q	R		T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Рассмотрим сообщение 'DOG' и представленный ниже ключ (GYBNQKURP в буквенном виде):

6241131610201715

Так как букве 'D' соответствует число 3, 'O' — 14, 'G' — 6, то сообщение — это вектор

3146

Тогда зашифрованный вектор будет

62411316102017153146=360323388≡221124(mod 26)

что соответствует шифротексту 'WLY'. Теперь предположим, что наше сообщение было 'GOD' или

6143

Теперь зашифрованный вектор будет

62411316102017156143=375332403≡112013(mod 26),

что соответствует шифротексту 'LUN'. Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг диффузии по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.

Проведем исследование возможностей технологии CUDA. CUDA (англ.ComputeUnifiedDeviceArchitecture) — программно-аппаратная архитектура параллельных вычислений, которая позволяет существенно увеличить вычислительную производительность благодаря использованию графических процессоров фирмы Nvidia [2-3]. CUDA SDK позволяет программистам реализовывать на специальном упрощённом диалекте языка программирования Си алгоритмы, выполнимые на графических процессорах Nvidia, и включать специальные функции в текст программы на Си. Архитектура CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью.

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

• Интерфейс программирования приложений CUDA (CUDA API) основан на стандартном языке программирования Си с некоторыми ограничениями. По мнению разработчиков, это должно упростить и сгладить процесс изучения архитектуры CUDA.

• Разделяемая между потоками память (shared memory) размером в 16 Кб может быть использована под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур.

• Более эффективные транзакции между памятью центрального процессора и видеопамятью.

• Полная аппаратная поддержка целочисленных и побитовых операций.

• Поддержка компиляции GPU кода средствами открытого LLVM.

Выделим встречающиеся ограничения использования технологии. Все функции, выполнимые на устройстве, не поддерживают рекурсии (в версии CUDA Toolkit 3.1 поддерживает указатели и рекурсию) и имеют некоторые другие ограничения.

Реализация параллельного шифрования шифром Хилла с использованием технологии CUDA. Введем основные понятия технологии CUDA:

• Хост (host) – узел с CPU и его память.

• Устройство (device) – графический процессор и его память.

• Ядро (kernel) – это фрагмент программы, предназначенный для выполнения на GPU.

Пользователь самостоятельно запускает с CPU ядра на GPU. Перед выполнением ядра пользователь копирует данные из памяти хоста в память GPU. После выполнения ядра пользователь копирует данные из памяти GPU в память хоста.

Изучив математическую модель шифра Хилла, попробуем перенести её в программный код с помощью технологии CUDA. Матрицу - ключ представим в виде двумерного массива размером N*N, тип данных будет int (целочисленный), т.к. очевидно, что индексы букв будут положительными числами. Выделим для неё оперативную память с помощью оператора new. Далее необходимо заполнить массив, для чего нам понадобится два цикла for, которые будут индексировать элементы и функция rand(), которая будет заполнять их случайными целыми числами в диапазоне от 0 до 25 включительно[0,25].

Для простоты подсчёта времени будем брать открытый текст из текстового файла(text.txt) и записывать шифротекст в другой текстовый файл(crypto.txt), для чего создадим два файловых потока, свяжем их с соответствующими файлами(ifstream texts("text.txt"); ofstream crypto("crypto.txt", ios_base::out); ). Представим исходный текст как одномерный массив типа char размера N. Также для индексации букв введём английский алфавит и представим его, как массив типа char размера 27. Считаем из файла открытый текст в массив типа char с помощью функции getline().

Для хранения индексов открытого текста создадим указатель на массив h_b типа int, выделим для него динамическую память размера N, и поместим их туда, используя операторы циклов while и for. Сравнивая с помощью оператора условия if элементы массива открытого текста с элементами массива с английским алфавитом. Если они равны, то в массив h_b заносим индексы элементов массива с английским алфавитом.

Теперь постараемся выяснить, в чем же разница между обработкой данных на CPU и GPU. Простой способ понять разницу между CPU и GPU – это сравнить то, как они выполняют задачи. CPU состоит из нескольких ядер, оптимизированных для последовательной обработки данных. А GPU состоит из тысяч более мелких и энергоэффективных ядер, созданных для обработки нескольких задач одновременно.

Если наши блоки шифруются последовательно, т.е. каждый i-тый блок шифрования зависит от результата (i-1)-го блока, то понятно, что распараллелить такую задачу невозможно. Однако, если блоки шифруются независимо друг от друга, одинаковым ключом(например шифр Хилла), то такую задачу можно распараллелить путём одновременного вычисления всех блоков и нитей.

Создадим указатели типа int для девайсовской функции. На видеокарте нет ПЗУ, т.к. оно ей и не нужно в принципе. Но зато есть достаточно большое ОЗУ, им и воспользуемся. Выделим на девайсе оперативную память для матрицы - ключа, открытого текста и шифротекста с помощью функции cudaMalloc(). Перенесём данные с хоста на девайс с помощью функции cudaMemcpy(). Установим количество блоков и потоков для параллельного вычисления с помощью спецификатора dim3 и ключевых слов grid(для количества блоков) и threads( для количества потоков). Вызовем девайсовскую функцию. С помощью оператора > поместим в неё информацию о количестве блоков, потоков и переменные. Девайсовская функция начинается со спецификатора ___global___ , в ней инициализируем итератор i, который будет равен

int i = blockIdx.x*blockDim.x+threadIdx.x,

где threadIdx.x – идентификатор потока в блоке по координате x,

blockIdx.x – идентификатор блока в гриде по координате x,

blockDim.x – количество потоков в одном блоке.

Вычисляем параллельно, для чего перемножаем матрицу - ключ на индексы открытого текста. Параллельно делим все элементы шифротекста на 26 и вычисляем остаток, с помощью оператора %.

Переносим вычисленные данные с девайса на хост с помощью функции cudaMemcpy(). Освобождаем динамически выделенную память на девайся с помощью функции cudaFree() и на хосте delete[].

Осталось только записать результат. С помощью цикла for поэлементно записываем в файл с результатом элементы массива с алфавитом по индексу cript[i]. Закроем файлы с помощью функции close(). Время работы программы также измерялось в милисекундах.

Алгоритм работы параллельной программы:

1) Подключаем библиотеки.

2)Открываем файл с открытым текстом(text.txt) и файл, в который будет записан результат(crypto.txt). Проверяем открылись ли файлы, если нет, то завершаем программу, если да то продолжаем вычисления.

3)Считываем открытый текст из файла.

4)Создаём и заполняем массив, в котором будут хранится индексы букв открытого текста.

5)Создаем матрицу-ключ и заполняем её для удобства случайными числами.

6)Выделяем видеопамять для переменных.

7)Подгружаем данные матрицы-ключа и открытого текста с хоста на девайс.

8)Устанавливаем количество блоков и устанавливаем количество потоков в блоке.

9)Вызываем функцию, которая распараллелит шифрование открытого текста.

10) Подгружаем данные шифротекста с девайса на хост.

11)Записываем получившийся результат в файл.

12)Считаем времы работы программы.

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

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

Отсутствие сокращения времени работы программы может быть связано с API системой, которая загружает данные с хоста на девайс и наоборот, с девайся на хост. Отчасти это замедляет работу программы. С другой стороны технология CUDA рассчитана на вычисление большого объёма данных и решения более сложных задач, чем симметричное блочное шифрование методом Хилла.

Таблица 1. Время работы последовательной и параллельной программы

Порядок матрицы и длина шифруемого слова, N	Скорость исполнения в секундах, с
	Без CUDA	С CUDA
3	0.101	0.137
6	0.101	0.133
10	0.101	0.137
15	0.102	0.131
100	0.102	0.139
500	0.124	0.139

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

Список литературы

1. Шифр Хилла // Электронный ресурс http://dic.academic.ru/dic.nsf/ruwiki/1346299.

2. CUDA // Электронный ресурс https://ru.wikipedia.org/wiki/CUDA.

3. Параллельные вычисления CUDA // Электронный ресурс http://www.nvidia.ru/object/cuda-parallel-computing-ru.html.

8

Код для цитирования: Скопировать