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

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

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

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

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

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

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

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

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

Известны способы формирования ключа шифрования-дешифрования (см., например, Российский стандарт шифрования стандарт СССР ГОСТ 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. "Информационная технология. Криптографическая защита информации. Функция хеширования".

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

Способ формирования ключа шифрования-дешифрования, основанный на генерировании двух двоичных векторов чисел а и р, причем 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 для шифрования сообщения, формируют двоичный вектор α, который передают по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения пользователи сети формируют случайный двоичный вектор ξ, а затем формируют двоичный вектор β путем сложения по модулю два битов случайного двоичного вектора ξ с битами двоичного вектора общего секретного подключа К и двоичный вектор β используют в шифрующем устройстве, формирующем псевдослучайную последовательность символов, используемую для дешифрования сообщения, отличающийся тем, что при передаче пользователи сети независимо друг от друга формируют для связи с другим пользователем сети двоичный вектор обратного элемента общего секретного подключа между пользователями сети К₀ путем преобразования двоичного вектора общего секретного подключа между пользователями сети и формируют двоичный вектор α путем сложения по модулю два битов случайного двоичного вектора ξ с битами двоичного вектора обратного элемента общего секретного подключа между пользователями К₀, а при приеме сообщения случайный двоичный вектор ξ формируют путем сложения по модулю два битов принимаемого двоичного вектора α с битами двоичного вектора обратного элемента общего секретного подключа между пользователями К₀.