ПОСТРОЕНИЕ КОНЕЧНЫХ ГРУПП ВЕКТОРОВ ДЛЯ СИНТЕЗА АЛГОРИТМОВ ЦИФРОВОЙ ПОДПИСИ
Построение конечных групп векторов для синтеза алгоритмов цифровой подписи
11
УДК 681.3
Л. В. ГОРТИНСКАЯ, Е. С. ДЕРНОВА, Д. Н. МОЛДОВЯН, П. А. МОЛДОВЯНУ
ПОСТРОЕНИЕ КОНЕЧНЫХ ГРУПП ВЕКТОРОВ ДЛЯ СИНТЕЗА АЛГОРИТМОВ ЦИФРОВОЙ ПОДПИСИ
Рассматривается задача построения конечных коммутативных и некоммутативных групп m-размерных векторов, содержащих подгруппы простого порядка большого размера, а также построения алгоритмов цифровой подписи на их основе.
Ключевые слова: конечные группы m-размерных векторов, электронная цифровая подпись, криптографические алгоритмы.
Введение. Для придания юридической силы электронным документам применяется электронная цифровая подпись (ЭЦП). Алгоритмы, используемые при создании ЭЦП, основаны на вычислительно сложных задачах с применением конечных алгебраических структур с ассоциативной операцией [1, 2]. При построении схем ЭЦП наиболее часто используется задача дискретного логарифмирования (ЗДЛ) в мультипликативных группах большого простого порядка, содержащихся в конечных простых полях Галуа порядка р, GF(p), или расширенных — GF(pm). При этом в качестве простого поля GF(p) используется кольцо Zp, где p — простое число большого размера, а в качестве расширенного GF(pm) — конечные поля многочленов (m — натуральное число). Для обоих типов полей были предложены методы решения ЗДЛ, имеющие субэкспоненциальную сложность, в соответствии с ними для обеспечения достаточной стойкости алгоритмов ЭЦП требуется использовать поля GF(p) и GF(pm) размером порядка 1024 бит и более, что ограничивает производительность процедур.
Более высокую производительность обеспечивают алгоритмы ЭЦП, основанные на применении конечных групп точек эллиптической кривой (ЭК), групповой операцией в которых является операция сложения (композиции) точек. Для решения ЗДЛ на эллиптической кривой известны только методы, имеющие экспоненциальную сложность, благодаря чему возможно использовать ЭК с точкой (x, y), длина x—y лежит в пределах 160—320 бит. Однако возрастание производительности в случае применения ЭК ограничено тем, что операция композиции точек в качестве составного элемента включает вычисление обратных значений в конечном поле, над которым задана ЭК [3—5].
Недавно в качестве примитивов алгоритмов ЭЦП были предложены конечные коммутативные группы и поля, формируемые в векторных пространствах, в которых определяется специальная операция умножения [6]. В этой работе показано, что при соответствующих параметрах конечное векторное пространство является конечным полем, содержащим подгруппы достаточно простого порядка, размер которого близок к размеру порядка группы. Однако вопрос формирования нециклических подгрупп векторов, содержащих подгруппы большого простого порядка, остался открытым. Также не был рассмотрен вопрос формирования некоммутативных конечных групп векторов, представляющих интерес для синтеза алгоритмов ЭЦП.
В настоящей работе рассматривается построение нециклических групп векторов, содержащих подгруппы большого простого порядка, а также некоммутативных конечных групп векторов. Интерес к конечным группам векторов обусловлен тем, что в них сложность ЗДЛ представляется более высокой, поскольку элементы задачи не могут быть представлены в виде степеней некоторого фиксированного элемента.
Определение операции умножения в конечном векторном пространстве. Конечное векторное пространство представляет собой множество элементов (векторов) вида
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
12 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
ae + bi + … + cj, где a, b, …, c — координаты, являющиеся элементами конечного простого
поля GF(p); e, i, … j — базисные векторы, которые могут быть представлены также в виде
набора координат (a, b, …, c). Операция сложения векторов может быть представлена сле-
дующей формулой:
(ae + bi + … + cj) + (xe + yi + … + zj) = (a + x)e + (b + y)i + … + (c + z)j.
В настоящей работе рассматривается задача построения мультипликативных групп век-
торов, различающихся видами операции умножения. Все варианты операции умножения оп-
ределяются в соответствии с работой [6] по общему правилу умножения каждой компоненты
первого вектора-сомножителя на каждую компоненту второго вектора-сомножителя с сохра-
нением в общем случае порядка следования перемноженных компонент. Произведения двух
базисных векторов заменяются на вектор γv, где γ ∈ GF(p) и v ∈ {e, i, …, j}. Конкретному ви-
ду операции умножения свойствен конкретный вид такой подстановки. Формальное пред-
ставление умножения следующее:
(ae + bi + … + cj) (xe + yi + … + zj) = axee + ayei + …
+ azej + … + bxie + byii + … + bzij + … + cxje + cyji + … + czjj,
где каждое из произведений ee, ei, ej, ie, ii, …, ij, …, je, ji, …, jj следует заменить на значение γv,
задаваемое таблицей умножения базисных векторов (ТУБВ). Конкретный вариант этой таб-
лицы определяется конкретным вариантом операции умножения m-мерных векторов. После
выполнения указанной подстановки получается некоторая сумма однокомпонентных векто-
ров. Синтез ТУБВ выполняется таким образом, чтобы операция умножения векторов была
ассоциативной и коммутативной для формирования коммутативных групп векторов или не-
коммутативной — для формирования некоммутативных групп векторов.
Таблицы умножения базисных векторов. В данной работе рассматривается построе-
ние мультипликативных групп в векторном пространстве, заданном не над Zp, а над конеч-
ным кольцом Zn, где n = kp, k — простое число. При этом операции сложения и умножения координат векторов и коэффициентов растяжения, фигурирующие в определении операции
умножения векторов, рассматриваются в кольце Zn. Для случаев m = 5 и 7 правила умножения базисных векторов могут быть заданы табл. 1 и 2.
Данные ТУБВ определяют для произвольных комбинаций значений коэффициентов растя-
жения ε, µ, τ, λ ∈ Zn операцию умножения, обладающую свойствами ассоциативности и коммутативности.
Таблица 1
‘Операция умножения
‘e
‘i
‘j
‘k ‘u
‘e ‘e ‘i ‘j ‘k ‘u
‘i ‘i ελj εµk ελu εµτλe
‘j
‘j εµk
εµu εµτλe µτi
‘k
‘k ελu εµτλe τλi
τλj
‘u
‘u εµτλe
µτi
τλj µτk
Операция умножения
‘e ‘i ‘j ‘k ‘u ‘v ‘w
‘e
‘e ‘i ‘j ‘k ‘u ‘v ‘w
‘i
‘i λεj λεk τεu λεv λεw τλεµτe
‘j
‘j λεk τεu τεv λεw τλεµe τµk
‘k
‘k τεu τεv τεw τλεµe τµi τµj
‘u
‘u λεv λεw τλεµe λµv λµj λµk
‘v
‘v λεw τλεµe τµi λµj λµk τµu
Таблица 2
‘w
‘w τλεµe τµk
τµj λµk τµu τµv
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Построение конечных групп векторов для синтеза алгоритмов цифровой подписи
13
Синтез коммутативных групп, содержащих подгруппы с большим размером про-
стого порядка. Рассмотрим подмножество {Z} m-мерных ненулевых векторов, координаты
которых являются элементами кольца Zn, где n = kp, p >> k, причем значение коэффициента при базисном векторе не делится на k, µ=τ–λ=1, число k делит число ε. Операцию умножения
векторов зададим по общей схеме с использованием табл. 1, 2. Легко видеть, что такая опера-
ция умножения, выполняемая над двумя векторами из рассматриваемого подмножества, дает
в результате вектор, принадлежащий этому же множеству. Мощность рассматриваемого под-
множества равна
#{Z} = p(k − 1)(kp)m − 1, где p(k − 1) — число возможных значений первой координаты, а (kp)m − 1 — число возможных
комбинаций значений остальных координат. Совокупность всех векторов Z, для которых существует обратный вектор Z−1, будет образовывать группу, порядок которой равен
Ω = #{Z} − #{N},
где {N} — совокупность всех векторов, принадлежащих подмножеству {Z}, для которых не
существует обратных значений. Определим мощность {N}. Векторы, для которых нет обрат-
ных значений, имеют следующий вид:
N = (q1 p, q2 p, …, qm p),
где q1 ∈ {1, 2, …, k − 1} и q2, q3, …, qm ∈ {0, 1, 2, …, k − 1} (нулевой вектор не входит в подмножество {Z}). Легко показать, что для таких векторов отсутствуют обратные значения.
Действительно, из определенной операции умножения непосредственно вытекает, что у век-
тора V = NX для произвольного вектора X каждая из координат делится на p, следовательно,
V не может быть единичным вектором (1, 0, 0, …, 0). Число векторов N равно #{N} = (k − 1)km − 1, следовательно, порядок рассматриваемой группы векторов не превышает
Ω = p(k − 1)(kp)m − 1 − (k − 1)km − 1 = (k − 1)km − 1(pm − 1).
Это значение достигается, если m делит p − 1, а ε является невычетом степени m по мо-
дулю p. Покажем, что это действительно так. Рассмотрим некоторый вектор Z = (a, b, ..., c),
принадлежащий множеству {Z}. Перейдем от вектора Z к вектору Z′ = (a′, b′, ..., c′), где
a′ = a mod p, b′ = b mod p, ..., c′ = c mod p. Вектор Z′ принадлежит при заданных условиях к векторному полю GF(pm) [6]. Поскольку Z′ ≠ ( 0, 0, …, 0), то в векторном поле GF(pm) относи-
тельно неизвестного вектора X′ существует решение уравнения Z′X′ = E, где E = (1,0,…,0).
Координаты вектора X′ = (x′, y′, .., z′) удовлетворяют системе сравнений следующего вида:
f11 (a′, b′,..., c′)x′ + f12 (a′,b′,..., c′) y′ + ... + f1m (a′,b′,..., c′)z′ = 1, ⎫
f21 (a′,b′,..., c′)x′ +
f22 (a′,b′,..., c′) y′ + ... + ......
f2m (a′,b′,..., c′)z′
=
0, ⎪⎪ ⎬ ⎪
fm1 (a′,b′,..., c′)x′ + fm2 (a′,b′,..., c′) y′ + ... + fmm (a′,b′,..., c′)z′ = 0.⎪⎭
В данной системе коэффициенты ftl при неизвестных x′, y′, ..., z′ определяются коэффициентами растяжения и координатами вектора Z′. Известно, что если обе части сравнения и
модуль делятся на одно и то же целое число, то обе части сравнения и модуль можно разде-
лить на это число, получив в результате эквивалентное сравнение (см. [7], теорема 128). За-
менив в этой системе сравнений a′ на a, b′ на b, ..., c′ на c и умножив левую и правую части
каждого сравнения и модуль на число t, получим систему сравнений, эквивалентную исход-
ной. В векторном множестве {Z} полученной системе соответствует векторное уравнение
ZX = E′, где E′ = (t,0,…,0) = tE. Очевидно, что вектор X = (tx′, ty′, .., tz′) = tX′ является реше-
нием последнего уравнения, которое можно представить в виде tZX′ = tE, откуда следует
ZX′ = E, т.е. X′ является вектором, обратным Z. Таким образом, при m⏐(p − 1) и ε, являю-
щемся невычетом степени m по модулю p, всем векторам множества {Z}, кроме векторов
вида N, можно поставить в соответствие единственный обратный вектор, что и требовалось
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
14 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
доказать. Теоретически определенное значение Ω = (t− 1)t m − 1(pm − 1) подтверждается вычис-
лительным экспериментом.
При простом значении m, таком, что m⏐(p − 1), значение p можно выбрать таким образом, что множитель q = m−1(pm − 1 + pm − 1 +…+ p + 1), содержащийся в разложении числа
pm − 1, будет простым. Некоторые конкретные варианты таких значений p приведены в табл. 3
(знак „\“ обозначает перенос записи числа на другую строку). Таким образом, построенная
нами группа векторов содержит подгруппу простого порядка длиной |q| в двоичном представ-
лении: |q| = (m − 1)|p| − |m| ≈ (m − 1)|p|. Для построения алгоритмов ЭЦП требуется использо-
вать подгруппы простого порядка q размером не менее |q| ≥ 160 бит. Для этой цели следует
выбрать простое число p размером |p| при условии
|
p
|
≥
|
q|−|m m −1
|
≈
|q| m −1
(бит).
Для синтеза алгоритмов ЭЦП удобно использовать кольца размерностъю m ∈ {3, 5, 7,
11, 13, 17, 19}. При выборе конкретных значений m и k следует учитывать требования к про-
изводительности алгоритмов ЭЦП, вариант реализации и обеспечиваемый уровень стойкости.
Для синтеза ТУБВ, соответствующих случаям m = 3, 11, 13, 17, 19, можно воспользоваться
результатами работ [6, 8].
Таблица 3
mp
q = m − 1(pm − 1 + pm − 1 +…+ p + 1)
5 731 347 069 147
286 084 350 321 693 088 102 651 075 474 527 140 170 997 913 161
5 50 676 921 106 512 713
6 595 396 132 044 187 165 178 914 150 733 683 078 979 644 173 924 260 \
305 243 710 080 341
7 186 419 693
41 971 136 855 362 349 259 612 655 092 913 923 374 434 953 935 443
11 34 919
2 695 444 645 954 794 709 894 042 480 955 311 929 186 425 401
13 8693
186 245 641 178 891 833 068 301 313 943 899 460 753 528 874 501
Построение некоммутативных групп векторов. Некоммутативные группы векторов,
заданных над простым полем GF(p) и имеющих размерность m = 4, были построены путем
задания операции умножения по табл. 4. В построенных группах для произвольных ненуле-
вых значений коэффициентов A, B и C максимальное значение порядка векторов равно
Ωmax = p(p − 1)(p + 1).
Таблица 4
Операция умножения
:e
:i
:j
:k
:e :e :i :j :k
:i
:i
−ACe
Ak
−Cj
:j
:j
−Ak −ABe
Bi
:k :k Cj −Bi −BCe
Для синтеза алгоритмов ЭЦП представляет интерес выбор простого числа p, при котором p + 1 = 2q, а также использование циклической подгруппы порядка q. Например, при p = 87 049 239 434 461, A = 1, B = 2 и C = 3 вектор G = (12 051 687 713 738, 12 743 450 807 620, 58 233 746 685 306, 75 018 447 720 758) имеет простой порядок q = 43 524 619 717 231.
Синтез алгоритмов ЭЦП на основе циклических подгрупп достаточно большого простого порядка, содержащихся в группах многомерных векторов, может быть выполнен по аналогии с алгоритмами [9, 10], построенными с учетом сложности задачи дискретного логарифмирования в конечном простом поле. Рассмотрим возможный вариант обобщенной схе-
мы ЭЦП, предположим, что в нем используется циклическая группа векторов Γ, имеющая
достаточно большой порядок q (|q| ≥ 160 бит). Например, в качестве Γ может быть использована подгруппа максимального простого порядка, содержащаяся в векторной группе, заданной над кольцом Zn, где n = kp, k = 8693 и p = 50 676 921 106 512 713 (см. табл. 3), или под-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Построение конечных групп векторов для синтеза алгоритмов цифровой подписи
15
группа порядка q в некоммутативной группе, построенной в предыдущем разделе. При ука-
занных параметрах кольца Zn в группе векторов содержится подгруппа простого порядка, размер которой превышает 200 бит.
Подписывающий формирует свой открытый ключ Y в виде вектора Y = Gx, где G —
вектор, являющийся генератором группы Γ. Формирование подписи к сообщению M выполняется следующим образом:
1) выбрать случайное число k < q и вычислить вектор R = Gk; 2) используя некоторую криптографически стойкую хэш-функцию Fh, вычислить хэшкод h от сообщения M с присоединенным к нему вектором R: h = Fh(M, R). Значение h будет первым элементом ЭЦП; 3) вычислить второй элемент ЭЦП: s = xh + t mod q. Проверка подлинности подписи (h, s) состоит в следующем: 1) вычисляется вектор R′ = Y q − h G s;
2) вычисляется значение h′ = Fh(M, R′); 3) сравниваются значения h′ и h; если h′ = h, то ЭЦП признается подлинной.
Заключение. Построены конечные коммутативные нециклические группы векторов, содержащие подгруппы простого порядка большого размера, и конечные некоммутативные группы, перспективные для применения в алгоритмах ЭЦП и открытого распределения ключей. Для случаев пяти- и семимерных векторов предложены таблицы умножения базисных векторов, содержащие четыре независимых коэффициента растяжения. Особенностью построенных коммутативных групп является то, что координаты векторов являются элементами
конечного кольца Zkp. При соответствующем выборе конкретных значений p в нециклической группе содержится подгруппа простого порядка длиной (m − 1)|p| − |m| бит. Некоммутативная группа построена для случая четырехмерных векторов, заданных над простым конечным полем. На основе построенных групп векторов могут быть разработаны алгоритмы ЭЦП, обладающие высокой производительностью.
Для дальнейших исследований интерес представляет разработка некоммутативных групп векторов для случаев m = 6, 8 и 16 и синтез криптоалгоритмов с открытым ключом на основе сложности вычисления сопрягающего элемента [11] в некоммутативных конечных группах векторов.
Работа поддержана грантом РФФИ № 08-07-00096-а.
СПИСОК ЛИТЕРАТУРЫ
1. Венбо Мао. Современная криптография. Теория и практика. М.—СПб—Киев: Изд. дом „Вильямс“, 2005. 763 с.
2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. М.: ТРИУМФ, 2002. 816 с.
3. Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2006. 324 с.
4. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006. 274 с.
5. Koblitz N. A Course in Number Theory and Cryptography. Berlin: Springer-Verlag, 2003. 236 p.
6. Молдовян Н.А. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах // Автоматика и телемеханика. 2008. № 12. С. 163—177.
7. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966. 384 с.
8. Молдовян Д. Н., Молдовяну П. А. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. № 3(82). С. 12—17.
9. Молдовян Н. А. Практикум по криптосистемам с открытым ключом. СПб: БХВ-Петербург, 2007. 298 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
16 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
10. Menezes A. J., Van Oorschot P. C., and Vanstone S. A. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1997. 780 p.
11. Ko K. H., Lee S. J., Cheon J. H., Han J. W., Kang J.-S., Park Ch. New Public Key Cryptosystems Using Braid Groups // Advances in cryptology — CRYPTO 2000. Proc. Springer-Verlag LNCS. 2000. Vol. 1880. P. 166—183.
Сведения об авторах
Лидия Вячеславовна Гортинская — Научно-исследовательский институт „Вектор“, Санкт-Петербург;
старший научный сотрудник; E-mail: lydia-gort@mail.ru
Евгения Сергеевна Дернова
— аспирант; Санкт-Петербургский государственный электротехнический
университет „ЛЭТИ“, кафедра автоматизированных систем обработки
информации и управления; E-mail: evgeshka19@mail.ru
Дмитрий Николаевич Молдовян — Санкт-Петербургcкий институт информатики и автоматизации РАН;
младший научный сотрудник; E-mail: mnd.spectr@mail.ru
Петр Андреевич Молдовяну
— Научно-исследовательский институт „Вектор“, Санкт-Петербург; на-
чальник службы главного метролога; E-mail: nmold@mail.ru
Рекомендована НИИ „Вектор“
Поступила в редакцию 12.10.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
11
УДК 681.3
Л. В. ГОРТИНСКАЯ, Е. С. ДЕРНОВА, Д. Н. МОЛДОВЯН, П. А. МОЛДОВЯНУ
ПОСТРОЕНИЕ КОНЕЧНЫХ ГРУПП ВЕКТОРОВ ДЛЯ СИНТЕЗА АЛГОРИТМОВ ЦИФРОВОЙ ПОДПИСИ
Рассматривается задача построения конечных коммутативных и некоммутативных групп m-размерных векторов, содержащих подгруппы простого порядка большого размера, а также построения алгоритмов цифровой подписи на их основе.
Ключевые слова: конечные группы m-размерных векторов, электронная цифровая подпись, криптографические алгоритмы.
Введение. Для придания юридической силы электронным документам применяется электронная цифровая подпись (ЭЦП). Алгоритмы, используемые при создании ЭЦП, основаны на вычислительно сложных задачах с применением конечных алгебраических структур с ассоциативной операцией [1, 2]. При построении схем ЭЦП наиболее часто используется задача дискретного логарифмирования (ЗДЛ) в мультипликативных группах большого простого порядка, содержащихся в конечных простых полях Галуа порядка р, GF(p), или расширенных — GF(pm). При этом в качестве простого поля GF(p) используется кольцо Zp, где p — простое число большого размера, а в качестве расширенного GF(pm) — конечные поля многочленов (m — натуральное число). Для обоих типов полей были предложены методы решения ЗДЛ, имеющие субэкспоненциальную сложность, в соответствии с ними для обеспечения достаточной стойкости алгоритмов ЭЦП требуется использовать поля GF(p) и GF(pm) размером порядка 1024 бит и более, что ограничивает производительность процедур.
Более высокую производительность обеспечивают алгоритмы ЭЦП, основанные на применении конечных групп точек эллиптической кривой (ЭК), групповой операцией в которых является операция сложения (композиции) точек. Для решения ЗДЛ на эллиптической кривой известны только методы, имеющие экспоненциальную сложность, благодаря чему возможно использовать ЭК с точкой (x, y), длина x—y лежит в пределах 160—320 бит. Однако возрастание производительности в случае применения ЭК ограничено тем, что операция композиции точек в качестве составного элемента включает вычисление обратных значений в конечном поле, над которым задана ЭК [3—5].
Недавно в качестве примитивов алгоритмов ЭЦП были предложены конечные коммутативные группы и поля, формируемые в векторных пространствах, в которых определяется специальная операция умножения [6]. В этой работе показано, что при соответствующих параметрах конечное векторное пространство является конечным полем, содержащим подгруппы достаточно простого порядка, размер которого близок к размеру порядка группы. Однако вопрос формирования нециклических подгрупп векторов, содержащих подгруппы большого простого порядка, остался открытым. Также не был рассмотрен вопрос формирования некоммутативных конечных групп векторов, представляющих интерес для синтеза алгоритмов ЭЦП.
В настоящей работе рассматривается построение нециклических групп векторов, содержащих подгруппы большого простого порядка, а также некоммутативных конечных групп векторов. Интерес к конечным группам векторов обусловлен тем, что в них сложность ЗДЛ представляется более высокой, поскольку элементы задачи не могут быть представлены в виде степеней некоторого фиксированного элемента.
Определение операции умножения в конечном векторном пространстве. Конечное векторное пространство представляет собой множество элементов (векторов) вида
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
12 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
ae + bi + … + cj, где a, b, …, c — координаты, являющиеся элементами конечного простого
поля GF(p); e, i, … j — базисные векторы, которые могут быть представлены также в виде
набора координат (a, b, …, c). Операция сложения векторов может быть представлена сле-
дующей формулой:
(ae + bi + … + cj) + (xe + yi + … + zj) = (a + x)e + (b + y)i + … + (c + z)j.
В настоящей работе рассматривается задача построения мультипликативных групп век-
торов, различающихся видами операции умножения. Все варианты операции умножения оп-
ределяются в соответствии с работой [6] по общему правилу умножения каждой компоненты
первого вектора-сомножителя на каждую компоненту второго вектора-сомножителя с сохра-
нением в общем случае порядка следования перемноженных компонент. Произведения двух
базисных векторов заменяются на вектор γv, где γ ∈ GF(p) и v ∈ {e, i, …, j}. Конкретному ви-
ду операции умножения свойствен конкретный вид такой подстановки. Формальное пред-
ставление умножения следующее:
(ae + bi + … + cj) (xe + yi + … + zj) = axee + ayei + …
+ azej + … + bxie + byii + … + bzij + … + cxje + cyji + … + czjj,
где каждое из произведений ee, ei, ej, ie, ii, …, ij, …, je, ji, …, jj следует заменить на значение γv,
задаваемое таблицей умножения базисных векторов (ТУБВ). Конкретный вариант этой таб-
лицы определяется конкретным вариантом операции умножения m-мерных векторов. После
выполнения указанной подстановки получается некоторая сумма однокомпонентных векто-
ров. Синтез ТУБВ выполняется таким образом, чтобы операция умножения векторов была
ассоциативной и коммутативной для формирования коммутативных групп векторов или не-
коммутативной — для формирования некоммутативных групп векторов.
Таблицы умножения базисных векторов. В данной работе рассматривается построе-
ние мультипликативных групп в векторном пространстве, заданном не над Zp, а над конеч-
ным кольцом Zn, где n = kp, k — простое число. При этом операции сложения и умножения координат векторов и коэффициентов растяжения, фигурирующие в определении операции
умножения векторов, рассматриваются в кольце Zn. Для случаев m = 5 и 7 правила умножения базисных векторов могут быть заданы табл. 1 и 2.
Данные ТУБВ определяют для произвольных комбинаций значений коэффициентов растя-
жения ε, µ, τ, λ ∈ Zn операцию умножения, обладающую свойствами ассоциативности и коммутативности.
Таблица 1
‘Операция умножения
‘e
‘i
‘j
‘k ‘u
‘e ‘e ‘i ‘j ‘k ‘u
‘i ‘i ελj εµk ελu εµτλe
‘j
‘j εµk
εµu εµτλe µτi
‘k
‘k ελu εµτλe τλi
τλj
‘u
‘u εµτλe
µτi
τλj µτk
Операция умножения
‘e ‘i ‘j ‘k ‘u ‘v ‘w
‘e
‘e ‘i ‘j ‘k ‘u ‘v ‘w
‘i
‘i λεj λεk τεu λεv λεw τλεµτe
‘j
‘j λεk τεu τεv λεw τλεµe τµk
‘k
‘k τεu τεv τεw τλεµe τµi τµj
‘u
‘u λεv λεw τλεµe λµv λµj λµk
‘v
‘v λεw τλεµe τµi λµj λµk τµu
Таблица 2
‘w
‘w τλεµe τµk
τµj λµk τµu τµv
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Построение конечных групп векторов для синтеза алгоритмов цифровой подписи
13
Синтез коммутативных групп, содержащих подгруппы с большим размером про-
стого порядка. Рассмотрим подмножество {Z} m-мерных ненулевых векторов, координаты
которых являются элементами кольца Zn, где n = kp, p >> k, причем значение коэффициента при базисном векторе не делится на k, µ=τ–λ=1, число k делит число ε. Операцию умножения
векторов зададим по общей схеме с использованием табл. 1, 2. Легко видеть, что такая опера-
ция умножения, выполняемая над двумя векторами из рассматриваемого подмножества, дает
в результате вектор, принадлежащий этому же множеству. Мощность рассматриваемого под-
множества равна
#{Z} = p(k − 1)(kp)m − 1, где p(k − 1) — число возможных значений первой координаты, а (kp)m − 1 — число возможных
комбинаций значений остальных координат. Совокупность всех векторов Z, для которых существует обратный вектор Z−1, будет образовывать группу, порядок которой равен
Ω = #{Z} − #{N},
где {N} — совокупность всех векторов, принадлежащих подмножеству {Z}, для которых не
существует обратных значений. Определим мощность {N}. Векторы, для которых нет обрат-
ных значений, имеют следующий вид:
N = (q1 p, q2 p, …, qm p),
где q1 ∈ {1, 2, …, k − 1} и q2, q3, …, qm ∈ {0, 1, 2, …, k − 1} (нулевой вектор не входит в подмножество {Z}). Легко показать, что для таких векторов отсутствуют обратные значения.
Действительно, из определенной операции умножения непосредственно вытекает, что у век-
тора V = NX для произвольного вектора X каждая из координат делится на p, следовательно,
V не может быть единичным вектором (1, 0, 0, …, 0). Число векторов N равно #{N} = (k − 1)km − 1, следовательно, порядок рассматриваемой группы векторов не превышает
Ω = p(k − 1)(kp)m − 1 − (k − 1)km − 1 = (k − 1)km − 1(pm − 1).
Это значение достигается, если m делит p − 1, а ε является невычетом степени m по мо-
дулю p. Покажем, что это действительно так. Рассмотрим некоторый вектор Z = (a, b, ..., c),
принадлежащий множеству {Z}. Перейдем от вектора Z к вектору Z′ = (a′, b′, ..., c′), где
a′ = a mod p, b′ = b mod p, ..., c′ = c mod p. Вектор Z′ принадлежит при заданных условиях к векторному полю GF(pm) [6]. Поскольку Z′ ≠ ( 0, 0, …, 0), то в векторном поле GF(pm) относи-
тельно неизвестного вектора X′ существует решение уравнения Z′X′ = E, где E = (1,0,…,0).
Координаты вектора X′ = (x′, y′, .., z′) удовлетворяют системе сравнений следующего вида:
f11 (a′, b′,..., c′)x′ + f12 (a′,b′,..., c′) y′ + ... + f1m (a′,b′,..., c′)z′ = 1, ⎫
f21 (a′,b′,..., c′)x′ +
f22 (a′,b′,..., c′) y′ + ... + ......
f2m (a′,b′,..., c′)z′
=
0, ⎪⎪ ⎬ ⎪
fm1 (a′,b′,..., c′)x′ + fm2 (a′,b′,..., c′) y′ + ... + fmm (a′,b′,..., c′)z′ = 0.⎪⎭
В данной системе коэффициенты ftl при неизвестных x′, y′, ..., z′ определяются коэффициентами растяжения и координатами вектора Z′. Известно, что если обе части сравнения и
модуль делятся на одно и то же целое число, то обе части сравнения и модуль можно разде-
лить на это число, получив в результате эквивалентное сравнение (см. [7], теорема 128). За-
менив в этой системе сравнений a′ на a, b′ на b, ..., c′ на c и умножив левую и правую части
каждого сравнения и модуль на число t, получим систему сравнений, эквивалентную исход-
ной. В векторном множестве {Z} полученной системе соответствует векторное уравнение
ZX = E′, где E′ = (t,0,…,0) = tE. Очевидно, что вектор X = (tx′, ty′, .., tz′) = tX′ является реше-
нием последнего уравнения, которое можно представить в виде tZX′ = tE, откуда следует
ZX′ = E, т.е. X′ является вектором, обратным Z. Таким образом, при m⏐(p − 1) и ε, являю-
щемся невычетом степени m по модулю p, всем векторам множества {Z}, кроме векторов
вида N, можно поставить в соответствие единственный обратный вектор, что и требовалось
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
14 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
доказать. Теоретически определенное значение Ω = (t− 1)t m − 1(pm − 1) подтверждается вычис-
лительным экспериментом.
При простом значении m, таком, что m⏐(p − 1), значение p можно выбрать таким образом, что множитель q = m−1(pm − 1 + pm − 1 +…+ p + 1), содержащийся в разложении числа
pm − 1, будет простым. Некоторые конкретные варианты таких значений p приведены в табл. 3
(знак „\“ обозначает перенос записи числа на другую строку). Таким образом, построенная
нами группа векторов содержит подгруппу простого порядка длиной |q| в двоичном представ-
лении: |q| = (m − 1)|p| − |m| ≈ (m − 1)|p|. Для построения алгоритмов ЭЦП требуется использо-
вать подгруппы простого порядка q размером не менее |q| ≥ 160 бит. Для этой цели следует
выбрать простое число p размером |p| при условии
|
p
|
≥
|
q|−|m m −1
|
≈
|q| m −1
(бит).
Для синтеза алгоритмов ЭЦП удобно использовать кольца размерностъю m ∈ {3, 5, 7,
11, 13, 17, 19}. При выборе конкретных значений m и k следует учитывать требования к про-
изводительности алгоритмов ЭЦП, вариант реализации и обеспечиваемый уровень стойкости.
Для синтеза ТУБВ, соответствующих случаям m = 3, 11, 13, 17, 19, можно воспользоваться
результатами работ [6, 8].
Таблица 3
mp
q = m − 1(pm − 1 + pm − 1 +…+ p + 1)
5 731 347 069 147
286 084 350 321 693 088 102 651 075 474 527 140 170 997 913 161
5 50 676 921 106 512 713
6 595 396 132 044 187 165 178 914 150 733 683 078 979 644 173 924 260 \
305 243 710 080 341
7 186 419 693
41 971 136 855 362 349 259 612 655 092 913 923 374 434 953 935 443
11 34 919
2 695 444 645 954 794 709 894 042 480 955 311 929 186 425 401
13 8693
186 245 641 178 891 833 068 301 313 943 899 460 753 528 874 501
Построение некоммутативных групп векторов. Некоммутативные группы векторов,
заданных над простым полем GF(p) и имеющих размерность m = 4, были построены путем
задания операции умножения по табл. 4. В построенных группах для произвольных ненуле-
вых значений коэффициентов A, B и C максимальное значение порядка векторов равно
Ωmax = p(p − 1)(p + 1).
Таблица 4
Операция умножения
:e
:i
:j
:k
:e :e :i :j :k
:i
:i
−ACe
Ak
−Cj
:j
:j
−Ak −ABe
Bi
:k :k Cj −Bi −BCe
Для синтеза алгоритмов ЭЦП представляет интерес выбор простого числа p, при котором p + 1 = 2q, а также использование циклической подгруппы порядка q. Например, при p = 87 049 239 434 461, A = 1, B = 2 и C = 3 вектор G = (12 051 687 713 738, 12 743 450 807 620, 58 233 746 685 306, 75 018 447 720 758) имеет простой порядок q = 43 524 619 717 231.
Синтез алгоритмов ЭЦП на основе циклических подгрупп достаточно большого простого порядка, содержащихся в группах многомерных векторов, может быть выполнен по аналогии с алгоритмами [9, 10], построенными с учетом сложности задачи дискретного логарифмирования в конечном простом поле. Рассмотрим возможный вариант обобщенной схе-
мы ЭЦП, предположим, что в нем используется циклическая группа векторов Γ, имеющая
достаточно большой порядок q (|q| ≥ 160 бит). Например, в качестве Γ может быть использована подгруппа максимального простого порядка, содержащаяся в векторной группе, заданной над кольцом Zn, где n = kp, k = 8693 и p = 50 676 921 106 512 713 (см. табл. 3), или под-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Построение конечных групп векторов для синтеза алгоритмов цифровой подписи
15
группа порядка q в некоммутативной группе, построенной в предыдущем разделе. При ука-
занных параметрах кольца Zn в группе векторов содержится подгруппа простого порядка, размер которой превышает 200 бит.
Подписывающий формирует свой открытый ключ Y в виде вектора Y = Gx, где G —
вектор, являющийся генератором группы Γ. Формирование подписи к сообщению M выполняется следующим образом:
1) выбрать случайное число k < q и вычислить вектор R = Gk; 2) используя некоторую криптографически стойкую хэш-функцию Fh, вычислить хэшкод h от сообщения M с присоединенным к нему вектором R: h = Fh(M, R). Значение h будет первым элементом ЭЦП; 3) вычислить второй элемент ЭЦП: s = xh + t mod q. Проверка подлинности подписи (h, s) состоит в следующем: 1) вычисляется вектор R′ = Y q − h G s;
2) вычисляется значение h′ = Fh(M, R′); 3) сравниваются значения h′ и h; если h′ = h, то ЭЦП признается подлинной.
Заключение. Построены конечные коммутативные нециклические группы векторов, содержащие подгруппы простого порядка большого размера, и конечные некоммутативные группы, перспективные для применения в алгоритмах ЭЦП и открытого распределения ключей. Для случаев пяти- и семимерных векторов предложены таблицы умножения базисных векторов, содержащие четыре независимых коэффициента растяжения. Особенностью построенных коммутативных групп является то, что координаты векторов являются элементами
конечного кольца Zkp. При соответствующем выборе конкретных значений p в нециклической группе содержится подгруппа простого порядка длиной (m − 1)|p| − |m| бит. Некоммутативная группа построена для случая четырехмерных векторов, заданных над простым конечным полем. На основе построенных групп векторов могут быть разработаны алгоритмы ЭЦП, обладающие высокой производительностью.
Для дальнейших исследований интерес представляет разработка некоммутативных групп векторов для случаев m = 6, 8 и 16 и синтез криптоалгоритмов с открытым ключом на основе сложности вычисления сопрягающего элемента [11] в некоммутативных конечных группах векторов.
Работа поддержана грантом РФФИ № 08-07-00096-а.
СПИСОК ЛИТЕРАТУРЫ
1. Венбо Мао. Современная криптография. Теория и практика. М.—СПб—Киев: Изд. дом „Вильямс“, 2005. 763 с.
2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. М.: ТРИУМФ, 2002. 816 с.
3. Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2006. 324 с.
4. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006. 274 с.
5. Koblitz N. A Course in Number Theory and Cryptography. Berlin: Springer-Verlag, 2003. 236 p.
6. Молдовян Н.А. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах // Автоматика и телемеханика. 2008. № 12. С. 163—177.
7. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966. 384 с.
8. Молдовян Д. Н., Молдовяну П. А. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. № 3(82). С. 12—17.
9. Молдовян Н. А. Практикум по криптосистемам с открытым ключом. СПб: БХВ-Петербург, 2007. 298 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
16 Л. В. Гортинская, Е. С. Дернова, Д. Н. Молдовян, П. А. Молдовяну
10. Menezes A. J., Van Oorschot P. C., and Vanstone S. A. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1997. 780 p.
11. Ko K. H., Lee S. J., Cheon J. H., Han J. W., Kang J.-S., Park Ch. New Public Key Cryptosystems Using Braid Groups // Advances in cryptology — CRYPTO 2000. Proc. Springer-Verlag LNCS. 2000. Vol. 1880. P. 166—183.
Сведения об авторах
Лидия Вячеславовна Гортинская — Научно-исследовательский институт „Вектор“, Санкт-Петербург;
старший научный сотрудник; E-mail: lydia-gort@mail.ru
Евгения Сергеевна Дернова
— аспирант; Санкт-Петербургский государственный электротехнический
университет „ЛЭТИ“, кафедра автоматизированных систем обработки
информации и управления; E-mail: evgeshka19@mail.ru
Дмитрий Николаевич Молдовян — Санкт-Петербургcкий институт информатики и автоматизации РАН;
младший научный сотрудник; E-mail: mnd.spectr@mail.ru
Петр Андреевич Молдовяну
— Научно-исследовательский институт „Вектор“, Санкт-Петербург; на-
чальник службы главного метролога; E-mail: nmold@mail.ru
Рекомендована НИИ „Вектор“
Поступила в редакцию 12.10.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5