Предложения по улучшению криптографических схем с эллиптической кривой (ECC)

Suggestions for Improving Elliptic Curve Cryptographic Schemes (ECC)

Dmitry Vesyulin

Undergraduate student, Belgorod State National Research University, Russia, Belgorod

Andrey Bukhantsov

Candidate of Technical Sciences, associate Professor, Belgorod State National Research University, Russia, Belgorod

Аннотация. Аутентификация и конфиденциальность являются двумя основными аспектами криптографии. Никоим образом нельзя сказать, что сообщение полностью защищено: любая третья сторона может атаковать сообщение на любой стадии обработки. Для отправки конфиденциальных сообщений необходимо использование преобразований информации, доступных законным сторонам информационного процесса и недоступных всем остальным. Необходимо закодировать сообщение перед шифрованием в ECC. В этой статье мы использовали новый механизм для обеспечения значения k с помощью генератора PRN и значения m с помощью SHA (для использования одностороннего свойства). На основе смоделированных результатов мы получаем надежный механизм аутентификации и конфиденциальности, который в конечном итоге повышает безопасность данных.

Abstract. Authentication and privacy are two main aspects of cryptography. In no way can we say that the message is completely protected: any third party can attack the message at any stage of processing. To send confidential messages, it is necessary to use transformations of information that are accessible to the legitimate parties of the information process and inaccessible to everyone else. You must encode the message before encryption in ECC. In this article, we used a new mechanism to provide the value of k using the PRN generator and the value of m using SHA (to use the one-way property). Based on the simulated results, we get a reliable authentication and privacy mechanism that ultimately improves data security.

Ключевые слова: кодирование; декодирование; ECC; PRN; хэш-функция; точечное шифрование.

Keywords: encoding; decoding; ECC; PRN; hash function; point encryption.

Криптография с эллиптической кривой (ECC) была открыта в 1985 году Нилом Коблицем и Виктором Миллером. Криптографические схемы с эллиптической кривой представляют собой механизмы с открытым ключом, которые обеспечивают те же функциональные возможности, что и схемы RSA. Однако их безопасность основана на сложности другой задачи, а именно задачи дискретного логарифма эллиптической кривой (ECDLP). В настоящее время лучшие алгоритмы, известные для решения ECDLP, имеют полностью экспоненциальное время выполнения, в отличие от алгоритмов субэкспоненциального времени, известных для задачи целочисленной факторизации. Это означает, что желаемый уровень безопасности может быть достигнут с помощью значительно меньших ключей в системах с эллиптической кривой, чем это возможно с их аналогами RSA[1].

Преимущества, которые можно получить от ключей меньшего размера, включают скорость и эффективное использование энергии, пропускной способности и хранилища. Параметры домена - это набор предопределенных констант, которые должны быть известны всем устройствам в ECC. Генератор псевдослучайных чисел (PRNG) [2], также известный как генератор детерминированных случайных битов (DRBG), представляет собой алгоритм для генерации последовательности чисел, которая приближает свойства случайных чисел. Последовательность не является действительно случайной в том смысле, что она полностью определяется относительно небольшим набором начальных значений, называемых состоянием PRNG, которое может включать в себя действительно случайное начальное число.

Защищенный алгоритм хеширования [3] определяет четыре алгоритма - SHA-1, SHA-256, SHA-384 и SHA-512 - для вычисления сжатого представления электронных данных / сообщений. Когда сообщение любой длины <264 бит (для SHA-1 и SHA-256) или <2128 бит (для SHA-384 и SHA-512) вводится в алгоритм, результатом является выход, называемый дайджестом сообщения. Дайджесты сообщений имеют длину от 160 до 512 бит, в зависимости от алгоритма. Алгоритмы защищенного хеширования обычно используются с другими криптографическими алгоритмами, такими как алгоритмы цифровой подписи и коды аутентификации сообщений с хеш-ключами, или для генерации случайных чисел (битов).

Общее кубическое уравнение эллиптических кривых имеет вид

y²+axy+by=x³+cx²+dx+e. (1)

После преобразования уравнения (1), получаем:

y² = x³ + ax + b

Рисунок 1. Общая кривая для уравнения y² = x³ + ax + b

E_P(a, b), состоящий из всех точек (x, y), которые удовлетворяют вышеуказанному уравнению, вместе с элементом на бесконечности O. Группу можно определить на основе набора E_P(a, b) для конкретных значений a и b. Если P, Q, R являются точками на E_P(a, b), то коммутативность отношений, ассоциативность, существование единичного элемента и существование обратного - верны. Центральной проблемой для реализации ECC является проблема дискретного логарифма, которая может быть сформулирована как «сложно найти значение k такое, что Q = kP, где P и Q известны». Но «должно быть относительно легко найти Q, где k и P известны» P, Q - точки на эллиптической кривой[4].

ПРЕДЛАГАЕМЫЙ МЕТОД ДЛЯ КОДИРОВАНИЯ ПО ЭТАПАМ:

Шаг 1: Выбор эллиптической кривой E_p (a, b).

Шаг 2: Допустим, что у E есть N точек.

Шаг 3: Предположим, что наш алфавит состоит из цифр, полученных при кодировании ASCII.

Шаг 4: Это преобразует наше сообщение в серию чисел от 0 до 126.

Шаг 5: Теперь выберите вспомогательный базовый параметр, который должен быть сгенерирован генератором псевдослучайных чисел (обе стороны должны договориться об этом).

Шаг 6: Необходимо использование SHA при передаче значения m.

Шаг 7: Нужно рассчитать все возможные пары x и y, соответственно проверить x = (mk) mod p, затем x = (mk + 1) mod p… и далее найти для y.

Шаг 8: Найти такой y перед тем, как ввести x=(mk+k -1)mod p. Затем взять точку (x, y). Теперь это преобразует число m в точку на эллиптической кривой. Таким образом, все сообщение становится последовательностью точек.

ДЕКОДИРОВАНИЕ: Найти каждую точку (x, y) и задать m как наибольшее целое число, меньшее (x-1)/k. Затем точка (x, y) декодируется как символ m.

ВЫВОДЫ: Время выполнения для функций кодирования и декодирования немного увеличено по сравнению с оригинальным методом. Использование техники сжатия повышает эффективность, а также делает сообщение более безопасным. Использование PRN и SHA делает метод намного более безопасным, чем другие криптографические методы.