СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ-ДЕШИФРОВАНИЯ Российский патент 2018 года по МПК H04L9/08 

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

Известны способы формирования ключей шифрования/дешифрования (Okamoto Е. Key distribution Systems based on identification information. - Adwances in Cryptology. CKYPTO, 87, Leeture Notex in Computers Science, №293, Springer - Verlag, 1988, p. 194-202), заключающиеся в формировании конфиденциального ключа центра распределения ключей (ЦРК), присвоении идентификаторов пользователям, выработке личных конфиденциальных ключей пользователей, получении сеансовых ключей для конфиденциальной связи любой пары корреспондентов. Однако известные способы-аналоги являются лишь вычислительно стойкими и не позволяют получить безусловную стойкость к компрометациям личных и сеансовых ключей.

Наиболее близким по своей технической сущности к заявляемому является способ формирования ключа шифрования-дешифрования по патенту РФ №2090006, МПК H04L 9/00, опубл. 10.09.1997. Способ-прототип заключается в формировании конфиденциального ключа ЦРК как коэффициентов симметричного многочлена над заданным конечным полем, присвоение идентификаторов Y_A, Y_B пользователям (А и В номера пользователей в системе обмена, A≠В), выработку личных конфиденциальных ключей пользователей как коэффициентов многочленов над заданным полем и получение сеансовых ключей для любой пары корреспондентов как значения многочленов.

Пусть n - требуемая длина ключа, r=n/16 - количество блоков ключа, а - число компрометаций личных ключей. Тогда формирование конфиденциального ключа ЦРК осуществляют путем выбора на основе случайных чисел коэффициентов b_i,sν, b_i,mm симметричных полиномов {ƒ_l(x_l,x₂)}, где , вида

,

где b_i,sν≠0, , , b_i,mm≠0, , , выработку личного конфиденциального ключа пользователя А в виде коэффициентов полиномов {g_A,i(х₁,х₂)}, , полученных подстановкой идентификатора Y_A вместо одного из аргументов полинома Х₁ или Х₂, получение сеансового ключа K_АB подстановкой в полиномы {g_A,i(x)}, , коэффициентами которых является личный конфиденциальный ключ пользователя А, идентификатора Y_B вместо аргумента X, при этом сеансовый ключ длиной n бит представляет собой конкатенацию элементов ключа {K_AB,i}, по 16 бит каждый, где K_АВ=K_AB,0+K_AB,1⋅(2¹⁶)+K_AB,2⋅(2¹⁶)²+K_AB,r-1⋅(2¹⁶)^r-1, r=n/16, g_A,i(x)=ƒ_i(x,y_A)mod2¹⁶, , K_AB,i=g_A,i(y_B)mod2¹⁶, .

Однако, учитывая, что для обеспечения гарантированной стойкости криптографической системы длина ключа n должна быть не менее 256 бит (ГОСТ 28147-89, ГОСТ Р 34.12-2015), способ-прототип имеет недостатки. При программно-аппаратной реализации устройств, выполняющих процедуры получения личных и сеансовых ключей, возникают проблемы при применении этих устройств для работы в реальном масштабе времени, так как на выполнение этих процедур требуется нерационально много процессорного времени. В частности, повышается вычислительная сложность процедур из-за того, что при использовании современных 64 разрядных микропроцессоров, таких как 1891ВМ8Я, происходит единовременное выполнение операций лишь над элементами, состоящими из 16 бит ключа.

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

Поставленная цель достигается тем, что в способе формирования ключа шифрования-дешифрования, заключающемся в формировании конфиденциального ключа ЦРК как коэффициентов симметричного многочлена над заданным конечным полем, присвоении идентификаторов Y_A, Y_B пользователям (А и В номера пользователей в системе обмена, А≠В), выработке личных конфиденциальных ключей пользователей как коэффициентов многочленов над заданным полем и получении сеансовых ключей для любой пары корреспондентов как значения многочленов, согласно изобретению вместо конечного поля GF(2¹⁶) используется поле GF(2⁶⁴).

Тогда алгоритм формирования ключа шифрования-дешифрования будет модифицирован следующим образом.

Пусть n - требуемая длина ключа, r=n/64 - количество блоков ключа, а - число компрометаций личных ключей. Пусть F∈F[x] - некоторый неприводимый многочлен степени 64 над полем GF(2). Тогда на его основе строится факторкольцо F[x]/(F), являющееся полем Галуа GF(2⁶⁴). Каждому пользователю А по некоторому правилу ставится во взаимно-однозначное соответствие единственный элемент данного поля Y_A∈GF(2⁶⁴). Формирование конфиденциального ключа ЦРК осуществляют путем выбора на основе датчика случайных чисел коэффициентов симметрических полиномов {ƒ_i(x₁,x₂)}, над полем GF(2⁶⁴). Личный конфиденциальный ключ пользователя А вырабатывается в виде коэффициентов полиномов {g_A,i(x)}, , получаемых при подстановке в полиномы {ƒ_i(x₁,x₂)}, , идентификатора Y_A вместо одного из аргументов: g_A,i(x)=ƒ_i(x,Y_A)=ƒ_i(Y_A,x)mod(2⁶⁴). Сеансовый ключ K_АВ получен с помощью подстановки в личный конфиденциальный ключ {g_A,i(x)}, идентификатора корреспондента В: K_AB,i=g(Y_B)mod(2⁶⁴). При этом сеансовый ключ длиной n бит представляет собой конкатенацию значений многочленов над полем GF(2⁶⁴) K_АВ=K_AB,0||K_AB,1||…||K_AB,r-1, т.e. может быть вычислен по формуле K_АВ=К_АВ,0+К_АВ,1⋅(2⁶⁴)+K_AB,2⋅(2⁶⁴)²+K_AB,r-1⋅(2⁶⁴)^r-1.

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

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

Благодаря новой совокупности существенных признаков в заявленном способе уменьшение временных затрат на выполнение процедур получения личных и сеансовых ключей и вычислительной сложности данных процедур, повышение количества пользователей достигается за счет использования вместо конечного поля GF(2¹⁶) поля GF(2⁶⁴), т.е. арифметические операции выполняются над числами, разрядность которых соответствует применяемым типовым 64-разрядным микропроцессорам, например 1891ВМ8Я, вместо ранее применяемого 16-разрядного типового микропроцессора, например КР1810ВМ86, что приводит к уменьшению количества конкатенаций элементов ключа. Представление конфиденциального ключа ЦРК, личных конфиденциальных ключей пользователей и сеансовых ключей в виде конкатенации r независимых частей сохраняет равновероятное распределение значения сеансового ключа в интервале (1, 2⁶⁴), устойчивость к компрометациям, также, если бы в качестве конфиденциального ключа ЦРК были выбраны коэффициенты одного полинома ƒ(х₁,х₂) в конечном поле GF(2¹⁶), в качестве личного конфиденциального ключа коэффициенты полинома g_A(x) в GF(2¹⁶). Такое представление позволяет, не изменяя общего объема конфиденциального ключа ЦРК, личных конфиденциальных ключей пользователей, уменьшить вычислительную сложность процедур получения сеансовых и личных конфиденциальных ключей более чем в 4 раза.

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

,

где b_i,sν≠0, , , b_i,mm≠0, , . Тогда вычислительная сложность алгоритма получения ключа определяется как , где h - время выполнения одной операции (зависит от процессора). Для сравнения вычислительная сложность алгоритма-прототипа определяется как . Для вычисления личного ключа пользователей необходимо на основании симметрических многочленов рассчитать коэффициенты полиномов вида , . Вычислительная сложность данной задачи определяется как для алгоритма-прототипа над полем GF(2¹⁶) и для представленного алгоритма над полем GF(2⁶⁴). Для вычисления сеансового ключа необходимо рассчитать значения r многочленов над заданным полем Галуа. Сложность этого алгоритма: для случая GF(2¹⁶) и для случая GF(2⁶⁴), т.е. получаем уменьшение сложности в 4 раза по сравнению с прототипом. На основании ГОСТ Р 34.12-2015 сложность алгоритмов определяется как , , для формирования конфиденциального, личного и сеансового ключей соответственно. Для сравнения сложности данных алгоритмов в способе прототипе определяются как , и соответственно.

Реализация заявленного способа формирования ключа шифрования/дешифрования длиной n, например 256 бит, объясняется следующим образом. После того, как выбраны значения требуемой стойкости системы обмена конфиденциальной информацией к компрометациям личных ключей пользователей и неприводимый табличный полином степени 64, в ЦРК формируют конфиденциальный ключ в виде конкатенации коэффициентов симметрических полиномов {ƒ_i(x₁,x₂)}, , которые выбирают на основе датчика случайных чисел. Можно показать, что для того, чтобы сохранить объем конфиденциального ключа ЦРК и личных конфиденциальных ключей пользователей для заданной стойкости к компрометациям личных конфиденциальных ключей пользователей, симметрические полиномы {ƒ_i(x_l,x₂)}, , у которых все коэффициенты отличны от нуля, должны иметь вид

,

где b_isν≠0, , b_i,mm≠0, , . После этого конфиденциальный ключ ЦРК записывается на носителе, содержится в секрете и известен только ЦРК. Присвоение идентификаторов пользователям осуществляется путем постановки им в соответствие некоторого элемента поля Галуа Y_i∈GF(2⁶⁴), такого, что Y_i≠Y_j, при i≠j, которое выбирают, например, либо на основе датчика случайных чисел, либо получают элемент по номеру, под которым пользователь вводится в систему, как степень этого элемента в мультипликативной группе поля Галуа. Идентификаторы пользователей размещаются на носителе. Данный носитель доступен всем пользователям. Выработку личного конфиденциального ключа, например пользователя А, осуществляют путем подстановки его идентификатора Y_A вместо одного из аргументов в симметрические полиномы {ƒ_i(х₁,х₂)}, . Тогда личный ключ представляет собой конкатенацию коэффициентов полиномов {g_A,i(x)}, , где g_A,i(x)=ƒ_i(x,Y_A) и которые после преобразования имеют вид:.

После этого личный конфиденциальный ключ записывают на носителе (перфоленте, магнитной ленте, магнитном диске и т.д.), выдают пользователю, который хранит его в секрете.

Теперь, если какие-либо пользователи, например А и В, хотят получить сеансовый ключ K_AB, причем K_АВ=K_ВА, то для этого каждый из них, например пользователь А, выполняет подстановку идентификатора пользователя В в полиномы {g_A,i(x)}, , коэффициенты которых являются личным ключом пользователя A: K_AB,i.=g(Y_B)mod(2⁶⁴). Сеансовый ключ K_АВ длиной, например, 256 бит образуют как конкатенацию К_АВ=K_АВ,0||K_АВ,1||K_АВ,2||K_АВ,3, или K_АВ=K_AB,0+K_AB,0⋅(2⁶⁴)+K_АВ,2⋅(2⁶⁴)²+K_АВ,r-1⋅(2⁶⁴)³.

Таким образом, в рассмотренном способе за счет использования вместо конечного поля GF(2¹⁶) поля GF(2⁶⁴) обеспечивается достижение сформулированного технического результата - снижение временных затрат на выполнение процедур получения личных и сеансовых ключей, уменьшение вычислительной сложности процедур получения сеансовых и личных конфиденциальных ключей и увеличение общего числа пользователей в системе с 2¹⁶ (≈32000) до 2⁶⁴ (≈128000).

Изобретение относится к области криптографии, а именно к распределению ключей шифрования-дешифрования. Техническим результатом является снижение временных затрат на выполнение процедур получения личных и сеансовых ключей. Технический результат достигается за счет формирования конфиденциального ключа центра распределения ключей, которое осуществляют путем выбора на основе датчика случайных чисел коэффициентов симметрических полиномов {ƒ_i{x₁, x₂)}, над полем GF(2⁶⁴), личный конфиденциальный ключ пользователя А вырабатывается в виде коэффициентов полиномов {g_A,i (x)}, , получаемых при подстановке в полиномы {ƒ_i(x₁, x₂)}, , идентификатора Y_A вместо одного из аргументов: g_A,i(x)=ƒ_i(x,Y_A)=ƒ_i(Y_A, x)mod(2⁶⁴), сеансовый ключ K_AB получается с помощью подстановки в личный конфиденциальный ключ {g_A,i(x)}, идентификатора корреспондента В: K_AB,i=g(Y_B)mod(2⁶⁴), при этом сеансовый ключ длиной n бит представляет собой конкатенацию значений многочленов над полем GF(2⁶⁴) К_АВ=К_АВ,0||К_АВ,1||…||K_AB,r-1, т.е. может быть вычислен по формуле К_АВ=K_AB,0+К_АВ,1⋅(2⁶⁴)+К_АВ,2⋅(2⁶⁴)²+К_АВ,r-1⋅(2⁶⁴)^r-1.

Способ формирования ключа шифрования-дешифрования, включающий формирование конфиденциального ключа центра распределения ключей как коэффициентов симметричного многочлена над заданным конечным полем, присвоение идентификаторов Y_A, Y_B пользователям (А и В номера пользователей в системе обмена, А≠В), выработку личных конфиденциальных ключей пользователей как коэффициентов многочленов над заданным полем и получение сеансовых ключей для любой пары корреспондентов как значения многочленов, отличающийся тем, что формирование конфиденциального ключа центра распределения ключей осуществляют путем выбора на основе датчика случайных чисел коэффициентов симметрических полиномов {ƒ_i{x₁, x₂)}, над полем GF(2⁶⁴), личный конфиденциальный ключ пользователя А вырабатывается в виде коэффициентов полиномов {g_A,i (x)}, , получаемых при подстановке в полиномы {ƒ_i(x₁, x₂)}, , идентификатора Y_A вместо одного из аргументов g_A,i(x)=ƒ_i(x,Y_A)=ƒ_i(Y_A, x)mod(2⁶⁴), сеансовый ключ K_AB получается с помощью подстановки в личный конфиденциальный ключ {g_A,i(x)}, идентификатора корреспондента В: K_AB,i=g(Y_B)mod(2⁶⁴), при этом сеансовый ключ длиной n бит представляет собой конкатенацию значений многочленов над полем GF(2⁶⁴) К_АВ=К_АВ,0||К_АВ,1||…||K_AB,r-1, т.е. может быть вычислен по формуле К_АВ=K_AB,0+К_АВ,1⋅(2⁶⁴)+К_АВ,2⋅(2⁶⁴)²+К_АВ,r-1⋅(2⁶⁴)^r-1.