Похожие работы
|
Нир: «Разработка программного комплекса шифрования данных, на основе использования - страница №3/4
4 Анализ методов и алгоритмов умножения точки эллиптической кривой на скаляр В последние годы интенсивно развивается и имеет важные приложения в различных областях науки и техники прикладная теория чисел. Например, в настоящее время, практически весь мировой парк средств асимметричной криптографии (алгоритмы Диффи-Хеллмана и RSA) в математическом плане основан на теоретико-числовых задачах, которые приводят к большим объемам вычислений над многоразрядными числами [46]. Для повышения качества решения задач такого рода особую актуальность имеет повышение эффективности следующих теоретико-числовых методов и алгоритмов:
При реализации этих алгоритмов требуется работа с большими числами, в большинстве современных компьютеров при обработке многоразрядных чисел используется арифметика многократной точности. Суть этого способа состоит в том, что целое число, заполняющее например 10 машинных слов в памяти компьютера, размер слова которого , имеет 100 десятичных разрядов. Однако, согласно арифметике многократной точности, это число рассматривается как 10 разрядное по основанию . То есть арифметика многократной точности представляет собой арифметику приведения по модулю [46]. Один из интересных способов кодирования информации и выполнения действий с многоразрядными числами основан на некоторых простых фактах теории чисел. Идея этого метода состоит в том, чтобы иметь несколько модулей , , …, , которые попарно взаимно просты, и оперировать не непосредственно с числами , а с его “остатками” , , ..., . Преимущество модулярного кодирования данных состоит в том, что сложение, вычитание и умножение можно выполнять за один цикл синхронизации. Для решения поставленной задачи следует разработать математический аппарат для алгоритма редукции числа по модулю . Утверждение 4.1 . Доказательство Для доказательства нам достаточно показать, что делится на . Для этого представим в виде , где и и . Рассмотрим 2 случая. 1 Случай. Если , то и следовательно делится . 2. Случай. Если , то , следовательно делится . Утверждение доказано. Решение Используя утверждение + получим Как видно из примера 2, что операция редукция по модулю при применение утверждения 2 сводится к операции сложения и вычитания. Замечание. Если число , то для вычисления операции редукция требует не больше двух сложений и одного вычитания. Предложим алгоритм сравнения чисел в представленных в двух модульной системе остаточных классов по модулям и . Алгоритм 4.1 Нахождения представления числа () Вход: Выход:
Алгоритм 4.1 основан на следующем утверждении. Утверждение 4.1 Пусть заданно число в системе остаточных классов по модулям , то тогда справедливо равенство , где Доказательство Утверждение доказано. Алгоритм 4.2 Сравнение чисел в СОК () Вход: ,, Выход: если то 1. Если то 0. Если то -1.
Алгоритм 4.3 Сложение чисел и по модулю простого числа в СОК () Вход: , , , Выход:
Else
Алгоритм 4.4 Нахождения представления числа () Вход: Выход:
Алгоритм 1.5 Умножение двух чисел и по модулю () Вход: , , , , Выход:
Утверждение 4.2 Алгоритм умножения чисел в СОК по модулю простого числа работает корректно. Доказательство Для доказательства утверждения нам необходимо показать, что при выполнении всех операций нет переполнения. Каждая из выполнимых в отдельности операций не превосходит , следовательно утверждение доказано. Алгоритм, использующий двоичное представление скаляра, это наиболее простой метод, который может использоваться для умножения точки эллиптической кривой на скаляр. Представим в двоичной системе исчисления , где . Тогда будет справедлив алгоритм. Оценка сложности алгоритма представленного на рисунке 4.1. Поскольку на каждой интеграции алгоритма производиться удвоение , то общее количество операций удвоения точки составит . Сложение точек происходит, только если на позициях двоичного представления стоят единицы. В среднем число единиц в двоичном представлении составит . Тогда количество операций, выполняемых алгоритмом составит:
где — сложность сложения двух точек, — сложность удвоения. Из этого алгоритма можно выделить три стратегии ускорения: Рисунок 4.1 – Блок-схема двоичного алгоритма вычисления Можно ускорить представление, например, использовать представление по другому основанию. Можно уменьшить количества учениц двоичного представления . Это уменьшит количество сложений в предложенном алгоритме Можно снизить сложность удвоения за счет использования более легких операций, воспользовавшись сбалансированным двоичным представлением скаляра. Среднее количество сложений может быть уменьшенным. Ранее отмечалось, что вычисление точки, обратной к данной, вычислительно просто. Этим фактом можно воспользоваться. Перейдем от просто двоичного представления к сбалансированному двоичному представлению , где . Для того чтобы получить такое представление, можно последовательно заменять встречающиеся в двоичном представлении последовательности подряд идущие единицы на . Например, Блок-схема алгоритма вычисление двоичного сбалансированного представления представлена на рисунке 4.2. Рисунок 4.2 – Блок-схема алгоритма вычисление двоичного сбалансированного представления Сбалансированное двоичное представление имеет следующее свойства: 1. Произведение двух подряд идущих символов последовательности будет нулевым. 2. Длина последовательности составляет . 3. Среднее количество единиц в векторе равно . 4. В худшем случае количество единиц составляет . Двоичное сбалансированное представление может быть подсчитано с помощью следующего алгоритма. Приведем алгоритм на рисунке 4.3, использующий сбалансированное представление скаляра для вычисления умножения точки на скаляр. Рисунок 4.3 – Блок-схема алгоритма, использующего сбалансированное представление для вычисления . Поскольку в среднем количество ненулевых символов в двоичной сбалансированной последовательности равно , то количество операций равно
Рассмотрим метод окон, схема которого приведена на рисунке 4.4: Рисунок 4.4 – Схема метода окон Последовательность длины (окна), предварительно вычислим все возможные комбинации , где . Например, пусть требуется вычислить . Представим как тогда Это представление имеет следующие свойства: 1. Длина последовательности составляет . 2. В среднем количество ненулевых элементов последовательности составляет . Необходимое количество предвычислений составляет . Сложность вычислений в среднем составляет
так как метод окна обладает свойством (2). В таблице 4.1 представлена сравнительная оценка временных показателей умножения точки эллиптической кривой на скаляр [47] при использовании различных систем счисления. (Время указано в миллисекундах) Из таблицы 4.1 следует, что самым быстрым является метод окон, но у него есть один недостаток: необходимость больших предвычислений. Метод NAF немного уступает методу окон в скорости выполнения операций, но не требует предвычислений, поэтому в случае, когда у вычислительного устройства ограничена память, целесообразно использовать метод NAF. Сравнивая в таблице 4.1 столбец где приведено время работы методов и алгоритмов работающих в позиционной системе исчисления со столбцом в СОК, замечаем, что при выполнении операций в СОК можно получать существенное преимущество в скорости вычисления в среднем на 58%.
5 Разработка алгоритма кодирования алфавита точками эллиптической кривой Большинство эллиптических криптосистем используют представление информации в виде точек на эллиптической кривой, однако, этот переход от алфавита к точкам эллиптической кривой нужно еще осуществить. Алгоритмы кодирования алфавитов делятся на вероятностные и детерминированные. Проанализируем вероятностный алгоритм кодирования алфавита точками эллиптической кривой (1.1), предложенный в 1985 году Н. Коблиц [48], блок-схема которого приведена на рисунке 5.1. Функция вычисляет корень квадратный из числа по модулю . Рисунок 5.1 – Блок-схема вероятностного алгоритма кодирования алфавита точками эллиптической кривой Рассмотрим алгоритм декодирования (рисунок 5.2). Рисунок 5.2 – Блок-схема вероятностного алгоритма декодирования символа из точки эллиптической кривой Преимущество данного алгоритма состоит в том, что для вычисления числа необходимо держать в памяти только точку и число . Недостатки алгоритма: 1. Вероятность того, что будет не закодировано равна , а при большом выборе вероятность не закодировать один из символов алфавита возрастает многократно. Например, при и вероятность не закодировать алфавит равна , то есть вероятность не закодировать алфавит больше, чем вероятность его закодировать. 2. С помощью данного алгоритма можно закодировать алфавит, мощность которого равна , что приблизительно в раз меньше, чем количество точек на эллиптической кривой, согласно теореме Хассе. Проведем анализ детерминированного алгоритма кодирования алфавитов точками эллиптических кривых, предложенного в работе [49]. Для рассмотрения детерминированного алгоритма кодирования алфавита точками эллиптической кривой введем понятие дуальных эллиптических кривых. Определение 5.1: Две эллиптические кривые:: и : , заданные над конечным полем , где — простое число, , , называются дуальными, если имеет место следующие соотношение:
где — квадратичный невычет по модулю . Для дуальных эллиптических кривых справедлива следующая теорема. Теорема 5.1 [49]: Пусть и — две дуальные эллиптические кривые над конечным полем , . Тогда
Перейдем теперь к алгоритму кодирования рисунок 5.3. Рисунок 5.3 – Блок-схема алгоритма кодирования алфавита точками эллиптической кривой Рассмотрим применения алгоритма 3 к кодированию алфавита точками эллиптических кривых из работы [50], которые рекомендованы в США. Пример 5.1. Эллиптическая кривая : задана над полем , где — простое число. Закодировать числа . Рассмотрим эллиптическую кривую : Так как — простое число вида , то является квадратичным невычетом в и, значит, . Вычислим и : Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в . Результат вычислений приведен в таблице 5.1, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Мы получили, что в строке эллиптической кривой количество плюсов равно 5, а в строке эллиптической кривой — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой . Для кодирования числа «0» воспользуемся строкой с номером 2. Этой строке соответствует точка Таким образом, «0» будет закодирован точкой . Кратко будем записывать так. Найдем . Так как , то, используя теорему 5.1, получим, что Из того, что максимальный множитель в разложении равен следует, что, используя метод Полларда, задачу дискретного логарифмирования можно решить за операций с точками на эллиптической кривой [42]. При условии, что современная техника может производить операций с точками на эллиптической кривой, то задачу дискретного логарифмирования на эллиптической кривой можно решить за 4 часа 30 минут. На основе этих данных мы можем сделать вывод, что данная эллиптическая кривая непригодна к использованию в криптографических целях. 2. Рассмотрим эллиптическую кривую : Найдем наименьший квадратичный невычет. Числа 1, 4, 9 являются квадратичными вычетами , так как представимы в виде: , , . Так как имеет вид , то из свойств символа Лежандра является квадратичным вычетом в , следовательно, и является квадратичным вычетом в . Из того, что имеет вид , следует, что 3 является квадратичным вычетом в , значит, и является квадратичным вычетом в . Вычислим символ Лежандра для чисел , , , получим: , , , следовательно, наименьшим квадратичным невычетом в , является , значит, . Найдем и : Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в . Результат вычислений представлен в таблице 5.2, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Из таблицы видно, что в строке содержится 5 плюсов, а в строке — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой . Найдем . Так как , то, используя теорему 5.1, получим, что Из того, что максимальный множитель в разложении равен , следует, что для криптосистемы, построенной на эллиптической кривой , задача дискретного логарифмирования решается методом Полларада в раз быстрее, чем для криптосистемы, построенной на эллиптической кривой . 3. Рассмотрим эллиптическую кривую : Так как — простое число вида , то является квадратичным невычетом в . Значит, Вычислим и : Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в . Результат вычислений представлен в таблице 5.3, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Из таблицы видно, что в строке содержится 5 плюсов, а в строке — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой . Найдем . Так как , то, используя теорему 5.1, получим, что Из того, что максимальный множитель в разложении равен , следует, что для криптосистемы, построенной на эллиптической кривой , задача дискретного логарифмирования методом Полларада решается в раз быстрее. 4. Рассмотрим эллиптическую кривую : Так как — простое число вида , то является квадратичным невычетом в и, значит, Вычислим и : Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в . Результат вычислений представлен в таблице 5.4, где знаком «+» обозначается квадратичный вычет в , а знаком «-» обозначается квадратичный невычет в
Из таблицы видно, что в строке содержится 6 плюсов, а в строке — 9 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой . Найдем . Так как , , то, используя теорему 5.1, получим, что Из того, что максимальный множитель в разложении равен , следует, что для криптосистемы, построенной на эллиптической кривой , задача дискретного логарифмирования методом Полларада решается за то же время, что и для криптосистемы, построенной на эллиптической кривой . 5. Рассмотрим эллиптическую кривую : Так как — простое число вида , то является квадратичным невычетом в , значит, Вычислим и : Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в . Результат вычислений представлен в таблице 5.5, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Из таблицы видно, что в строке содержится 8 плюсов, а в строке — 7 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой . Из примера 5.1 видно, что детерминированный метод кодирования алфавита точками эллиптической кривой приводит к понижению криптостойкости эллиптических кривых , и на дуальные, но не криптостойкие кривые. Кривая заменяется на криптостойкую дуальную эллиптическую кривую, а кривая остается без изменений. Из всего выше сказанного следует, что при переходе от эллиптической кривой к дуальной эллиптической кривой уменьшается криптостойкость данной криптосистемы. В связи с этим на эллиптическую кривую нужно накладывать дополнительные условия, что требует дополнительных временных затрат и ведет к увеличению времени для выбора одной кривой с нужными свойствами, что делает данный метод неудобным для частого применения. В качестве более удобной для практического применения рассмотрим эллиптическую кривую, заданную уравнением:
где , – попарно простые числа и В блок-схеме алгоритма представленного на рисунке 5.4 функция возвращает множество попарно различных простых делителей числа . Рисунок 5.4 – Блок-схема алгоритм кодирования алфавита точками эллиптической кривой, заданной уравнением (5.3) Теперь для данного алгоритма предложим алгоритм декодирования (рисунок 5.5). Функция переводит число из системы остаточных классов в десятеричную систему исчисления, где — пара чисел, представленных в системе остаточных классов, а — трехмерный массив, где каждой тройке чисел соответствует число, равное представлению восстанавливаемого числа в системе остаточных классов. Данай алгоритм при соответствующем выборе и эллиптической кривой позволяет закодировать алфавит, мощность которого равна мощности множества точек эллиптической кривой, не считая точку в бесконечность. Рисунок 5.5 – Блок-схема алгоритм декодирования алфавита из точек эллиптической кривой, заданной уравнением (2.3) Приведем пример эллиптической кривой, которая позволяет это сделать. << предыдущая страница следующая страница >> |
|