Моделирование и анализ аппаратных реализаций криптографических алгоритмов на основе эллиптических кривых Домаев Роман Михайлович Научный руководитель: - презентация

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

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

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

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

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

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

7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24 Арифметика в группе точек Сумма двух элементов 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 )

25 Арифметика в группе точек Скалярное произведение 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

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

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

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

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

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

31 Первая модель атаки 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

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

33 Вторая модель атаки 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

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

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

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

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

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