Сочинение на тему Оптимизация и улучшение производительности алгоритма цифровой подписи эллиптических кривых (ECDSA)

Криптография имеет 2 типа: криптография с симметричным ключом и криптография с асимметричным ключом. Криптография с симметричным ключом. В криптографии с симметричным ключом обе стороны используют один и тот же ключ. Отправитель использует этот ключ и алгоритм шифрования для шифрования данных; получатель использует тот же ключ и соответствующий алгоритм дешифрования для дешифрования данных [2]. AES, DES, RC5 являются примерами криптографии с симметричным ключом. Криптография с асимметричным ключом. Асимметричная криптография, также известная как криптография с открытым ключом, использует открытый и закрытый ключи для шифрования и дешифрования данных. Ключи – это просто большие числа, которые были соединены вместе, но не идентичны (асимметрично). Одним ключом в паре можно поделиться с каждым; он называется открытым ключом.

Другой ключ в паре держится в секрете; это называется закрытый ключ. Любой из ключей может быть использован для шифрования сообщения; ключ, противоположный тому, который использовался для шифрования сообщения, используется для расшифровки [3]. ECC, DSA, ECDSA, RSA являются примерами алгоритма асимметричного ключа. II.ECC Алгоритм Криптография с эллиптической кривой (ECC) – это метод шифрования с открытым ключом, основанный на теории эллиптических кривых, который можно использовать для создания более быстрой, меньшей и более эффективной криптографической системы. ключи. ECC генерирует ключи через свойства уравнения эллиптической кривой вместо традиционного метода генерации как произведение очень больших простых чисел. Поскольку ECC помогает установить эквивалентную защиту при более низкой вычислительной мощности и использовании ресурсов аккумулятора, он широко используется для мобильных приложений [3]. ECC имеет некоторые дополнительные преимущества, такие как более компактная структура, меньшая пропускная способность и более быстрые вычисления, которые делают ECC пригодным для использования как в высокоскоростных приложениях, так и в приложениях с ограниченными ресурсами [1]. Благодаря лучшей производительности ECC эллиптическая кривая была адаптирована для нескольких криптографических схем, таких как схема согласования ключей: ECDH, схема шифрования: ECIES, схема цифровой подписи: ECDSA. Рисунок 1. показывает операцию, выполняемую на эллиптической кривой. a) Сложение: P + Q = R b) Удвоение P + P = R Рис.1 Сложение геометрии и удвоение точек эллиптической кривой [1]. Алгоритм III.ECDSA В этой статье алгоритм ECDSA используется для реализации. Алгоритм цифровой подписи эллиптической кривой (ECDSA) является аналогом алгоритма цифровой подписи эллиптической кривой (DSA). Это наиболее широко стандартизированная схема подписи на основе эллиптических кривых [1]. Алгоритм ECDSA обеспечивает высокий уровень безопасности, более быстрые вычисления и меньшую вычислительную мощность, объем памяти благодаря меньшему размеру ключа. Цифровые подписи эллиптической кривой, используемые для распространения программного обеспечения, финансовых транзакций, транспортных средств и мобильных телефонов. В данной работе использовался алгоритм цифровой подписи на основе эллиптической кривой secp256r1. Используя параметры области этой кривой, реализуется алгоритм ECDSA. Генерация пары ключей, генерация подписи и проверка подписи являются наиболее важной частью алгоритма ECDSA. 3.1. Генерация пары ключей ECDSA Прежде чем аутентификатор ECDSA сможет работать, он должен знать свой закрытый ключ.

Открытый ключ получен из закрытого ключа и параметров домена. Как следует из названия, закрытый ключ не доступен из внешнего мира. Открытый ключ, напротив, должен быть открыто доступным для чтения. На рис.2 показана генерация пары ключей [4]. Рис.2. Генерация пары ключей [4] Для этого шага требуется один генератор псевдослучайных чисел, чтобы выбрать d, и умножение одной точки для вычисления Q для большей безопасности. Для генерации ключей отправитель делает следующее: выбирает эллиптическую кривую E, определенную над Fp. Количество точек в E должно делиться на большое простое число n. Выберите генератор точек P € E (a, b) порядка n. Выберите статистически уникальное и непредсказуемое целое число d из [1, n – 1]. Вычислить точку Q = d.P Открытый ключ отправителя – Q; закрытый ключ отправителя d. 3.2. Генерация подписи ECDSA Цифровая подпись позволяет конвертировать сообщение переменной длины в дайджест сообщения фиксированной длины H (m) с использованием алгоритма безопасного хеширования. После вычисления дайджеста сообщения активируется генератор случайных чисел, чтобы обеспечить значение k для расчетов эллиптической кривой [4]. На рис.3 показан процесс генерации подписи. Рис.3. Генерация подписи [4] Подпись – это множество (r, s). Чтобы подписать сообщение m, выберите статистически уникальное и непредсказуемое целое число k из [1, n – 1]. Вычислить k.P = (x1, y1). Вычислить r = x1 mod n Вычислить e = h (m) с помощью e дайджеста сообщения и h хэш-функции Compute s = k-l. (e + d.r) мод n 3.3. ECDSA Проверка подписи Проверка подписи является аналогом вычисления подписи. Его целью является проверка подлинности сообщения с использованием открытого ключа отправителя [3]. На рис.4 показан процесс проверки подписи Рис.4. Проверка подписи [4] Чтобы проверить подпись отправителя (r, s) на m, получатель должен сравнить v и r. Если v = r, то подпись идентична, иначе она не идентична. Вычислить e = h (m) вычислить ul = es-1 mod n вычислить u2 = rs-1 mod n вычислить ul.P + u2.Q = (xl, y2) вычислить v = x2 mod n Принять подпись, если и только если v = r. Внутривенно Внедрение программного обеспечения 4.1. Алгоритм ECDSA Алгоритм ECDSA, написанный на языке C с использованием компилятора GCC Dev-C ++ 5.11, был скомпилирован и запущен. Рис.5. показан временной анализ алгоритма ECDSA. Рис.5. Тематический анализ алгоритма ECDSA. Пара ключей: открытый ключ и закрытый ключ пользователя 1 и пользователя 2, сгенерированные с использованием свойств эллиптической кривой. Использование алгоритма ECDSA хэширует данные. Хеширование, используемое для процесса цифровой подписи, когда сообщение передается через хеш-функцию, при этом закрытый ключ пользователя 1 и открытый ключ пользователя 2 генерируют подпись. Полученная подпись передается пользователю 2, где пользователь 2 проверяет подпись, используя открытый ключ пользователя 1 и закрытый ключ пользователя 2.

Полученная подпись сопоставляется с полученной подписью, и оба признаются одинаковыми, поэтому подпись идентична, если подпись не совпадает, тогда подпись не идентична. Когда при использовании одних и тех же открытых и закрытых ключей одного и того же пользователя подпись не совпадает, это означает, что алгоритм работает правильно. 4.2. Оптимизированный алгоритм ECDSA Чтобы повысить производительность алгоритма ECDSA, были изучены методы оптимизации Развертывание цикла, уменьшение прочности, движение кода, свертывание констант, распространение констант, устранение мертвого кода, удаление общих подвыражений и т. Д. В соответствии с выражением, используемым в C-коде раскрутки цикла алгоритма ECDSA и уменьшения прочности, эти два метода применили и оптимизировали C-код, который увеличивает скорость. 4.4.1 Оптимизация с использованием развёртывания цикла Развертывание цикла, также известное как разматывание цикла, представляет собой метод преобразования цикла, который пытается оптимизировать скорость выполнения программы. Это увеличивает эффективность программы и уменьшает накладные расходы цикла. Используя метод развертки цикла, два цикла развернуты по алгоритму ECDSA, так что код выполняется быстро. 4.4.2 Оптимизация с использованием снижения прочности Это метод оптимизации, при котором тип операции заменяется другим типом операции, а те операции, которые в вычислительном отношении стоят дороже, заменяются более простыми, которые имеют эквивалентный эффект. Код C алгоритма ECDSA имеет так много операций умножения, сложения, инверсии и т. Д., В которых операция сложения занимает меньше времени по сравнению с операцией умножения, следовательно, операция умножения заменяется операцией сложения. В этой статье код ECDSA C имеет 15 выражений, которые содержат операции умножения, поэтому операция умножения заменяется сложением, так что скорость выполнения кода увеличилась. Оптимизация алгоритма ECDSA с использованием методов оптимизации кода C была выполнена. Временной анализ оптимизированного алгоритма ECDSA показан на рис.6. Рис.6. Анализ времени оптимизированного алгоритма ECDSA V. Реализация аппаратного обеспечения Для реализации программного кода в аппаратном обеспечении наиболее применим инструмент синтеза высокого уровня, поскольку он преобразовал код c в аппаратное обеспечение. Синтез высокого уровня улучшил производительность и производительность системы. Оба программно реализованных C-кода алгоритма ECDSA преобразуются в аппаратные средства с использованием инструментов синтеза высокого уровня Vivado 14.4. 5.1. Шаги для инструмента и преобразования ECDSA и Оптимизированного алгоритма ECDSA из C в Verilog 1] Создайте новый проект в Vivado HLS, добавьте / удалите исходные файлы на основе C (спецификация проекта). 2] Создать решение Vivado HLS для выбранной технологии. 3] Откройте исходный код слева и напишите код ECDSA C, после чего сохраните этот файл. 4] Решение на верхней боковой вкладке и выберите запустить все активные решения. 5] В подпапке решения Verilog содержится сгенерированный аппаратный код.

Создан аппаратный код ECDSA и реализован оптимизированный алгоритм ECDSA. Virtex6 xc6vlx760-2ff1760 используется для реализации аппаратного кода на Xilinx ISE 14.5 и анализирует время выполнения ECDSA и оптимизированный алгоритм ECDSA. В таблице .1 показано время выполнения алгоритма ECDSA. Таблица 1: Время выполнения алгоритма ECDSA Время выполнения алгоритма ECDSA Неоптимизированный код 2,768 нс Оптимизированный код 2,055 нс VI. Заключение Проанализировано, что после компиляции кода C ECDSA на компиляторе GCC алгоритм работает правильно и проверяет подпись. Для повышения производительности алгоритм ECDSA оптимизируется с использованием двух методов оптимизации кода на языке C: развертывание цикла и уменьшение прочности, благодаря чему увеличивается скорость выполнения оптимизированного алгоритма. Кроме того, улучшена производительность кода C обоих алгоритмов, преобразованного в аппаратный язык с помощью инструмента Vivado HLS 2014.4.