Построение системы защиты данных на основе гиперэллиптических кривых

Размещено на http://www.allbest.ru/

ПОСТРОЕНИЕ СИСТЕМЫ ЗАЩИТЫ ДАННЫХ НА ОСНОВЕ ГИПЕРЭЛЛИПТИЧЕСКИХ КРИВЫХ

С.И. Алешников*, А.А. Горбачев

* Калининградский государственный университет им. И. Канта

236008, г. Калининград, ул. А. Невского, 14

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

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

- Комплекс правовых норм.

- Комплекс организационных мер.

- Технические средства.

- Программные средства.

- Криптографические средства.

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

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

Из сказанного выше вытекают следующие основные задачи системы защиты ЛРС:

- Разработка организационной документации.

- Обеспечение разграничения доступа к ресурсам пользователей.

- Криптографическая защита информации, хранящейся на ЛРС (конфиденциальность и целостность).

- Аутентификация пользователей и авторизация их действий.

- Обеспечение невозможности влияния программно-технического обеспечения ЛРС на регламент функционирования прикладных процессов и контроль целостности прикладного и системного ПО.

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

- Алгоритмы проверки простоты целых чисел.

- Методы факторизации (методы поиска разложения целых чисел на множители).

- Вычисления, использующие эллиптические кривые над конечными полями.

- Алгоритмы дискретного логарифмирования.

- Методы разложения многочленов на множители над конечными полями и над полем рациональных чисел.

- Способы решения систем линейных уравнений над конечными полями.

- Алгоритмы полиномиальной арифметики.

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

Эллиптические кривые используются для построения систем защиты информации начиная с 1985 года [3, 4, 5]. Эффективность таких систем обусловлена тем, что при обеспечении примерно одинаковой степени защиты данных в них требуется на порядок меньшая длина ключа по сравнению, например, с широко распространенной системой RSA. Кроме того, до настоящего времени не разработан эффективный алгоритм взлома таких систем. Несколько позже для аналогичных целей стали использоваться гиперэллиптические кривые [6, 7, 8].

Системы, основанные на гиперэллиптических кривых, обеспечивают, как представляется, более высокую степень защиты информации. Эффективный алгоритм взлома таких систем также неизвестен. При этом времени преобразования информации в данном случае необходимо больше, чем в случае эллиптических кривых. Отсюда вытекает, что проблема повышения вычислительной эффективности весьма актуальна, так как именно её решение может существенно расширить область применения криптосистем на гиперэллиптических кривых и перевести их из разряда теоретических изысков в плоскость практического применения. Основой структуры таких систем служат так называемые рациональные якобианы этих кривых, представляющие собой конечные абелевы группы. Единичные сообщения маркируются точками якобиана. Шифрующая и дешифрующая функция, как и в случае эллиптических кривых, представляют собой умножение точки якобиана на целое число. Анализ существующих атак выделяет класс "подходящих" гиперэллиптических кривых: число точек якобиана должно делиться на большое простое число l 10⁴⁰, l не должно делить q^k - 1 для малых k (1 k 2000/log₂q), где q - число элементов конечного поля констант, род g кривой не должен превосходить 4.

Согласно [8] мы рассматриваем гиперэллиптическую кривую C над конечным полем F_q, определяемую уравнением y² + h(x)y = f(x), где h(x) и f(x) - многочлены степеней deg h g и deg f = 2g + 1; K алгебраическое замыкание поля F_q.

Пусть P₀ - фиксированная F_q-рациональная точка кривой С. Единичное сообщение исходного текста маркируется сначала целым числом m. Затем числу m сопоставляется элемент x_m конечного поля F_q. Далее вычисляется y_m F_q такой, что точка P_m = (x_m, y_m) лежит на кривой C. Точке P_m сопоставляется класс [P_m - P₀] из рационального якобиана J(F_q) кривой. Процедура демаркировки обратна процедуре маркировки.

Шифровальный ключ есть целое число e, взаимно простое с числом точек N якобиана J(F_q). Шифрующая функция имеет вид P eP = P + P +...+ P (всего e слагаемых), где P - точка из J(F_q). Дешифровальный ключ d есть целое такое, что ed 1 (mod N). Дешифрующая функция имеет вид Q dQ = Q + Q +...+ Q (всего d слагаемых), где Q J(F_q).

Эффективность вычислений в якобиане определяется способом представления дивизоров и их алгоритмом редукции. Всякий полуредуцированный дивизор D, представляющий точку из J(F_q), согласно [1] может быть записан в виде наибольшего общего делителя

D = m_i(u_i, v_i) ( m_i) = НОД(div a(x), div(b(x) y))

главных дивизоров div a(x) и div(b(x) y), где a(x) и b(x) многочлены над F_q; a(x) = . Для каждой точки P_i = (u_i, v_i) существует единственный многочлен b_i(x) из K[x], удовлетворяющий условиям:

1) deg b_i < m_i;

2) b_i(u_i) = v_i;

3) + b_i(x)h(x) f(x).

Этот многочлен ищется так. Если P_i = (u_i, v_i) специальная точка, то b_k(x) = v_i. Если P_i = (u_i, v_i) обыкновенная точка, то многочлен b_i(x) ищется в виде

b_i(x) = c₀ + c₁(x u) + c₂(x u)² +...+ c_k1(x u)^k1,

где k = m_i. Ясно, что c₀ = b_i(u_i) = v_i. Обозначим t = x u_i. Тогда x = t + u_i. Положим (t) = h(t + u_i), (t) = f(t + u_i), _i(t) = b_k(t + u_i). Тогда

_i(t) = c₀ + c₁t + c₂t² +...+ c_k1t^k1

и условие 3) можно переписать так:

.

Оно означает, что коэффициенты многочленов в левой и правой частях условия совпадают вплоть до номера k - 1. Это даёт систему уравнений для c₀, c₁, c₂,...…, c_k1:

c₁ = ; c₂ = ; c₃ = ;

c₄ = ,

причем, если j > 4, то c_j считают равными

c_j = ,

где j k 1. В случае же если дивизор D редуцирован, то k 1< g.

Если вдобавок char F_q = 2, то коэффициенты вычисляют следующим образом:

c₁ = (₁ + ₁c₀)/₀; c₂ = (₂ + ₁c₁ + ₂c₀ + )/₀;

c₃ = (₃ + ₁c₂ + ₂c₁ + ₃c₀)/₀, c₄ = (₄ + ₁c₃ + ₂c₂ + ₃c₁ + ₄c₀ + )/₀,

причем, если j > 4 и j нечётно, то c_j считают равными

c_j = (_j + ₁c_j1 + ₂c_j2 +…+ _jc₀)/₀,

если j > 4 и j чётно, то

c_j = (_j + ₁c_j1 + ₂c_j2 +…+ _jc₀ + )/₀.

Если род g = 2, то коэффициенты вычисляют так:

c₁ = (₁ + ₁c₀)/₀; c₂ = (₂ + ₁c₁ + ₂c₀ + )/₀; c₃ = (₃ + ₁c₂ + ₂c₁)/₀;

c₄ = (₄ + ₁c₃ + ₂c₂ + )/₀; c₅ = (1 + ₁c₄ + ₂c₃)/₀,

причем, если j > 5 и j нечётно, то c_j считают равными c_j = (₁c_j1 + ₂c_j2)/₀, если j > 5 и j чётно, то c_j = (₁c_j1 + ₂c_j2 + )/₀. Если, кроме того, дивизор D редуцирован, то вычисляют только c₀, c₁.

Если char F_q > 2, то h(x) = 0 и, значит, (t) = 0. Тогда коэффициенты вычисляют следующим образом:

c₁ = ; c₂ = ; c₃ = ; c₄ = ,

причем для j > 4 коэффициенты c_j считают равными

c_j = .

Если род g = 2, то deg = deg f = 5, и коэффициенты вычисляют так:

c₁ = ; c₂ = ; c₃ = ;

c₄ = ; c₅ = ,

причем для j > 5 коэффициенты c_j полагают равными

c_j = .

Если вдобавок дивизор D редуцирован, то вычисляют только c₀, c₁.

По китайской теореме об остатках для многочленов ищется единственный многочлен b(x) K[x], deg_x b < m_i такой, что b(x) b_i(x) (mod) для всех i.

Предыдущие формулы для c_j являются рекуррентными и позволяют быстро подсчитывать многочлены a(x) и b(x) в процессе их использования в алгоритмах сложения и редукции, чем достигается существенная экономия памяти. В сочетании с алгоритмами «быстрой» арифметики в конечных полях [9] их применение даёт возможность построить достаточно эффективную систему защиты данных [10].

Список литературы

1. Закон РФ от 05.03 1992 г. № 2446-1 "О безопасности".

2. ГОСТ Р ИСО/МЭК 15408-1-2002 "Методы и средства обеспечения безопасности. Критерии оценки безопасности информационных технологий".

3. Elliptic curves in cryptography / I.F.Blake, G.Seroussi and N.P.Smart. - (London Mathematical Society Lecture Note Series; 265). Cambridge University Press, 1999.

4. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. Springer-Verlag New York, 2004.

5. Menezes A. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.

6. Frey G. Application of Arithmetical Geometry to Cryptographic Constructions. IEM Universitet GH Essen. Preprint № 2 (2000).

7.Handbook of elliptic and hyperelliptic curve cryptography / Scientific editors, Henry Cohen &Gerhard Frey. Chapman & Hall/CRC, 2006.

8. Koblitz N. Algebraic Aspects of Cryptography. Springer-Verlag, 1998.

9. Jungnickel D. Finite fields: structure and arithmetics. Mannheim; Leipzig; Wien; Zurich: BI-Wiss.-Verl., 1993.

10. Патент РФ. Заявка № 2006104426/09(004794) кл. H 04K 1/00, H 04L 9/30 (принято решение о выдаче).

Размещено на Allbest.ru