PCLMULQDQ

PCLMULQDQ — это инструкция для процессоров архитектуры x86-64, реализующая операцию беззнакового умножения двух 64-битных операндов с результатом 128 бит, выполняемая с использованием техники «умножение без переноса» (carry-less multiplication). Данная инструкция входит в набор расширений AES-NI (Advanced Encryption Standard New Instructions) и впервые была представлена компанией Intel в 2010 году в процессорах на микроархитектуре Westmere. PCLMULQDQ применяется преимущественно в криптографии, в частности для ускорения вычислений в режимах аутентифицированного шифрования (например, GCM — Galois/Counter Mode), а также в других областях, требующих быстрых полиномиальных умножений над полем Галуа GF(2).

История

Разработка инструкции PCLMULQDQ была обусловлена необходимостью повышения производительности криптографических алгоритмов, особенно в контексте стандартов шифрования, принятых в начале 2000-х годов. Режим GCM, стандартизированный NIST в 2007 году, требует выполнения большого количества умножений в поле GF(2^128), что на универсальных процессорах без аппаратной поддержки было вычислительно затратным. Intel включила PCLMULQDQ в состав расширения AES-NI, которое было впервые реализовано в процессорах Westmere (линейки Core i3, i5, i7 первого поколения, а также серверные Xeon серии 5600). Позднее поддержка инструкции была добавлена в процессоры AMD, начиная с микроархитектуры Bulldozer (2011 год). С тех пор PCLMULQDQ является стандартной возможностью большинства современных x86-совместимых процессоров.

Принцип работы

Обычное умножение целых чисел включает в себя сложение частичных произведений с переносами между разрядами. В операции «умножение без переноса» (carry-less multiplication) переносы игнорируются, и сложение выполняется по модулю 2 (операция XOR). Формально результат вычисляется как полиномиальное умножение в поле GF(2), где каждый бит операнда представляет коэффициент полинома (0 или 1), а сложение коэффициентов происходит без переноса.

Инструкция PCLMULQDQ имеет формат: PCLMULQDQ xmm1, xmm2, imm8 где:

• xmm1 — первый операнд (128-битный регистр XMM);
• xmm2 — второй операнд (128-битный регистр XMM или ячейка памяти);
• imm8 — 8-битная константа, управляющая выбором 64-битных половинок из каждого операнда.

Параметр imm8 кодируется следующим образом:

• биты 0 и 1 (младшие) определяют, какая половина первого операнда используется: 00 — младшая (биты 0–63), 01 — старшая (биты 64–127);
• биты 4 и 5 определяют, какая половина второго операнда используется: 00 — младшая, 01 — старшая.

Результат — 128-битное произведение, записываемое в регистр xmm1. При необходимости выполнения умножения над 128-битными числами (например, в GCM) требуется несколько вызовов PCLMULQDQ и последующее комбинирование результатов.

Применение

Криптография

Основное применение PCLMULQDQ — ускорение аутентифицированного шифрования в режиме GCM, используемом в протоколах TLS, IPsec, IEEE 802.11 (Wi-Fi) и других. В GCM для вычисления тега аутентичности требуется умножение в поле GF(2^128). Без аппаратной поддержки эта операция выполняется программно с использованием табличных методов или циклических сдвигов, что занимает десятки тактов. PCLMULQDQ позволяет выполнить умножение за 1–2 такта (в зависимости от микроархитектуры), что даёт значительный прирост производительности.

Также инструкция применяется в других криптографических схемах, основанных на полиномиальных вычислениях, например:

• в некоторых реализациях эллиптической криптографии (ECC) для операций в поле GF(2^m);
• в алгоритмах хеширования, использующих полиномиальное деление (например, CRC — Cyclic Redundancy Check);
• в схемах кодирования с исправлением ошибок (коды Рида — Соломона, БЧХ-коды).

Вычислительная математика

PCLMULQDQ может использоваться для ускорения вычисления циклических избыточных кодов (CRC), которые широко применяются в сетевых протоколах (Ethernet, SATA, USB) и системах хранения данных. Традиционные реализации CRC основаны на табличных методах, но с использованием PCLMULQDQ возможно вычисление CRC за меньшее число тактов, особенно для длинных сообщений. Алгоритмы, такие как «folded CRC» (свёрнутый CRC), используют инструкцию для параллельной обработки нескольких байт.

Другие области

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

Производительность

Производительность PCLMULQDQ варьируется в зависимости от микроархитектуры процессора. В процессорах Intel на микроархитектуре Westmere и Sandy Bridge латентность инструкции составляла около 8–12 тактов, а пропускная способность — одно умножение за 2–4 такта. В более поздних микроархитектурах (Haswell, Skylake, Ice Lake) латентность была снижена до 4–6 тактов, а пропускная способность увеличена до одного умножения за такт (при условии использования нескольких исполнительных блоков). В процессорах AMD на микроархитектуре Zen 2 и Zen 3 латентность составляет около 5 тактов.

Для сравнения, программная реализация умножения в GF(2^128) без аппаратной поддержки может занимать от 50 до 200 тактов в зависимости от используемого алгоритма (табличный метод, метод Карацубы и т.д.). Таким образом, PCLMULQDQ обеспечивает ускорение в десятки раз.

Программная поддержка

Для использования PCLMULQDQ требуется процессор с поддержкой набора инструкций AES-NI (или отдельно PCLMULQDQ). Проверка наличия инструкции выполняется с помощью команды CPUID: бит 1 регистра ECX (после вызова CPUID с входным значением EAX=1) указывает на поддержку PCLMULQDQ. В операционных системах поддержка инструкции реализуется на уровне ядра (например, в Linux через криптографический API, в Windows через CNG). Компиляторы (GCC, Clang, MSVC) предоставляют встроенные функции (intrinsics) для вызова инструкции, например _mm_clmulepi64_si128 (в заголовочном файле wmmintrin.h).

Критика и ограничения

Несмотря на высокую производительность, PCLMULQDQ имеет некоторые ограничения:

• Инструкция работает только с 64-битными операндами, что требует дополнительных операций для умножения 128-битных чисел (например, в GCM). Для полного умножения 128-битных чисел необходимо выполнить три или четыре вызова PCLMULQDQ и объединить результаты.
• Результат умножения — 128-битное число, что может быть недостаточно для некоторых приложений, требующих умножения с большей разрядностью (например, для полей GF(2^256) в эллиптической криптографии). В таких случаях требуется программная эмуляция.
• Инструкция не поддерживает операции с плавающей точкой и не является универсальной; её применение ограничено узким кругом задач.

Альтернативы

В архитектуре ARM аналогичная функциональность реализована в виде инструкций PMULL и PMULL2 (полиномиальное умножение 64-битных и 128-битных операндов) в наборе NEON. В архитектуре RISC-V подобные инструкции отсутствуют в базовом наборе, но могут быть добавлены через расширения (например, векторное расширение V). В графических процессорах (GPU) полиномиальное умножение может быть реализовано программно с использованием логических операций, но аппаратная поддержка обычно отсутствует.

Интересные факты

• Название инструкции расшифровывается как «Parallel Carry-Less MULtiply Qword» (параллельное умножение без переноса 64-битных слов). Буква «Q» обозначает «quadword» (64 бита).
• PCLMULQDQ была одной из первых инструкций, специально разработанных для ускорения криптографии с симметричным ключом на уровне процессора.
• В некоторых процессорах Intel (например, Atom) поддержка PCLMULQDQ отсутствовала в ранних моделях, что ограничивало их применение в криптографических приложениях.

Источники

• Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 2: Instruction Set Reference.
• AMD64 Architecture Programmer’s Manual, Volume 3: General-Purpose and System Instructions.
• NIST Special Publication 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC.
• Gueron, S. (2010). Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode. Intel Corporation.
• Käsper, E., & Schwabe, P. (2009). Faster and Timing-Attack Resistant AES-GCM. In: Cryptographic Hardware and Embedded Systems (CHES).