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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

у отправителя информации формируют образ ключа шифрования в виде МДЧ 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₁ по формуле mod p.

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

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

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

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

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

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

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

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

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

новым в заявленном изобретении является то, что формируют два вспомогательных общих элемента D и Н конечного множества алгебраических элементов Г, у первого абонента формируют OK Y₁ путем генерации его личного секретного ключа в виде двух натуральных многоразрядных двоичных чисел х₁ и t₁ и последующей генерации ОК Y₁ по формуле у второго абонента формируют ОК Y₂ путем генерации его личного секретного ключа в виде двух натуральных многоразрядных двоичных чисел х₂ и t₂ и последующей генерации ОК Y₂ по формуле причем в качестве конечного множества алгебраических элементов Г с ассоциативной операцией умножения генерируют конечную алгебру с некоммутативной ассоциативной операцией умножения, содержащую множество глобальных единиц, а вспомогательные общие элементы D и H удовлетворяют условию DH=Е, где Е - глобальная единица

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

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

При наличии в некоторой КНАА более одной правой глобальной единицы в ней не могут содержаться двухсторонние глобальные единицы или левые глобальные единицы алгебры. При наличии в некоторой КНАА более одной левой глобальной единицы в ней не могут содержаться двухсторонние глобальные единицы или правые глобальные единицы алгебры.

Пусть дана КНАА, содержащая множество правых глобальных единиц. Тогда, используя два элемента D и Н удовлетворяют условию DH=E_R, где E_R - некоторая фиксированная правая глобальная единица, можно задать операцию гомоморфного отображения, описываемую следующей формулой:

W=HZD,

где переменная Z пробегает все значения алгебры. Эта операция гомоморфного отображения алгебры является взаимно коммутативной с операцией возведения в степень, т.е. справедлива следующая формула: HZ^xD=(HZD)^x, где x - неотрицательное целое число. Пусть дана КНАА, содержащая множество левых глобальных единиц. Тогда, используя два элемента D и Н, удовлетворяющие условию DH=E_L, где E_L - некоторая фиксированная левая глобальная единица, можно задать операцию гомоморфного отображения, описываемую следующей формулой:

W=HVD,

где переменная V пробегает все значения алгебры. Операция гомоморфного отображения второго типа также является взаимно коммутативной с операцией возведения в степень, т.е. справедлива следующая формула: HZ^xD=(HZD)^x.

Легко показать, что из условия DH=Е, где Е=E_L или Е=E_R, вытекает справедливость формулы D^tH^t=Е для любого натурального значения t и возможность задания параметризуемой операции автоморфного отображения вида W=H^tVD^t, где переменная V пробегает все значения алгебры; t - секретное значение используемое как параметр операции гомоморфного отображения. При использовании элементов КНАА D и Н в качестве вспомогательных общих элементов формирование ОК можно осуществить путем последовательного выполнения операции возведения в степень и операции гомоморфного отображения, т.е. в соответствии со следующей формулой:

Y=H^tZ^xD^t,

где пара натуральных МДЧ х и t составляют секретный ключ, связанный с ОК.

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

Пример 1: Генерация 4-мерной конечной алгебры Г с некоммутативной ассоциативной операцией умножения, в которой содержится большое множество левых глобальных единиц.

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

Операция умножения двух векторов ае+bi+…+qv и хе+yi+…+wv определяется по правилу перемножения каждой компоненты первого вектора с каждой компонентой второго вектора, т.е. по формуле:

(ае+bi+…+qv)(xe+yi+…+wv)=ахее+ayei+…+awev+

+bxie+byii+…+bwiv+…+qxve+qyvi+…+qwvv,

с последующей заменой в каждом слагаемом произведения пар базисных векторов на однокомпонентный вектор в соответствии с так называемой таблицей умножения базисных векторов (ТУБВ). Координаты таких однокомпонентных векторов, присутствующих в ТУБВ называются структурными коэффициентами, которые в частных случаях могут быть равны единице или нулю. После такой замены правая часть последней формулы будет представлять собой сумму однокомпонентных векторов. После их сложения в общем случае получим результат в виде m-мерного вектора вида а''е+b''i+…+q''v, т.е. свойство замкнутости операции умножения обеспечивается.

Для случая векторов размерности m=4 запись некоторого четырехмерного вектора имеет вид Z=ае+bi+cj+dk. Обеспечения свойств некоммутативности и ассоциативности конечной алгебры четырехмерных векторов реализуется, например, при использовании ТУБВ, представленной в виде таблицы 1.

Генерация различных вариантов конечных четырехмерных алгебр с некоммутативной ассоциативной операцией умножения осуществляется генерацией различных значений простого МДЧ р и различных конкретных значений коэффициента λ.

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

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

Х⋅А=А,

где Х=(х₀, х₁, x₂, х₃) - неизвестное значение; А - некоторый заданный элемент рассматриваемой КНАА. С учетом табл. 1 решение этого уравнения сводится к решению системы из четырех линейных уравнений с четырьмя неизвестными х₀, х₁, х₂ и х₃, которая распадается на следующие две независимые системы из двух уравнений:

Выполнив замену переменных по формулам u₁=х₁+х₂ и u₂=х₀+х₃, можно легко установить, что для всех значений А решениями систем (1) и (2) являются векторы L, которые описываются следующей формулой

где х₀, x₁=0, 1, … р-1. Поскольку векторы L действуют как левые единицы на все элементы алгебры, то будем называть их левыми глобальными единицами. Легко видеть, что формула (3) описывает все единицы такого типа и их количество равно р². Для нахождения правых единиц следует рассмотреть векторное уравнение вида

которое сводится к совместному решению следующих двух независимых систем из двух линейных уравнений:

Обе последние системы имеют одинаковый главный определитель

Для всех векторов А, таких, что выполняется условие Δ_A≠0, существует единственная правая единица, значение которой определяется значениями координат вектора А. В общем случае различным векторам А соответствуют различные правые единицы, которые будем называть локальными, поскольку они действуют только в рамках некоторых подмножеств элементов рассматриваемой КНАА. Координаты локальной правой единицы R=(r, r₁, r₂, r₃), относящейся к вектору А, описывается следующими формулами

Подставляя значения х₀=r₀ и х₁=r₁ в формулу (3), можно получить и . Таким образом, всевозможные локальные правые единицы содержатся в множестве (3) глобальных левых единиц. Это означает, что локальная правая единица, действующая в некотором подмножестве элементов алгебры, является локальной двухсторонней единицей этого подмножества.

Пример 2: Генерация 4-мерной конечной алгебры Г с некоммутативной ассоциативной операцией в которой содержится большое множество правых глобальных единиц.

Рассмотрим четырехмерную КНАА с операцией умножения, задаваемой ТУБВ, представленной в виде таблицы 2. Формула, описывающая множество глобальных правосторонних единиц алгебры, может быть получена при рассмотрении следующего векторного уравнения: вида

где А=(а₀, а₁, а₂, а₃) - некоторый заданный четырехмерный вектор; Х=(х₀, х₁, х₂, х₃) - неизвестный вектор. Используя табл. 1 можно легко представить векторное уравнение (7) в виде следующей системе линейных уравнений с неизвестными х₀, х₁, х₂ и х₃:

Заменяя переменные по формулам u₁=х₀+x₂ и u₂=x₁+x₃, систему (8) можно свести к следующим двум независимым системам из двух линейных уравнений:

Решение u₁=1 и u₂=0 удовлетворяет системам (9) и (10) для всех векторов А, поэтому это решение определяет множество глобальных правых единиц, координаты которых можно получить выполнив обратную замену переменных и задав значения (u₁, u₂)=(1, 0):х₀+х₂=1 и х₁+х₃=0. Последние два соотношения означают, что всевозможные четверки значений неизвестных, удовлетворяющих этим двум условиям являются координатами глобальных правых единиц R. Таким образом, получаем следующую формулу, которая описывает полное множество единиц такого типа, число которых равно р²:

где h, k=0, 1, …, р-1.

Левые единицы вектора А можно найти, рассматривая векторное уравнение которое сводится к следующим двум независимым системам уравнений:

В каждой из систем (12) и (13) главный детерминант равен следующему значению:

Если Δ_A≠0, то вектору А соответствует единственная локальная левая единица координаты которой равны

Подставляя значения и в формулу (11), можно получить и То есть всевозможные локальные левые единицы содержатся в множестве глобальных правых единиц.

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

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

1.1) генерируют простое 256-битовое МДЧ р;

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

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

3. Формируют два вспомогательных элемента D и Н конечной алгебры Г, удовлетворяющие условию DH=E_L, где E_L - левая глобальная единица.

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

4.1) генерируют личный секретный ключ первого абонента в виде пары МДЧ х₁ и t₁.

4.2) формируют ОК первого абонента Y₁ путем осуществления вычислений по формуле

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

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

6.1) генерируют личный секретный ключ второго абонента в виде пары МДЧ x₂ и t₂.

6.2) формируют ОК второго абонента Y₂ путем осуществления вычислений по формуле

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

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

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

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

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

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

1.1) генерируют простое 256-битовое МДЧ р;

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

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

3. Формируют два вспомогательных элемента D и Н конечной алгебры Г, удовлетворяющие условию D•H=E_R, где E_R - левая глобальная единица.

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

4.1) генерируют личный секретный ключ первого абонента в виде пары МДЧ х₁ и t₁.

4.2) формируют ОК первого абонента Y₁ путем осуществления вычислений по формуле

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

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

6.1) генерируют личный секретный ключ второго абонента в виде пары МДЧ х₂ и t₂.

6.2) формируют ОК второго абонента Y₂ путем осуществления вычислений по формуле

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

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

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

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

Доказательство корректности работы рассмотренного примера реализации способа состоит в доказательстве того, что на шагах 8 и 9 примера 3 и примера 4 первый и второй абоненты формируют одинаковый элемент конечной алгебры Г. Действительно имеем: на шаге 7:

на шаге 8:

То есть, оба абонента формируют одинаковое секретное значение.

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

Приложение

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

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

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

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

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

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

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

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

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

9. Множество алгебраических элементов - это алгебраическая структура.

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

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

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

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

14. Конечная алгебра - это конечное векторное пространство, в котором дополнительно задана операция умножения вектора на вектор, результатом которой является некоторый вектор, причем операция умножения является дистрибутивной относительно операции сложения векторов.

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

16. Левая единица - это элемент алгебры действующий как единица при выполнении операции умножения, в которой он является левым операндом.

17. Правая единица - это элемент алгебры действующий как единица при выполнении операции умножения, в которой он является правым операндом.

18. Глобальная единица алгебры - элемент алгебры, действующий как единица на все элементы алгебры. Если глобальная единица является двухсторонней, то она является единственной. Если алгебра содержит две или более глобальные правые (левые) единицы, то в алгебре отсутствуют глобальные левые (правые) единицы и отсутствует глобальная двухсторонняя единица.

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

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

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

22. Операция возведения элемента алгебры V в степень, равную натуральному числу n - это операция n-кратного умножения элемента (n раз), где - обозначение операции умножения. Если операция умножения является ассоциативной, то тогда могут быть применены алгоритмы быстрого возведения в степень, которые позволяют достаточно быстро осуществить возведение в степень, разрядность которой равна 1000 бит и более.