ГОСТ 28147-89 и векторные расширения CPU

Говоря о параллельных вычислениях на одном компьютере, чаще всего имеют в виду одновременные вычисления на нескольких процессорах (или ядрах одного процессора). Но помимо этого существует также возможность параллельных вычислений в пределах одного ядра — это использование векторных инструкций.

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

Возможность выполнения векторных операций в современных вычислительных системах на платформах x86/x64 обеспечивается специальными процессорными расширениями SSE и AVX. Эти расширения добавляют новые регистры длиной 128 и более бит, а также инструкции для работы с ними.

Покажем, как можно применить эти расширения для эффективной реализации алгоритма ГОСТ 28147-89.

Как известно, один раунд алгоритма ГОСТ 28147-89 состоит из сложения с ключом по модулю 2, восьми 4-х битовых узлов замены и циклического сдвига на 11 бит влево. Очевидно, что выигрыш в производительности за счет использования векторных инструкций можно получить, только обрабатывая несколько блоков за раз. Причем чем большее количество блоков будет обсчитываться одновременно, тем больший выигрыш в скорости мы получим. Размер блока в алгоритме ГОСТ 28147-89 равен 64 битам, но так как используется сеть Фейстеля, все ресурсоемкие преобразования производятся только над половиной блока, то есть над 32 битами данных. Эта особенность алгоритма позволяет нам, например, складывать с раундовым ключом или циклически сдвигать одновременно несколько блоков, используя один AVX-регистр.

Отдельного внимания заслуживают узлы замен. Дело в том, что в расширении AVX была добавлена команда VPSHUFB, которая копирует байты из регистра-источника в регистр-приемник в порядке, описанном в индексном регистре.

Если в регистр-источник записать таблицу замен, а в индексный регистр (в младшие полубайты) поместить обрабатываемые данные, то с помощью этой инструкции можно за один такт процессора сделать замену для 16 полубайт, что позволяет получить значительный выигрыш в скорости по сравнению с последовательным применением узлов замен.

Стоит отметить, что эффективное использование этой инструкции возможно только благодаря тому, что в алгоритме ГОСТ 28147-89 используются именно 4-битные узлы замен. Действительно, так как команда VPSHUFB использует только младшие 4 бита каждого байта индексного регистра, то и заменять мы можем соответственно только их. К тому же одна таблица замен для 4 бит имеет размер 2⁴ x 4 = 64 бита, что позволяет в один 128-битный регистр поместить сразу две таблицы.

Теперь перейдем непосредственно к цифрам. На графиках ниже представлены результаты измерений скорости шифрования в режиме гаммирования (режима, который весьма часто используется в криптографических протоколах) в зависимости от числа потоков. Измерения производились на стендах №1, №2 и №3. Стенд №1 имитирует серверный компьютер, стенды №2 и №3 — обычные пользовательские компьютеры.

При реализации протоколов TLS и IPsec для контроля целостности данных используется имитовставка по алгоритму ГОСТ 28147-89, поэтому распространенной задачей при использовании этих протоколов является шифрование с одновременным вычислением имитовставки. Ниже представлен график зависимости скорости шифрования с одновременным вычислением имитовставки от количества потоков. На графике режим MultiPacket обозначает одновременную обработку нескольких пакетов, подробнее этот режим описан в документации на КриптоПро CSP.

ГОСТ и GPU

Рассматривая эффективные реализации криптографических алгоритмов, нельзя не упомянуть о таком направлении как GPGPU (General-purpose graphics processing units).

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

Во-первых, это количество ядер. Если центральные процессоры имеют в среднем от 2 до 16 ядер, то графические – от нескольких сотен до нескольких тысяч — например, графический процессор GeForce GTX 970 содержит 1664 ядра, а Radeon R9 295X2 — 5632.

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

В-третьих, это пропускная способность памяти, которая у графических процессоров в несколько раз больше. Для примера, при использовании процессора Intel Xeon E5-2670 и 4-х модулей оперативной памяти DDR3 пропускная способность памяти составляет примерно 80 Гб/с, в то время как пропускная способность памяти уже упоминавшихся графических процессоров GeForce GTX 970 и Radeon R9 295X2 составляет 224 и 680 Гб/с соответственно.

Чтобы объяснить, чем же хорош алгоритм ГОСТ 28147-89 для реализации на GPU, нужно сначала немного рассказать о принципе вычислений на GPU.

Не вдаваясь в подробности, любая программа на GPU содержит несколько основных шагов, изображенных на рисунке ниже.

Данные на этапе вычислений на GPU обрабатываются в несколько тысяч потоков. Потоки выполняются не все одновременно, а группами. Во время работы одной такой группы все ресурсы графического процессора (векторные и скалярные регистры, память и т.п.) делятся между потоками этой группы, поэтому количество потоков в группе зависит от ресурсов используемых одним потоком для вычислений. Очевидно, что чем меньше ресурсов использует один поток, тем больше потоков может выполняться на GPU одновременно, а, следовательно, тем выше будет скорость работы программы.

Поэтому для достижения высокой скорости работы какого-либо алгоритма на GPU необходимо минимизировать количество ресурсов, используемых им для вычислений.

С этой точки зрения алгоритм ГОСТ 28147-89 имеет ряд преимуществ. Во-первых, это простая процедура получения раундовых ключей, которая не требует много ресурсов. Во-вторых, с помощью предвычисленной таблицы можно упростить раундовое преобразование. Таким образом, вместо восьми 4-битовых узлов замен и циклического сдвига мы имеем сложение по модулю 2 четырех элементов из предвычисленной таблицы. Все это значительно снижает количество аппаратных ресурсов, необходимых для работы алгоритма, и существенно увеличивает скорость его работы на GPU

Другой способ оптимизации базового цикла алгоритма ГОСТ 28147–89 для GPU был предложен в работе [4]. Для уменьшения количества обращений к памяти автор предлагает реализовать таблицу замены через булеву функцию, что значительно повышает скорость работы алгоритма.

На графике ниже представлены результаты скорости шифрования на GPU для различных алгоритмов для построенной на основе данных идей реализации. Все измерения сделаны на тестовом стенде №2. Во время тестов в режиме простой замены шифровались данные размера 256 МБ и измерялась теоретическая и практическая производительность реализации алгоритма. Теоретическая производительность показывает скорость непосредственно шифрования на GPU, а практическая — скорость шифрования + копирования данных в память GPU и результатов из памяти GPU в оперативную. Реализации алгоритмов для OpenCL (кроме реализации ГОСТ 28147-89) взяты из открытого проекта engine-cuda.

Как видно из графика, практическая скорость шифрования на GPU слабо коррелирует с теоретической. Происходит это из-за того, что большую часть времени в реальных условиях занимают операции копирования данных из оперативной памяти в память GPU и обратно. Все это затрудняет использование GPU для шифрования на практике.