Math-Net.

Ru
Общероссийский математический портал

В. В. Назаров, Схемы открытого распределения ключа

на основе некоммутативной операции, Дискрет. матем.,
2006, том 18, выпуск 4, 148–157
DOI: 10.4213/dm79

Использование Общероссийского математического портала Math-Net.Ru подра-

зумевает, что вы прочитали и согласны с пользовательским соглашением
http://www.mathnet.ru/rus/agreement

Параметры загрузки:
IP: 31.61.184.173
28 января 2025 г., 12:56:23
Дискретная математика
том 18 ВЫПУСК 4 * 2006
УДК 519.7

Схемы открытого распределения ключа на

основе некоммутативной операции
© 2006 г. В. В. Назаров

В работе изучаются свойства двух схем открытого распределения ключа, основан­

ных на некоммутативной операции и предложенных В. М. Сидельниковым. В качестве
некоммутативной операции рассматриваются операция из семейства, предложенного
М. А. Черепневым, а именно, операции в кольцах целых чисел круговых полей, ос­
нованные на символе степенного вычета. В работе проведен криптоанализ обеих схем
для одного частного случая некоммутативной операции. В случае произвольной опе­
рации из вышеупомянутого класса доказана нестойкость первой схемы. Для второй
схемы доказана эквивалентность задачи ее вскрытия одной задаче вычислительной
алгебраической теории чисел.

1. Введение
Список односторонних функций, используемых в криптографии, весьма невелик. Подав­
ляющее большинство криптографических протоколов основано на отсутствии в насто­
ящее время полиномиальных алгоритмов обращения операций умножения целых чисел
и возведения в степень в конечных полях. В настоящей работе изучается операция вы­
числения символа степенного вычета на предмет ее использования в схеме открытого
распределения ключа на основе некоммутативной операции.
Принципиальная схема открытого распределения ключа на основе некоммутативной
операции была предложена В. М. Сидельниковым [1]. М. А. Черепнев [2] предложил
использовать для этой схемы символы Лежандра и Якоби. О. Н. Василенко заметил,
что можно использовать и символ степенного вычета (обобщенный символ Якоби). В
работах [2, 3] рассмотрены примеры полиномиально вычислимых функций, на основе
данного символа, которые оказались намного более стойкими к обращению, чем все
предложенное ранее для данной схемы.

2. Используемый математический и криптографический

аппарат
Пусть
 Схемы открытого распределения ключа 149

— круговое поле, где р — простое целое рациональное число,

КР = e2"i/p.

Обозначим R кольцо целых поля К. Известно, что R является факториальным кольцом и

векторным пространством над Z с базисом, состоящим из степеней £р, а именно,

R= (1, ?„..., £/"2>z.

Введем также обозначение

А= 1 - КР-

Известно, что

р = и-Хр-\

где и — обратимый элемент кольца R.

Пусть $ — простой идеал в R, a e R, причем $ и (а) взаимно просты с (А) и между
собой, пусть также $ — идеал в R, взаимно простой с (а) и (А).

Определение 1. Символ степенного вычета (обобщенный символ Якоби) есть

е{- п(5):$\$,$ — простые УсГ у

Р

где

Свойство 1. Символ степенного вычета мультипликативен по верхнему и по нижнему

аргументам (при соблюдении условий взаимной простоты).

Свойство 2. Пусть а\, а 2 е R \ {0}, ( я 0 , (а2) взаимно просты с (/?), $ — идеал, взаимно
простой с (at) и (/?),

я 1 = а2 (mod $).

Тогда

=
\1)р \1)р'
Определение 2. Пусть а, Ь е R \ {0}, (а), (Ь) взаимно просты между собой и с (р). Тогда

=
\b)P {W))p'
150 В. В. Назаров

Определение 3. Пусть р — простое целое рациональное число, х е Z взаимно просто с

р. Тогда частное Ферма от х
хр~1 - 1
Фр(х) = ( m o d Р)-
Р
Легко заметить, что для х, у е Z, (х,р) = (у, р) = 1, выполнено соотношение
Фр(ху) =Е Фр(х) + Фр(у) (mod p).
Далее рассмотрим два варианта схемы открытого распределения ключа на основе
некоммутативной операции. Оба варианта были предложены В. М. Сидельниковым в [1].
Пусть (G, *) — полугруппа, где * — некоммутативная, ассоциативная, полиномиаль­
но вычислимая операция, Go, Gi, G2 — подполугруппы, внутри которых операция *
коммутирует, А, В — абоненты, у £ Go, Ж — общий секретный ключ.

Схема I.

Абонент А Абонент В

1. выбирает а 1,^2 € Go, 1. выбирает Ь\, Ьг € Go,

вычисляет ид = я 1 * у * #2, вычисляет ds = Ь\ * у * Ъг,
отправляет С1А абоненту В. отправляет */д абоненту А.

2. вычисляет Ж = ЖА = а\ * с1в * ^2- 2. вычисляет 3£ = 3£# = Ъ\ * о^ * ^2-

Схема II.
Абонент А Абонент В

1. выбирает я, £ Gj, 1 = 1,2; 1. выбирает Ъ\ е Gi, 1 = 1,2;

вычисляет oU = я 1 * сц\ вычисляет г/д = 6i * Ъг\
отправляет oU абоненту В. отправляет ds абоненту А.

2. Calculate Ж = ЖА = «i * ds * «2- 2. вычисляет Ж = Жв = b\ * dA * 62-

В [3] показано, что в качестве операции * можно использовать операцию в К

(о
где /i(*), rj(x) — мультипликативные функции такие, что

В частности, при ^(дс) = N(x) (где N(x) — норма из К в Q) и /л(х) = ^ф/> W*)) получим
операцию [2]

а *Ь = а -Ъ •
т *Р№Ь))

Замечание 1. Вместо Фр(М(х)) можно взять любую логарифмическую функцию по мо­

(2)

дулю р.
 Схемы открытого распределения ключа 151

3. Криптоанализ схем I, II для операции (1)

Теорема 1. Схема I с операцией (1) нестойкая.
В схеме II с той же операцией * задача нахождения ключа по открытой информации
эквивалентна задаче нахождения по открытой информации любого из трех элементов

= ( fliai) \ (гШ\ = ( Фг) \ (ri(dA)\

Т
° \^dB))p\n(a2))p \ii{dA))p U ( W /

\V(bi))p \ii(a2))p Ъх*а2

(Фг)\ frj(ai)\ ~l = b2*ai

При /i = rj, x\ = (77(02), T/(^I))A' T 2 = (Ж^г), ^ ( ^ I ) ) A ~ символы норменного вычета.

В этом случае можно считать, что общим секретным ключом, вырабатываемым в схеме,
является один заранее выбранный символ норменного вычета, например х\ = (^U *d#)/3£.
Напомним, что открытой информацией являются элементы ^ и г/д, а также описание
коммутирующих подполугрупп G,-, / = 0 в схеме I и / = 1,2 в схеме II; кроме того, в
схеме I известен элемент у.

Доказательство. Сначала докажем первое утверждение теоремы.

Заметим, что

\ii(y))p U « v
то есть

для всех хуу б Go-

Положим

#i =dA/y*dB.

Ясно, что 5£\ может быть вычислен противником по открытой информации за одно вы­
числение операции * и одно деление в Z[%p]. To, что а*д делится нацело на у (в смысле
Z[£p]) следует из определений а1 А И операции *.
Распишем Ж и !£\ через обычное умножение, используя определение операции *, ее
152 В. В. Назаров

ассоциативность и свойства функций ц и \х\

Ж = а\ * йв * а2

(l(fli)\ (l(fli)\ (Фг)\ (rj(ai)\ (Ф0\

* \fi(bo)p" U(w,' U(y) Л" U(«2)/," Ucw,
(Фг)\ (Фг)\ ( rj(Y) \ ( rj(y) \ ( ф2)\
\li(Y))p \^a2))p \fi(b2))/{fM(a2))p'\fi(a2))p
d
Xx = —A ^dB
У
= а\ • b\ • у • b2 • a2
(ФОЛ (ФОЛ (ФОЛ (п(аОЛ (ФОЛ
' \ц(Ь0)р Л А*(У) ) Р ' U f o ) / , ' (/л(Ь2))р ' U ( * 2 ) / ,
(ФОЛ (Фг)Л ( Ф) Л ( Ф) Л
(fi(y))p U(W, \Ma2))p'\lt(b2))p
(ФОЛ (ФпаОЛ
' U ( W / V Ц(У) )р
Так как а2, Ь\, Ь2 € Go, мы видим, что

(ФОЛ =(ФОЛ
\li(bi))p (11(02))/
(ФОЛ =(п(Ь2)Л
(fi(b2))p (ii(a2))p'

поэтому
с£\ = Ж • Х\,

где
frj(aia2)\
Г1 =
(~ш-)Р-
В силу определения операции * и свойств функции rj

ri
V H(Y) )Р V Д(У) Л
= dA/y * у dA/y * у
dA/y -у dA
Таким образом,
%^U^dAly*dB dA
хх dA/y * у
то есть для вычисления Ж по открытой информации противнику нужно произвести два
деления в Z[£p], одно умножение и два вычисления операции *, что и доказывает первое
утверждение теоремы.
 Схемы открытого распределения ключа 153

Обратимся теперь ко второму утверждению теоремы. Выкладками, аналогичными

вышеизложенным, можно показать, что
Ж = dA • ds • ть,
Ж = (dA * dB) - гГ\
Ж= (dв*dA)^T2-l.
Так как dA и dB находятся в открытом доступе, по этим формулам, зная Ж, можно
найти г0, ri,T 2 .

4. Криптоанализ схемы II для операции (2)

Введем обозначение

Е = {х е Щр\ | ((*),# = ((*), (/>)) = 1},

где р - простое целое рациональное число. Тогда * определена на Е х Е. В разделе 2
мы показали, что данная операция * является частным случаем операции, для которой
формулировались теоремы в разделе 3, поэтому мы можем применять второе утверждение
теоремы 1.
Определим функции /(х), g(x) на Е, полагая

/(*) = /, где/ е [О,/7-1], (J^j =y,

g(x) = у, где j е [О, р - 1], Фр(Щх)) = у (mod p).

Заметим, что при таком определении f(x),g(x) справедливо равенство

a*b=a.b.$pf(a)g(b).

Предложение 1. Справедливы соотношения

МР) = g{KP) = о,
f(xy) = f(x) + f{y) (mod p),
g(xy) s= g(x) + g(y) (mod p).
Доказательство. Докажем первое утверждение. Ясно, что

ЩР) = 1,
поэтому из определения частного Ферма следует, что

Фр№Ъ)) =lP ~ * (mod />) = О

(то есть g(£p) = 0) и из определения символа степенного вычета получаем, что

№Р) = о.
154 В. В. Назаров

Второе утверждение верно в силу логарифмического свойства показателя и частных

Ферма.
Рассмотрим следующие подмножества Е:

Я0,о = {х е Е | / ( * ) = g{x) = 0},

Я 0 = {х € Е | / ( * ) = 0, g(x) ф 0},
Нр = {х е Е | / ( * ) / 0, g(x) = 0},
Я„ ={xeE\f(x)-g(x)-1 =п (mod/7)}, л = 1 , . . . , / ? - 1.

Заметим, что введенные множества попарно не пересекаются, а их объединение рав­

но Е.

Предложение 2. Элементы множества Яо,о коммутируют со всеми элементами Е.

Элементы xi,x2 ^ Яо,о коммутируют тогда и только тогда, когда существует
по € { 0 , 1 , . . . , р) такое, что х\,Х2 € Я Л() .
Доказательство. Из определения следует, что

хх * х2 = х 2 * xi Ф=» / ( * i ) • #(х 2 ) = / ( * 2 ) • g(xi)

(здесь и далее все сравнения по модулю р).

Если х\ е Я 0 ,о, то для всех х2 еЕ

/(*1)S(*2)^/(*2)S(*1)=0,

поэтому
Xi * JC2 = JC2 * Х\.

Таким образом, первое утверждение доказано.

Пусть х\, х2 е Я Л() . Рассмотрим три случая.
Пусть п0 = 0, тогда
A * I ) = /(JC 2 ) = 0,

поэтому
f{Xi).g(X2) = f(x2)-g{Xi)=0.
Пусть по = р, тогда
£(*i) = g(x2) = 0,
поэтому
ЯхО . g{x2) = f(x2) - g(xi) = 0.
Пусть по ф. {0, /?}, тогда

Домножим обе части сравнения на g(x\) • g(x2) ф 0, получим, что

/(*i)-£(x2) = /(*2)-£(*i).

Во всех трех случаях

f(xi)-g(x2) = /(x2)-g(xi),
 Схемы открытого распределения ключа 155

поэтому
Х\ * Х2 = Х2 * Х\.

Таким образом, мы доказали, что если элементы лежат в одном множестве НПо, то они
коммутируют.
Пусть
хх * х2 = х2 * * ь xi,x2,x3 $ Я0,о-
Тогда
f(x\)-g(x2) = f(x2)-g(xi).
Рассмотрим два возможных варианта.
Пусть f(x\) • g(x2) = 0, тогда в силу простоты р либо f(x\) = О, либо g(x2) == 0.
Если f(x\) = 0, то (так как JCI fi Яо,о) справедливо равенство g(x\) ф 0. Кроме того,

f(X2).g(Xl)^f(Xl).g(x2)^0.

Поэтому f(x2) = 0, то есть х2 е Но (так как х2 £ Яо,о)- Если же g(x2) = 0, то аналогично

получим, что х\, х2 е Нр.
Пусть теперь
f(xi)-g(x2) = f(x2)-g(xi)£0.
Тогда обе части равенства можно разделить на ненулевое выражение g(x\) • g(x2). Полу­
чим, что
/ ( * 0 * g(xi)~l = f(x2) • g(x2)~l = n0.
то есть x\,x2 € Hno для no € [l,p — 1].
Из предложения 2 ясно, что при данном выборе операции * подполугруппы Gi, G2
будут подмножествами Hni U Я0,о и Я„ 2 U Я0,о для некоторых п\фп2 соответственно.
Заметим, что щ нужно считать известными противнику, так как они могут быть вычис­
лены по произвольному элементу из G/ \ Яо,о-

Теорема 2. Для операции (2) схема II является нестойкой.

Доказательство. Как мы уже отмечали, можно применить пункт 2 теоремы 1: если мы

покажем, что по открытой информации можно быстро вычислять элемент

(N(a2)\ **<"<*!» /N(bi)\ -*"<"<e2))

_ Y f^2>gib\)-fibxyg{a2)
— ЪР

то этим мы докажем теорему. Таким образом достаточно показать, что по открытой ин­
формации можно быстро вычислить

Р = f(ai)' g{b\) - f(b\) • g(a2) (mod p).

Будем считать, что G/ не содержат элементов из Яо,о (случай, когда такие элементы есть,
рассматривается аналогично).
156 В. В. Назаров

Введем обозначения

*1 = Д я О , У\ = /(«2), zi = /(fti), wi = f(b2)y <^ = f{dA), cB = /'№?)>

*2 = gfai), J2 = g f e ) , z2 = g(fei), w2 = g(b2), eA = #№4), <?2? = £№?)•

здесь jc/, jj:, Z|, Ш/ — неизвестные, сд, ел, с#, ед известны (они вычисляются по открытой
информации исходя из определения). В таких обозначениях

р = yiz2-ziy2 (mod p).

Посмотрим, какие уравнения с неизвестными х%, yi, z,-, Wi мы можем составить. По

предложению 1

xi+yi = сА,
х2 +у2 = eAi
Z\ + W\ = Сд,
z2 + w2 = ев-

Далее нам нужно будет отдельно рассмотреть следующие случаи:

гц €{0,/?}, i = 1,2,
"1 € {0, /?}, п2 $ {0, /?} или п2 € {0, /?}, «1 $ {0, /?},
л,- *{0,/>}, i = 1,2.

Мы подробно разберем только последний из названных случаев, в остальных все

получается аналогично.
Напишем систему для лс,, у,-, z/, и;,-, получаемую непосредственно из определений
множеств Я Л1 , # „ 2 . В данном случае она имеет вид

Х\ = Х2 . . . Л ь
JVi s У2...Л2,
Zi = Z2 ...Ль

Ш1 = w2...n2. (3)

Подставляя уравнения системы (4) в систему (3), получим, что

п\х2+п2у2 = сА,
х2 +у2 = еА,
n2w2 = ев,
z2 + w2 = ев.
Это линейная система в поле Z//?Z с определителем (п\ — п2)2 ф 0. Поэтому она
имеет единственное решение. Решая ее, получаем определенные выше неизвестные х2,
у2, z2, w2 и далее по уравнениям системы (4) находим х\, у\, z\, w\.
В случаях, когда один или оба из Льп 2 лежат в {0, /?}, мы получим другие системы
вида (4) и соответственно другие системы вида (5). Но во всех случаях определитель
системы вида (5) будет ненулевым и все неизвестные будут найдены.
 Схемы открытого распределения ключа 157

Список литературы
1. Сидельников В. М, Черепнев М. А., Ященко В. В., Системы открытого распределения ключей
на основе некоммутативных полугрупп. ДАН СССР (1993), 332, 566-567.
2. Черепнев М. А., Схемы открытого распределения ключа на основе некоммутативной группы.
Дискретная математика (2003) 15, №2, 47-51.
3. Черепнев М. А., Схемы открытого распределения ключа на основе некоммутативной операции.
В сб.: Тез. докл. XIII Международной конф. «Проблемы теоретической кибернетики». Казань,
2002, с. 190.

Статья поступила 9.09.2004.