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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования ключа шифрования/дешифрования, заключающемся в том, что формируют исходные последовательности на передающей и приемных сторонах направления связи, для чего кодируют исходную последовательность на передающей стороне направления связи, выделяют из кодированной последовательности блок проверочных символов, затем передают его на приемную сторону направления связи по прямому каналу связи без ошибок, после чего поразрядно сравнивают блок проверочных символов передающей стороны направления связи с блоком проверочных символов приемной стороны направления связи, формируют бит подтверждения и на его основе формируют ключевые последовательности, после чего формируют из ключевых последовательностей на передающей и приемной сторонах направления связи ключ шифрования/дешифрования, на приемной и передающей сторонах направления связи формируют по одной исходной последовательности с предварительно заданной длиной N, путем генерации случайным образом N двоичных символов. Формируют первичные последовательности на передающей и приемной сторонах направления связи путем корректирования исходных последовательностей на передающей и приемной сторонах направления связи. Формируют вторичные последовательности путем корректирования первичных последовательностей на передающей и приемной сторонах направления связи. Формируют третичные последовательности путем выполнения процедуры рассогласования вторичных последовательностей на передающей и приемной сторонах направления связи. Формируют ключевые последовательности путем корректирования третичных последовательностей на передающей и приемной сторонах направления связи. Разбивают ключевые последовательности на передающей и приемной сторонах направления связи на l блоков длиной ν двоичных символов, где l - требуемая длина ключа шифрования/дешифрования. Затем формируют бит ключа шифрования/дешифрования путем суммирования по модулю 2 всех символов l-го блока, причем i=1, 2,…, l. Формируют ключ шифрования/дешифрования на передающей и приемной сторонах направления связи путем запоминания сформированного бита в качестве i-то элемента ключа шифрования/дешифрования на передающей и приемной сторонах направления связи.

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

Для корректирования двоичных последовательностей длиной Z двоичных символов на передающей и приемной сторонах направления связи предварительно двоичные последовательности разделяют на Q информационных подблоков длиной k двоичных символов, где Q=Z/k. Формируют кодовое слово на передающей и приемной сторонах направления связи путем кодирования каждого m-ый подблока двоичных последовательностей, где m=1, 2,…, Q, (n, k)-кодом, где k - длина информационного слова, n - длина кодового слова в битах, причем n=2k-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 - количество стертых подблоков двоичных последовательностей на передающей и приемной сторонах направления связи.

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

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

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

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

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

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

- на фиг.3 - временная диаграмма генерирования исходной

последовательности XN на передающей стороне направления связи;

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

- на фиг.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 - временная диаграмма исходной последовательности передающей стороны направления связи ХL без стертых подблоков;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, «Системы связи», М.: Высшая школа, 1987, стр.208. Формируют кодовое слово из каждого m-го подблока, где m=1, 2,…, Q. Для формирования кодового слова кодируют каждый 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. Принятую ППС ПерСНС и ППС ПрСНС разбивают на Q БПС длиной k-1 бит (см. фиг.9 и 10). На ПрСНС производят обнаружение несовпадающих с ПерСНС информационных слов длиной k бит с помощью принятой от ПерСНС ППС. Для этого принятую ППС ПерСНС и ППС ПрСНС разбивают на Q БПС длиной k-1 бит (см. фиг.9 и 10), где

Затем последовательно для каждой m-й соответствующей пары БПС из ППС ПерСНС и ППС ПрСНС, где m=1, 2,…, Q, формируют m-й бит последовательности принятия решений (ППР) ПрСНС. Для этого сравнивают поразрядно каждый m-ый БПС ИП ПерСНС с соответствующим БПС ИП ПрСНС (см. фиг.9 и 10). Известные способы сравнения бит описаны, например, в книге П.Хоровиц, У.Хилл, «Искусство схемотехники», М.: Мир, т.1, 1983, стр.212. Формирование m-го бита ППР производят по правилу: запоминают символ «1» в случае полного поразрядного совпадения в результате сравнения (k-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. Первичные последовательности, полученные из исходных последовательностей ЗСНС путем их корректирования, все еще не совпадают с большой вероятностью. Поэтому необходимо произвести исправление несовпадений в первичных последовательностях ЗСНС. ЗСНС осуществляют корректирование первичных последовательностей аналогично корректированию исходных последовательностей ЗСНС. В результате корректирования первичных последовательностей на ЗСНС формируют вторичные последовательности длиной R двоичных символов. В процессе повторного корректирования длина информационного слова k может выбираться другой. Предполагается, что нарушителю известны порядок кодирования исходных и первичных последовательностей, параметры кода и порядок формирования ППР на ПрСНС. Также нарушитель перехватывает все данные, которые передают ЗСНС по прямому и обратному каналам связи без ошибок в процессе корректирования исходных и первичных последовательностей. Это уменьшает стойкость КлШД к компрометации. Поэтому для уменьшения количества знания нарушителя о формируемом КлШД необходимо выполнить процедуру рассогласования на ЗСНС, которая уменьшает количество совпадающих символов во вторичных последовательностях на ЗСНС. Для этого создают копии вторичных последовательностей на ЗСНС и запоминают их (см. фиг.21 и 26). Известные способы хранения последовательности бит описаны, например, в книге Л.Мальцев, Э.Фломберг, В.Ямпольский, «Основы цифровой техники», М.: Радио и связь, 1986, стр.38. Синхронно по одинаковому способу перемешивают сохраненные копии вторичных последовательностей на ЗСНС (см. фиг.22 и 27). Известные способы перемешивания последовательности бит описаны, например, в книге Р.Галлагер «Теория информации и надежная связь», М.: «Советское радио», 1974, стр.305. Затем каждый j-ый бит вторичных последовательностей суммируют по модулю 2 с соответствующим 7-ым битом копий вторичных последовательностей на ЗСНС, причем j=1, 2,…, R, где R - длина вторичных последовательностей (см. фиг.22 и 23, 27 и 28). Известные способы суммирования по модулю 2 бит описаны, например, в книге Р. Галлагер. «Теория информации и надежная связь», М.: «Советское радио», 1974, стр.212. Полученные в результате суммирования последовательности запоминают в качестве промежуточных последовательностей (см. фиг.24 и 29). Действия ЗСНС по уменьшению количества совпадающих символов в последовательностях ЗСНС назовем процедурой рассогласования вторичных последовательностей на ЗСНС. Применяется несколько итераций процедуры рассогласования. Число итераций обозначим - Т. В результате выполнения процедуры рассогласования вторичных последовательностей на ЗСНС формируют третичные последовательности. ЗСНС не могут приступить к формированию КлШД, так как полученные третичные последовательности не совпадают с высокой вероятностью, но в то же время вероятность несовпадения последовательности нарушителя с последовательностями ЗСНС выше, чем вероятность несовпадения третичной последовательности ПерСНС с третичной последовательностью ПрСНС, благодаря выполнению процедуры рассогласования вторичных последовательностей на ЗСНС. Для устранения несовпадающих символов в третичных последовательностях на ЗСНС осуществляют однократное корректирование третичных последовательностей, выполняя действия аналогичные описанным выше. При выполнении корректирования третичных последовательностей на ЗСНС параметры помехоустойчивого кода с обнаружением ошибок могут выбираться другими. Как правило, длина информационного слова k выбирается большей по сравнению с предыдущими корректированиями для обеспечения высокой вероятности согласования последовательностей на ЗСНС. В результате корректирования третичных последовательностей на ЗСНС формируют ключевые последовательности, на основе которых ЗСНС могут приступить к формированию КлШД. Формирование КлШД на ЗСНС заключается в следующем. Разбивают ключевые последовательности на ЗСНС на l блоков длиной v двоичных символов, где l - требуемая длина КлШД (см. фиг.30 и 32). Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, «Системы связи», М.: Высшая школа, 1987, стр.208. Суммируют по модулю 2 между собой все символы i-го блока длиной ν на ЗСНС (см. фиг.30 и 31, 32 и 33). Запоминают сформированный бит в качестве i-го элемента КлШД на ЗСНС (см. фиг.31 и 33). После сжатия всех l блоков получают на ЗСНС КлШД, совпадающие с высокой вероятностью. При этом ключ нарушителя не совпадает к ключами ЗСНС с высокой вероятностью.

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Процедура корректирования последовательностей ЗСНС.

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

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

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

pm1=0,196;

pw1=0,11.

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

pm2=0,056;

pw2=0,042.

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

pm3=0,035;

pw3=0,017.

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

pm4=0,101;

pw4=0,332.

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

pm5=0,00000197;

pw5=0,181.

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

pm6=0,00000985;

pw6=0,447.

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

РНЕСАВ=0,000985;

Вероятность совпадения ключа нарушителя с ключом одной из ЗСНС PСЕА равна РСЕА=1,883·10-26, (а вероятность несовпадения ключа нарушителя с ключом одной из ЗСНС PHECEA=1-PCEA равна PНЕСЕА=0,99999999999999999999999997117).

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

РСЕА≈1,883·10-26

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

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

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

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

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

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

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

PCnpEA≈6,65·10-14.

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

РCnpEA≈2,646·10-2.

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

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

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

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

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

Формула изобретения RU 2 356 168 C2

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

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

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

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

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

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

Каркас сейсмостойкого многоэтажного здания 1974
  • Бородин Леонид Алексеевич
SU511420A1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Коржик В.И.
  • Молдовян А.А.
  • Молдовян Н.А.
  • Синюк А.Д.
  • Яковлев В.А.
RU2183051C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ-ДЕШИФРОВАНИЯ 1994
  • Коржик В.И.
  • Меринович Ю.В.
RU2090006C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2000
  • Синюк А.Д.
  • Коржик В.И.
  • Молдовян А.А.
  • Молдовян Н.А.
  • Яковлев В.А.
RU2180469C2
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ 2005
  • Бакаев Михаил Васильевич
  • Яковлев Виктор Алексеевич
RU2295199C1
СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ-ДЕШИФРОВАНИЯ 2004
  • Тупота Виктор Иванович
  • Мирошников Вячеслав Викторович
  • Трофимов Руф Федорович
RU2277759C2
US 5515438, А, 07.05.1996
Прибор для очистки паром от сажи дымогарных трубок в паровозных котлах 1913
  • Евстафьев Ф.Ф.
SU95A1
US 5307410, А, 26.04.1994
US 5724426, А, 03.03.1998.

RU 2 356 168 C2

Авторы

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

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

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

Мансур Наваль

Даты

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

2007-05-21Подача