способ формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы

Формула изобретения

1. Способ формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы, заключающийся в том, что генерируют конечную группу Г, формируют общий элемент Z конечной группы Г, у первого абонента генерируют его личный секретный ключ и его открытый ключ в виде элемента Y₁ конечной группы Г, передают открытый ключ Y₁ первого абонента второму абоненту, у второго абонента генерируют его личный секретный ключ и его открытый ключ в виде элемента Y₂ конечной группы Г, передают открытый ключ Y₂ второго абонента первому абоненту, у первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от открытого ключа Y₂ второго абонента и личного секретного ключа первого абонента, а у второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от открытого ключа Y₁ первого абонента и личного секретного ключа второго абонента, отличающийся тем, что у первого абонента формируют открытый ключ Y₁ путем генерации его личного секретного ключа в виде двух элементов Х₁ и W₁ группы Г, таких, что выполняются условия

где знак обозначает групповую операцию, и , генерации дополнительного личного секретного ключа первого абонента в виде многоразрядного двоичного числа s₁ , формирования элемента V₁ конечной группы Г по формуле и последующего выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, а у второго абонента формируют открытый ключ Y₂ путем генерации его личного секретного ключа в виде двух элементов Х₂ и W₂ группы Г, таких что выполняются условия и , генерации дополнительного личного секретного ключа второго абонента в виде многоразрядного двоичного числа s₂ , формирования элемента V₂ конечной группы Г по формуле и последующего выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, причем в качестве конечной группы Г используют некоммутативную конечную группу.

2. Способ по п.1, отличающийся тем, что формируют дополнительный общий элемент D конечной группы Г, для которого выполняется условие где знак обозначает групповую операцию, генерируют личный секретный ключ первого абонента в виде двух элементов X₁ и W ₁ группы Г путем генерации случайных многоразрядных двоичных чисел а₁ и b₁ и последующей генерации элементов X₁ и W₁ конечной группы Г по формулам и и генерируют личный секретный ключ второго абонента в виде двух элементов Х₂ и W₂ группы Г путем генерации случайных многоразрядных двоичных чисел а₂ и b₂ и последующей генерации элементов Х₂ и W₂ конечной группы Г по формулам и .

Описание изобретения к патенту

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

Известен способ формирования ключа шифрования у абонентов конфиденциального сеанса связи, включающий преобразование случайного многоразрядного двоичного числа, называемого временной отметкой и определяемого по моменту времени, например по моменту времени начала сеанса связи, по заранее оговоренному криптографическому алгоритму под управлением секретного ключа, которым абоненты обмениваются предварительно по защищенному каналу связи [Иванов М.А. Криптография. М., КУДИЦ-ОБРАЗ, 2001, - с.197-198]. Недостатком этого способа формирования ключа шифрования является необходимость передачи секретного ключа по защищенному каналу связи, который является дорогостоящим элементом систем секретной связи.

Также известен способ формирования ключей шифрования путем многократного последовательного модифицирования секретного ключа в соответствии с алгоритмом одностороннего преобразования [Иванов М.А. Криптография. М., КУДИЦ-ОБРАЗ, 2001, - с.205]. Недостатком известного способа формирования ключа шифрования является то, что при компрометации текущего ключа компрометируются все последующие ключи шифрования.

Также известен способ формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы с использованием открытых каналов связи, описанный в книге [Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. - СПб, БХВ-Петербург, 2004, - 436 с. - см. с.408 и с.412-413]. Способ-аналог заключается в выполнении следующей последовательности действий:

1. У первого абонента формируют открытый ключ (ОК) в виде двух многоразрядных двоичных чисел (МДЧ) первого n и второго (здесь и далее по тексту описания под МДЧ следует понимать электромагнитный сигнал в двоичной цифровой форме, в котором общее число битов и порядок их следования отражает некоторое двоичное число¹) (¹ Толкование терминов, используемых в описании, приведено в Приложении 1), для чего

генерируют первый m и второй q вспомогательные простые множители в виде МДЧ, а первое МДЧ n ОК вычисляют как произведение n=mq;

вычисляют функцию Эйлера (n) от первого МДЧ n ОК по формуле (n)=(m-1)(q-1);

генерируют второе МДЧ ОК, являющееся взаимно простым со значением функции Эйлера (n) (пара МДЧ n и образует ОК);

вычисляют секретное МДЧ = ^-1mod (n), при котором выполняется условие mod (n)=1.

2. Передают ОК, т.е. пару МДЧ р и , второму абоненту, например, по телекоммуникационным сетям.

3. У второго абонента генерируют секретный ключ К и формируют образ секретного ключа в виде МДЧ r, путем его вычисления по формуле r=K modn.

4. Передают получателю информации образ ключа r.

5. У получателя информации вычисляют ключ шифрования Т по формуле K=r modn.

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

Однако известный способ имеет недостаток - относительно большое время, необходимое для формирования общего секретного ключа шифрования, что связано с необходимостью выполнения большого объема вычислений у получателя информации, обусловленного большой разрядностью МДЧ , примерно равной разрядности первого МДЧ n ОК, которую для достижения требуемой криптостойкости выбирают в пределах 1024-2048 бит.

Также известен способ формирования ключа шифрования, предложенный в патенте Российской Федерации № 2286022 и заключающийся в следующей последовательности действий:

у получателя информации (первого абонента) формируют ОК в виде первого р и второго МДЧ, разрядность каждого из которых выбирается равной не менее 1024 бит,

передают ОК отправителю информации (второму абоненту),

у отправителя информации формируют образ ключа шифрования в виде МДЧ r и передают его получателю информации;

у получателя информации по образу ключа шифрования r вычисляют ключ шифрования в виде МДЧ K.

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

Наиболее близким по своей технической сущности к заявленному является известный способ формирования общего секретного ключа шифрования двух абонентов с использованием открытых каналов связи, описанный в книге [Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. - СПб, БХВ-Петербург, 2005, - 286 с. - см. с.408 и с.104-105]. Ближайший способ-аналог (прототип) включает следующие действия:

1. Генерируют конечную группу Г, включающую множество целых чисел {1, 2, , p-1}, над которыми в качестве групповой операции задана операция умножения по модулю р, где р - простое МДЧ, имеющее разрядность не менее 1024 бит. Для этого генерируют простое МДЧр требуемой разрядности.

2. Формируют общий для обоих абонентов элемент Z конечной группы Г, представляющий собой МДЧ Z {1, 2, , p-1}, относящееся к показателю р-1 по модулю р.

3. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего генерируют его личный секретный ключ в виде случайно сгенерированного МДЧ х₁ и вычисляют Y₁ по формуле .

4. Открытый ключ Y₁ передают по открытому каналу второму абоненту.

5. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего генерируют его личный секретный ключ в виде МДЧ х₂ и вычисляют Y₂ по формуле .

6. Открытый ключ Y₂ передают по открытому каналу первому абоненту.

7. У первого абонента формируют общий секретный ключ в виде элемента К конечной группы Г путем его вычисления по формуле .

8. У второго абонента формируют общий секретный ключ в виде элемента К конечной группы Г путем его вычисления по формуле .

Недостатком ближайшего аналога является относительно высокая сложность процедуры формирования общего секретного ключа шифрования K, связанная с тем, что общий секретный ключа шифрования K вычисляют путем возведения по модулю МДЧ р ОК одного абонента в большую целочисленную степень, равную личному секретному ключу другого абонента.

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

Кроме того, заявленное техническое решение расширяет арсенал средств данного назначения.

Поставленная цель достигается тем, что в известном способе формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы, заключающемся в том, что генерируют конечную группу Г, формируют общий элемент Z конечной группы Г, у первого абонента генерируют его личный секретный ключ и его ОК в виде элемента Y₁ конечной группы Г, передают ОК первого абонента Y₁ второму абоненту, у второго абонента генерируют его личный секретный ключ и его ОК в виде элемента Y₂ конечной группы Г, передают ОК второго абонента Y₂ первому абоненту, у первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента Y₂ и личного секретного ключа первого абонента, а у второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента Y₁ и личного секретного ключа второго абонента, новым в заявленном изобретении является то, что у первого абонента формируют OK Y₁ путем генерации его личного секретного ключа в виде двух элементов Х₁ и W₁ конечной группы Г, формирования элемента V₁ конечной группы Г в зависимости от элемента Х₁ конечной группы Г и общего элемента Z конечной группы Г и последующего выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, у второго абонента формируют OK Y₂ путем генерации его личного секретного ключа в виде двух элементов Х₂ и W₂ конечной группы Г, формирования элемента V₂ конечной группы Г в зависимости от элемента Х₂ конечной группы Г и общего элемента Z конечной группы Г и последующего выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, причем в качестве конечной группы Г используют некоммутативную конечную группу.

Некоммутативную конечную группу Г можно задать, расширяя способ задания коммутативных мультипликативных групп векторов, предложенный в работе [Молдовяну П.А., Дернова Е.С., Молдовян Д.Н. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации. 2008. № 3 (82). С.2-7]. Примеры задания некоммутативных групп векторов с операцией умножения векторов, обладающей относительно низкой сложностью, приведены ниже. Благодаря сравнительно низкой сложности операции векторного умножения и возможности ее эффективного распараллеливания обеспечивается существенное уменьшение времени формирования общего секретного ключа двух абонентов.

Новым является также и то, что у первого абонента формируют OK Y₁ путем генерации его личного секретного ключа в виде двух элементов Х₁ и W₁ конечной группы Г, таких, что выполняются условия X₁ Z Z X₁ и W₁ Z Z W₁, где знак обозначает групповую операцию, формирования элемента V ₁ конечной группы Г путем выполнения групповой операции над элементами Х₁ и Z конечной группы Г и последующего выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, у второго абонента формируют OK Y₂ путем генерации его личного секретного ключа в виде двух элементов Х₂ и W₂ конечной группы Г, таких, что выполняются условия Х₂ Z Z Х₂ и W₂ Z Z W₂, формирования элемента V₂ конечной группы Г путем выполнения групповой операции над элементами Х ₂ и Z конечной группы Г и последующего выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, у первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г путем формирования элемента R₁ конечной группы Г, заключающегося в выполнении групповой операции над элементом Х₁ конечной группы Г и ОК Y₂ второго абонента Z, т.е. по формуле R ₁=X₁ Y₂, и последующего выполнения групповой операции над элементами R₁ и W₁ конечной группы Г, т.е. по формуле К=R₁ W₁, a у второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г путем формирования элемента R₂ конечной группы Г, заключающегося в выполнении групповой операции над элементом Х₂ конечной группы Г и ОК Y₁ первого абонента, т.е. по формуле R ₂=Х₂ Y₁, и последующего выполнения групповой операции над элементами R₂ и W₂ конечной группы Г, т.е. по формуле K=R₂ W₂.

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

Новым является также и то, что формируют дополнительный общий элемент D конечной группы Г, для которого выполняется условие D Z Z D, генерируют личный секретный ключ первого абонента в виде двух элементов Х₁ и W₁ конечной группы Г путем генерации случайных МДЧ а₁ и b₁ и последующей генерации элементов Х₁ и W₁ конечной группы Г по формулам и и генерируют личный секретный ключ второго абонента в виде двух элементов Х₂ и W₂ конечной группы Г путем генерации случайных МДЧ а₂ и b₂ и последующей генерации элементов Х₂ и W₂ конечной группы Г по формулам и .

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

Новым является также и то, что генерируют личный секретный ключ первого абонента в виде двух элементов Х₁ и W₁ конечной группы Г, таких что выполняются условия Х₁ Z Z Х₁ и , и генерируют личный секретный ключ второго абонента в виде двух элементов Х₂ и W₂ конечной группы Г, таких что выполняются условия Х₁ Х₂=Х₂ Х₁, Х₂ Z Z Х₂ и .

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

Новым является также и то, что у первого абонента формируют ОК Y₁ путем генерации его личного секретного ключа в виде двух элементов Х₁ и W₁ конечной группы Г, таких что выполняются условия Х₁ Z Z X₁ и генерации дополнительного личного секретного ключа первого абонента в виде МДЧ s₁, формирования элемента V ₁ конечной группы Г по формуле и последующего выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, а у второго абонента формируют ОК Y₂ путем генерации его личного секретного ключа в виде двух элементов Х₂ и W ₂ конечной группы Г, таких что выполняются условия Х ₁ Х₂=Х₂ Х₁, Х₂ Z Z Х₂ и генерации дополнительного личного секретного ключа второго абонента в виде МДЧ s₂, формирования элемента V ₂ конечной группы Г по формуле и последующего выполнения групповой операции над элементами V₂ и W₂ конечной группы Г.

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

Новым является также и то, что формируют два дополнительных общих элемента D₁ и D₂ конечной группы Г, для которых выполняются условия D₁ Z Z D₁ и D₂ Z=Z D₂, генерируют личный секретный ключ первого абонента в виде двух элементов Х₁ и W₁ группы Г путем генерации случайных МДЧ а₁ и b ₁ и последующей генерации элементов Х₁ и W ₁ по формулам и и генерируют личный секретный ключ второго абонента в виде двух элементов Х₂ и W₂ группы Г путем генерации случайных МДЧ а₂ и b₂ и последующей генерации элементов Х₂ и W₂ по формулам и .

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

Новым является также и то, что формируют два дополнительных общих элемента D₁ и D ₂ конечной группы Г, для которых выполняются условия D ₁ Z Z D₁, D₂ D₁ D₁ D₂ и D₂ Z Z D₂, генерируют личный секретный ключ первого абонента в виде двух элементов Х₁ и W₁ группы Г путем генерации случайных МДЧ а₁ и b ₁ и последующей генерации элементов Х₁ и W ₁ по формулам и и генерируют личный секретный ключ второго абонента в виде двух элементов Х₂ и W₂ группы Г путем генерации случайных МДЧ а₂ и b₂ и последующей генерации элементов Х₂ и W₂ по формулам и .

Благодаря генерации дополнительных общих элементов D₁ и D₂ конечной группы Г, удовлетворяющих условиям D₁ Z Z D₁ и D₂ Z Z ZD₂, а также дополнительному условию D₂ D₁ D₁ D₂, и вычислению личных секретных ключей абонентов путем возведения общих элементов D₁ и D₂ конечной группы Г в степени, равные случайно выбираемым числам, расширяются варианты унификации процедуры формирования личных секретных ключей абонентов и одновременно обеспечивается дополнительное повышение криптостойкости.

Изобретательский замысел заявленного нового технического решения состоит в применении некоммутативных конечных групп, в которых в общем случае результат выполнения групповой операции зависит от порядка расположения элементов группы, над которыми выполняется групповая операция. Благодаря этому уравнения вида Y=X Z X^-1 с неизвестным значением X являются трудно решаемыми при соответствующем выборе некоммутативной конечной группы Г и значений Y и Z. Это позволяет выполнить вычисление ОК Y абонента в зависимости от его секретного ключа X по формуле Y=X Z X^-1, в которой элементы X и Z некоммутативной конечной группы Г выбираются так, что выполняется условие Z X X Z. При этом в некоммутативных группах всегда существуют коммутативные подгруппы Г_к', которые легко могут быть установлены. Если выбирать личные секретные ключи абонентов из таких коммутативных подгрупп, то возникает возможность формирования общего секретного ключа по ОК первого абонента и личному секретному ключу второго абонента, а также по ОК второго абонента и личному секретному ключу первого абонента. Действительно, пусть Z - общий элемент, Х₁ Г_к' и Х₂ Г_к' - личные секретные ключи первого и второго абонентов соответственно, причем выполняются условия некоммутативности Z X₁ X₁ Z и Z Х₂ Х₂ Z, а также условие коммутативности Х₁ Х₂=Х₂ Х₁ (из последнего условия вытекает выполнимость условия ). Тогда ОК первого (Y₁) и второго (F₂ ) абонентов формируются путем их вычисления по формулам и . Первый абонент вычисляет общий секретный ключ по формуле , а второй - по формуле , где при преобразовании последнего выражения использованы условия коммутативности личных секретных ключей Х₁ и Х₂ и их обратных значений и . Таким образом, описанная процедура формирования общего секретного ключа действительно обеспечивает формирование одинаковых значений у первого и второго абонентов.

Для произвольных элементов V, X и Z некоммутативной группы Г выполняется соотношение (X Z X^-1) (X V X^-1)=X (Z V) X^-1, из которого легко установить справедливость формулы

(X Z X^-1)^s=X Z^s Х^-1.

Выполнимость последнего соотношения обусловливается тем фактом, что групповая операция обладает свойством ассоциативности в группах любого типа (см. с.28-43 в книге [Б.Л. ван дер Варден «Алгебра». Изд-во «Лань». 2004, - 623 с.]). Данное соотношение может быть применено для построения варианта заявленного способа формирования общего секретного ключа двух абонентов телекоммуникационной системы, обеспечивающего повышение криптостойкости за счет использования дополнительного личного секретного ключа первого (второго) абонента в виде МДЧ s₁ (МДЧ s₂) и формирования ОК Y₁ и Y₂ по формулам и соответственно. Криптостойкость повышается за счет того, что при таком формировании ОК значительно повышается вычислительная сложность нахождения секретного ключа по ОК. При таком варианте генерации ОК в заявленном способе формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы у первого абонента общий секретный ключ вычисляют по формуле

а у второго абонента - по формуле

Легко видеть, что значения секретного ключа, формируемого у первого и второго пользователей, совпадают.

Возможен также вариант формирования ОК по личному секретному ключу, представляющему собой пару независимых элементов Х₁ и W₁ некоммутативной конечной группы Г для первого абонента и элементов Х₂ и W₂ некоммутативной конечной группы Г для второго абонента. Если для элементов Х₁, W₁, Х₂ и W ₂ некоммутативной конечной группы Г выполняются условия коммутативности Х₁ Х₂=Х₂ Х₁ и W₁ W₂=W₂ W₁, то первый абонент может вычислить общий секретный ключ по ОК Y₂=Х₂ Z W₂ второго абонента, осуществляя вычисления по формуле K=X₁ Y₂ W₁=X₁ Х₂ Z W₂ W₁, а второй абонент может вычислить общий секретный ключ по формуле K=Х₂ Y₁ W₂=Х₂ X₁ Z W₁ W₂=X₁ Х₂ Z W₂ W₁. Сравнение правых частей последних двух выражений показывает, что первый и второй абоненты формируют одно и то же секретное значение K.

Рассмотрим примеры генерации некоммутативных конечных групп и конкретные примеры реализации заявленного способа формирования общего секретного ключа двух абонентов телекоммуникационной системы.

Пример 1: Генерация некоммутативных конечных групп векторов.

Рассмотрим упорядоченные наборы МДЧ (a₁, а₂ , , a_m), каждое из которых не превосходит некоторого выбранного простого МДЧ р. Такой набор называется вектором, а МДЧ a₁, а₂, , a_m - координатами вектора, значение m 2 - это размерность вектора, равная числу координат в векторе. Координаты представляют собой МДЧ, принадлежащие множеству МДЧ {1, 2, , p-1}, где р - заданное простое МДЧ, над которыми определены операции сложения и умножения по модулю р. Другой формой записи векторов является его запись в виде суммы одномерных векторов, называемых компонентами вектора, каждый из которых представляет собой координату вектора с приписанным к ней формальным базисным вектором. Обозначим формальные базисные вектора строчными латинскими буквами е, i, j и т.д. В последней записи очередность записи компонентов вектора не имеет значения, например вектора Z ₁=523425е+3676785i+53453453j и Z₂=3676785i+523425е+53453453j, где е, i, j - формальные базисные вектора, в которых координатами являются МДЧ, рассматриваются как равные, т.е. Z₁=Z ₂. Операция умножения векторов определяется как перемножение всех компонентов векторов-сомножителей, с учетом того, что возникающие при этом произведения формальных базисных векторов заменяются по некоторой специфицированной таблице одним базисным вектором или однокомпонентным вектором, после чего все координаты, приписанные одному и тому же базисному вектору, складываются по модулю р. Указанная таблица умножения базисных векторов (ТУБВ) для случая векторов размерности m=3 имеет, например, вид таблицы 1, которая определяет следующее правило подстановки базисных векторов:

е е е, e i i, e j j, i е е, i i j, i j µe,

j e j, j i µe, j j µi,

где µ - заданное МДЧ, принадлежащее множеству МДЧ {1, 2, , р-1}.

Например, пусть Z₁=a ₁e+b₁i+c₁i и Z₂=a ₂e+b₂i+c2j, тогда операция умножения векторов Z₁ и Z₂ (обозначим ее знаком « ») выполняется следующим образом:

Z ₁ Z₂=(a₁e+b₁i+c₁ j) (a₂e+b₂i+c₂j)=а₁ а₂е е+a₁b₂e i+a₁c₂e j+b₁a₂i e+b₁b₂i i+b₁c₂i j+c₁a₂j e+c₁b₂j i+c₁c₂j j=(a₁a₂+µb₁c ₂+µc₁b₂)e+(a₁b ₂+b₁a₂+µc₁c₂ )i+(a₁c₂+c₁a₂+b ₁b₂)j.

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

Некоммутативная конечная группа четырехмерных векторов вида Z=ае+bi+cj+dk может быть сгенерирована путем выбора простого МДЧ р и выбора ТУБВ, представленной таблицей 2. Единичным элементом данной некоммутативной конечной группы является вектор Е=1е+0i+0j+0k=(1, 0, 0, 0). Генерация различных вариантов некоммутативных конечных групп четырехмерных векторов осуществляется генерацией различных значений простого МДЧ р и различных конкретных значений коэффициентов µ и .

Некоммутативная конечная группа шестимерных векторов вида Z=ае+bi+cj+dk+gu+hv может быть сгенерирована путем выбора простого МДЧ р и выбора ТУБВ, представленной таблицей 3. Единичным элементом данной некоммутативной конечной группы является вектор Е=1е+0i+0j+0k+0u+0v=(1, 0, 0, 0, 0, 0). Генерация различных вариантов некоммутативных конечных групп шестимерных векторов осуществляется генерацией различных значений простого МДЧ р и различных конкретных значений коэффициентов µ и .

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

По аналогии с приводимыми ниже примерами могут быть реализованы различные варианты заявленного способа, в котором используются некоммутативные конечные группы шестимерных векторов, некоммутативные конечные группы векторов других размерностей, а также некоммутативные конечные группы другой природы, например некоммутативные конечные группы невырожденных матриц с групповой операцией матричного умножения (о формировании конечных групп матриц см., например, статью [Дернова Е.С., Костина А.А., Молдовяну П.А. Конечные группы матриц как примитив алгоритмов цифровой подписи // Вопросы защиты информации. 2008. № 3 (82). С.8-12]).

Пример 2: Реализация заявленного способа по пп.1 и 2 формулы изобретения (ФИ).

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧр=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219).

3. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

3.1) генерируют личный секретный ключ первого абонента в виде векторов

Х₁=(412485650, 354714868, 11415120, 374981699) и

W₁=(218734814, 538682836, 87527669, 422047718),

таких что выполняются условия X₁ Z Z X₁ и W₁ Z Z W₁;

3.2) формируют вектор V ₁ в зависимости от элемента (вектора) Х₁ конечной группы Г и общего элемента Z конечной группы Г:

V₁=X₁ Z=(728320531, 654181207, 65070899, 577618629);

3.3) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁.

Y₁=V₁ W₁=(425148910, 246457671, 747646831, 410216744).

4. Передают ОК первого абонента второму абоненту, например, по открытому телекоммуникационному каналу.

5. У второго абонента генерируют ОК в виде элемента (вектора) Y₂ конечной группы Г, для чего

5.1) генерируют личный секретный ключ второго абонента в виде векторов

Х₂=(370670118, 625081252, 441595984, 439787129)и

W₂=(260962717, 154659585, 690010063, 41501431);

проверка показывает, что условия Х₂ Z Z Х₂ и W₂ Z Z W₂ выполняются;

5.2) формируют вектор V₂ в зависимости от элемента (вектора) Х ₂ конечной группы Г и общего элемента Z конечной группы Г:

V₂=Х₂ Z=(479451174, 559227309, 256367878, 729027484);

5.3) формируют ОК второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₂ и W₂:

Y₂=V₂ W₂=(469173303, 40216341, 439013336, 697933857).

6. Передают ОК второго абонента первому абоненту, например, по открытому телекоммуникационному каналу.

7. У первого абонента формируют общий секретный ключ в виде элемента (вектора) K конечной группы Г в зависимости от ОК второго абонента и личного секретного ключа первого абонента, для чего

7.1) формируют элемент (вектор) R₁ конечной группы Г путем выполнения групповой операции над элементом (вектором) Х₁ конечной группы Г и ОК Y₂ второго абонента, т.е. путем умножения вектора Х₁ на вектор Y₂ :

R₁=Х₁ Y₂=(661128145, 71383748, 132286367, 491638663);

7.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. в данном примере умножают вектор R₁ на вектор W₁ :

K=R₁ W₁=(56050234, 472712410, 528948385, 229431566).

8. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента и личного секретного ключа второго абонента, для чего

8.1) формируют элемент R₂ конечной группы Г путем выполнения групповой операции над элементом Х₂ конечной группы Г и OK Y₁ первого абонента, т.е. путем умножения вектора Х₂ на вектор Y₁ :

R₂=Х₂ Y₁=(482946163, 375061607, 517975082, 716663007);

8.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂:

K=R₂ W₂=(56050234, 472712410, 528948385, 229431566).

В результате выполненных действий у первого и второго абонентов сформирован один и тот же секретный ключ, который в явном виде не передавался по ОК. Для постороннего субъекта, перехватывающего сообщения, передаваемые по каналу связи абонентов вычисление секретного ключа K вычислительно неосуществимо на практике при выборе размера МДЧ р, равного 80 бит и более, Данный вариант реализации заявленного способа формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы обеспечивает уменьшение времени формирования общего секретного ключа по сравнению с ближайшим способом аналогом даже при выборе размера МДЧ р, равного 2048 бит, что позволяет существенно повышать криптостойкость, сохраняя относительно малое время формирования общего секретного ключа.

Пример 3: Реализация заявленного способа по п.3 ФИ.

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧр=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219).

3. Формируют дополнительный общий элемент D конечной группы Г, для которого выполняется условие D Z Z D, в виде следующего вектора:

D=(534608750, 512739492, 524918926, 447002300).

4. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

4.1) генерируют случайные МДЧ а₁ и b₁: а₁=291530213 и b₁=184575638;

4.2) генерируют личный секретный ключ первого абонента в виде элементов Х₁ и W₁ конечной группы Г, вычисляемых по формулам и :

Х₁=(33699142, 27614207, 589607720, 562339745) и

W₁=(156041335, 433249021, 449252506, 154059360).

4.3) формируют вектор V₁ в зависимости от элемента X₁ конечной группы Г и общего элемента Z конечной группы Г:

V₁=X₁ Z=(501417156, 131388964, 621523999, 283611901);

4.4) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁:

Y₁=V₁ W₁=(717857199, 69545294, 183473883, 632506213).

5. Передают ОК первого абонента второму абоненту.

6. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего

6.1) генерируют случайные МДЧ а₂ и b₂: а ₂=116495327 и b₂=317562913;

6.2) генерируют личный секретный ключ второго абонента в виде элементов Х₂ и W₂ конечной группы Г, вычисляемых по формулам и :

Х₂=(676077679, 640501448, 302593640, 440687969) и

W₂=(585868651, 727531050, 697946319, 367672412);

проверка показывает, что условия Х₂ Z Z Х₂ и W₂ Z Z W₂ выполняются;

6.3) формируют вектор V₂ в зависимости от элемента Х₂ конечной группы Г и общего элемента Z конечной группы Г:

V₂=Х₂ Z=(291393458, 652305749, 344861251, 175372945);

6.4) формируют ОК второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₂ и W₂:

Y₂=V₂ W₂=(422879155, 641610894, 540116498, 145646709).

7. Передают ОК второго абонента первому абоненту.

8. У первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента и личного секретного ключа первого абонента, для чего

8.1) формируют элемент R₁ конечной группы Г путем выполнения групповой операции над элементом Х₁ конечной группы Г и ОК Y₂ второго абонента, т.е. путем умножения вектора Х₁ на вектор Y₂ :

R₁=Х₁ Y₂=(685855902, 712172111, 595007995, 499592732);

8.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. умножают вектор R₁ на вектор W₁:

K=R₁ W₁=(16329912, 348186141, 483076292, 468651775).

9. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента и личного секретного ключа второго абонента, для чего

9.1) формируют элемент R₂ конечной группы Г путем выполнения групповой операции над элементом Х₂ конечной группы Г и ОК Y₁ первого абонента, т.е. путем умножения вектора Х₂ на вектор Y₁ :

R₂=Х₂ Y₁=(313099699, 536879836, 647240501, 568582030);

9.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂:

K=R₂ W₂=(16329912, 348186141, 483076292, 468651775).

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

Пример 4: Реализация заявленного способа по п.4 ФИ.

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧр=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219),

порядок которого равен МДЧ q=375894199.

3. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

3.1) генерируют личный секретный ключ первого абонента в виде векторов

Х₁=(412485650, 354714868, 11415120, 374981699) и

,

таких что выполняются условия X ₁ Z Z X₁ и ;

3.2) формируют вектор V₁ в зависимости от элемента Х₁ конечной группы Г и общего элемента Z конечной группы Г:

V₁=X ₁ Z=(728320531, 654181207, 65070899, 577618629);

3.3) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁:

Y₁=V₁ W₁=(225775009, 81555981, 151356132, 669845920).

4. Передают ОК первого абонента второму абоненту, например, по открытому каналу связи.

5. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего

5.1) генерируют личный секретный ключ второго абонента в виде векторов

Х₂ =(370670118, 625081252, 441595984, 439787129) и

таких, что выполняются условия Х ₁ Х₂=Х₂ Х₁, Х₂ Z Z Х₂ и ;

5.2) формируют вектор V₂ в зависимости от элемента Х₂ конечной группы Г и общего элемента Z конечной группы Г:

V₂=Х ₂ Z=(479451174, 559227309, 256367878, 729027484);

5.3) формируют ОК второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере формируют ОК в виде вектора, равного произведению векторов V₂ и W ₂:

Y₂=V₂ W₂=(225775009, 359096640, 159959475, 610994590).

6. Передают ОК второго абонента первому абоненту, например, по открытому каналу связи.

7. У первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента и личного секретного ключа первого абонента, для чего

7.1) формируют элемент R₁ конечной группы Г путем выполнения групповой операции над элементом Х₁ конечной группы Г и OK Y ₂ второго абонента, т.е. путем умножения вектора Х ₁ на вектор Y₂:

R₁ =Х₁ Y₂=(728320531, 667645298, 157932283, 733253337);

7.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. умножают вектор R₁ на вектор W₁:

K=R₁ W₁=(225775009, 365259173, 573285714, 745051492).

8. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента и личного секретного ключа второго абонента, для чего

8.1) формируют элемент R₂ конечной группы Г путем выполнения групповой операции над элементом Х₂ конечной группы Г и ОК Y₁ первого абонента, т.е. путем умножения вектора Х₂ на вектор Y₁ :

R₂=Х₂ Y₁=(479451174, 91855889, 444557157, 435069688);

8.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂:

K=R₂ W₂=(225775009, 365259173, 573285714, 745051492).

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

Пример 5: Реализация заявленного способа по п.5 ФИ.

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧр=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219),

порядок которого равен МДЧ q=375894199.

3. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

3.1) генерируют личный секретный ключ первого абонента в виде векторов

Х₁=(412485650, 354714868, 11415120, 374981699) и

таких что выполняются условия X ₁ Z Z X₁ и ;

3.2) генерируют дополнительный личный секретный ключ первого абонента в виде МДЧ s₁: s ₁=287457372;

3.3) формируют элемент V ₁ конечной группы Г в зависимости от элемента Х₁ конечной группы Г и общего элемента Z конечной группы Г путем вычисления вектора ( обозначает операцию возведения вектора Z в степень s ₁, т.е. (s₁ раз)) и умножения вектора Х₁ на вектор :

3.3) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁:

Y₁=V₁ W₁=(13407495, 117475284, 729495990, 112340265).

4. Передают ОК первого абонента второму абоненту, например, по открытому каналу связи телекоммуникационной системы.

5. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего

5.1) генерируют личный секретный ключ второго абонента в виде векторов

Х₂=(370670118, 625081252, 441595984, 439787129) и

таких, что выполняются условия Х ₁ Х₂=Х₂ X₁, Х₂ Z Z Х₂ и ;

5.2) генерируют дополнительный личный секретный ключ второго абонента в виде МДЧ s₂: s ₂=302751365;

5.3) формируют вектор V ₂ в зависимости от элемента X₂ конечной группы Г и общего элемента Z конечной группы Г путем вычисления вектора (возведение вектора Z в степень s₂) и умножения вектора Х₂ на вектор :

5.3) формируют OK второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₂ и W₂:

Y₂=V₂ W₂=(268323899, 366097580, 492488923, 372628196).

6. Передают ОК второго абонента первому абоненту, например, по открытому каналу связи телекоммуникационной системы.

7. У первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента, личного секретного ключа первого абонента и дополнительного личного секретного ключа первого абонента, для чего

7.1) формируют элемент R₁ конечной группы Г путем выполнения групповой операции над элементом Х ₁ конечной группы Г и ОК Y₂ второго абонента, т.е. путем умножения вектора Х₁ на вектор Y₂ :

формируют элемент R₂ конечной группы Г путем вычисления вектора и умножения вектора Х₂ на вектор :

7.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. умножают вектор R₁ на вектор W₁ :

K=R₁ W₁=(665169598, 698972005, 207121212, 631745661).

8. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента, личного секретного ключа второго абонента и дополнительного личного секретного ключа второго абонента, для чего

8.1) формируют элемент R₂ конечной группы Г путем вычисления вектора и умножения вектора Х₂ на вектор :

8.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂ .

K=R₂ W₂=(665169598, 698972005, 207121212, 631745661).

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

Пример 6: Реализация заявленного способа по п.6 ФИ.

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧр=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219).

3. Формируют два дополнительных общих элемента D₁ и D₂ конечной группы Г, для которых выполняются условия D₁ Z Z D₁ и D₂ Z=Z D₂:

D₁=(534608750, 512739492, 524918926, 447002300) и

D₂ =(723700851, 9764039, 138183077, 407816790).

4. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

4.1) генерируют случайные МДЧ а₁ и b₁: а₁=291530213 и b₁=184575638;

4.2) генерируют личный секретный ключ первого абонента в виде элементов Х₁ и W₁ конечной группы Г, вычисляемых по формулам и :

Х₁=(33699142, 27614207, 589607720, 562339745) и

W₁=(106030556, 503651307, 708182581, 544725304).

4.3) формируют элемент V₁ конечной группы Г в зависимости от элемента Х ₁ конечной группы Г и общего элемента Z конечной группы Г:

V₁=X₁ Z=(501417156, 131388964, 621523999, 283611901);

4.4) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁:

Y₁=V₁ W₁=(416571129, 64019502, 534537127, 433602441).

5. Передают ОК первого абонента второму абоненту.

6. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего

6.1) генерируют случайные МДЧ а₂ и b₂: а ₂=116495327 и b₂=317562913;

6.2) генерируют личный секретный ключ второго абонента в виде элементов Х₂ и W₂ конечной группы Г, вычисляемых по формулам и :

Х₂=(676077679, 640501448, 302593640, 440687969) и

W₂=(134525578, 32936500, 312364224, 676034188);

проверка показывает, что условия Х₂ Z Z Х₂ и W₂ Z Z W₂ выполняются;

6.3) формируют вектор V₂ в зависимости от элемента Х₂ конечной группы Г и общего элемента Z конечной группы Г:

V₂=Х₂ Z=(291393458, 652305749, 344861251, 175372945);

6.4) формируют ОК второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₂ и W₂:

Y₂=V₂ W₂=(291299135, 679249764, 201973270, 700852854).

7. Передают ОК второго абонента первому абоненту.

8. У первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента и личного секретного ключа первого абонента, для чего

8.1) формируют элемент R₁ конечной группы Г путем выполнения групповой операции над элементом Х₁ конечной группы Г и ОК Y₂ второго абонента, т.е. путем умножения вектора Х₁ на вектор Y₂ :

R₁=Х₁ Y₂=(261999283; 6137698; 233045854; 1770367);

8.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. умножают вектор R₁ на вектор W₁:

K=R₁ W₁=(727736088, 404584806, 193596713, 424443795).

9. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента и личного секретного ключа второго абонента, для чего

9.1) формируют элемент R₂ конечной группы Г путем выполнения групповой операции над элементом Х₂ конечной группы Г и ОК Y₁ первого абонента, т.е. путем умножения вектора Х₂ на вектор Y₁ :

R₂=Х₂ Y₁=(40601245, 718350287, 567209164, 241014819);

9.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂:

K=R₂ W₂=(727736088, 404584806, 193596713, 424443795).

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

Пример 7: Реализация заявленного способа по п.7 ФИ.

1. Генерируют некоммутативную конечную группу Г в виде некоммутативной конечной группы четырехмерных векторов, для чего

1.1) генерируют простое МДЧ р=751788397;

1.2) генерируют ТУБВ в виде таблицы 2, где µ=2 и =3.

2. Формируют общий элемент Z конечной группы Г в виде вектора

Z=(225775009, 612940870, 565904108, 399985219).

3. Формируют два дополнительных общих элемента D₁ и D₂ конечной группы Г, для которых выполняются условия D₁ Z Z D₁, D₂ D₁ D₁ D₂ и D₂ Z Z D₂:

D₁=(534608750, 512739492, 524918926, 447002300) и

D₂ =(679666808, 377694615, 565138462, 505041338).

4. У первого абонента генерируют ОК в виде элемента Y₁ конечной группы Г, для чего

4.1) генерируют случайные МДЧ а₁ и b₁: а₁=291530213 и b₁=184575638;

4.2) генерируют личный секретный ключ первого абонента в виде элементов Х₁ и W₁ конечной группы Г, вычисляемых по формулам и :

Х₁=(33699142, 27614207, 589607720, 562339745) и

W₁=(437014043, 413669527, 582430806, 419833824).

4.3) формируют вектор V₁ в зависимости от элемента Х₁ конечной группы Г и общего элемента Z конечной группы Г:

V₁=X₁ Z=(501417156; 131388964; 621523999; 283611901);

4.4) формируют ОК первого абонента Y₁ путем выполнения групповой операции над элементами V₁ и W₁ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₁ и W₁:

Y₁=V₁ W₁=(105090004, 388090680, 664039794, 512841850).

5. Передают ОК первого абонента второму абоненту.

6. У второго абонента генерируют ОК в виде элемента Y₂ конечной группы Г, для чего

6.1) генерируют случайные МДЧ а₂ и b₂: а ₂=116495327 и b₂=317562913;

6.2) генерируют личный секретный ключ второго абонента в виде элементов Х₂ и W₂ конечной группы Г, вычисляемых по формулам и :

Х₂=(676077679, 640501448, 302593640, 440687969) и

W₂=(408454641, 129510874, 712799849, 107283989);

проверка показывает, что условия Х₂ Z Z Х₂ и W₂ Z Z W₂ выполняются;

6.3) формируют элемент V₂ конечной группы Г в зависимости от элемента Х₂ конечной группы Г и общего элемента Z конечной группы Г:

V₂=Х₂ Z=(291393458, 652305749, 344861251, 175372945);

6.4) формируют ОК второго абонента Y₂ путем выполнения групповой операции над элементами V₂ и W₂ конечной группы Г, т.е. в данном примере в виде вектора, равного произведению векторов V₂ и W₂:

Y₂=V₂ W₂=(228621823, 365421749, 562763903, 532545831).

7. Передают ОК второго абонента первому абоненту.

8. У первого абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК второго абонента и личного секретного ключа первого абонента, для чего

8.1) формируют элемент R₁ конечной группы Г путем выполнения групповой операции над элементом Х₁ конечной группы Г и ОК Y₂ второго абонента, т.е. путем умножения вектора Х₁ на вектор Y₂ :

R₁=X₁ Y₂=(531923262, 696869496, 226339945, 460508234);

8.2) выполняют групповую операцию над элементами R₁ и W₁ конечной группы Г, т.е. умножают вектор R₁ на вектор W₁:

K=R₁ W₁=(515074148, 347934926,307920204, 133652455).

9. У второго абонента формируют общий секретный ключ в виде элемента K конечной группы Г в зависимости от ОК первого абонента и личного секретного ключа второго абонента, для чего

9.1) формируют элемент R₂ конечной группы Г путем выполнения групповой операции над элементом Х₂ конечной группы Г и ОК Y₁ первого абонента, т.е. путем умножения вектораХ₂ на вектор Y₁ :

R₂=Х₂ Y₁=(122092361, 587709477, 404972314, 211551832);

9.2) выполняют групповую операцию над элементами R₂ и W₂ конечной группы Г, т.е. умножают вектор R₂ на вектор W₂:

K=R₂ W₂=(515074148, 347934926, 307920204, 133652455).

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

В случае некоммутативных конечных групп четырехмерных векторов заявленный способ формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы обеспечивает достаточную стойкость при выборе простого МДЧ р размером 80 бит и более. Одна операция умножения векторов, являющаяся групповой операцией в рассмотренных вариантах реализации заявленного способа, требует выполнения не более 22 операций умножения по модулю р. Уменьшение времени формирования общего секретного ключа в заявленном способе по сравнению со способами-аналогами обеспечивается тем, что 1) при формировании общего секретного ключа выполняется меньшее количество групповых операций, 2) в некоммутативных группах четырехмерных векторов вычисления ведутся по простому модулю, разрядность которого примерно в 12,8 раз меньше разрядности простого модуля в способах-аналогах и 3) время выполнения операции умножения по модулю пропорционально квадрату разрядности модуля. Наибольшее время формирования общего секретного ключа K двух удаленных абонентов в заявленном способе соответствует варианту его реализации по п.6 формулы изобретения, поскольку в этом варианте реализации при формировании общего секретного ключа K выполняется дополнительная операция возведения в степень, равную значению дополнительного личного секретного ключа. Даже в этом случае время формирования общего секретного ключа K в заявленном способе примерно в 12,8²/22 7,5 раз меньше по сравнению со способами-аналогами при одинаковой криптостойкости.

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

Приложение 1

Толкование терминов, используемых в описании заявки

1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.

2. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.

3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например число 10011 является 5-разрядным.

4. Битовая строка - двоичный цифровой электромагнитный сигнал, представляемый в виде конечной последовательности цифр «0» и «1».

5. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».

6. Открытый ключ - битовая строка, параметры которой зависят от секретного ключа. Открытый ключ вычисляется по секретному как значение функции, вычислимой в одну сторону, которая делает практически неосуществимым вычисление секретного ключа по открытому ключу.

7. Многоразрядное двоичное число (МДЧ) - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».

8. Операция возведения числа S в дискретную степень А по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1, 2, , n-1}, включающим n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972, - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю.

9. Показатель q по модулю n числа а, являющегося взаимно простым с n - это минимальное из чисел , для которых выполняется условие a mod n=1, т.е. q=min { ₁, 2, } [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972, - 167 с.].

10. Порядок числа q по модулю n числа а - это показатель q по модулю n числа а.

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

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

13. Группа - это алгебраическая структура (т.е. множество элементов различной природы), над элементами которой определена одна операция, которая при заданной операции обладает следующим набором свойств: операция ассоциативна, результатом выполнения операции над двумя элементами является также элемент этой же структуры, существует единичный элемент, такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Детальное описание групп дано в книгах [А.Г.Курош. Теория групп. - М.: изд-во «Наука», 1967, - 648 с.] и [М.И.Каргаполов, Ю.И.Мерзляков. Основы теории групп. - М.: изд-во «Наука. Физматлит», 1996, - 287 с.].

14. Групповая операция - это операция, определенная над элементами группы. Обычно в группе определяют операцию возведения в степень, которая является производной от групповой операции. Возведение в степень в группе - это многократное выполнение групповой операции над одним и тем же элементом. Например, для элемента группы а и натурального числа n по определению имеем aⁿ =а а а а (n раз), где « » обозначает групповую операцию.

15. Единичный элемент группы Г - это такой элемент, что при выполнении операции над ним и другим произвольным элементом Z группы Г результатом является элемент Z, т.е. для любого Z Г имеем E Z=Z E=Z, где Е - единичный элемент группы.

16. Порядком элемента Z группы Г называется наименьшее натуральное число q, такое что Z^q=Е, где Е - единичный элемент группы Г.

17. Обратный элемент по отношению к заданному элементу Z группы Г - некоторый элемент группы Г, обозначаемый как Z^-1, такой что Z^-1 Z=Z Z^-1=Е, где Е - единичный элемент группы Г.

18. Некоммутативная группа - это группа с некоммутативной групповой операцией, т.е. с групповой операцией, для которой в общем случае результат ее действия над двумя элементами группы зависит от их расстановки относительно знака групповой операции, например, для двух элементов Z₁ Г и Z₂ Г в общем случае имеет место следующее неравенство Z ₁ Z₂ Z₂ Z₁.

19. Вектор - это набор из двух или более МДЧ, называемых координатами вектора. Число координат вектора называется размерностью вектора.

20. Операция векторного умножения - это операция умножения двух векторов, являющаяся групповой операцией в конечной группе векторов.

21. Конечная группа - это группа, содержащая конечное число элементов.

22. Знак принадлежности « » используется для обозначения принадлежности, например, элемента а группе Г следующим образом: а Г.

23. Функция Эйлера от некоторого заданного натурального числа - это число чисел, являющихся взаимно простыми с заданным натуральным числом.