Способ шифрования
Владельцы патента RU 2450457:
Государственное образовательное учреждение высшего профессионального образования Марийский государственный технический университет (RU)
Изобретение относится к области электросвязи, а именно к области устройств и способов криптографической защиты информации, хранящейся на носителях информации, либо передаваемой по открытым каналам связи. Техническим результатом является повышение криптостойкости при использовании относительно невысоких степеней вычислений. Технический результат достигается тем, что формируют исходное сообщение М в виде элемента некоммутативной конечной группы Г на основе алгебры Кэли с выполнением операций по модулю простого числа p, генерируют секретный ключ шифрования в виде пары элементов Х и X-1 группы Г и многоразрядного числа е, генерируют начальную криптограмму Y путем формирования элемента R группы Г возведением исходного сообщения М в степень е, формирования элемента V группы Г путем выполнения групповой операции над элементами Х и R группы Г и последующего выполнения групповой операции над элементами V и X-1 группы Г, генерируют криптограмму С в виде элемента Г путем у-кратного выполнения операции, аналогичной операции генерирования начальной криптограммы Y, за исключением того, что на каждом i шаге в качестве элементов Х и X-1 группы Г используются элементы Xi и X-i соответственно, а вместо элемента М используется результат предыдущей операции (Y, Y1, Y2, …, Yi). 3 табл., 1 пр.
Изобретение относится к области электросвязи и вычислительной техники, а именно к области информационной безопасности вычислительных и телекоммуникационных систем, и может быть использовано в системах криптографической защиты информации, обеспечивающих конфиденциальность сообщений, передаваемых по открытым каналам связи, и данных, хранящихся на информационных носителях.
Известен способ шифрования [Смарт Н. Мир программирования. Криптография. М.: ТЕХНОСФЕРА, 2005. - 525 с.; см. с.200-202], в котором генерируют конечную группу Г с операцией умножения по модулю р, где р - простое число, в качестве групповой операции. Формируют элемент G конечной группы Г. У получателя сообщения генерируют открытый ключ в виде элемента Y конечной группы Г, для чего генерируют его личный секретный ключ в виде любого натурального числа х, и вычисляют Н по формуле Н=Gx mod p. Открытый ключ G передают по открытому каналу отправителю сообщения. У отправителя сообщения генерируют секретный ключ шифрования в виде элемента Z конечной группы Г, для чего формируют вспомогательный секретный ключ в виде случайного k и вычисляют элемент R группы Г по формуле R=Gk mod p. По открытому ключу получателя и вспомогательному секретному ключу k генерируют секретный ключ шифрования Z по формуле Z=Hk mod p. Затем формируют сообщение в виде элемента М конечной группы Г и генерируют криптограмму в виде элемента С конечной группы Г путем выполнения групповой операции между элементами Z и М, т.е. по формуле C=Z·M mod p. Недостатком данного способа шифрования является относительная сложность реализации процедуры шифрования, затраты памяти, выделяемой на хранение и обработку нескольких ключей, и относительное увеличение времени передачи сообщений, также связанное с обработкой и передачей нескольких ключей.
Также известен способ шифрования, являющийся ближайшим аналогом, заключающийся в генерации конечной группы Г, формирования сообщения в виде элемента М конечной группы Г, генерации секретного ключа шифрования, генерации криптограммы в виде элемента С конечной группы Г путем преобразования сообщения М в зависимости от секретного ключа шифрования [Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. СПб.: БХВ-Петербург, 2010. - 304 с.; см. с.245-248].
Прототип выполняет следующие действия:
1. Генерируют некоммутативную конечную группу Г.
2. Формируют сообщение в виде элемента М конечной группы Г. Генерируют секретный ключ шифрования в виде многоразрядного двоичного числа е и двух взаимно обратных элементов Х и W группы Г, для которых выполняются условия W=Х-1 и Х=W-1.
3. Генерируют криптограмму С путем формирования элемента R конечной группы Г, равного е-й степени сообщения М, т.е. R=Me, формирования элемента V конечной группы Г путем выполнения групповой операции между элементами Х и R конечной группы Г и последующего выполнения групповой операции между элементами V и W конечной группы Г.
Недостатком прототипа является неформализованное правило умножения базисных векторов и, следовательно, неформализованный способ получения элементов конечной группы Г. Алге6ры Клиффорда-Грассмана позволяют алгоритмизировать процедуру построения различных таблиц умножения элементов некоммутативных групп. Также прототип использует поиск одного сопряженного элемента некоммутативной группы. Данная задача относится к классу сложных, однако однократное применение этой процедуры значительно уступает по сложности ее многократному применению. Разработанный способ предлагает поиск нескольких сопряженных элементов (до р), что существенно повышает криптостойкость предлагаемого алгоритма, по сравнению с прототипом.
Целью изобретения является разработка метода шифрования с четко определенным способом задания конечных некоммутативных групп, обладающего повышенной криптостойкостью при использовании относительно малых разрядностей чисел за счет значительного повышения вычислительной емкости алгоритма.
Поставленная цель достигается путем того, что генерируют конечную группу Г, формируют исходное сообщение М в виде элемента конечной группы Г, формируют секретный ключ шифрования, генерируют криптограмму С в виде элемента группы Г преобразованием исходного сообщения М секретным ключом шифрования, отличаясь тем, что в качестве конечной группы Г генерируют некоммутативную конечную группу на основе алгебры Клиффорда с выполнением групповых операций по модулю простого многоразрядного числа р, генерируют секретный ключ шифрования в виде пары элементов Х и X-1 группы Г и многоразрядного числа е, генерируют начальную криптограмму Y путем формирования элемента R группы Г возведением исходного сообщения М в степень е, формирования элемента V группы Г путем выполнения групповой операции над элементами Х и R группы Г и последующего выполнения групповой операции над элементами V и X-1 группы Г, генерируют криптограмму С путем у-кратного выполнения операции, аналогичной операции генерирования начальной криптограммы Y, за исключением того, что на каждом i шаге в качестве элементов Х и X-1 группы Г используются элементы Xi и X-i соответственно, а вместо элемента М используется результат предыдущей операции (Y, Y1, Y2, …, Yi).
Новым в разработанном методе является способ формирования группы Г по конкретизированному правилу умножения базисных векторов, основанному на использовании специального вида ассоциативной алгебры, называемой также алгеброй Клиффорда. Конечные ассоциативные группы, основанные на данном виде алгебры, всегда проявляют некоммутативные свойства, не требуя каких-либо дополнительных подборов коэффициентов.
Также новым в изобретении является то, что над исходным сообщением у-кратно выполняют групповые операции. Это производится с целью максимально полного использования возможного набора разрешенных элементов конечной группы, что позволяет многократно усилить криптостойкость кодированного сообщения.
Изобретательский замысел заявленного нового технического решения состоит в применении некоммутативных конечных групп, построенных по правилам алгебры Клиффорда и имеющих элементы, значения которых не превышают некоторого простого многоразрядного числа р, в которых в общем случае результат выполнения групповой операции зависит от порядка расположения элементов группы, над которыми выполняется групповая операция. Благодаря этому уравнения вида C=X•Ze•X-1 с неизвестным значением Х являются трудно решаемыми при соответствующем выборе группы Г и ее элементов Х и Z. Это позволяет использовать значение Х в качестве секретного ключа шифрования и выполнять шифрование, предварительно формируя сообщение в виде элемента М группы Г, по формуле Y=X•Me•X-1, где е - многоразрядное число. Для получения шифротекста С с целью увеличения криптостойкости получаемого шифра применяется у-кратное выполнение аналогичной групповой операции, в которой на каждом i шаге вместо значений Х и X-1 принимаются элементы Xi и Х-i группы Г, а в качестве элемента М группы Г принимается результат предыдущего шага, т.е.
где 
а Y1=X•Me•X-1.
На начальном этапе реализации метода следует сгенерировать 2 некоммутативные конечные подгруппы: Г1 для выбора из нее элемента секретного ключа X, и Г2 для формирования на основе ее элементов исходного сообщения М. Данные подгруппы формируются по одному из правил алгебры Клиффорда с условием, что порядок подгрупп будет максимально возможным для выбранного способа построения, а значения элементов не превосходят выбранного многоразрядного простого числа р. Для генерации элемента секретного ключа Х следует выбрать любой элемент подгруппы Г1, не являющийся единичным элементом группы. Также генерируются дополнительные ключи шифрования в виде многоразрядных чисел е и у. При такой реализации заявленного способа шифрования формула шифрования примет вид:
где 
а Y1=X•Me•X-1.
Формула расшифровки сообщения в этом случае примет вид:
где 
а Yу=X-y•Cd•Xy,
где d - дополнительный секретный ключ дешифрования, который легко вычисляется из дополнительного секретного ключа шифрования как МДМ, обратное е по модулю, равному максимальному значению р порядка элементов группы.
Как уже говорилось, правило задания конечной некоммутативной группы основывается на выполнении групповой операции по правилам алгебры Клиффорда. Это позволяет конкретизировать генерацию конечной группы и, более того, увеличить мощность шифрования, поскольку с каждым новым выбранным правилом выполнения групповой операции меняется порядок элементов конечной группы. Этот факт является дополнительным фактором в усилении стойкости алгоритма шифрования. Так, например, для известного множества векторов алгебры Клиффорда, названных кватернионами, правило выполнения групповой операции над векторами вида (1, ie1, je2, ke3) при построении таблицы умножения базисных векторов имеет диагональ вида (1, -1, -1, -1). Ниже приведены примеры таблиц умножения базисных векторов.
Аналогичным способом можно задается любое правило выполнения групповых операций. Также правила алгебры Клиффорда позволяют генерировать конечные некоммутативные группы с n-мерными элементами. Так, известными примерами реализации правил n-мерной алгебры Клиффорда являются 4-мерные кватернионы, 8-мерные бикватернионы, 16-мерные седенионы, и т.д.
Рассмотрим пример реализации заявленного способа шифрования.
Пример 1
Реализация способа шифрования сообщения с последующей его расшифровкой. Для формирования группы используется наиболее распространенное правило умножения элементов алгебры Клиффорда, формирующее множество кватернионов (Таблица 1).
1. Генерируют простое число р=67.
2. Генерируют две подгруппы Г1 и Г2.
3. Генерируют элемент секретного ключа Х из подгруппы Г1, а также дополнительные ключи шифрования - произвольное простое число е и произвольное число у. Также из группы М2 выберем произвольный элемент М в качестве исходного сообщения.
Х=(13 40 29 54), е=13, у=7.
4. Формируют исходное сообщение в виде элемента М подгруппы Г2.
М=(40 13 57 59)
5. Генерируют криптограмму С
Y1=X•M13•X-1=(37 1 40 19),
…
В результате указанных выше действий получают криптограмму С. Для вычисления исходного сообщения М из шифра С найдем дополнительный секретный ключ расшифрования d=1381, который вычисляется из дополнительного секретного ключа шифрования как МДМ, обратное е по модулю, равному максимальному значению р порядка элементов группы.
,
,
…
Сравнение вычисленного сообщения с исходным сообщением показывает, что криптограмма С расшифрована правильно, т.е. из нее получено исходное сообщение М.
Таким образом, приведенные конкретные примеры реализации показывают, что заявляемый способ шифрования технически реализует и позволяет достичь сформулированный технический результат.
Способ шифрования, заключающийся в том, что генерируют конечную группу Г, формируют исходное сообщение М в виде элемента конечной группы Г, формируют секретный ключ шифрования, генерируют криптограмму С в виде элемента группы Г преобразованием исходного сообщения М секретным ключом шифрования, отличающийся тем, что в качестве конечной группы Г генерируют некоммутативную конечную группу на основе алгебры Кэли с выполнением операций по модулю простого числа р, генерируют секретный ключ шифрования в виде пары элементов Х и X-1 группы Г и многоразрядного числа е, генерируют начальную криптограмму Y путем формирования элемента R группы Г возведением исходного сообщения М в степень е, формирования элемента V группы Г путем выполнения групповой операции над элементами Х и R группы Г и последующего выполнения групповой операции над элементами V и X-1 группы Г, генерируют криптограмму С путем у-кратного выполнения операции, аналогичной операции генерирования начальной криптограммы Y, за исключением того, что на каждом i шаге в качестве элементов Х и X-1 группы Г используются элементы Xi и X-i соответственно, а вместо элемента М используется результат предыдущей операции (Y, Y1, Y2, …, Yi).
