УДК 511.3, 621.391
ПОСТРОЕНИЕ СИСТЕМЫ ЗАЩИТЫ ДАННЫХ НА ОСНОВЕ ГИПЕРЭЛЛИПТИЧЕСКИХ КРИВЫХ
*,
* Калининградский государственный университет им. И. Канта
4
Проанализированы все аспекты повышения эффективности вычислений в криптосистемах, рассматривается конструкция криптосистемы, основанной на якобиане гиперэллиптической кривой. Эффективность гарантируется при помощи рекуррентных формул для разложения многочленов, представляющих дивизоры на гиперэллиптической кривой
информационная безопасность, компьютерные системы, криптографические средства защиты, локальная рабочая станция, криптоалгоритмы, эллиптические и гиперэллиптические кривые, рациональные якобианы, шифрующая и дешифрующая функции, конечные поля, редуцированные дивизоры.
Проблема обеспечения информационной безопасности может быть решена успешно только в том случае, если создана и функционирует комплексная система защиты информации, охватывающая весь жизненный цикл КС от разработки до утилизации и всю технологическую цепочку сбора, хранения, обработки и выдачи информации [1]. С этих позиций обеспечение безопасности информации в компьютерных системах (КС) сегодня рассматривается в виде единства трех компонент [2]: собственно информация; технические и программные средства; обслуживающий персонал и пользователи. В общем случае структура системы информационной безопасности в КС включает:
- Комплекс правовых норм.
- Комплекс организационных мер.
- Технические средства.
- Программные средства.
- Криптографические средства.
При решении проблемы защиты информации в КС необходимо учитывать противоречивость человеческого фактора. В частности, обслуживающий персонал и пользователи могут быть как объектом, так и источником несанкционированного воздействия на информацию. Статистика нарушений в современных информационных системах свидетельствует о том, что большинство из них совершаются на конкретном рабочем месте и приходятся на так называемых внутренних нарушителей. В этой связи одной из актуальнейших задач является построение системы защиты информации на локальной рабочей станции (ЛРС) – персональном компьютере, не подключенном (или периодически подключаемом) к каналам передачи данных.
Задача осложняется тем, что большинство ЛРС включает разнородное ПО со сложной структурой, а также аппаратную часть, реализующую большое количество функций. При этом наибольшую опасность представляют недокументированные возможности и закладки, находящиеся в ядре операционной системы.
Из сказанного выше вытекают следующие основные задачи системы защиты ЛРС:
- Разработка организационной документации.
- Обеспечение разграничения доступа к ресурсам пользователей.
- Криптографическая защита информации, хранящейся на ЛРС (конфиденциальность и целостность).
- Аутентификация пользователей и авторизация их действий.
- Обеспечение невозможности влияния программно-технического обеспечения ЛРС на регламент функционирования прикладных процессов и контроль целостности прикладного и системного ПО.
С математической точки зрения для целей криптографической защиты информации (как для практической реализации основания стойкости, так и для разработки методов их вскрытия) необходимо в первую очередь повышать эффективность следующих методов и алгоритмов:
- Алгоритмы проверки простоты целых чисел.
- Методы факторизации (методы поиска разложения целых чисел на множители).
- Вычисления, использующие эллиптические кривые над конечными полями.
- Алгоритмы дискретного логарифмирования.
- Методы разложения многочленов на множители над конечными полями и над полем рациональных чисел.
- Способы решения систем линейных уравнений над конечными полями.
- Алгоритмы полиномиальной арифметики.
Настоящая работа посвящена разработке одного из элементов криптографической подсистемы защиты информации – комплекса алгоритмов шифровки данных, основанного на гиперэллиптических кривых. Актуальность проблемы обусловлена, прежде всего, постоянно возрастающими вычислительными мощностями, посредством которых используемые в современных криптосистемах алгоритмы могут быть взломаны.
Эллиптические кривые используются для построения систем защиты информации начиная с 1985 года [3, 4, 5]. Эффективность таких систем обусловлена тем, что при обеспечении примерно одинаковой степени защиты данных в них требуется на порядок меньшая длина ключа по сравнению, например, с широко распространенной системой RSA. Кроме того, до настоящего времени не разработан эффективный алгоритм взлома таких систем. Несколько позже для аналогичных целей стали использоваться гиперэллиптические кривые [6, 7, 8].
Системы, основанные на гиперэллиптических кривых, обеспечивают, как представляется, более высокую степень защиты информации. Эффективный алгоритм взлома таких систем также неизвестен. При этом времени преобразования информации в данном случае необходимо больше, чем в случае эллиптических кривых. Отсюда вытекает, что проблема повышения вычислительной эффективности весьма актуальна, так как именно её решение может существенно расширить область применения криптосистем на гиперэллиптических кривых и перевести их из разряда теоретических изысков в плоскость практического применения. Основой структуры таких систем служат так называемые рациональные якобианы этих кривых, представляющие собой конечные абелевы группы. Единичные сообщения маркируются точками якобиана. Шифрующая и дешифрующая функция, как и в случае эллиптических кривых, представляют собой умножение точки якобиана на целое число. Анализ существующих атак выделяет класс "подходящих" гиперэллиптических кривых: число точек якобиана должно делиться на большое простое число l ~ 1040, l не должно делить qk – 1 для малых k (1 £ k £ 2000/log2q), где q – число элементов конечного поля констант, род g кривой не должен превосходить 4.
Согласно [8] мы рассматриваем гиперэллиптическую кривую C над конечным полем Fq, определяемую уравнением y2 + h(x)y = f(x), где h(x) и f(x) – многочлены степеней deg h £ g и deg f = 2g + 1; K - алгебраическое замыкание поля Fq.
Пусть P0 – фиксированная Fq-рациональная точка кривой С. Единичное сообщение исходного текста маркируется сначала целым числом m. Затем числу m сопоставляется элемент xm конечного поля Fq. Далее вычисляется ym Î Fq такой, что точка Pm = (xm, ym) лежит на кривой C. Точке Pm сопоставляется класс [Pm – P0] из рационального якобиана J(Fq) кривой. Процедура демаркировки обратна процедуре маркировки.
Шифровальный ключ есть целое число e, взаимно простое с числом точек N якобиана J(Fq). Шифрующая функция имеет вид P a eP = P + P +...+ P (всего e слагаемых), где P – точка из J(Fq). Дешифровальный ключ d есть целое такое, что ed º 1 (mod N). Дешифрующая функция имеет вид Q a dQ = Q + Q +...+ Q (всего d слагаемых), где Q Î J(Fq).
Эффективность вычислений в якобиане определяется способом представления дивизоров и их алгоритмом редукции. Всякий полуредуцированный дивизор D, представляющий точку из J(Fq), согласно [1] может быть записан в виде наибольшего общего делителя
D = å mi(ui, vi) - (å mi)¥ = НОД(div a(x), div(b(x) - y))
главных дивизоров div a(x) и div(b(x) - y), где a(x) и b(x) - многочлены над Fq; a(x) = 
. Для каждой точки Pi = (ui, vi) существует единственный многочлен bi(x) из K[x], удовлетворяющий условиям:
1) deg bi < mi;
2) bi(ui) = vi;
3) 
+ bi(x)h(x) - f(x).
Этот многочлен ищется так. Если Pi = (ui, vi) - специальная точка, то bk(x) = vi. Если Pi = (ui, vi) - обыкновенная точка, то многочлен bi(x) ищется в виде
bi(x) = c0 + c1(x - u) + c2(x - u)2 +...+ ck-1(x - u)k-1,
где k = mi. Ясно, что c0 = bi(ui) = vi. Обозначим t = x - ui. Тогда x = t + ui. Положим h(t) = h(t + ui), j(t) = f(t + ui), bi(t) = bk(t + ui). Тогда
bi(t) = c0 + c1t + c2t2 +...+ ck-1tk-1
и условие 3) можно переписать так:
.
Оно означает, что коэффициенты многочленов в левой и правой частях условия совпадают вплоть до номера k – 1. Это даёт систему уравнений для c0, c1, c2,...…, ck-1:
c1 = 
; c2 = 
; c3 = 
;
c4 = 
,
причем, если j > 4, то cj считают равными
cj = 
,
где j £ k - 1. В случае же если дивизор D редуцирован, то k - 1< g.
Если вдобавок char Fq = 2, то коэффициенты вычисляют следующим образом:
c1 = (j1 + h1c0)/h0; c2 = (j2 + h1c1 + h2c0 + 
)/h0;
c3 = (j3 + h1c2 + h2c1 + h3c0)/h0, c4 = (j4 + h1c3 + h2c2 + h3c1 + h4c0 + 
)/h0,
причем, если j > 4 и j нечётно, то cj считают равными
cj = (jj + h1cj-1 + h2cj-2 +…+ hjc0)/h0,
если j > 4 и j чётно, то
cj = (jj + h1cj-1 + h2cj-2 +…+ hjc0 + 
)/h0.
Если род g = 2, то коэффициенты вычисляют так:
c1 = (j1 + h1c0)/h0; c2 = (j2 + h1c1 + h2c0 + )/h0; c3 = (j3 + h1c2 + h2c1)/h0;
c4 = (j4 + h1c3 + h2c2 + )/h0; c5 = (1 + h1c4 + h2c3)/h0,
причем, если j > 5 и j нечётно, то cj считают равными cj = (h1cj-1 + h2cj-2)/h0, если j > 5 и j чётно, то cj = (h1cj-1 + h2cj-2 + )/h0. Если, кроме того, дивизор D редуцирован, то вычисляют только c0, c1.
Если char Fq > 2, то h(x) = 0 и, значит, h(t) = 0. Тогда коэффициенты вычисляют следующим образом:
c1 = 
; c2 = 
; c3 = 
; c4 = 
,
причем для j > 4 коэффициенты cj считают равными
cj = 
.
Если род g = 2, то deg j = deg f = 5, и коэффициенты вычисляют так:
c1 = ; c2 = ; c3 = ;
c4 = ; c5 = 
,
причем для j > 5 коэффициенты cj полагают равными
cj = 
.
Если вдобавок дивизор D редуцирован, то вычисляют только c0, c1.
По китайской теореме об остатках для многочленов ищется единственный многочлен b(x) Î K[x], degx b < å mi такой, что
b(x) º bi(x) (mod
) для всех i.
Предыдущие формулы для cj являются рекуррентными и позволяют быстро подсчитывать многочлены a(x) и b(x) в процессе их использования в алгоритмах сложения и редукции, чем достигается существенная экономия памяти. В сочетании с алгоритмами «быстрой» арифметики в конечных полях [9] их применение даёт возможность построить достаточно эффективную систему защиты данных [10].
СПИСОК ЛИТЕРАТУРЫ
1. Закон РФ от 05г. № 000-1 "О безопасности".
2. ГОСТ Р ИСО/МЭК 2 "Методы и средства обеспечения безопасности. Критерии оценки безопасности информационных технологий".
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. Патент РФ. Заявка № /09(004794) кл. H 04K 1/00, H 04L 9/30 (принято решение о выдаче).
KONSTRUCTION OF THE INFORMATION PROTECTION SYSTEM ON THE HYPERELLIPTIC CURVES BASIS
S. I. Aleshnikov, A. A. Gorbachev
In report is analyzed all aspects of the increase of efficiency of the computation in cryptosystems, considered the construction of the cryptosystem on the Jacobian of the hyperelliptic curve. Efficiency is guaranteed by means recurrent formulas for factors of the polynomials representing divisors on a hyperelliptic curve.
