способ формирования ключа шифрования-дешифрования

Формула изобретения

Способ формирования ключа шифрования-дешифрования, основанный на генерировании двух двоичных векторов чисел а и р, причем 1<а<2 ⁿ, а р является простым числом и р 2ⁿ-1, где n - длина ключа в битах, передаче по незащищенному каналу связи двоичных векторов чисел а и р каждому пользователю сети, генерировании пользователями сети независимо друг от друга секретных ключей x_A, ..., x_B , где x_А - секретный ключ пользователя А, 1<x _А<2ⁿ, x_B - секретный ключ пользователя В, 1<x_B<2ⁿ, и формировании пользователями сети открытых ключей путем преобразования двоичных векторов секретного ключа и чисел а и р где у_A - открытый ключ пользователя А, у_B - открытый ключ пользователя В, передаче по незащищенному каналу связи открытых ключей всем другим пользователям сети и формировании пользователями сети для связи с другим пользователем сети общего секретного подключа К путем преобразования двоичных векторов своего секретного ключа и открытого ключа другого пользователя сети К=К_AB=К_BA, где К_AB - общий секретный подключ между пользователями А и В, К _ва - общий секретный подключ между пользователями В и А, К - общий секретный подключ, и для передачи сообщения генерируют для каждого сеанса связи случайный двоичный вектор , формируют двоичный вектор путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа К, используют двоичный вектор в качестве ключа шифрования для шифрующего устройства, формирующего псевдослучайную последовательность символов максимальной длины 2ⁿ-1 для шифрования сообщения, формируют двоичный вектор , который передают по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения пользователи сети формируют случайный двоичный вектор , а затем формируют двоичный вектор путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа К и двоичный вектор используют в шифрующем устройстве, формирующем псевдослучайную последовательность символов, используемую для дешифрования сообщения, отличающийся тем, что при передаче пользователи сети независимо друг от друга формируют для связи с другим пользователем сети двоичный вектор обратного элемента общего секретного подключа между пользователями сети К₀ путем преобразования двоичного вектора общего секретного подключа между пользователями сети и формируют двоичный вектор путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора обратного элемента общего секретного подключа между пользователями К₀, а при приеме сообщения случайный двоичный вектор формируют путем сложения по модулю два битов принимаемого двоичного вектора с битами двоичного вектора обратного элемента общего секретного подключа между пользователями К₀.

Описание изобретения к патенту

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

В совокупности признаков заявляемого способа используются следующие термины:

секретный ключ (или пароль) представляет собой комбинацию битов, известную только законному пользователю;

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

шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием шифрключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного устройства;

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

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

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

Известны способы формирования ключа шифрования-дешифрования (см., например, Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 [1], Британский алгоритм В-Grypt, Стандарт США DES, Японский алгоритм шифрования данных FEAL [2], стр. 48-52, а также патент Российской Федерации на изобретение №2171012, МПК⁷ Н 04 L 9/08, 9/00, заявка №2000108296/09 от 03.04.2000).

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

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

Наиболее близким по своей технической сущности к заявляемому способу формирования ключа шифрования-дешифрования является способ, описанный протоколом в стандарте США DES [2], стр. 71, и [3], стр.61.

Способ-прототип включает в себя формирование для всех пользователей сети двух двоичных векторов чисел а и р, при этом простое число р 2ⁿ-1, выбор пользователями сети независимо друг от друга секретных ключей x_A, ..., x_B, таких, что 1<x_А<2ⁿ, 1<x_B <2ⁿ, формирование пользователями сети открытых ключей обмен пользователями открытыми ключами и формирование каждым из них общего секретного подключа К=K_AB=К_ВА и использование этого подключа в качестве базы для начального заполнения регистра сдвига, имеющего n разрядов и вырабатывающего псевдослучайную последовательность символов максимальной длины.

Однако способ-прототип имеет недостаток. Несмотря на то, что шифр, основанный на сложении потока псевдослучайных битов с битами исходного текста по модулю 2, является в общем случае теоретически нераспознаваемым (см. [2], стр.128), сама криптосистема не отличается стойкостью и может быть раскрыта. Если структура регистра сдвига, имеющего n разрядов, известна, то для нахождения начального состояния регистра сдвига надо знать n символов известного открытого текста, которые складываются по модулю 2 с соответствующими n символами шифртекста. Полученные n символов псевдослучайной последовательности определяют состояние регистра сдвига на некоторый момент времени. Моделируя работу регистра сдвига в обратном направлении, можно определить его исходное состояние, а следовательно, и ключи, используемые пользователями сети при шифровании-дешифровании информации.

Если структура регистра сдвига, имеющего n разрядов, является неизвестной, то достаточно 2 n символов известного открытого текста и им соответствующих 2 n символов шифрованного текста, чтобы сравнительно быстро (в течение нескольких секунд работы ЭВМ) определить состояние регистра сдвига и вычислить используемые ключи (см., например, [4] стр. 93).

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

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

Это достигается тем, что в известном способе формирования ключа шифрования-дешифрования, заключающемся в генерировании для всех пользователей сети двоичных векторов двух чисел а и р, при этом простое число р 2ⁿ-1, в генерировании пользователями сети независимо друг от друга секретных ключей x_А, ..., x_B , таких, что 1<x_А<2ⁿ, 1<х _B<2ⁿ, формировании пользователями сети открытых ключей обмене пользователями сети открытыми ключами и формировании каждым из них для связи с другими пользователями сети общего секретного подключа К=К_АВ=К_ВА, дополнительно пользователи сети формируют для связи с другими пользователями сети двоичный вектор обратного элемента общего секретного подключа между пользователями сети К₀ путем преобразования двоичного вектора общего секретного подключа между пользователями сети и для передачи сообщения формируют случайный двоичный вектор , формируют шифрключ путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа К, закладывают его в шифрующее устройство, формирующее псевдослучайную последовательность символов максимальной длины 2ⁿ-1 для шифрования сообщения, формируют двоичный вектор путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора обратного элемента общего секретного подключа между пользователями К₀ сети и передают его по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения пользователи сети формируют случайный двоичный вектор путем сложения по модулю два битов принимаемого двоичного вектора с битами двоичного вектора обратного элемента общего секретного подключа между пользователями сети K₀, а затем формируют шифрключ путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа К и закладывают его в шифрующее устройство для дешифрования сообщения.

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

Случайный двоичный вектор может быть сформирован, например, путем использования генератора случайных чисел в комбинации с показаниями таймера. В этом случае исключается возможность определения секретных ключей, а также общих секретных подключей пользователей сети даже при использовании метода криптоанализа с известным открытым текстом. Несмотря на то, что в каком-то сеансе связи будет определено начальное состояние регистра сдвига, но для определения секретных подключей К и требуется знание случайного двоичного вектора , который выбирается для каждого сеанса связи случайным образом. Поскольку статистические методы криптоанализа в этом случае неприменимы, то секретные подключи К₁, К ₂ могут быть вскрыты только путем тотального перебора всего множества ключей. В соответствии с Российским стандартом ГОСТ 28147-89 для регистра сдвига, имеющего 256 ячеек памяти, мощность множества ключей будет составлять 10⁷⁷. Если вскрытие ключа будет осуществляться с помощью ЭВМ, имеющей тактовую частоту 100 ГГц, то число операций, выполняемое этой ЭВМ в течение года, будет составлять 3·10²⁰, а время вскрытия ключа составит 3·10⁵⁶ лет.

Знание криптоаналитиком открытых ключей, а также чисел а и р, передаваемых по незащищенным каналам связи, не позволяет также отыскать значения секретных ключей x_A1,x_A2, ..., x_B1, x _B2 и общих секретных подключей пользователей сети К ₁ и К₂, т.к. процедура их нахождения сводится к вычислению дискретного логарифма произвольного элемента конечного поля F_p, имеющего общее число элементов 10⁷⁷ . Поэтому решение этой задачи находится за пределами технологических возможностей современных ЭВМ.

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

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

Возможность технической реализации предлагаемого способа поясняется следующим образом. В центре распределения ключей выбираются два числа а и р, которые доводятся до всех пользователей сети путем генерирования двоичных векторов и передачи их по незащищенным каналам связи. Число а может быть выбрано в пределах 1<а<2 ⁿ, что не составляет больших проблем, а число р должно быть выбрано простым. Это число может быть выбрано из простых чисел Мерсенна типа 2^k-1, где k - простое число. Например, стандарт США DES предусматривает использование регистра сдвига, имеющего 127 ячеек памяти (длина ключа 127 бит). В этом случае в качестве простого числа может использоваться число Мерсенна р=2¹²⁷-1. Для Российского стандарта ГОСТ 28147-89 можно использовать число р=2²⁵⁷-1.

Для формирования пользователями сети открытых ключей y_А, ..., y _B, а также общих секретных подключей К и обратных элементов общих секретных подключей К₀ может быть использован алгоритм быстрого возведения числа в степень в конечном поле F_p (см. [4] стр.39) и для р=2²⁵⁷-1 на современных ЭВМ ключи могут быть сформированы в несколько минут. Для формирования случайного двоичного вектора могут быть использованы алгоритмы, представленные в [5]. Остальные процедуры формирования ключа шифрования-дешифрования реализуются известными способами и не вызывают сомнения.

Предлагаемый способ может быть реализован с помощью ЭВМ или вычислительного устройства, представленного блок-схемой на чертеже, где

блок 1 - устройство ввода- вывода;

блок 2 - устройство для формирования открытых ключей;

блок 3 - устройство формирования секретных подключей для связи с выбранным пользователем сети;

блок 4 - устройство формирования случайного двоичного вектора;

блок 5 - устройство формирования сеансового ключа шифрования;

блок 6 - устройство формирования сеансового ключа дешифрования.

Для простоты описания работы устройства будем пользоваться малыми числами. Будем считать, что пользователи сети используют регистры сдвига, имеющие 5 ячеек памяти (длина ключа 5 бит, n=5). Тогда в центре распределения ключей определяют два числа а=2 и р=2⁵-1= 31 и генерируют двоичные векторы этих чисел

а=00010=2

р=11111=31

и по незащищенному каналу связи передают их всем пользователям сети.

Принятые двоичные векторы чисел а и р пользователи сети фиксируют в блоке 1 и подают их в блок 2. В блоке 2 пользователи сети генерируют секретные ключи (например, пользователь А генерирует секретные ключи x_А=00011=3, а пользователь В генерирует секретные ключи x_B=00010=2), фиксируют их и формируют открытые ключи (например, пользователь А формирует открытый ключ)

Y_А 2³(mod 31)=01000=8,

(а пользователь В формирует открытые ключи)

y_B 2²(mod 31)=00100=4.

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

Если пользователь А хочет послать зашифрованное сообщение пользователю В, он поступает следующим образом.

В блоке 3 пользователь формирует секретные подключи между пользователями А и В, используя при этом открытый ключ пользователя В (у_B), который поступает из блока 1, и свой секретный ключ (x_A), поступающий из блока 2, а также формирует двоичный вектор обратного элемента общего секретного подключа между пользователями сети K₀

K_AB (mod р) 4³(mod 31)=00010=2

К₀ (mod р) 2²⁹(mod 31)=10000=16

В блоке 4 пользователь А формирует случайный двоичный вектор (например, путем использования генератора случайных чисел в комбинации с показаниями таймера получено число =10101=21).

В блоке 5 пользователь А формирует двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа K_AB, поступающего из блока 3

а также формирует двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора общего секретного подключа K_AB, поступающего из блока 3

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

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

В блоке 3 пользователь В формирует общий секретный подключ между пользователями В и А, используя при этом открытый ключ пользователя А (у_A ), поступающий из блока 1, и свой секретный ключ (x_B ), поступающий из блока 2, а также формирует двоичный вектор обратного элемента общего секретного подключа между пользователями сети K₀.

В блоке 6 пользователь В формирует случайный двоичный вектор путем сложения по модулю 2 принятых битов двоичного вектора , поступающего из блока 1, с битами двоичного вектора обратного элемента общего секретного подключа К₀, поступающего из блока 3

а в блоке 5 формируют двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора , поступающего из блока 6, с битами двоичного вектора общего секретного подключа К_BA, поступающего из блока 3

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

Источники информации

1. Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

2. С.Мафтик. Механизмы защиты в сетях ЭВМ, М., 1993 г.

3. В.И.Нечаев. Элементы криптографии. Основы теории защиты информации, М.: Высшая школа, 1999 г.

4. В.И.Тупота. Адаптивные средства защиты информации в вычислительных сетях. - М.: Радио и связь, 2002, - 176 с.

5. ГОСТ Р 34.11-94. "Информационная технология. Криптографическая защита информации. Функция хеширования".