Способ шифрования

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов защиты информации, передаваемой по открытым каналам телекоммуникационных систем. Техническим результатом является повышение скорости шифрования. Технический результат достигается тем, что способ шифрования включает следующую последовательность действий: генерируют конечную группу Г, формируют сообщение в виде элемента М конечной группы Г, генерируют секретный ключ шифрования, генерируют криптограмму в виде элемента С конечной группы Г путем преобразования сообщения М в зависимости от секретного ключа шифрования, причем в качестве конечной группы Г генерируют некоммутативную конечную группу, генерируют секретный ключ шифрования в виде двух элементов X и W группы Г и многоразрядного двоичного числа е, генерируют криптограмму С путем формирования элемента R конечной группы Г, равного е-й степени сообщения М, т.е. R=М^е, формирования элемента V конечной группы Г в зависимости от элементов X и R конечной группы Г и последующего выполнения групповой операции между элементами V и W конечной группы Г. 3 з.п. ф-лы, 3 табл.

 

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

Известен способ шифрования путем формирования секретного ключа, генерации ключевого потока в виде последовательности битов, зависящих от секретного ключа, и сложения текущих битов ключевого потока с текущими битами передаваемого сообщения [Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. СПб., Лань, 2000. - 218 с.; см. с.88-89]. Недостатком этого способа шифрования является необходимость синхронизации ключевого потока и потока данных.

Также известен способ шифрования, включающий генерацию 56-битового секретного ключа, формирование сообщения М в виде 64-битового блока данных, разбиение блока данных, генерацию криптограммы, представляющей собой 64-битовый блок данных, преобразованных в зависимости от секретного ключа [Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. С-Петербург, Лань, 2000. - 218 с.; см. с.68-73]. При этом генерация криптограммы осуществляется путем разбиения сообщения М на два 32-битовых подблока данных и поочередное преобразование подблоков в зависимости от секретного ключа. Недостатком этого способа является малый размер секретного ключа, что не обеспечивает криптостойкости, соответствующей современным требованиям.

Также известен способ шифрования, включающий генерацию мультипликативной группы Г, генерацию секретного ключа в виде двух больших простых чисел р и q, генерацию открытого ключа в виде многоразрядных двоичных чисел¹ (Толкование терминов, используемых в описании, приведено в Приложении 1) (МДЧ) n и е, генерацию дополнительного секретного ключа в виде МДЧ d, формирование сообщения в виде элемента М группы Г и генерацию криптограммы в виде элемента С группы Г путем возведения сообщения М в степень е по модулю n [Смарт Н. Мир программирования. Криптография. М.: ТЕХНОСФЕРА, 2005. - 525 с.; см. с.192-193]. Генерация группы Г осуществляется путем генерации трудноразложимого на простые множители числа n. Число n задает множество чисел {1, 2, 3, …, n-1}, включающее подмножество взаимно простых с n чисел, которое образует конечную группу с групповой операцией, являющейся операцией умножения по модулю n. Расшифрование криптограммы осуществляется путем возведения криптограммы С в степень d по модулю n. Недостатком этого способа шифрования является достаточно низкая скорость расшифрования криптограммы, что связано с тем, что для обеспечения требуемой стойкости следует генерировать модуль n, разрядность которого составляет не менее 1024 бит. При этом, если генерируется открытый ключ, в котором МДЧ е имеет сравнительно малую разрядность, то вычисляемое в зависимости от е МДЧ d имеет разрядность, примерно равную разрядности модуля n. Если генерируется дополнительный секретный ключ d таким образом, чтобы он имел сравнительно малую разрядность, то МДЧ е, вычисляемое в зависимости от МДЧ d, имеет разрядность, примерно равную разрядности модуля n. Это приводит к тому, что скорость расшифрования увеличивается, но при этом скорость шифрования становится низкой.

Наиболее близким по своей технической сущности к заявленному является известный способ шифрования, описанный в книге [Смарт Н. Мир программирования. Криптография. М.: ТЕХНОСФЕРА, 2005. - 525 с.; см. с.200-202]. Ближайший способ-аналог (прототип) включает следующие действия:

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

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

3. У получателя сообщения генерируют открытый ключ в виде элемента Y конечной группы Г, для чего генерируют его личный секретный ключ в виде МДЧ х, разрядность которого выбирают не менее 160 бит, и вычисляют Н по формуле Н=G^xmod p.

4. Открытый ключ G передают по открытому каналу отправителю сообщения.

5. У отправителя сообщения генерируют секретный ключ шифрования в виде элемента Z конечной группы Г, для чего формируют вспомогательный секретный ключ в виде МДЧ k, разрядность которого выбирают не менее 160 бит, и вычисляют элемент R группы Г по формуле R=G^kmod p. По открытому ключу получателя и вспомогательному секретному ключу k генерируют секретный ключ шифрования Z по формуле Z=H^kmod p.

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

7. Генерируют криптограмму в виде элемента С конечной группы Г путем выполнения групповой операции между элементами Z и М, т.е. по формуле С=ZMmod p.

В результате выполненных действий получена криптограмма С, в котором содержится зашифрованное сообщение М. Криптограмму С можно передавать по открытому каналу, так как без знания секретного ключа Z или личного секретного ключа получателя х и элемента R группы Г практически невозможно получить исходное сообщение из криптограммы. Чтобы получатель мог правильно расшифровать криптограмму, т.е. сгенерировать по ней исходное сообщение, ему отправляют вместе с криптограммой С также и элемент R группы Г. Он генерирует исходное сообщение М, выполняя вычисления по формуле: М=R^-xCmod p.

Недостатком ближайшего аналога является относительно высокая сложность процедуры шифрования, поскольку для каждого нового сообщения генерируется новое значение вспомогательного секретного ключа k и выполняются две операции возведения в k-ю степень по модулю МДЧ р, разрядность которого из соображения получения достаточной криптостойкости выбирается равной 1024 бит и более. Наиболее быстрый алгоритм возведения в большую степень по модулю использует таблицу предвычислений и требует выполнения операций умножения по модулю, где - разрядность МДЧ k. Другим недостатком является то, что для хранения или передачи по каналу связи сообщения размером, например 1024 бит, требуется хранить или передавать два элемента С и R группы Г, размер каждого из которых равен примерно 1024 бит. Элемента R группы Г представляет собой дополнительный блок данных, ассоциированный с криптограммой. Он требуется для обеспечения возможности вычисления сообщения М из криптограммы по секретному ключу расшифрования. Это увеличивает в два раза объем требуемой памяти и время передачи сообщения по каналу связи.

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

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

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

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

Новым является также и то, что формируют элемент V конечной группы Г путем выполнения групповой операции между элементом Х конечной группы Г и сообщением М.

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

Новым является также и то, что генерируют секретный ключ шифрования в виде двух элементов Х и W группы Г, удовлетворяющих условию X∘W≠W∘X, где знак ∘ обозначает групповую операцию.

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

Новым является также и то, что генерируют секретный ключ шифрования в виде двух взаимно обратных элементов Х и W группы Г, для которых выполняются условия W=X^-1 и Х=W^-1.

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

Новым является также и то, что генерируют дополнительный секретный ключ шифрования в виде МДЧ е, формируют элемент V конечной группы Г путем формирования элемента R конечной группы Г, равного е-й степени сообщения М, т.е. R=M^e, и последующего выполнения групповой операции между элементами X и R конечной группы Г, т.е. по формуле V=X∘M^e.

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

Изобретательский замысел заявленного нового технического решения состоит в применении некоммутативных конечных групп, в которых в общем случае результат выполнения групповой операции зависит от порядка расположения элементов группы, над которыми выполняется групповая операция. Благодаря этому уравнения вида C=X∘Z∘X^-1 с неизвестным значением X являются трудно решаемыми при соответствующем выборе группы Г и ее элементов Y и Z. Это позволяет использовать значение Х в качестве секретного ключа шифрования и выполнять шифрование по формуле C=X∘M∘X^-l, предварительно формируя сообщение в виде элемента М группы Г. В общем случае в некоммутативных группах для двух ее элементов Х и Z обычно выполняется неравенство Z∘Х≠Х∘Z. Вероятность случайного выбора двух элементов Х и Z некоммутативной группы таких, что Z∘X=X∘Z является достаточно малой. Чтобы шифрование приводило к изменению сообщения М, и в этих случаях можно применить шифрование по формуле

C=X∘M∘W,

где для элементов Х и W, используемых в качестве секретного ключа шифрования, выполняется неравенство Z∘W≠W∘Z. При этом в некоммутативных группах всегда существуют коммутативные подгруппы Г_к′, что может быть использовано для осуществления коммутативного шифрования.

Для этого следует задать одну коммутативную подгруппу Г_х′ для случайного выбора из нее элемента Х секретного ключа шифрования, а другую Г_w′ - для случайного выбора из нее элемента W секретного ключа шифрования. Задание таких коммутативных подгрупп может быть осуществлено следующим образом. Генерируются два элемента группы G_x и G_w, порядок которых является достаточно большим простым числом q и для которых имеет место неравенство G_x∘G_w≠G_w∘G_x. Для генерации секретного ключа в виде пары элементов Х и W группы Г генерируют два случайных МДЧ а и b, каждое из которых не превосходит q. Элемент Х и вычисляют по формуле а элемент W - по формуле При этом для любых МДЧ а и b, в силу неравенства G_x∘G_w≠G_w∘G_x, имеет место неравенство т.е. X∘W≠W∘X. В то же время для любых двух МДЧ а и а′ элементы и коммутируют между собой, т.е. имеет место равенство Х∘Х′=Х′∘Х. Аналогично для любых двух МДЧ b и b′ элементы и имеет место равенство Х∘Х′=Х′∘Х. Если в качестве первого ключа шифрования использовать пару элементов Х и W, а в качестве второго ключа шифрования - пару элементов X′ и W′, то будет реализовываться коммутативное шифрование, для которого результат шифрования по двум ключам не зависит от очередности их использования. Детально особенности коммутативного шифрования рассмотрены в книге [Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. С-Петербург. БХВ-Петербург, 2005. - 286 с.], где также рассмотрены специальные технические области их применения (см. с.129-133 и с.237-238). Расшифрование криптограммы С осуществляется по формуле

M=X^-1∘C∘W^-1,

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

C=X∘M^e∘W,

а формула расшифрования - вид М=(X∘C∘W)^d, где d - дополнительный секретный ключ расшифрования, который легко вычисляется из дополнительного секретного ключа шифрования как МДМ, обратное к МДЧ е по модулю, равному максимальному значению порядка элементов группы. При этом обеспечивается более высокая скорость шифрования по сравнению с прототипом. Если в варианте реализации заявленного способа с дополнительным секретным ключом шифрования использовать пару элементов Х и W, таких что выполняется условие Х и W=X^-1, то процедура шифрования будет обладать свойством коммутативности. Действительно, для произвольных элементов V, М и X некоммутативной группы Г выполняется соотношение (X∘M∘X^-l)∘(X∘V∘X^-l)=X∘(M∘V)∘X^-1, из которого легко установить справедливость формулы

(X∘M∘X^-1)^s=X∘M^s∘X^-1.

Выполнимость последнего соотношения обусловливается тем фактом, что групповая операция обладает свойством ассоциативности в группах любого типа (см. с.28-43 в книге [Б.Л. ван дер Варден «Алгебра». Изд-во «Лань». 2004 г. - 623 с.]). Данное соотношение обусловливает свойство коммутативности процедуры шифрования также и в случае использования дополнительного секретного ключа шифрования. Действительно, пусть дана первая пара элементов Х₁ и W₁=Х₁ ^-1 (первый секретный ключ шифрования) и первое МДЧ е₁ (первый дополнительный секретный ключ шифрования), задающие функцию шифрования Е₁, а также дана вторая пара элементов X₂ и (второй секретный ключ шифрования) и второе МДЧ е₂ (второй дополнительный секретный ключ шифрования), задающие функцию Е₂. Легко показать, что имеет место равенство Е₂(Е₁(М))=E₁(E₂(M)), определяющее свойство коммутативности процедуры шифрования:

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

Пример 1

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

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

е∘е→е, e∘i→i, e∘j→j, i∘e→e, i∘i→j, i∘j→µe,

j∘e→j, j∘i→µe, j∘j→µi,

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

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

Z₁∘Z₂=(a₁e+b₁i+c₁j)∘(a₂e+b₂i+c₂j)=

=a₁a₂e∘e+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 может быть сгенерирована путем выбора простого МДЧ p и выбора ТУБВ, представленной таблицей 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). Генерация различных вариантов некоммутативных конечных групп шестимерных векторов осуществляется генерацией различных значений простого МДЧ р и различных конкретных значений коэффициентов µ и ε.

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

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

Пример 2

Данный пример иллюстрирует реализацию заявленного способа по пп.1, 2 и 3 формулы изобретения.

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

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

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

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

М=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

3. Генерируют секретный ключ шифрования в виде двух элементов Х и W группы Г:

X=(12051687713738, 12743450807620, 58233746685306, 75018447720758);

W=(66976554653300, 55000279002666, 77076465402894, 78895259854281).

Проверка показывает, что условие X∘W≠W∘X выполняется.

4. Генерируют криптограмму С, для чего

4.1) формируют вектор V конечной группы Г в зависимости от элемента Х конечной группы Г и сообщения М по формуле V=X∘M:

V=(68460548570101, 22813135953984, 62519151350007,84899633263035).

4.2) формируют криптограмму С путем выполнения групповой операции между элементами V и W конечной группы Г, т.е. по формуле С=V∘W:

С=(55081147763695, 7256895867211, 6835460242342, 10411406180456).

В результате выполненных действий сформирована криптограмма С, размер которой равен размеру исходного сообщения. Для ее правильного расшифрования, т.е. вычисления по С исходного сообщения, достаточно использовать только секретный ключ расшифрования, который легко вычисляется из секретного ключа шифрования. Необходимость наличия дополнительного блока данных, ассоциированного с криптограммой, в заявленном способе устранена. Криптограмму можно передавать по открытому каналу связи, поскольку получить из нее исходное сообщение может только законный получатель, владеющий секретным ключом шифрования (обмен ключами между санкционированными отправителями сообщений и получателями сообщений выполняется по защищенному каналу связи). Для постороннего субъекта, перехватывающего сообщения, передаваемые по каналу связи, вычисление секретного ключа шифрования или сообщения М вычислительно неосуществимо на практике при выборе размера МДЧ p, равного 80 бит и более. Данный вариант реализации заявленного способа шифрования увеличивает скорость шифрования по сравнению с прототипом, в котором по требованиям криптостойкости выбирается разрядность МДЧ р, равная 1024 бит. Действительно, одна операция умножения векторов в группе Г реализуется путем выполнения не более 22 операций умножения по 80-битовому модулю р. При шифровании выполняются две операции умножения векторов, т.е. всего 44 операции умножения по 80-битовому модулю. В способе-прототипе используются две операции возведения в степень, разрядность которой из соображений криптостойкости выбирается равной не менее 160 бит, поэтому одна операция возведения в степень в способе-прототипе требует выполнения в среднем не менее 160/2=80 операций умножения по 1024-битовому модулю, причем сложность операции умножения по модулю пропорциональна квадрату разрядности. Коэффициент λ достигаемого возрастания скорости составляет примерно

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

Расшифрование криптограммы в примере 2 выполняется по формуле расшифрования вида M′=X^-1∘C∘W^-1, где обратные значения X^-1 и W^-1 легко вычисляются:

Х^-1=(12051687713738, 74305788626841, 28815492749155, 12030791713703);

W^-1=(66976554653300, 32048960431795, 9972774031567, 8153979580180).

Вычисление по формуле расшифрования дает

М′=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

Сравнение с исходным сообщением показывает, что сообщение расшифровано правильно.

Пример 3

Данный пример иллюстрирует реализацию заявленного способа по п.4 формулы изобретения.

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

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

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

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

М=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

3. Генерируют секретный ключ шифрования в виде двух взаимно обратных элементов Х и W группы Г, для которых выполняются условия W=X^-1 и Х=W^-1, для чего

3.1) генерируют элемент X группы Г, значение порядка которого равно

q=43524619717231:

X=(12051687713738, 12743450807620, 58233746685306, 75018447720758);

3.2) вычисляют элемент W группы Г, например, по формуле

W=X^-1=X^q-1=X^{43524619717230}:

W=(12051687713738, 74305788626841, 28815492749155, 12030791713703).

Проверка показывает, что произведение WX равно единичному элементу Е=(1, 0, 0, 0) группы Г, т.е. элементы Х и W группы Г действительно являются взаимно обратными.

4. Генерируют криптограмму С, для чего

4.1) формируют вектор V конечной группы Г в зависимости от элемента X конечной группы Г и сообщения М по формуле V=X∘M:

V=(68460548570101, 22813135953984, 62519151350007, 84899633263035);

4.2) формируют криптограмму С путем выполнения групповой операции между элементами V и W конечной группы Г, т.е. по формуле С=V∘W:

C=(38231784837662, 55597852011830, 31133631402162, 67373330976147).

В результате выполненных действий сформирована криптограмма С, размер которой равен размеру исходного сообщения. Расшифрование криптограммы выполняется по формуле расшифрования М′=Х^-1∘С∘W^-1, где Х^-1=W и W^-1=X. По формуле расшифрования получаем

М′=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

Сравнение с исходным сообщением показывает, что сообщение расшифровано правильно.

Пример 4

Данный пример иллюстрирует реализацию заявленного способа по п.5 формулы изобретения.

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

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

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

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

М=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

3. Генерируют секретный ключ шифрования в виде двух элементов Х и W группы Г, значение порядка которых равно q=43524619717231:

X=(12051687713738, 12743450807620, 58233746685306, 75018447720758);

W=(66976554653300, 55000279002666, 77076465402894, 78895259854281).

Проверка показывает, что условие X∘W≠W∘X выполняется.

4. Генерируют дополнительный секретный ключ шифрования в виде случайного МДЧ е=1564738297.

5. Генерируют криптограмму С, для чего

5.1) формируют элемент R конечной группы Г, равный е-й степени сообщения М, т.е. R=М^е

R=(33165708342194, 44635145878926, 27218913703632, 86167722855141);

5.2) формируют элемент V конечной группы Г путем выполнения групповой операции между элементами Х и R группы Г, т.е. по формуле V=Х∘M^e=X∘R:

V=(21225882163327,81784979805756, 36290579760498, 59011556699378);

5.3) формируют криптограмму С путем выполнения групповой операции между элементами V и W конечной группы Г, т.е. по формуле С=V∘W:

С=(81151321903463; 34928622232905; 40321732625021; 27943213385539).

В результате выполненных действий сформирована криптограмма С, размер которой равен размеру исходного сообщения. По криптограмме исходное сообщение получают по формуле расшифрования М′=(X^-1∘C∘W^-1)^d, где Х^-1=W,

W^-1=Х и d - МДЧ, обратное к МДЧ е по модулю р(р²-1);

d=e^-1modp(p²-1)=57047190496431981721267140853661386109713;

X^-1=(12051687713738, 74305788626841, 28815492749155, 12030791713703);

W^-1=(66976554653300, 32048960431795, 9972774031567, 8153979580180).

Вычисления по формуле расшифрования дают

X^-1∘C∘W^-1=

=(33165708342194, 44635145878926, 27218913703632, 86167722855141);

(X^-1∘C∘W^-1)^d=(X^-1∘C∘W^-1)^{57047190496431981721267140853661386109713}=

=(56361567605757, 15257986828317, 58542760700288, 35609765290075;)

M′=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

Сравнение с исходным сообщением показывает, что сообщение расшифровано правильно.

Пример 5

Данный пример иллюстрирует реализацию заявленного способа по п.6 формулы изобретения.

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

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

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

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

М=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

3. Генерируют секретный ключ шифрования в виде двух взаимно обратных элементов Х и W группы Г, для которых выполняются условия W=X^-1 и Х=W^-1, для чего

3.1) генерируют элемент Х группы Г, значение порядка которого равно

q=43524619717231:

X=(12051687713738, 12743450807620, 58233746685306, 75018447720758);

3.2) вычисляют элемент W группы Г, например, по формуле

W=X^-1=X^q-1=X^{43524619717230}:

W=(12051687713738, 74305788626841, 28815492749155, 12030791713703).

Проверка показывает, что произведение WX равно единичному элементу Е=(1, 0, 0, 0) группы Г, т.е. элементы X и W группы Г действительно являются взаимно обратными.

4. Генерируют дополнительный секретный ключ шифрования в виде случайного МДЧ е=1564738297.

5. Генерируют криптограмму С, для чего

5.1) формируют элемент R конечной группы Г, равный е-той степени сообщения М, т.е. R=M^e

R=(33165708342194, 44635145878926, 27218913703632, 86167722855141);

5.2) формируют элемент V конечной группы Г путем выполнения групповой операции между элементами Х и R группы Г, т.е. по формуле V=Х∘M^e=X∘R:

V=(21225882163327, 81784979805756, 36290579760498, 59011556699378);

5.3) формируют криптограмму С путем выполнения групповой операции между элементами V и W конечной группы Г, т.е. по формуле С=V∘W:

С=(33165708342194, 59052072691720, 80363916760611, 79904520870827).

В результате выполненных действий сформирована криптограмма С, размер которой равен размеру исходного сообщения. Расшифрование криптограммы выполняется по формуле расшифрования М′=Х^-1∘C^d∘W^-1, где Х^-1=W,

W^-1=Х и d - МДЧ, обратное к МДЧ е по модулю р(р²-1);

d=e^-1 mod p(p²-1)=57047190496431981721267140853661386109713.

Вычисления по формуле расшифрования дают

C^d=(38231784837662, 55597852011830, 31133631402162, 67373330976147);

X^-1∘C^d=X^-1∘C^{57047190496431981721267140853661386109713}=

=(11810164016425, 31707129959260, 10338075247979, 75038288163169);

(X^-1∘C^d)∘W^-1=

=(38231784837662, 81700379195104, 32430684295463, 4516085675164);

M′=(38231784837662, 81700379195104, 32430684295463, 4516085675164).

Сравнение с исходным сообщением показывает, что криптограмма С расшифрована правильно, т.е. из нее получено исходное сообщение М. В варианте реализации заявленного способа по примерам 4 и 5 наиболее трудоемкой операцией при выполнении процедуры шифрования (расшифрования) является операция возведения в степень МДЧ е (МДЧ d). Для обеспечения требуемой криптостойкости достаточно выбрать разрядность МДЧ р, равную 80 бит, поэтому разрядность МДЧ е и d составляет 80 бит и 240 бит, соответственно. С учетом этих значений расчет коэффициента α повышения скорости шифрования и скорости расшифрования, обеспечиваемого реализацией заявленного способа по примерам 4 и 5, в сравнении со способом-прототипом, в котором вычисления ведутся по 1024-битовому модулю, дает:

При этом в заявленном способе устранена необходимость генерации дополнительного блока данных, ассоциируемого с криптограммой. Кроме того, реализация заявленного способа по пп.4 и 6 обеспечивает свойство коммутативности процедуры шифрования, что позволяет использовать заявленный способ шифрования для повышения скорости конфиденциальной передачи сообщений по открытым каналам без обмена ключами между отправителем и получателем при использовании протокола, описанного в книге [Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. СПб. БХВ-Петербург, 2005. - 286 с.; см. с.129-133] и основанного на применении коммутативной процедуре шифрования.

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

Приложение 1

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

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

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

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

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

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

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

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

8. Разрядность МДЧ - это число двоичных разрядов (битов) в записи МДЧ по двоичному основанию.

9. Простое МДЧ - это МДЧ, которое делится только на единицу и на само себя.

10. Взаимно простые МДЧ - это МДЧ, наибольший общий делитель которых равен единице.

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

12. Сложность операции Oper - количество стандартных элементарных битовых операций (т.е. операций над битами), которые необходимо осуществить для выполнения операции Oper. Чем сложнее операция, тем больше время ее выполнения.

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

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

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

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

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

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

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

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

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

22. Коммутирующие элементы группы Г - это два элемента Z₁∈Г и Z₂∈Г, действие групповой операции над которыми дает результат, не зависящий от порядка расположения этих элементов, т.е. для коммутирующих элементов выполняется соотношение Z₁∘Z₂=Z₂∘Z₁.

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

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

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

1. Способ шифрования, заключающийся в том, что генерируют конечную группу Г, формируют сообщение в виде элемента М конечной группы Г, генерируют секретный ключ шифрования, генерируют криптограмму в виде элемента С конечной группы Г путем преобразования сообщения М в зависимости от секретного ключа шифрования, отличающийся тем, что в качестве конечной группы Г генерируют некоммутативную конечную группу, генерируют секретный ключ шифрования в виде двух элементов X и W группы Г и многоразрядного двоичного числа е, генерируют криптограмму С путем формирования элемента R конечной группы Г, равного е-й степени сообщения М, т.е. R=М^е, формирования элемента V конечной группы Г в зависимости от элементов X и R конечной группы Г и последующего выполнения групповой операции между элементами V и W конечной группы Г.

2. Способ по п.1, отличающийся тем, что формируют элемент V конечной группы Г путем выполнения групповой операции между элементами X и R конечной группы Г.

3. Способ по п.2, отличающийся тем, что генерируют секретный ключ шифрования в виде многоразрядного двоичного числа е и двух элементов X и W группы Г, удовлетворяющих условию где знак ◦ обозначает групповую операцию.

4. Способ по п.2, отличающийся тем, что генерируют секретный ключ шифрования в виде многоразрядного двоичного числа е и двух взаимно обратных элементов X и W группы Г, для которых выполняются условия W=X^-1 и X=W^-1.