Выполнил: Скрябин Иван, 513 Научный руководитель: Сахин Ю.Х. Операции поддержки алгоритмов шифрования с открытым ключом и их реализация в микропроцессоре «Эльбрус»

Постановка задачи Развитие интернета и электронной коммерции вынуждает производителей микропроцессоров внедрять аппаратную поддержку алгоритмов шифрования: Intel (Westmere), AMD (Bulldozer) - AES VIA Padlock Security Engine - AES, SHA-1, SHA Умножение Монтгомери (поддержка шифров с открытым ключом) SPARC T3 (Криптографический ускоритель в каждом из 16 ядер) - DES, AES, Kasumi, MD5, SHA-1, SHA-256, SHA Modular Arithmetic Unit (поддержка шифров с открытым ключом) ЗАДАЧА: Предложить решение по аппаратной поддержке алгоритмов шифрования с открытым ключом в микропроцессорах «Эльбрус»

Два типа алгоритмов шифрования Шифры с секретным ключом Многочисленное повторение одного и того же набора простых операций (раундов) над блоками данных 128 / 64 / 256 бит Большое разнообразие шифров – сложно выделить общие операции, эффективней реализовывать конкретные алгоритмы Шифры с открытым ключом Сложные операции (умножение по модулю) над очень большими числами (192 – 3072 бит) В основе – операции умножения и возведения в степень по модулю EncryptDecrypt BobAlice EncryptDecrypt BobAlice

Операции в шифрах с открытым ключом RSA (1024 – 3072 бит) Генерация ключей: Выбор простых p, q. φ = (p-1) * (q-1) N = p * q (1024 – 3072 бита) Выбор e, взаимно простого с φ Вычисление d = e -1 mod φ (N, e) – открытый, (p, q, d) – секретный ключ Шифрование сообщения m (m < N) c = m e mod N Расшифровка: m = c d mod N Основные операции (A, B, M: бит) A*B mod M A B mod M ECDSA (192 – 512 бит) Операции над точками (x, y) эллипт. кривой y 2 = x 3 + a*x + b mod q Базовая точка P порядка n (n*P=0) Q=d*P : Q – открытый, d – секретный ключ Проверка подписи (r, s) сообщения m Вычислить w = s -1 mod n Вычислить u 1 = m*w, u 2 = r*w mod n Вычислить X = u 1 *P + u 2 *Q = (x 1, y 1 ) Сравнить x 1 == r mod n Основные операции (числа: 192 – 512 бит) A*B mod M A B mod M P + Q (сложение точек элл. кривой) k*Q (умножение точки на скаляр)

Арифметика в двоичном поле GF(2 n ) Стандарт DSS определяет так же операции в GF(2n), потому что они эффективно реализуются аппаратно. GF(2 n ) – конечное поле многочленов степени меньше n с коэффициентами 0 или 1 x 6 + x 4 + x 2 + x (удобное представление в виде набора бит) * Умножение (сложение XOR) Вычисление остатка по модулю (вычитание XOR) Сложение и вычитание в GF(2 n ) Вместо сложения и вычитания – операция XOR Умножение и деление в GF(2 n ) Сложение XOR

ECDSA, ECDH, ГОСТ Р ECDSA, ECDH, ГОСТ Р RSA, DSA, DH k * P P + Q Операции в шифрах с открытым ключом A B mod M A -1 mod M A * B mod M в GF(P) и GF(2 n ) - реализованные операции A, B, M, k - от 192 до 3072 бит

Умножение по модулю Требования к аппаратной реализации Масштабируемость (scalable) Возможность работы с числами «произвольного» размера – расчёт на будущее Работа в двух полях (dual-field) Поддержка операций в GF(p) и в GF(2 n ) в соответствии со стандартом США Высокая разрядность (high-radix) Разрядность функционального блока от 32 бит для повышения производительности

Умножение по модулю Алгоритм Монтгомери Ключевая идея – заменить деление на M делением на 2 n, которое легко выполняется аппаратно Mont(A, B) = A * B * 2 -n mod M Алгоритм: A, B < M < 2 n, M - нечётное M = -M -1 mod 2 n // предвычисленная константа, зависит только от M P = A * B U = P * M mod 2 n // просто оставляем первые n бит P = (P + U * M) >> n // деление на 2 n if P M then // результат в пределах 0 P < 2*M P = P – M end if

Умножение по модулю Алгоритм Монтгомери Использование умножения Монтгомери Mont(A, B) = A * B * 2 -n mod M для вычисления A * B mod M 1.Переход к представлению Монтгомери: A r = A * 2 n mod M = Mont(A, 2 2n ) B r = B * 2 n mod M = Mont(B, 2 2n ) 2.Вместо обычного умножения – умножение Монтгомери P r = Mont(A r, B r ) = (A * 2 n ) * (B * 2 n ) * 2 -n mod M = A * B * 2 n mod M 3.Возврат к обычному представлению P = Mont(P r, 1) = (A * B * 2 n ) * 1 * 2 -n = A * B Эффективен только для выполнения множества операций подряд

Умножение по модулю Аппаратная реализация алгоритма Монтгомери A, B < M < 2n, w – количество бит в слове, e = n/w – количество слов M 0 = - M[0] -1 mod 2 w 1: P = 0 2: for j = 0 to e - 1 do 3: U j = (A[0] * B[j] + P[0]) * M 0 mod 2 w 4: (C, S) = A[0] * B[j] + P[0] + M[0] * U j 5: for i = 1 to e – 1 do 6: (C, S) = C + A[i] * B[j] + P[i] + M[i] * U j 7: P[i - 1] = S 8: end for 9: P[e -1] = C 10: end for 11: if P M then // только для GF(p) 12: P = P – M 13: end if A[3]A[2]A[1]A[0] B[3]B[2]B[1]B[0] A * B * 2 -n mod M A * B[0] M * U 0 A * B[1] M * U 1 A * B[2] M * U 2 A * B[3] M * U 3 P *

Умножение по модулю Аппаратная реализация алгоритма Монтгомери A[3]A[2]A[1]A[0] B[3]B[2]B[1]B[0] A * B[0] M * U 0 A * B * 2 -n mod M * A * B[1] M * U 1 A * B[2] M * U 2 A * B[3] M * U 3 B[j]A[i] * P[i+j] ++ M[i] * U j A * B Умножение Монтгомери: Mont(A, B) = A * B * 2 -n mod M w бит – размер слова w – битный ALU ALU вычисляет в цикле A[i]B[j]P[i] w P[i+j]M[i]UjUj

Умножитель в GF(p) и GF(2 n ) Подход 1: модифицированные FA / HA FA FSELABC in S C out HA FSELAB SC out FSEL = 1 - умножение в GF(p) FSEL = 0 - умножение в GF(2 n ) ABCin CoutS ABCin CoutS ABCin CoutS ABCin CoutS ABCin CoutS ABCin CoutS ABCin CoutS ABCin CoutS 2 xor 3 xor 1 xor 2 xor 1 xor 3 xor4 xor Оптимизация дерева умножителя с учетом различия задержек по разным входам FA/HA

Умножитель в GF(p) и GF(2 n ) Подход 2: специальное построение дерева FA / HA array w2w2 sum carry FA / HA array sum carry FA / HA array sum... carry a i * b j Wallace tree Final adder Результат в GF(p)Результат в GF(2 n ) 2w - 12w

Умножитель в GF(p) и GF(2 n ) Подход 3: использование умножителя из DesignWare IP w Результат в GF(2 n ) Synopsys DesignWare DW02_mult (обычный умножитель) x AB Результат в GF(p) BA w AB Синтезируемое verilog-описание для умножителя в GF(2 n ) 2w - 12w

Умножитель в GF(p) и GF(2 n ) Сравнение подходов для умножителя 64x64 бит

Умножитель Монтгомери Базовый блок montmul_unit (64 бит) x + x + A[i]B[j]P[i] M[i] / M 0 U (C, S) = C + A[i]*B[j] + P[i] + M[i]*U P[i-1] SC precalc

MEMORY Умножитель Монтгомери Организация конвейера montmul unit FSM montmul unit FSM montmul unit FSM A[i] M[i] P[i] B[j] MEMORY result FSM стадии задержки

Умножитель Монтгомери Выбор параметров конвейера: быстродействие Две 64-битных стадии дают ускорение примерно в 4 раза для ECC и в 8 раз для RSA по сравнению с программной реализацией (все операнды на регистрах, операции в GF(p)).

Умножитель Монтгомери Выбор параметров конвейера: площадь

Вычисление «в лоб» A B mod M = A * A * A * … * A mod M [!] 2 n операций умножения по модулю если B – n-битное число Быстрое возведение в степень (Square & multiply) x 19 - ? 19 : = (2 * 2 * 2 + 1) * x 19 = (((x 2 ) 2 ) 2 * x) 2 * x В среднем n + n/2 операций умножения Вычисление обратного значения по модулю Малая теорема Ферма: A -1 mod M = A M - 2 mod M если M – простое число Возведение в степень по модулю

Сложение в группе точек на эллиптической кривой над полем GF(p) y 2 = x 3 + a*x + b mod M P = (x 1, y 1 ), Q = (x 2, y 2 ), P Q Сложение точек: P + Q = (x 3, y 3 ) λ = (y 2 – y 1 ) / (x 2 – x 1 ) mod M x 3 = λ 2 – x 1 – x 2 mod M y 3 = λ* (x 1 – x 3 ) – y 1 mod M Удвоение точки: 2*P = (x3, y3) λ = (3*x a) / (2 * y 1 ) mod M x 3 = λ 2 – x 1 mod M y 3 = λ* (x 1 – x 3 ) – y 1 mod M Операция деления (т.е. вычисления обратного по модулю) – медленная Для ускорения вычислений используются проекционные координаты

Сложение в группе точек на эллиптической кривой над полем GF(p) Проекционные координаты Переход к проекционным координатам (x, y) -> (x, y, 1) Возврат к обычному представлению (X, Y, Z) -> (X/Z 2, Y/Z 3 ) Вычисление обратного по модулю только на этапе возврата к обычному представлению Сложение точек: λ 1 = X 1 * Z 2 2 λ 2 = X 2 * Z 1 2 λ 3 = λ 1 – λ 2 λ 4 = Y 1 * Z 2 3 λ 5 = Y 2 * Z 1 3 λ 6 = λ 4 – λ 5 λ 7 = λ 1 + λ 2 λ 8 = λ 4 + λ 5 Z 3 = Z 1 *Z 2 * λ 3 X 3 = λ 6 2 – λ 7 * λ 3 2 λ 9 = λ 7 * λ 3 2 – 2 * X 3 Y 3 = (λ 9 * λ 6 – λ 8 * λ 3 3 ) / 2 Итого: 16 умножений

MEMORY Архитектура сопроцессора Montgomery Multiplier Montgomery Multiplier Adder / Subtracter MEMORY 3.1 kb data bus EC add/sub/double scalar mult EC add/sub/double scalar mult mod add/sub/mult Level 3 Level 1 mod exp Level 2 Sequencer block System interface control

Результаты работы Разработано verilog-описание и произведён синтез криптографического сопроцессора для микропроцессора «Эльбрус», позволяющего аппаратно ускорить выполнение алгоритмов шифрования с открытым ключом. Особенности: Поддержка современных алгоритмов шифрования с открытым ключом, включая алгоритмы на эллиптических кривых Масштабируемость – размеры операндов ограничены только объёмом памяти. Эффективность (умножение по модулю в 4-8 раз быстрее программной реализации) Основные характеристики: Тактовая частота 500 MHz (90nm) 3.1 kb внутренней памяти – поддержка до 4096 бит RSA и до 571 бит ECC Площадь ~ 1.2мм 2