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

Описание патента на изобретение RU2355116C1

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

Предлагаемый способ формирования КлШД может использоваться в криптографических системах в случае отсутствия или потери криптосвязности1 (1 Криптосвязность - наличие у законных сторон одинакового КлЩД) между законными сторонами направления связи2 (2 Законные стороны НС - т.е. санкционированные участники обмена информации) (НС) или установления криптосвязности между новыми законными сторонами НС (ЗСНС) при ведении нарушителем перехвата информации, передаваемой по открытым каналам связи.

Известен способ формирования КлШД, описанный в книге У.Диффи «Первые десять лет криптографии с открытым ключом», ТИИЭР, т.76, №5, с.57-58. Известный способ заключается в предварительном распределении между законными сторонами направления связи чисел α и β, где α - простое число и 1≤β≤α-1. Передающая сторона НС (ПерСНС) и приемная сторона НС (ПрСНС), независимо друг от друга, выбирают случайные соответствующие числа ХA и ХB, которые хранят в секрете и затем формируют числа на основе ХA, α, β на ПерСНС и ХB, α, β на ПрСНС. ЗСНС обмениваются полученными цифрами по каналам связи без ошибок. После получения чисел корреспондентов законные стороны преобразовывают полученные числа с использованием своих секретных чисел в единый КлШД. Способ позволяет шифровать информацию во время каждого сеанса связи на новых КлШД (исключает хранение ключевой информации на носителях) и сравнительно быстро сформировать КлШД при использовании одного незащищенного канала связи.

Однако известный способ обладает низкой стойкостью КлШД к компрометации3 (3 Стойкость КлШД к компрометации - способность криптографической системы противостоять попыткам нарушителя получить КлШД который сформирован и используется законными сторонами НС, при использовании нарушителем информации о КлШД полученной в результате перехвата, хищения, утраты, разглашения, анализа и т.д.), время действия КлШД ограничено продолжительностью одного сеанса связи или его части, некорректное распределение чисел α и β приводит к невозможности формирования КлШД.

Известен также способ формирования КлШД при использовании квантового канала связи [Патент US №5515438 H04L 9/00 от 07.05.96], который позволяет автоматически сформировать КлШД без дополнительных мер по рассылке (доставке) предварительной последовательности. Известный способ заключается в использовании принципа неопределенности квантовой физики и формирует КлШД, посредством передачи фотонов по квантовому каналу. Способ обеспечивает получение КлШД с высокой стойкостью к компрометации, осуществляет гарантированный контроль наличия и степени перехвата КлШД.

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

Наиболее близким по технической сущности к заявляемому способу формирования КлШД является способ формирования КлШД на основе информационного различия [Патент ЕР №0511420 А1 МПК6 H04L 9/08 от 04.11.92].

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

Формирование ИП на передающей стороне НС заключается в выделении первой части ИП длиной L из предварительно сформированной коррелированной последовательности ПерСНС, генерировании случайным образом второй части ИП - R длиной М двоичных символов, конкатенации4 (4 Конкатенация - последовательное соединение справа последовательностей друг с другом) первой и второй частей ИП и получении ИП длины К двоичных символов, где К=L+М.

Кодирование ИП линейным блоковым систематическим помехоустойчивым (К, N) кодом, где N - длина кодированной ИП и N=1К - 1. Формирование каждого i-го проверочного символа блока проверочных символов ИП производится сложением по модулю 2 первого и (i+1)-го двоичных символов ИП, где (i=1, 2, 3, …, (N-К).

Выделение блока проверочных символов ИП заключается в разбиении кодированной ИП на ИП и блок проверочных символов кодированной ИП и выделении последнего.

Передача блока проверочных символов кодированной ИП по прямому каналу связи без ошибок на приемную сторону НС заключается в передаче его от передающей стороны НС по прямому каналу связи без ошибок на приемную сторону НС.

Формирование ДП на приемной стороне НС осуществляется следующим образом. Выделяется соответствующая первой части ИП на передающей стороне направления связи первая часть предварительной последовательности (ПРП) длиной L двоичных символов из предварительно сформированной коррелированной последовательности ПрСНС, затем для ее формируется блок проверочных символов первой части ПРП длины L -1 двоичных символов. Каждый i-й проверочный символ блока проверочных символов первой части ПРП формируется путем сложения по модулю 2 первого и (i+1)-го двоичных символов первой части ПРП, где i=1, 2, 3, …, (Z-1). Блок проверочных символов первой части ПРП поразрядно сравнивается с первыми L-1 двоичными символами принятого блока проверочных символов кодированной ИП, при хотя бы одном несовпадении которых биту подтверждения F присваивается значение ноль (F=0), а при полном совпадении биту подтверждения F присваивается значение единица (F=1) и формируется вторая часть ПРП длины М путем сложения по модулю 2 первого символа первой части ПРП и i+(Z-1)-го символа принятого блока проверочных символов кодированной ИП, где i=1, 2, 3, …, М. Бит подтверждения передается по обратному каналу связи без ошибок на передающую сторону НС. Затем формируется ДП длины К, где К=L+М, путем конкатенации первой части ПРП и второй части ПРП.

Формирование части КлШД из ИП и ДП, заключается в линейном преобразовании ИП и ДП в часть КлШД путем сложения по модулю 2 между собой символов ИП на передающей стороне НС и ДП на приемной стороне НС при наличии у законных сторон НС бита подтверждения, равного единице (F=1), а при наличии у законных сторон НС бита подтверждения, равного нулю (F=0) ИП, и первую часть ПРП стирают.

Указанная последовательность действий повторяется определенное количество раз, пока не будет сформирован КлШД требуемой длины.

Способ-прототип позволяет сформировать КлШД между законными сторонами НС с сравнительно небольшими материальными затратами при большом пространственном разнесении законных сторон НС.

Недостатком прототипа заявленного способа является низкая стойкость сформированного КлШД к компрометации, что обусловлено формированием КлШД из частей КлШД, сформированных на основе последовательной обработки коротких последовательностей двоичных символов, выделенных из предварительно сформированных коррелированных последовательностей сторон НС (обработка короткой последовательности увеличивает вероятность достоверного знания нарушителем сформированной части КлШД, что облегчает криптоанализ сформированного КлШД, например, при использовании метода перебора5 (5 Метод перебора ключа основан на переборе нарушителем всевозможных ключей и попытке расшифровать перехваченную криптограмму пока из криптограммы не будет получено осмысленное сообщение.) КлШД) и необходимостью хранения предварительно сформированных коррелированных последовательностей сторон НС на носителях, которые могут быть похищены, утеряны либо скопированы нарушителем. Каналы без ошибок используемые в прототипе не защищены методами аутентификации принимаемых сообщений6 (6 Аутентификация сообщений - процесс подтверждения подлинности (отсутствия фальсификации или искажения) произвольных сообщений принятых из канала связи.), что определяет высокую вероятность навязывания нарушителем ложных сообщений при формировании КлШД, что также уменьшает его стойкость к компрометации со стороны нарушителя. Кроме этого, достоверность формирования КлШД зависит от вероятности несовпадения бит в предварительно сформированной коррелированной последовательности, так как в случае большой ее величины формирование КлШД с требуемой достоверностью затруднительно.

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

Поставленная цель достигается тем, что в известном способе формирования ключа шифрования/дешифрования заключающемся в том, что на передающей и приемной сторонах направления связи формируют и кодируют исходные последовательности, выделяют из кодированных последовательностей блоки проверочных символов, затем передают блок проверочных символов от передающей на приемную сторону направления связи по прямому каналу связи без ошибок, после чего принятый блок проверочных символов поразрядно сравнивают с блоком проверочных символов приемной стороны направления связи, формируют и передают на передающую сторону квитанцию о результатах сравнения, формируют ключевые последовательности, из которых затем на передающей и приемной сторонах направления связи формируют ключ шифрования/дешифрования, для формирования исходных последовательностей на передающей и приемной сторонах направления связи N раз, где N - число двоичных символов в каждой из исходных последовательностей, случайным образом генерируют двоичный символ. После приема на передающей стороне квитанции о результатах сравнения на передающей и приемной сторонах направления связи формируют первичные последовательности путем согласования исходных последовательностей. Затем х раз, х≥2, последовательно рассогласовывают и вновь согласовывают первичные последовательности на передающей и приемной сторонах направления связи. После чего из них формируют ключевые последовательности на передающей и приемной сторонах направления связи. Для формирования ключа шифрования/дешифрования ключевые последовательности разбивают на φ блоков длиной ν двоичных символов каждый, из которых формируют φ битов ключа шифрования/дешифрования путем последовательного суммирования по модулю два всех символов в каждом из φ блоков.

Генерируют случайным образом двоичный символ из алфавита {0, 1} с вероятностью больше 0,5.

Для согласования последовательностей длиной Z двоичных символов на передающей и приемной сторонах направления связи их предварительно разделяют на Q информационных подблоков длиной k двоичных символов, где . Затем формируют кодовое слово на передающей и приемной сторонах направления связи. Для чего кодируют каждый m-ый подблок двоичных последовательностей на передающей и приемной сторонах направления связи, где m=1, 2, …, Q, (n, k)-кодом, где k - длина информационного слова, n - длина кодового слова в битах, причем n=2-k-1, а длина блока проверочных символов равна k-1. Затем из m-го кодового слова выделяют m-ый блок проверочных символов, который запоминают в качестве m-го подблока последовательности проверочных символов длиной и двоичных символов, где u=Q·(k-1). После чего передают последовательность проверочных символов от передающей на приемную сторону направления связи по прямому каналу связи без ошибок. На приемной стороне направления связи принятую последовательность проверочных символов разбивают на Q подблоков длиной k-1 двоичных символов. Затем формируют m-ый бит последовательности принятия решения на приемной стороне направления связи. Поразрядно сравнивают каждый j-ый бит m-го блока проверочных символов принятой последовательности проверочных символов передающей стороны направления связи с соответствующим j-ым битом m-го блока проверочных символов последовательности проверочных символов приемной стороны направления стороны связи, причем j=1, 2, …, k-1 и m=1, 2, …, Q. При наличии k-1 совпадений m-му биту последовательности принятия решений присваивают значение единица. При наличии хотя бы одного несовпадения m-му биту последовательности принятия решений на приемной стороне направления связи присваивают значение ноль. Затем передают последовательность принятия решений приемной стороны направления связи в качестве квитанции о результатах сравнения на передающую сторону направления связи по обратному каналу связи без ошибок. На передающей и приемной сторонах направления связи формируют согласованные последовательности. Каждому m-му биту последовательностей принятия решений, где m=1, 2, …, Q, ставят в соответствие m-ый подблок длиной k бит двоичных последовательностей на передающей и приемной сторонах направления связи. При m-ом бите последовательности принятия решения, равном нулю, m-ые подблоки двоичных последовательностей на передающей и приемной сторонах направления связи стирают. При m-ом бите, равном единице, первый бит m-го подблока двоичных последовательностей запоминают соответственно на передающей и приемной сторонах направления связи в качестве s-го элемента, причем s=1, 2, …,Z-U, согласованных последовательностей соответственно на передающей и приемной сторонах направления связи, где U - количество стертых подблоков двоичных последовательностей на передающей и приемной сторонах направления связи.

Для рассогласования выделенных последовательностей двоичных символов на передающей и приемной сторонах направления связи выполняют процедуру уменьшения количества соответствующих совпадающих двоичных символов в последовательностях на приемной и передающей сторонах направления связи Т раз, 1≤T≤10. Начальными последовательностями для каждой g-1 итерации являются последовательности, полученные после выполнения g-1 итерации на передающей и приемной сторонах направления связи, где g=1, 2, …, T. Для первой итерации начальными последовательностями выбирают выделенные последовательности на передающей и приемной сторонах направления связи.

Выполняют процедуру уменьшения количества соответствующих совпадающих двоичных символов в последовательностях двоичных символов длиной Н на приемной и передающей сторонах направления связи. Для чего формируют копии начальных последовательностей длиной Н двоичных символов. Синхронно по одинаковому способу перемешивают копии начальных последовательностей на передающей и приемной сторонах направления связи. Формируют промежуточные последовательности на передающей и приемной сторонах направления связи. Каждый j-ый бит начальных последовательностей, где j=1, 2, …, Н, суммируют по модулю два с соответствующим j-ым битом копий начальных последовательностей на передающей и приемной сторонах направления связи.

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

Заявленный способ поясняется чертежами, на которых показаны:

- на фиг.1 - обобщенная структурная схема направления, связи применяемого в заявленном способе;

- на фиг.2 - временная диаграмма генерирования случайного бита х на передающей стороне направления связи;

- на фиг.3 - временная диаграмма генерирования исходной последовательности XN на передающей стороне направления связи;

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

- на фиг.5 - временная диаграмма генерирования исходной последовательности YN на приемной стороне направления связи;

- на фиг.6 - временная диаграмма исходной последовательности XN на передающей стороне направления связи, разделенной на Q подблоков длиной k бит;

- на фиг.7 - временная диаграмма формирования последовательности проверочных символов PRAU на передающей стороне направления связи;

- на фиг.8 - временная диаграмма исходной последовательности YN на приемной стороне направления связи, разделенной на Q подблоков длиной k бит;

- на фиг.9 - временная диаграмма формирования последовательности проверочных символов PRBU на приемной стороне направления связи;

- на фиг.10 - временная диаграмма принятой от передающей стороны направления связи последовательности проверочных символов PRAU, сравниваемой с последовательностью проверочных символов приемной стороны направления связи PRBU;

- на фиг.11 - временная диаграмма последовательности принятия решения СBQ, сформированной по результатам сравнения на приемной стороне направления связи;

- на фиг.12 - временная диаграмма последовательности принятия решения CBQ, переданной на передающую сторону направления связи;

- на фиг.13 - временная диаграмма исходной последовательности XN на передающей стороне направления связи, разбитой на Q подблоков длиной k бит, и стирания из нее подблоков, которым соответствует значение 0 в последовательности принятия решения CBQ,

- на фиг.14 - временная диаграмма исходной последовательности передающей стороны направления связи ХZ без стертых подблоков;

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

- на фиг.16 - временная диаграмма последовательности принятия решения CBQ на приемной стороне направления связи;

- на фиг.17 - временная диаграмма исходной последовательности YN на приемной стороне направления связи, разбитой на Q подблоков длиной k бит, и стирания из нее подблоков, которым соответствует значение 0 в последовательности принятия решения CBQ;

- на фиг.18 - временная диаграмма исходной последовательности приемной стороны направления связи YZ без стертых подблоков;

- на фиг.19 - временная диаграмма первичной последовательности приемной стороны направления связи WBS, сформированной из первых бит сохраненных подблоков исходной последовательности;

- на фиг.20 - временная диаграмма последовательности двоичных символов передающей стороны направления связи WAH;

- на фиг.21 - временная диаграмма копии последовательности двоичных символов передающей стороны направления связи WAHС;

- на фиг.22 - временная диаграмма перемешанной копии последовательности двоичных символов передающей стороны направления связи WAHCp;

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

- на фиг.24 - временная диаграмма промежуточной последовательности передающей стороны направления связи WAHóõ;

- на фиг.25 - временная диаграмма последовательности двоичных символов приемной стороны направления связи WBN,

- на фиг.26 - временная диаграмма копии последовательности двоичных символов приемной стороны направления связи WBHC,

- на фиг.27 - временная диаграмма перемешанной копии последовательности двоичных символов приемной стороны направления связи WBHCp;

- на фиг.28 - временная диаграмма последовательности двоичных символов приемной стороны направления связи WBH и ее побитное суммирование по модулю 2 с перемешанной копией последовательности двоичных символов приемной стороны направления связи WBHCp;

- на фиг.29 - временная диаграмма промежуточной последовательности приемной стороны направления связи WBHóõ;

- на фиг.30 - временная диаграмма ключевой последовательности передающей стороны направления связи КлПANN, разделенной на φ подблоков длиной ν двоичных символов;

- на фиг.31 - временная диаграмма ключа шифрования/дешифрования на передающей стороне направления связи Кφ, каждый бит которого сформирован суммированием по модулю 2 ν символов соответствующего подблока ключевой последовательности КлПANN;

- на фиг.32 - временная диаграмма ключевой последовательности приемной стороны направления связи КлПBNN, разделенной на φ подблоков длиной ν двоичных символов;

- на фиг.33 - временная диаграмма ключа шифрования/дешифрования на приемной стороне направления связи Кφ, каждый бит которого сформирован суммированием по модулю 2 ν символов соответствующего подблока ключевой последовательности КлПBNN,

На представленных фигурах буквой «А» обозначены действия, происходящие на передающей стороне НС, буквой «В» - на приемной стороне НС. На фигурах заштрихованный импульс представляет собой двоичный символ «1», а не заштрихованный - двоичный символ «0». Знак «+» обозначает сложение в поле Галуа GF(2). Верхние буквенные индексы обозначают длину последовательности (блока), нижние буквенные индексы обозначают сторону направления связи, на которой сформирована последовательность.

Реализация заявленного способа заключается в следующем. Современные криптосистемы построены по принципу Керкхоффа, описанного, например, в книге Д.Месси, «Введение в современную криптологию», ТИИЭР т.76, №5, май 1988, с.24, согласно которому полное знание нарушителя включает, кроме информации полученной с помощью перехвата, полную информацию о алгоритме взаимодействия законных сторон НС и процессе формирования КлШД. Формирование общего КлШД можно разделить на три основных этапа.

Первый этап - генерирование исходных последовательностей (ИП) пользователей ЗСНС. На данном этапе прямой и обратный каналы связи без ошибок для передачи информации не используются. Допускается передача некоторой дополнительной исходной информации о процессе генерирования ИП. Предполагается, что нарушитель перехватывает эту дополнительную информацию по своему каналу перехвата (КП) и использует ее для формирования своей версии ИП.

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

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

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

Законные стороны направления связи генерируют с помощью своих двоичных источников без памяти исходные последовательности XN и YN длиной N бит, соответственно. Известные двоичные источники без памяти описаны, например, в книге Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974, стр.20. Допускается преобладание вероятности генерирования любого символа. Например, вероятности р1 генерирования символа х=1 в ИП XN и у=1 в ИП YN равны между собой, а также вероятности 1-р1 генерирования символа х=0 в ИП XN и у=0 в ИП YN равны между собой и выполняется соотношение:

Соответствующие биты в сгенерированных с помощью двоичных источников без памяти ИП ЗСНС согласно распределению вероятностей описываемого выражениями (1) и (2) совпадают с вероятностью большей, чем 0,5. Временная диаграмма генерирования ИП на ЗСНС показана на фиг.3 и 5. Известные способы генерирования случайных чисел с заданным распределением вероятности описаны, например, в книге Кнут Д. Искусство программирования для ЭВМ. М.: Мир, 1977, т.2, с.22. После генерирования исходных последовательностей, использовать их для формирования ключа нельзя, так как они могут различаться с большой вероятностью. Поэтому необходимо произвести согласование ИП ЗСНС. Согласование может быть реализовано с использованием помехоустойчивого кодирования с обнаружением ошибок. Для исправления несовпадений разбивают ИП ЗСНС на Q информационных подблоков длиной k бит (см. фиг.6 и 8), где .

Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге В.Васильев, В.Свириденко. «Системы связи». М.: Высшая школа, 1987, с.208. Формируют кодовое слово из каждого m-го подблока, где m=1, 2, …,6. Для формирования кодового слова кодируют каждый m-ый подблок (n, k)-кодом, где k - длина информационного слова в битах, n - длина кодового слова в битах, причем n=2k-1, и длина блока проверочных символов (БПС) равна k-1 (см. фиг.6 и 7, 8 и 9). Известные способы помехоустойчивого кодирования блоков символов описаны, например, в книге Блейхут Р. Теория и практика кодов контролирующих ошибки. М.: Мир, 1986, с.63. Затем из каждого m-го кодового слова выделяют m-ый БПС на ЗСНС. Известные способы выделения блоков фиксированной длины описаны, например, в книге Васильев В., Свириденко В. Системы связи. М.: Высшая школа, 1987, с.208. Запоминают m-ый БПС в качестве m-го подблока последовательности проверочных символов (ППС), длиной и бит на ЗСНС (см. фиг.7 и 9), где u=Q·(k-1). Известные способы хранения последовательности бит описаны, например, в книге Мальцев Л., Фломберг Э., Ямпольский В. Основы цифровой техники. М.: Радио и связь, 1986, с.38. После чего передают ППС ИП ПерСНС на ПрСНС по прямому каналу связи ошибок. Известные способы передачи последовательностей по каналам связи описаны, например, в книге Зюко А., Кловский Д., Назаров М., Финк Л. Теория передачи сигналов. М.: Радио и связь, 1986, с.11. На ПрСНС производят обнаружение несовпадающих с ПерСНС информационных слов длиной k бит с помощью принятой от ПерСНС ППС. Для этого принятую ППС ПерСНС и ППС ПрСНС разбивают на Q БПС длиной k-1 бит (см. фиг.9 и 10), где .

Затем последовательно для каждой m-й соответствующей пары БПС из ППС ПерСНС и ППС ПрСНС, где m=1, 2, …, Q, формируют m-й бит последовательности принятия решений (ППР) ПрСНС. Для этого сравнивают поразрядно каждый m-ый БПС ИП ПерСНС с соответствующим БПС ИП ПрСНС (см. фиг.9 и 10). Известные способы сравнения бит описаны, например, в книге Хоровиц П., Хилл У. Искусство схемотехники. М.: Мир, т.1, 1983, с.212. Формирование m-то бита ППР производят по правилу: запоминают символ «1» в случае полного поразрядного совпадения в результате сравнения (А-1) бит или в противном случае запоминают символ «0» (см. фиг.11). ППР ПрСНС передают на ПерСНС по обратному каналу связи без ошибок (см. фиг.12). Известные способы передачи блоков двоичных символов по обратному каналу описаны, например, в книге Зюко А., Кловский Д., Назаров М., Финк Л. Теория передачи сигналов. М.: Радио и связь, 1986, с.156. Затем производят стирание несовпадающих информационных слов длиной k, для чего в ИП ЗСНС каждому m-му биту ППР ставят в соответствие m-ый подблок длиной k бит ИП ЗСНС (см. фиг.12 и 13, 16 и 17). При m-ом бите ППР, равном нулю, m-ые подблоки ИП на ЗСНС стирают (см. фиг.13 и 17). Известные способы стирания бит описаны, например, в книге Питерсон У., Уэлдон Э. Коды исправляющие ошибки. М.: Мир, 1976, с.17. При m-ом бите, равном единице, первый бит m-го подблока ИП запоминают соответственно на ЗСНС в качестве s-го элемента, причем s=1, 2, …, N-U, первичных последовательностей соответственно на ЗСНС, где U - количество стертых подблоков ИП на ЗСНС (см. фиг.14 и 15, 18 и 19). Известные способы хранения бит описаны, например, в книге Мальцев Л., Фломберг Э., Ямпольский В. Основы цифровой техники. М.: Радио и связь, 1986, с.79. Вид сформированной первичной последовательности на ПерСНС показан на фиг.15, а вид сформированной первичной последовательности на ПрСНС показан на фиг.19.

Предполагается, что нарушителю известны порядок кодирования исходных и первичных последовательностей, параметры кода и порядок формирования ППР на ПрСНС. Также нарушитель перехватывает все данные, которые передают ЗСНС по прямому и обратному каналам связи без ошибок в процессе корректирования исходных и первичных последовательностей. Это уменьшает стойкость КлШД к компрометации. Поэтому для уменьшения количества знания нарушителя о формируемом КлШД необходимо выполнить несколько последовательных рассогласований и согласований последовательностей на ЗСНС

Для рассогласования выделенных последовательностей создают их копии на ЗСНС и запоминают их (см. фиг.21 и 26). Известные способы хранения последовательности бит описаны, например, в книге Мальцев Л., Фломберг Э., Ямпольский В. Основы цифровой техники. М.: Радио и связь, 1986, с.38. Синхронно по одинаковому способу перемешивают сохраненные копии последовательностей на ЗСНС (см. фиг.22 и 27). Известные способы перемешивания последовательности бит описаны, например, в книге Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974, с.305. Затем каждый j-ый бит выделенных последовательностей суммируют по модулю 2 с соответствующим j-ым битом копий выделенных последовательностей на ЗСНС, причем у=1, 2, …, Н, где Н - длина последовательностей (см. фиг.22 и 23, 27 и 28). Известные способы суммирования по модулю 2 бит описаны, например, в книге Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974, с.212. Полученные в результате суммирования последовательности запоминают в качестве промежуточных последовательностей (см. фиг.24 и 29). Действия ЗСНС по уменьшению количества совпадающих символов в последовательностях ЗСНС назовем процедурой уменьшения количества соответствующих совпадающих двоичных символов в последовательностях на ЗСНС. Применяется несколько итераций процедуры уменьшения количества соответствующих совпадающих двоичных символов в последовательностях. Число итераций обозначим - Т.

Затем, с полученными в результате рассогласования последовательностями, выполняют процедуру согласования. Процедура согласования полученных последовательностей идентична процедуре согласования исходных последовательностей.

В результате х последовательных рассогласований и согласований, где х≥2, на ЗСНС формируют ключевые последовательности, на основе которых ЗСНС могут приступить к формированию КлТПД. Формирование КлШД на ЗСНС заключается в следующем. Разбивают ключевые последовательности на ЗСНС на φ блоков длиной ν двоичных символов, где φ - требуемая длина КлШД (см. фиг.30 и 32). Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге Васильев В., Свириденко В. Системы связи. М.: Высшая школа, 1987, с.208. Суммируют по модулю 2 между собой все символы i-го блока длиной v на ЗСНС (см. фиг.30 и 31, 32 и 33). Запоминают сформированный бит в качестве i-го элемента КлШД на ЗСНС (см. фиг.31 и 33). После сжатия всех φ блоков получают на ЗСНС КлШД, совпадающие с высокой вероятностью. При этом ключ нарушителя не совпадает к ключами ЗСНС с высокой вероятностью.

Для подтверждения возможности достижения сформулированного технического результата - повышения стойкости КлШД к компрометации - было проведено аналитическое и имитационное моделирование обмена данными между ЗСНС по прямому и обратному каналам связи без ошибок. Нарушитель имеет доступ к прямому и обратному каналам связи без ошибок по двум каналам перехвата без ошибок (Фиг.34). Адекватность аналитической модели подтвердилась результатами имитационного моделирования.

Процедура моделирования включала:

1. Заблаговременное распределение нижеперечисленных предварительных данных (ПД):

- длина ИП N=132970 бит;

- вероятность генерирования символа "1" p1=0,9;

- длина информационного слова в процедуре согласования исходных последовательностей k=2;

- число последовательных рассогласований и согласований последовательностей ЗСНС х=2;

- число итераций в первой процедуре рассогласования T=1;

- длина информационного слова в первой процедуре согласования k=2;

- число итераций во второй процедуре рассогласования T=4;

- длина информационного слова во второй процедуре согласования k=10;

- требуемая минимальная длина ключа φ=100 бит.

2. Генерирование исходных последовательностей.

3. Процедура согласования исходных последовательностей ЗСНС.

4. Первое последовательное рассогласование и согласование последовательностей ЗСНС.

5. Второе последовательное рассогласование и согласование последовательностей ЗСНС.

6. Формирование КлШД на ЗСНС.

Результаты моделирования дают основания для следующих выводов:

1. После генерирования ИП вероятность несовпадения битов исходных последовательностей на ЗСНС pm1, а также вероятность несовпадения битов исходных последовательностей нарушителя и одной из ЗСНС pw1 равны соответственно:

pw1=0,18;

pw1=0,1.

2. После процедуры согласования ИП вероятность несовпадения битов первичных последовательностей на ЗСНС pm2, а также вероятность несовпадения битов первичных последовательностей нарушителя и одной из ЗСНС pw2 равны соответственно:

pm1=0,046;

pw2=0,0346.

3. После первой процедуры рассогласования вероятность несовпадения битов последовательностей на ЗСНС pm3, а также вероятность несовпадения битов последовательностей нарушителя и одной из ЗСНС pw3 равны соответственно:

pm3=0,0877;

pw3=0,0668.

4. После первой процедуры согласования вероятность несовпадения битов последовательностей на ЗСНС pm4, а также вероятность несовпадения битов последовательностей нарушителя и одной из ЗСНС/w4 равны соответственно:

pm4=0,00916;

pw4=0,0295.

5. После второй процедуры рассогласования вероятность несовпадения битов последовательностей на ЗСНС pm5, а также вероятность несовпадения битов последовательностей нарушителя и одной из ЗСНС pw5 равны соответственно:

pm5=0,121;

pw5=0,3113.

6. После второй процедуры согласования вероятность несовпадения битов ключевых последовательностей на ЗСНС pm7, а также вероятность несовпадения битов ключевых последовательностей нарушителя и одной из ЗСНС/w6 равны соответственно:

pm6=0,00000000466;

pw6=0,08.

7. После формирования КлШД вероятность несовпадения битов ключей на ЗСНС pm7, а также вероятность несовпадения битов ключа нарушителя и ключа одной из ЗСНС pw7 равны соответственно:

pm6=0,0000000233;

pw6=0,2908.

Вероятность несовпадения ключей ЗСНС РHEC AB равна

PНЕС АВ=0,00000233.

Вероятность совпадения ключа нарушителя с ключом одной из ЗСНС РС ЕА равна

РС ЕА=1,192·10-15, (а вероятность несовпадения ключа нарушителя с ключом одной из ЗСНС РНЕС ЕА=1-РС EA равна РНЕС ЕА=0.999999999999998808).

Таким образом, в заявленном способе при заданных исходных данных обеспечивается величина вероятности совпадения ключа нарушителя с ключом одной из ЗСНС РС ЕА, приблизительно равная

РС ЕА=1,192·10-15

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

- требуемая минимальная длина ключа l=100 бит;

- длина исходной последовательности N=132970 бит;

- первая часть ИП Z=2 (эквивалентно k для процедуры корректирования);

- вероятность несовпадения битов в предварительно сформированных коррелированных последовательностях на ЗСНС ppm1=10-5;

- вероятность несовпадения битов в предварительно сформированных; коррелированных последовательностях нарушителя и одной из ЗСНС ppw1=10-4.

Полученная вероятность совпадения ключа нарушителя с ключом одной из ЗСНС приблизительно равна

PСпр ЕА≈4.108·10-6

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

Похожие патенты RU2355116C1

название год авторы номер документа
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2007
  • Деньжонков Кирилл Александрович
  • Невров Алексей Александрович
  • Синюк Александр Демьянович
  • Мансур Наваль
RU2356168C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Молдовян А.А.
  • Коржик В.И.
  • Молдовян Н.А.
  • Синюк А.Д.
  • Яковлев В.А.
RU2180770C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Коржик В.И.
  • Молдовян А.А.
  • Молдовян Н.А.
  • Синюк А.Д.
  • Яковлев В.А.
RU2183051C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Синюк А.Д.
  • Коржик В.И.
  • Молдовян А.А.
  • Молдовян Н.А.
  • Яковлев В.А.
RU2180469C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ / ДЕШИФРОВАНИЯ 2020
  • Бурлаков Сергей Олегович
  • Остроумов Олег Александрович
  • Синюк Александр Демьянович
  • Сысуев Сергей Юрьевич
RU2749016C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2019
  • Давыдов Александр Викторович
  • Остроумов Олег Александрович
  • Синюк Александр Демьянович
  • Сысуев Сергей Юрьевич
RU2713694C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Комашинский В.В.
  • Коржик В.И.
  • Молдовян А.А.
  • Молдовян Н.А.
  • Синюк А.Д.
  • Яковлев В.А.
RU2171012C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2005
  • Бакаев Михаил Васильевич
  • Яковлев Виктор Алексеевич
RU2295199C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2018
  • Лебедев Павел Владимирович
  • Ковайкин Юрий Владимирович
  • Яковлев Виктор Алексеевич
  • Бесков Андрей Владимирович
  • Романенко Павел Геннадьевич
  • Вотинов Михаил Леонардович
  • Худайназаров Юрий Кахрамонович
RU2684492C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2018
  • Лебедев Павел Владимирович
  • Ковайкин Юрий Владимирович
  • Яковлев Виктор Алексеевич
  • Бесков Андрей Владимирович
  • Романенко Павел Геннадьевич
  • Вотинов Михаил Леонардович
  • Уйманов Андрей Викторович
  • Жук Александр Юрьевич
  • Шатров Антон Владимирович
RU2695050C1

Реферат патента 2009 года СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ

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

Формула изобретения RU 2 355 116 C1

1. Способ формирования ключа шифрования/дешифрования, заключающийся в том, что на передающей и приемной сторонах направления связи формируют и кодируют исходные последовательности, выделяют из кодированных последовательностей блоки проверочных символов, затем передают блок проверочных символов от передающей на приемную сторону направления связи по прямому каналу связи без ошибок, после чего принятый блок проверочных символов поразрядно сравнивают с блоком проверочных символов приемной стороны направления связи, формируют и передают на передающую сторону квитанцию о результатах сравнения, формируют ключевые последовательности, из которых затем на передающей и приемной сторонах направления связи формируют ключ шифрования/дешифрования, отличающийся тем, что для формирования исходных последовательностей на передающей и приемной сторонах направления связи N раз, где N - число двоичных символов в каждой из исходных последовательностей, случайным образом генерируют двоичный символ, а после приема на передающей стороне квитанции о результатах сравнения на передающей и приемной сторонах направления связи формируют первичные последовательности путем согласования исходных последовательностей, после чего х раз, х≥2, последовательно рассогласовывают и вновь согласовывают первичные последовательности на передающей и приемной сторонах направления связи, после чего из них формируют ключевые последовательности на передающей и приемной сторонах направления связи, а для формирования ключа шифрования/дешифрования ключевые последовательности разбивают на φ блоков длиной v двоичных символов каждый, из которых формируют φ битов ключа шифрования/дешифрования путем последовательного суммирования по модулю два всех символов в каждом из φ блоков.

2. Способ по п.1, отличающийся тем, что генерируют случайным образом двоичный символ из алфавита {0,1} с вероятностью больше 0,5.

3. Способ по п.1, отличающийся тем, что для согласования последовательностей длиной Z двоичных символов на передающей и приемной сторонах направления связи их предварительно разделяют на Q информационных подблоков длиной k двоичных символов, где , затем формируют кодовое слово на передающей и приемной сторонах направления связи, для чего кодируют каждый m-й подблок двоичных последовательностей на передающей и приемной сторонах направления связи, где m=1, 2, …, Q, (n, k)-кодом, где k - длина информационного слова, n - длина кодового слова в битах, причем n=2-k-1, а длина блока проверочных символов равна k-1, затем из m-го кодового слова выделяют m-й блок проверочных символов, который запоминают в качестве m-го подблока последовательности проверочных символов длиной u двоичных символов, где u=Q·(k-1), после чего передают последовательность проверочных символов от передающей на приемную сторону направления связи по прямому каналу связи без ошибок, на приемной стороне направления связи принятую последовательность проверочных символов разбивают на Q подблоков длиной k-1 двоичных символов, затем формируют m-й бит последовательности принятия решения на приемной стороне направления связи, для чего поразрядно сравнивают каждый j-й бит m-го блока проверочных символов принятой последовательности проверочных символов передающей стороны направления связи с соответствующим j-м битом m-го блока проверочных символов последовательности проверочных символов приемной стороны направления стороны связи, причем j=1, 2, …, k-1 и m=1, 2, …, Q, и при наличии k-1 совпадений m-му биту последовательности принятия решений присваивают значение единица, а при наличии хотя бы одного несовпадения m-му биту последовательности принятия решений на приемной стороне направления связи присваивают значение ноль, после чего передают последовательность принятия решений приемной стороны направления связи в качестве квитанции о результатах сравнения на передающую сторону направления связи по обратному каналу связи без ошибок и на передающей и приемной сторонах направления связи формируют согласованные последовательности, для чего каждому m-му биту последовательностей принятия решений, где m=1, 2, …, Q, ставят в соответствие m-й подблок длиной k бит двоичных последовательностей на передающей и приемной сторонах направления связи, после чего при m-м бите последовательности принятия решения равном нулю m-е подблоки двоичных последовательностей на передающей и приемной сторонах направления связи стирают, а при m-м бите, равном единице, первый бит m-го подблока двоичных последовательностей запоминают соответственно на передающей и приемной сторонах направления связи в качестве s-го элемента, причем s=1, 2, …, Z-U, согласованных последовательностей соответственно на передающей и приемной сторонах направления связи, где U - количество стертых подблоков двоичных последовательностей на передающей и приемной сторонах направления связи.

4. Способ по п.1, отличающийся тем, что для рассогласования выделенных последовательностей двоичных символов на передающей и приемной сторонах направления связи выполняют процедуру уменьшения количества соответствующих совпадающих двоичных символов в последовательностях на приемной и передающей сторонах направления связи Т раз, 1≤T≤10, причем начальными последовательностями для каждой g-й итерации являются последовательности, полученные после выполнения g-1 итерации на передающей и приемной сторонах направления связи, где g=1, 2, …, Т, а для первой итерации начальными последовательностями выбирают выделенные последовательности на передающей и приемной сторонах направления связи.

5. Способ по п.4, отличающийся тем, что для выполнения процедуры уменьшения количества соответствующих совпадающих двоичных символов в последовательностях двоичных символов длиной Н на приемной и передающей сторонах направления связи формируют копии начальных последовательностей длиной Н двоичных символов, затем синхронно по одинаковому способу перемешивают копии начальных последовательностей на передающей и приемной сторонах направления связи, после чего формируют промежуточные последовательности на передающей и приемной сторонах направления связи, для чего каждый j-й бит начальных последовательностей, где j=1, 2, …Н, суммируют по модулю два с соответствующим j-м битом копий начальных последовательностей на передающей и приемной сторонах направления связи.

6. Способ по п.1, отличающийся тем, что задают длину ключа шифрования/дешифрования φ в интервале от 64 до 512 двоичных символов.

Документы, цитированные в отчете о поиске Патент 2009 года RU2355116C1

Каркас сейсмостойкого многоэтажного здания 1974
  • Бородин Леонид Алексеевич
SU511420A1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ-ДЕШИФРОВАНИЯ 2001
  • Кравец О.Я.
  • Тупота В.И.
  • Тупота А.В.
RU2230438C2
US 5515438 A1, 07.05.1996.

RU 2 355 116 C1

Авторы

Деньжонков Кирилл Александрович

Гузов Михаил Викторович

Невров Алексей Александрович

Нижегородов Антон Валентинович

Синюк Александр Демьянович

Даты

2009-05-10Публикация

2007-09-06Подача