способ формирования ключа шифрования-дешифрования
| Классы МПК: | H04L9/14 с использованием нескольких ключей или алгоритмов H04L9/16 меняющихся в процессе работы |
| Автор(ы): | Кравец О.Я. (RU), Тупота В.И. (RU), Тупота А.В. (RU) |
| Патентообладатель(и): | Воронежский государственный технический университет (RU) |
| Приоритеты: |
подача заявки:
2001-12-27 публикация патента:
10.06.2004 |
Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографического преобразования данных. Сущность изобретения заключается в генерировании двух двоичных векторов чисел а и р, причем р является простым числом и р
2n-1, где n - длина ключа в битах, передаче по незащищенному каналу связи двоичных векторов чисел а и р каждому пользователю сети, генерировании пользователями сети независимо друг от друга секретных ключей и формировании пользователями сети открытых ключей путем преобразования двоичных векторов секретного ключа и чисел a и p, передаче по незащищенному каналу связи открытых ключей всем другим пользователям сети и формировании пользователем сети для связи с другим пользователем сети общего секретного подключа путем преобразования двоичных векторов своего секретного ключа и открытого ключа другого пользователя сети. Технический результат, достигаемый при осуществлении изобретения, состоит в повышении быстродействия процесса формирования ключа шифрования-дешифрования и скорости шифрования. 1 ил.
Рисунок 1
2n-1, где n - длина ключа в битах, передаче по незащищенному каналу связи двоичных векторов чисел а и р каждому пользователю сети, генерировании пользователями сети независимо друг от друга секретных ключей и формировании пользователями сети открытых ключей путем преобразования двоичных векторов секретного ключа и чисел a и p, передаче по незащищенному каналу связи открытых ключей всем другим пользователям сети и формировании пользователем сети для связи с другим пользователем сети общего секретного подключа путем преобразования двоичных векторов своего секретного ключа и открытого ключа другого пользователя сети. Технический результат, достигаемый при осуществлении изобретения, состоит в повышении быстродействия процесса формирования ключа шифрования-дешифрования и скорости шифрования. 1 ил.
Формула изобретения
Способ формирования ключа шифрования-дешифрования, основанный на генерировании двух двоичных векторов чисел а и р, причем 1<а<2 2n-1, где n - длина ключа в битах, передачи по незащищенному каналу связи двоичных векторов чисел а и р каждому пользователю сети, генерировании пользователями сети независимо друг от друга первых секретных ключей xA1,..., xB1, где xА1 - первый секретный ключ пользователя А, 1<x
(mоd р),..., уВ1 
(mod р), где уА1 - первый открытый ключ пользователя А; уВ1 - первый открытый ключ пользователя В, передачи по незащищенному каналу связи первых открытых ключей всем другим пользователям сети и формировании пользователем сети для связи с другим пользователем сети первого общего секретного подключа K1 путем преобразования двоичных векторов своего первого секретного ключа и первого открытого ключа другого пользователя сетиKАВ1
(mod p); KBA1
(mod p); К1=KАВ1=KВА1,где KAB1 - первый общий секретный подключ между пользователями А и В;KBA1 - первый общий секретный подключ между пользователями В и А,отличающийся тем, что пользователи сети независимо друг от друга генерируют вторые секретные ключи xА2,..., xB2 где хА2 - второй секретный ключ пользователя A, 1<x
axA2(mod p),..., уB2
axB2(mod p), где уА2 - второй открытый ключ пользователя А, уВ2 - второй открытый ключ пользователя В, передают вторые открытые ключи по незащищенному каналу связи всем другим пользователям сети, формируют для связи с другим пользователем сети второй общий секретный подключ К2 путем преобразования двоичных векторов своего второго секретного ключа и второго открытого ключа другого пользователя сети КAB2
(mod p); KВА2
(mod p); К2=КАВ2=КВА2, где КАВ2 - второй общий секретный подключ между пользователями А и В; КВА2 - второй общий секретный подключ между пользователями В и А, и для передачи сообщения генерируют для каждого сеанса связи случайный двоичный вектор 
, 1< <2
путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора первого общего секретного подключа K1, используют двоичный вектор в качестве ключа шифрования для начального заполнения регистра сдвига, имеющего n разрядов и вырабатывающего псевдослучайную последовательность символов максимальной длины 2n-1 для шифрования сообщения, формируют двоичный вектор 
путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора второго общего секретного подключа К2 и передают его по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения пользователя сети формируют случайный двоичный вектор путем сложения по модулю два битов принимаемого двоичного вектора с битами двоичного вектора второго общего секретного подключа К2, а затем формируют двоичный вектор путем сложения по модулю два битов случайного двоичного вектора с битами двоичного вектора первого общего секретного подключа K1 и двоичный вектор закладывает в шифрующее устройство, вырабатывающее с помощью регистра сдвига псевдослучайную последовательность символов, используемую для дешифрования сообщения.
Описание изобретения к патенту
Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области способов и устройств криптографического преобразования данных.В совокупности признаков заявляемого способа используются следующие термины:секретный ключ (или пароль) представляет из себя комбинацию битов, известную только законному пользователю;ключ шифрования-дешифрования (шифрключ) представляет из себя комбинацию битов, используемого при шифровании информационных сигналов данных; шифрключ является сменным элементом шифра и используется для преобразования данного сообщения или данной совокупности сообщений; шифрключ является известным только законному пользователю или может быть выработан по детерминированным процедурам по паролю;шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием шифрключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного устройства;шифрование есть процесс криптографического преобразования блоков данных с использованием шифрключа, переводящий данные в криптограмму, представляющую собой псевдослучайную последовательность знаков, из которой получение информации без знания ключа практически невыполнимо;дешифрование есть процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании шифрключа;двоичный вектор числа - это сигнал в виде последовательности нулевых и единичных битов, соответствующей представлению числа в двоичной системе исчисления.Известны способы формирования ключа шифрования-дешифрования (см., например, Российский стандарт шифрования ГОСТ 28147-89 [1], Британский алгоритм В-Grypt, Стандарт США DES, Японский алгоритм шифрования данных FEAL [2] стр. 48-52, а также патент Российской Федерации на изобретение № 2171012, МПК7 Н 04 L 9/08, 9/00, заявка № 2000108296/09 от 03.04.2000).В известных способах формирование ключа шифрования-дешифрования осуществляют путем использования генератора случайных чисел с каким-либо непредсказуемым фактором, например, выбором битов от показаний таймера. Сформированный числовой ключ передается пользователем сети и используется в качестве базы (начального значения) генератора псевдослучайной последовательности чисел. При этом выходной поток битов суммируется по модулю 2 с исходным текстом, чтобы сформировать зашифрованное сообщение и наоборот.Однако известные способы-аналоги формирования ключа шифрования-дешифрования требуют использования защищенных каналов связи для передачи пользователям сети сформированного ключа.Наиболее близким по своей технической сущности к заявляемому способу формирования ключа шифрования-дешифрования является способ, описанный протоколом в стандарте США DES [2] стр. 71 и [3] стр.61.Способ прототип включает в себя формирование для всех пользователей сети двух двоичных векторов чисел а и р, при этом простое число p2n-1, выбор пользователями сети независимо друг от друга секретных ключей xA,...,xB, таких что 1<x
aхА(mod р),..., уB
axВ(mod р), обмен пользователями открытыми ключами и формировании каждым из них общего секретного подключа КAB
(mod р), Ква
(mod p), K=KАВ=KBA и использовании этого подключа в качестве базы для начального заполнения регистра сдвига, имеющего n разрядов и вырабатывающего псевдослучайную последовательность символов максимальной длины.Однако способ-прототип имеет недостаток. Несмотря на то, что шифр, основанный на сложении потока псевдослучайных битов с битами исходного текста по модулю 2 является в общем случае теоретически нераспознаваемым (см. [2] стр.128), сама криптосистема не отличается стойкостью и может быть раскрыта. Если структура регистра сдвига, имеющего n-разрядов известна, то для нахождения начального состояния регистра сдвига надо знать n символов известного открытого текста, которые складываются по модулю 2 с соответствующими n-символами шифртекста. Полученные n-символы псевдослучайной последовательности определяют состояние регистра сдвига на некоторый момент времени. Моделируя работу регистра сдвига в обратном направлении, можно определить его исходное состояние, а следовательно, и ключи, используемые пользователями сети при шифровании-дешифровании информации.Если структура регистра сдвига, имеющего n-разрядов, является неизвестной, то достаточно 2 n-символов известного открытого текста и им соответствующих 2 n-символов шифрованного текста, чтобы сравнительно быстро (в течение нескольких секунд работы ЭВМ) определить состояние регистра сдвига и вычислить используемые ключи (см., например, [4] с. 93).Поэтому ключи, сформированные для шифрования-дешифрования информации, могут использоваться только один раз и при очередном сеансе связи должны определяться по новому. А это приводит к значительному усложнению процедуры распределения ключей в вычислительной сети, т.к. всякий раз требуется подтверждение подлинности сеанса связи и подлинности пользователя сети путем использования электронных подписей или цифровых сигнатур. При этом снижается быстродействие процесса формирования ключа шифрования-дешифрования и скорость шифрования информации, т.к. требуется хеширование сообщения.Изобретение направлено на повышение быстродействия процесса формирования ключа шифрования-дешифрования и увеличение скорости шифрования сообщений.Это достигается тем, что в известном способе формирования ключа шифрования-дешифрования, заключающемся в генерировании для всех пользователей сети двоичных векторов двух чисел а и р, при этом простое число р2n-1, в генерировании пользователями сети независимо друг от друга секретных ключей 
таких что 
формировании пользователями сети открытых ключей 
обмене пользователями сети открытыми ключами и формировании каждым из них для связи с другими пользователями сети общего секретного подключа 
дополнительно осуществляется генерирование каждым пользователем сети независимо друг от друга вторых секретных ключей 
таких, что 
B2<2
обмен пользователями сети вторыми открытыми ключами и формирование каждым из них второго общего секретного подключа для связи с другим пользователем сети 
генерирование для каждого сеанса связи для передачи исходного текста случайного двоичного вектора ,1<<2 путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора первого общего секретного подключа K1, использование двоичного вектора в качестве ключа шифрования для начального заполнения регистра сдвига, имеющего n-разрядов и вырабатывающего псевдослучайную последовательность символов максимальной длины 2n-1, формирование двоичного вектора путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора второго общего секретного подключа К2 и передачи двоичного вектора по каналу связи вместе с зашифрованным сообщением, а при приеме сообщения осуществляют формирование случайного двоичного вектора путем сложения по модулю 2 принятых битов двоичного вектора с битами двоичного вектора второго общего секретного подключа К2 и формирование ключа дешифрования путем сложения по модулю 2 битов двоичного вектора первого общего секретного подключа К1 с битами случайного двоичного вектора .Перечисленная совокупность существенных признаков исключает возможность определения секретных ключей, а также общих секретных подключей пользователей сети даже при использовании метода криптоанализа с известным открытым текстом. В этом случае, хотя и будет определено начальное состояние регистра сдвига, но для определения секретных подключей К1 и К2 требуется знание случайного двоичного вектора , который выбирается для каждого сеанса связи случайным образом. Поскольку статистические методы криптоанализа в этом случае неприменимы, то секретные подключи К1, К2 могут быть вскрыты только путем тотального перебора всего множества ключей. В соответствии с Российским стандартом ГОСТ 28147-89 для регистра сдвига, имеющего 256 ячеек памяти, мощность множества ключей будет составлять 1077. Если вскрытие ключа будет осуществляться с помощью ЭВМ, имеющей тактовую частоту 10 ГГц, то число операций, выполняемых этой ЭВМ в течение года, будет составлять 3
1019, а время вскрытия ключа составит 31057 лет.Знание криптоаналитиком открытых ключей, а также чисел а и р, передаваемых по незащищенным каналам связи, не позволяет также отыскать значения секретных ключей 
и общих секретных подключей пользователей сети К1 и K2, т.к. процедура их нахождения сводится к вычислению дискретного логарифма произвольного элемента конечного поля p, имеющего общее число элементов 1077. Поэтому решение этой задачи находится за пределами технологических возможностей современных ЭВМ.Поскольку при рассмотренном способе секретные ключи и подключи не вскрываются, то отпадает необходимость в назначении ключей для связи новых сеансов, а следовательно, отпадает необходимость подтверждения подлинности абонентов и сеансов связи, что существенным образом упрощает процедуру распределения ключей в вычислительной сети и исключает необходимость использования электронных подписей или цифровых сигнатур для каждого сеанса связи, что приводит к повышению быстродействия формирования ключа шифрования-дешифрования и увеличению скорости шифрования, т.к. отпадает необходимость в хешировании передаваемых сообщений.Несмотря на то, что в вычислительной сети может быть множество пользователей, для предлагаемого способа формирования ключей шифрования-дешифрования с каждым из них будут использованы разные секретные подключи, недоступные другим пользователям сети.Возможность технической реализации предлагаемого способа поясняется следующим образом. В центре распределения ключей выбираются два числа а и р, которые доводятся до всех пользователей сети путем генерирования двоичных векторов и передачи их по незащищенным каналам связи. Число а может быть выбрано в пределах 1<а<2
а также общих секретных подключей К1 и K2 может быть использован алгоритм быстрого возведения числа в степень в конечном поле Fp (см. [4] стр.41) и для р=2257-1 на современных ЭВМ ключи могут быть сформированы в несколько минут. Остальные процедуры формирования ключа шифрования-дешифрования реализуются известными способами и не вызывают сомнения.Предлагаемый способ может быть реализован с помощью ЭВМ или вычислительного устройства, представленного блок-схемой на чертеже, гдеблок 1 - устройство ввода- вывода;блок 2 - устройство для формирования открытых ключей;блок 3 - устройство формирования секретных подключей для связи с выбранным пользователем сети;блок 4 - устройство генерирования случайного двоичного вектора сеанса связи;блок 5 - устройство формирования сеансового ключа шифрования;блок 6 - устройство формирования сеансового ключа дешифрования.Для простоты описания работы устройства будем пользоваться малыми числами. Будем считать, что пользователи сети используют регистры сдвига, имеющие 5 ячеек памяти (длина ключа 5 бит, n=5). Тогда в центре распределения ключей определяют два числа а=2 и р=25-1=31 и генерируют двоичные векторы этих чисела=00010=2р=11111=31и по незащищенному каналу связи передают их всем пользователям сети.Принятые двоичные векторы чисел а и р пользователи сети фиксируют в блоке 1 и подают их в блок 2. В блоке 2 пользователи сети генерируют секретные ключи (например, пользователь А генерирует секретные ключи 
а пользователь В генерирует секретные ключи 
фиксируют их и формируют открытые ключи (например, пользователь А формирует открытые ключи 
а пользователь В формирует открытые ключи 
Сформированные открытые ключи подают в блок 1, фиксируют их там и передают по незащищенному каналу связи через центр распределения ключей другим пользователям сети. Принятые открытые колючи других пользователей фиксируют в блоке 1.Если пользователь А хочет послать зашифрованное сообщение пользователю В, он поступает следующим образом:В блоке 3 пользователь формирует секретные подключи между пользователем А и В, используя при этом открытые подключи пользователя 
которые поступают из блока 1, и свои секретные ключи 
поступающие из блока 2: 
В блоке 4 пользователь А формирует случайный двоичный вектор (например, путем использования генератора случайных чисел в комбинации с показаниями таймера получено число =10101=21).В блоке 5 пользователь А формирует двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора второго общего секретного подключа 
, поступающего из блока 3: 
а также формирует двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора с битами двоичного вектора первого общего секретного подключа кАВ1, поступающего из блока 3: 
Двоичный вектор пользователь А закладывает в шифрующее устройство, вырабатывающее с помощью регистра сдвига псевдослучайную последовательность символов, и передает двоичный вектор и зашифрованный текст пользователю В.Получив двоичный вектор и зашифрованный текст от пользователя А, пользователь В поступает следующим образом.В блоке 3 пользователь В формирует общие секретные подключи между пользователем В и А, используя при этом открытые ключи пользователя 
, поступающие из блока 1, и свои секретные ключи 
поступающие из блока 2.В блоке 6 пользователь В формирует случайный двоичный вектор путем сложения по модулю 2 принятых битов двоичного вектора , поступающего из блока 1, с битами двоичного вектора второго общего секретного подключа 
поступающего из блока 3: 
а в блоке 5 формирует двоичный вектор путем сложения по модулю 2 битов случайного двоичного вектора , поступающего из блока 6, с битами двоичного вектора первого общего секретного подключа 
, поступающего из блока 3. 
Двоичный вектор пользователь В закладывает в шифрующее устройство, вырабатывающее с помощью регистра сдвига псевдослучайную последовательность символов, используемую для дешифрования сообщения.Источники информации1. Российский стандарт шифрования ГОСТ 28147-89 системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.2. С. Мафтик. Механизмы защиты в сетях ЭВМ. - М., 1993 г.3. В.И. Нечаев. Элементы криптографии. Основы теории защиты информации. - М.: Высшая школа, 1999 г.4. Б.Н. Воронков, В.И. Тупота. Методическое пособие по разработке средств защиты информации в вычислительных сетях. - Воронеж, Воронежский Государственный Университет, 2000.
Класс H04L9/14 с использованием нескольких ключей или алгоритмов
Класс H04L9/16 меняющихся в процессе работы
