Моделирование и анализ аппаратных реализаций криптографических алгоритмов на основе эллиптических кривых Домаев Роман Михайлович Научный руководитель: старший преподаватель АСТАПЕНКО Г. Ф.

Актуальность 1. Широкое распространение получает электронный документооборот, неотъемлемой часть которого являются процессы аутентификации, несимметричного шифрования и цифровой подписи. 2. Вышедший в 2011 году пред стандарт СТБ П регламентирует процессы выработки и проверки цифровой подписи, а также транспорта ключа.

Актуальность 3. Для данного пред стандарта требуется апробация его реализации, а также оценка криптостойкости (математической и физической) по отношению к различного рода атакам. 4. Физическая криптостойкость – эта противодействие анализу реализаций алгоритмов по побочным каналам, а также внедряемым дефектам. 5. Для разработки контрмер против внедряемых дефектов необходимо исследовать и разработать модели дефектов.

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

Задачи 1. Программно реализовать алгоритм несимметричной шифрации криптосистемы на эллиптических кривых (СТБ , ГОСТ Р ) a)Реализовать арифметику в группе точек на эллиптической кривой; b)Реализовать арифметику больших чисел над конечным полем; c)Оценка быстродействия предложенных реализаций. 2. Исследовать и оценить уязвимость предложенных реализаций по отношению к атакам с внедрением дефектов 3. Предложить и разработать контрмеры, повышающие стойкость данных алгоритмов

Эллиптическая кривая

Групповой закон

Проблема дискретного логарифмирования

Использование скалярного произведения kP Несимметричное шифрование Электронная цифровая подпись (ЭЦП) Генерация сессионного ключа

Типичная схема процесса цифровой подписи Выбор параметров ЭК Генерация пары открытый-закрытый ключ Выполнение операции kP Провереки

Целевые криптосистемы СТБ П ГОСТ Р Два данных стандарта регламентируют способ формирования пары закрытый-открытый ключ выбор эллиптической кривой (над конечным полем по модулю большого простого числа размерности 256 бит) выбор функции хэш-преобразования инфраструктуру открытого ключа

Алгоритмическая часть Арифметика в группе точек Нахождение обратного элемента Сумма двух элементов Скалярное произведение Арифметика больших чисел в конечном поле сложение вычитание умножение инвертирование

Арифметика больших чисел в конечном поле Вычитание Сложение -Переносы между словами -Сохранение в начальном поле

Арифметика больших чисел в конечном поле Перемножение двух больших чисел Умножение по модулю Редукция

Перемножение двух больших чисел Реализован метод Каратсубы-Офмана Идея: (1) (2) (3)

Перемножение двух больших чисел Фактическое представление 256-битного числа

Редукция Для уменьшения вычислительной сложности при редуцировании выбрано простое число особого вида: Одно из так называемых чисел Мерсенна

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

Редукция Для используемого простого числа результат редукции B находится по формуле: где

Арифметика больших чисел в конечном поле Инвертирование Вычитание Сложение

Инвертирование Для поиска обратного элемента в поле простого числа используется расширенный алгоритм Евклида (позволяющий найти x и y, таки, что ax + by = d, где d = НОД(x,y)). При реализации, был использован улучшенный алгоритм, позволяющий избежать дорогостоящих операций деления.

Инвертирование Бинарный алгоритм Евклида

Арифметика в группе точек Сумма двух элементов Input: простое p > 3; коэффициенты a, b для эллиптической кривой E: y 2 = x 3 + ax + b modp; точки P 0 = (x 0, y 0 ) и P 1 = (x 1, y 1 ) на E. Output: точка P 2 := P 0 + P 1 1. If P 0 = O then output P 2 P 1 and stop 2. If P 1 = O then output P 2 P 0 and stop 3. If x 0 x 1 then 3.1 set (y 0 – y 1 ) / (x 0 – x 1 ) mod p 3.2 перейти к 7 4. If y 0 y 1 then output P 2 O and stop 5. If y 1 = 0 then output P 2 O and stop 6 Set (3 + a) / (2y 1 ) mod p 7. Set x 2 2 – x 0 – x 1 mod p 8. Set y 2 (x 1 – x 2 ) – y 1 mod p Output P 2 (x 2, y 2 ) Нахождение обратного элемента Input: : простое p > 3, P 0 = (x 0, y 0 ) на E. Output: точка P 1 := - P 0 Output P 1 (x 0, -y 0 )

Арифметика в группе точек Скалярное произведение Input целое число n и точка P на эллиптической кривой. Output: точка на эллиптической кривой nP 1. If n = 0 then output O and stop. 2. Пусть hl hl–1...h1 h0 есть двоичное представление 3n, где наибольший значащий бит hl есть 1. Пусть nl nl–1... n1 n0 есть двоичное представление n. 3. S Q. 4. Для i от l – 1 до 1 выполнять 4.1 Set S 2S 4.2 If hi = 1 and ni = 0 then compute S S + Q 4.3 If hi = 0 and ni = 1 then compute S S - Q Output S

Оценка эффективности С использование библиотеки NTL Собственная реализация Собственная реализация / NTL,% Операция Длительность выполнения, мкс Операция Длительность выполнения, мкс Скалярное умножение точки 628,1 Скалярное умножение точки в аффинных координатах 18986,03022,8 Скалярное умножение в проективных координатах 10543,81678,7

Оценка эффективности Операция Длительность выполнения, мкс Собственная реализация / NTL,% С использование библиотеки NTL Собственная реализация Умножение в конечном поле 1,8832,81744,7 Сложение в конечном поле 0,631,41223,8 Вычитание в конечном поле 0,621,46235,5 Инвертирование 0,8445,35399,3

Размер объектного кода С использование библиотеки NTL Собственная реализация Размер объектного кода, КБ

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

Атака с изменением знака (The Sign Change Attack) Одним из простых, но в тоже время весьма мощным способом защиты от атак с внедрением ошибок, является проверка на сохранении точки на эллиптической кривой. Однако такой проверкой невозможно обнаружить SCA.

Первая модель атаки hi = 1 and ni = 0 hi = 0 and ni = 1 S S - Q S S + Q hi = 0 and ni = 0 hi = 1 and ni = 1

Результат атаки k = 1 * * * 0 1 * * * * * * 0 * 0 * 1 *

Вторая модель атаки hi = 1 and ni = 0 hi = 0 and ni = 1 S S - Q S S + Q hi = 0 and ni = 0 hi = 1 and ni = 1

Результат атаки k =

Атака с изменением знака (The Sign Change Attack) В дальнейшем по набору ошибочных результатов (количество которых рассчитывается по формуле: где m – параметр, который в моем случае равняется 1, n – размер ключа в битах (256 бит) ). Таким образом в моем случае с = 2304 реализаций. Перебирая возможные случаи ошибок с вероятностью ½ можно восстановить ключ.

Контрмеры Двукратный пересчет Параллельный подсчет Контроль зависимостей Использование вспомогательной ЭК

Результаты Разработана реализация алгоритмов ECC на основе использования арифметики больших чисел с использование чисел Мерсенна. Предложена двухуровневая схема реализации метода Каратсубы –Офмана произведения больших чисел. Исследование уязвимости реализации по отношению к дефектам и выполнена оценка наиболее опасных из них. Предложена модель дефекта на основе атаки с изменением знака (SCA). Разработаны контрмеры против исследованных атак дефекта.

Спасибо за внимание!