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

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

Известны способы формирования ключей шифрования/дешифрования [1] включающие формирование конфиденциального ключа центра распределения ключей (ЦРК), присвоение идентификаторов пользователям, выработку личных конфиденциальных ключей пользователей, получение сеансовых ключей для конфиденциальной связи любой пары корреспондентов. Однако, известные способы-аналоги являются лишь вычислительно стойкими и не позволяют получить безусловную стойкость к компрометациям личных и сеансовых ключей.

Наиболее близким по своей технической сущности к заявляемому способу формирования ключа шифрования/дешифрования является способ [2] Способ-прототип включает формирование конфиденциального ключа ЦРК, присвоение идентификаторов пользователям, выработку личных конфиденциальных ключей пользователей и получение сеансовых ключей для любой пары корреспондентов.

Формирование конфиденциального ключа ЦРК заключается в выборе случайным образом, например, при помощи датчика случайных чисел элементов симметричных матриц G₁, G₂, G_n размера m•m в конечном поле GF (2ⁿ).

Присвоение идентификаторов пользователям осуществляется следующим образом: i пользователю ставится в соответствие какое-то число y_i такое, что y_i≠y_j, при i≠j, например, номер, под которым пользователь вводится в систему.

Выработки личных конфиденциальных ключей заключается в выработке для каждого пользователя конфиденциального алгоритма X_i:
X_i(ξ) = x_i•R(ξ)^тmod(2ⁿ), ξ ∈ I
для каждого y_i ∈ I Здесь, I=y₁, y₂, множество идентификаторов всех пользователей, x_i есть матрица размера (n, m) и определяется выражением

где R однонаправленная функция, которая преобразует идентификатор пользователя y_i в матрицу R(y_i) размера 1•m.

Сеансовый ключ длиной n бит между корреспондентами A и B вычисляется как
K_AB=X_A(y_B) mod(2ⁿ)=X_B(y_A) mod(2ⁿ).

Однако, учитывая, что для обеспечения гарантированной стойкости криптографической системы длина ключа n должна быть не менее 256 бит (ГОСТ 28147-89. Спесивцев А. В. и др. Защита информации в персональных ЭВМ. М. Радио и связь, 1992 г. с. 29-44), способ-прототип имеет недостатки.

Для построения конечного поля GF(2ⁿ) необходимо выбрать неприводимый полином степени n (Лидл Р. Нидеррайтер Г. Конечные поля. М. Мир, 1988 г. с. 40-46). Процедура поиска таких полиномов заключается в случайном выборе полинома степени n и его тестирования на неприводимость. При этом тест дает лишь вероятностную оценку (Мафтик С. Механизмы защиты в сетях ЭВМ. М. Мир, 1993 г. с. 57-58).

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

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

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

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

Технический результат достигается тем, что в известном способе формирования ключа шифрования/дешифрования, включающем формирование конфиденциального ключа ЦРК, присвоение идентификаторов пользователям, выработку личных конфиденциальных ключей пользователей и получение сеансовых ключей для конфиденциальной связи любой пары пользователей, формирование конфиденциального ключа ЦРК осуществляют путем выбора на основе датчика случайных чисел коэффициентов симметрических полиномов выработку личного конфиденциального ключа пользователя A в виде коэффициентов полиномов получаемых при подстановке в полиномы идентификатора y_A, получение сеансового ключа K_AB подстановкой в личный конфиденциальный ключ идентификатора корреспондента B, при этом сеансовый ключ длиной n бит представляет собой конкатенацию (последовательно присоединение друг к другу справа) т.е. может быть вычислен по формуле:
K_AB=R_AB,0+R_AB,1•(2¹⁶)+R_AB,2 •(2¹⁶)²+.+R_AB,r-1•(2¹⁶)^r-1,
где r=n/16,

При этом представление конфиденциального ключа ЦРК (личных конфиденциальных ключей пользователей) в виде конкатенации r=n/16 независимых частей, представляющих собой коэффициенты полиномов вида позволяет исключить процедуры поиска неприводимых полиномов степени n, заменив их табличным поиском неприводимых полиномов степени 15 (Питерсон У. Уэлдон Э. Коды, исправляющие ошибки. М. Мир, 1976 г. с. 519-523). Более простая программно-аппаратная реализация на базе одного микропроцессора быстродействующего устройства формирования сеансового ключа достигается путем уменьшения вычислительной сложности процедур получения сеансового ключа и личного ключа пользователя за счет использования вместо конечных полей GF(2ⁿ) поля GF(2¹⁶), т.е. арифметические операции выполняются над числами, разрядность которых не превосходит разрядности типового микропроцессора, например КР1810ВМ86. Снижение вероятностных сбоев при вводе личного ключа, упрощение его хранения, повышения устойчивости к внешним механическим и электромагнитным воздействиям обеспечивается за счет уменьшения объема личного ключа.

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

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

Можно показать, что для того, чтобы обеспечить наименьший объем конфиденциального ключа ЦРК и личных конфиденциальных ключей пользователей для заданной стойкости l к компрометациям личных конфиденциальных ключей пользователей, симметрические полиномы у которых все коэффициенты отличны от нуля, должны иметь вид:

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

Присвоение идентификаторов пользователям осуществляется путем постановки им в соответствие какого-либо числа y_i, такого, что y_i≠y_j, при i≠j, которое выбирают, например, либо на основе датчика случайных чисел, либо приравнивают номеру, под которым пользователь вводится в систему. Идентификаторы пользователей размещаются на носителе, в качестве которого может выступать, например, магнитный диск, справочник, книга. Данный носитель доступен всем пользователям.

Выработку личного конфиденциального ключа, например пользователя A, осуществляют путем подстановки его идентификатора y_A вместо одного из аргументов в симметрические полиномы . Тогда личный ключ представляет собой конкатенацию коэффициентов полиномов где
g_A,i(x)=f_i(x,y_A),
и которые после преобразования имеют вид:
g_A,i(x)=a_i,0+a_i,1•x+a_i,2x² +a_i,3x³+.+a_i,1xⁱ mod(2¹⁶).

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

Теперь, если какие-либо пользователи, например A и B, хотят получить сеансовый ключ K_AB, причем K_AB=K_BA,то для этого каждый из них, например пользователь A, выполняет подстановку идентификатора пользователя B полиномы коэффициенты которых являются личным ключом пользователя A. Сеансовый ключ K_AB длиной 256 бит образуют как конкатенацию т.е. может быть вычислен по формуле
K_AB=R_AB,0+R_AB,1•(2¹⁶)+ +R_AB,2•(2¹⁶)²+.+R_AB,r-1• (2¹⁶)^r-1,
где
Можно показать, что применение симметрических полиномов вместо матриц позволяет уменьшить объем личных конфиденциальных ключей пользователей более чем в 32 раза (табл. 1). Это влечет снижение вероятностных сбоев при вводе личного ключа, упрощение его хранения, повышение устойчивости к внешним механическим и электромагнитным воздействиям.

Можно показать, что представление конфиденциального ключа ЦРК, личных конфиденциальных ключей пользователей и сеансовых ключей в виде конкатенации r независимых частей, сохраняет равновероятное распределение значения сеансового ключа в интервале (1, 2ⁿ), устойчивость к l компрометациям, также, если бы в качестве конфиденциального ключа ЦРК были выбраны коэффициенты одного полинома f(x₁, x₂) в конечном поле GF(2ⁿ), в качестве личного конфиденциального ключа коэффициенты полинома g_A(x) в GF(2ⁿ). Такое представление позволяет, не изменяя общего объема конфиденциального ключа ЦРК, личных конфиденциальных ключей пользователей, уменьшить вычислительную сложность процедур получения сеансовых и личных конфиденциальных ключей более чем в 100 раз (табл. 2). Это позволит получить более простую программно-аппаратную реализацию быстродействующего устройства формирования сеансового ключа на базе одного типового микропроцессора, например в виде интеллектуальной карточки. Хотя это приводит к ограничению общего числа пользователей в системе с 2ⁿ до 2¹⁶ (≈32000), но это вполне приемлемо для реально существующих систем.

Изобретение относится к области криптографии, а именно к распределению ключей и, в частности, может быть использовано для построения систем распределения ключей, устойчивых к заданному числу компрометаций личных ключей пользователей, для обеспечения конфиденциальной связи между любой их парой. Техническим результатом является разработка способа формирования ключа шифрования/дешифрования, обеспечивающего более простую программно-аппаратную реализацию на базе одного типового микропроцессора быстродействующего устройства формирования сеансового ключа, снижение вероятностных обоев при вводе личного ключа, упрощение его хранения, повышения устойчивости к внешним механическим и электромагнитным воздействиям. Способ включает формирование конфиденциального ключа ЦРК путем выбора на основе датчика случайных чисел коэффициентов симметрических полиномов f_i(x₁, x₂), выработку личного конфиденциального ключа пользователя - подстановкой в полиномы f_i(x₁, x₂) идентификатора пользователя, получение сеансового ключа - подстановкой в личный ключ идентификатора пользователя. 2 табл.

Способ формирования ключа шифрования-дешифрования, включающий формирование конфиденциального ключа центра распределения ключей, присвоение идентификаторов Y_A, Y_B пользователям (A, B номера пользователей в системе обмена, A≠B), выработку личных конфиденциальных ключей пользователей и получение сеансных ключей, отличающийся тем, что формирование конфиденциального ключа центра распределения ключей осуществляют путем выбора на основе случайных чисел коэффициентов b_i,sv, b_i,mm симметричных полиномов

вида

где b_i,sv≠ 0;





выработку личного конфиденциального ключа пользователя A в виде коэффициентов полиномов идентификатора Y_A вместо одного из аргументов полинома Х₁ или Х₂, получение сеансового ключа К_A B подстановкой в полиномы коэффициентами которых является личный конфиденциальный ключ пользователя A, идентификатора Y_B вместо аргумента Х, при этом сеансовый ключ длиной n бит представляет собой конкатенацию элементов ключа по 16 бит каждый, где

r n/16;
g_A,i(x) f_i(X,Y_A) mod 2¹⁶,
K_AB,i g_A,i(Y_B) mod 2¹⁶, н