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

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

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

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

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

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

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

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

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

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

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

Кодирование ИП линейным блоковым систематическим помехоустойчивым (N,K) кодом, где 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, ..., M. Затем формируется ДП длиной К, где К = L+М, путем конкатенации первой части ПРП и второй части ПРП. Бит подтверждения передается по обратному каналу связи без ошибок на передающую сторону НС.

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

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

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

Недостатком прототипа заявленного способа является низкая стойкость сформированного КлШД к компрометации, что обусловлено формированием КлШД из частей КлШД, сформированных на основе последовательной обработки коротких последовательностей двоичных символов, выделенных из предварительно сформированных коррелированных последовательностей законных сторон НС (обработка короткой последовательности увеличивает вероятность достоверного знания нарушителем сформированной части КлШД, что облегчает ему произвести криптоанализ сформированного КлШД, например, при использовании метода перебора (метод перебора КлШД основан на переборе нарушителем всевозможных КлШД при попытке расшифрования перехваченной криптограммы, пока из криптограммы не будет получено осмысленное сообщение) КлШД) и необходимостью хранения предварительно сформированных коррелированных последовательностей сторон НС на носителях (как описано, например, в книге Ю. Романец, П. Тимофеев, В. Шаньгин, "Защита информации в компьютерных системах и сетях", М.: Радио и связь, 1999, с. 174 ). Кроме этого, каналы без ошибок, используемые в способе-прототипе, не защищены методами аутентификации принимаемых сообщений (аутентификация сообщений - процесс подтверждения подлинности (отсутствия фальсификации или искажения) произвольных сообщений, принятых из канала связи), что определяет высокую вероятность навязывания нарушителем ложных сообщений при формировании КлШД, что также уменьшает стойкость КлШД к компрометации со стороны нарушителя.

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

Поставленная цель достигается тем, что в известном способе формирования ключа шифрования/дешифрования, заключающемся в том, что формируют исходную последовательность, кодируют ее, выделяют из кодированной исходной последовательности блок проверочных символов, передают его по каналу связи без ошибок и формируют декодированную последовательность, а из исходной и декодированной последовательностей формируют ключ шифрования/дешифрования, дополнительно предварительно L раз, где L > 104 - выбранная начальная длина первичной случайной последовательности, на передающей стороне направления связи генерируют случайный бит. Формируют из случайного бита кодовое слово. Передают кодовое слово по каналу связи с ошибками на приемную сторону направления связи. На приемной стороне направления связи из принятого кодового слова формируют принятый бит и бит подтверждения F. Передают бит подтверждения по обратному каналу без ошибок на передающую сторону направления связи. При бите подтверждения F, равном нулю, принятый бит и сгенерированный случайный бит стирают соответственно на приемной и передающей сторонах направления связи. При бите подтверждения F, равном единице, принятый бит и сгенерированный случайный бит запоминают соответственно на приемной и передающей сторонах направления связи в качестве i-x элементов, где i = 1, 2, 3, ..., L-U, принятой случайной (ПрСП) и первичной случайной (ПСП) последовательностей, где U - количество стертых символов при формировании принятой случайной и первичной случайной последовательностей. Затем на приемной стороне направления связи формируют исходную последовательность, причем каждый v-й бит исходной последовательности, где v = 1, 2, 3, ..., L-U, генерируют случайным образом. Формируют зашумленную исходную последовательность (ЗИП) длиной L-U двоичных символов путем поразрядного суммирования по модулю 2 исходной и принятой случайной последовательностей. Передают зашумленную исходную последовательность по обратному каналу связи без ошибок на передающую сторону направления связи. На передающей стороне направления связи формируют предварительную последовательность длиной L-U двоичных символов путем поразрядного суммирования зашумленной исходной и первичной случайной последовательностей. Декодированную последовательность на передающей стороне направления связи формируют из предварительной последовательности. После формирования исходной и декодированной последовательностей на передающей стороне направления связи формируют функцию хеширования последовательностей. Передают функцию хеширования последовательностей по прямому каналу связи без ошибок на приемную сторону направления связи. Ключи шифрования / дешифрования на приемной и передающей сторонах направления связи формируют путем хеширования исходной и декодированной последовательностей по сформированной на передающей стороне направления связи функции хеширования последовательностей. Затем на приемной стороне направления связи стирают исходную и принятую случайную последовательности. На передающей стороне направления связи стирают декодированную, предварительную и первичную случайную последовательности. Исходную последовательность на приемной стороне направления связи кодируют линейным блоковым систематическим двоичным помехоустойчивым (N, К) кодом, порождающая матрица которого имеет размерность К х N, причем N > К. При кодировании исходной последовательности предварительно исходную последовательность разделяют на Y подблоков длиной K двоичных символов, где Y = (L-U)/К. Затем, последовательно, начиная с 1-го до Y-го из каждого j-го подблока, где j = 1, 2, 3, ..., Y, формируют j-й кодовый блок длиной N двоичных символов перемножением j-го подблока на порождающую матрицу. Из j-го кодового блока выделяют j-й подблок проверочных символов длиной N-К двоичных символов. Запоминают j-й подблок проверочных символов в качестве j-го подблока блока проверочных символов кодированной исходной последовательности. Размеры К и N порождающей матрицы линейного блокового систематического двоичного помехоустойчивого (N, К) кода выбирают К=2m-1-m и N=2m-1, где m ≥3. Для формирования кодового слова сгенерированный случайный бит повторяют М раз, где М ≥ 1. Принятому биту присваивают значение первого бита принятого кодового слова. Для формирования бита подтверждения первый бит принятого кодового слова сравнивают с последующими М битами принятого кодового слова. Затем при наличии М совпадений первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения присваивают значение единица. При наличии хотя бы одного несовпадения первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения присваивают значение ноль. Для формирования декодированной последовательности на передающей стороне направления связи предварительную последовательность декодируют линейным блоковым систематическим двоичным помехоустойчивым (N, К) кодом, проверочная матрица которого имеет размерность (N-К) х N, причем N > К. При формировании декодированной последовательности предварительную последовательность и блок проверочных символов кодированной исходной кодированной последовательности разделяют на Y соответствующих пар декодируемых подблоков и подблоков проверочных символов, где Y = (L-U)/К. Длины декодируемых подблоков и подблоков проверочных символов выбирают равными соответственно К и N-К двоичных символов. Затем формируют У принятых кодовых блоков длиной N двоичных символов путем конкатенации справа к j-му декодируемому подблоку j-го подблока проверочных символов, где j = 1, 2, 3, ..., Y. Затем последовательно, начиная с 1-го до Y-го, вычисляют j-й синдром S длины N-К двоичных символов перемножением j-го принятого кодового блока на транспонированную проверочную матрицу. По полученному j-му синдрому S исправляют ошибки в j-м декодируемом подблоке. Затем j-й декодируемый подблок запоминают в качестве j-го подблока декодированной последовательности. Выбирают размеры К и N проверочной матрицы линейного блокового систематического двоичного помехоустойчивого (N, К) кода K=2m-1-m и N=2m-1, где m ≥ 3. Функцию хеширования последовательностей на передающей стороне направления связи формируют в виде двоичной матрицы G размерности (L-U) x T, где Т ≥ 64 - длина формируемого ключа шифрования/дешифрования. Каждый из элементов двоичной матрицы G генерируют случайным образом. Функцию хеширования последовательностей передают последовательно, начиная с 1-й по (L-U)-ю строки двоичной матрицы G. При формировании ключа шифрования/дешифрования предварительно на приемной стороне направления связи двоичную матрицу G и исходную последовательность разделяют на W соответствующих пар подматриц размерности Р х T, где P = (L-U)/W, и подблоков исходной последовательности длиной Р двоичных символов. При формировании ключа шифрования/дешифрования предварительно на передающей стороне направления связи двоичную матрицу G и декодированную последовательность разделяют на W соответствующих пар подматриц размерности Р х Т, где P = (L-U)/W, и подблоков декодированной последовательности длиной Р двоичных символов. Затем начиная с 1-го до W-й, вычисляют z-й первичный ключ длины Т двоичных символов, где z = 1, 2, 3, ..., W, перемножением z-го подблока исходной последовательности на z-ю подматрицу Gz на приемной стороне направления связи и z-го подблока декодированной последовательности на z-ю подматрицу Gz на передающей стороне направления связи. Формируют ключ шифрования/дешифрования путем поразрядного суммирования по модулю два W первичных ключей на приемной и передающей сторонах направления связи.

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

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

Заявленный способ поясняется фигурами, на которых показаны:
на фиг. 1 - обобщенная структурная схема НС, применяемого в заявленном способе;
на фиг. 2 - временная диаграмма генерирования случайного бита;
на фиг. 3 - временная диаграмма формирования кодового слова;
на фиг. 4 - временная диаграмма вектора ошибок в канале связи с ошибками;
на фиг. 5 - временная диаграмма принятого кодового слова;
на фиг. 6 - временная диаграмма формирования бита подтверждения;
на фиг. 7 - временная диаграмма формирования принятого бита;
на фиг. 8 - временная диаграмма принятого бита подтверждения;
на фиг. 9 - временная диаграмма хранящегося i-го элемента принятой случайной последовательности;
на фиг. 10 - временная диаграмма хранящегося i-го элемента первичной случайной последовательности;
на фиг. 11 - временная диаграмма сформированной первичной случайной последовательности;
на фиг. 12 - временная диаграмма сформированной принятой случайной последовательности;
на фиг. 13 - временная диаграмма сформированной ИП;
на фиг. 14 - временная диаграмма сформированной ЗИП;
на фиг. 15 - временная диаграмма принятой ЗИП;
на фиг. 16 - временная диаграмма первичной случайной последовательности;
на фиг. 17 - временная диаграмма сформированной предварительной последовательности;
на фиг. 18 - временная диаграмма сформированной исходной последовательности, разделенной на Y подблоков по К символов;
на фиг. 19 - временная диаграмма выделенного j-го подблока ИП;
на фиг. 20 - временная диаграмма формирования j-го кодового блока длиной N двоичных символов;
на фиг. 21 - временная диаграмма выделения j-го подблока проверочных символов длиной N - К двоичных символов;
на фиг. 22 - временная диаграмма формирования блока проверочных символов кодированной ИП из Y подблоков проверочных символов;
на фиг. 23 - временная диаграмма блока проверочных символов кодированной исходной последовательности, разделенного на Y подблоков проверочных символов длиной N-К двоичных символов, и выделение из нее j-го подблока проверочных символов;
на фиг. 24 - временная диаграмма предварительной последовательности, разделенной на Y декодируемых подблоков по К символов, и выделение из него j-го декодируемого подблока;
на фиг. 25 - временная диаграмма конкатенации справа j-го декодируемого подблока и j-го подблока проверочных символов;
на фиг. 26 - временная диаграмма вычисления j-го синдрома S длиной N-К двоичных символов;
на фиг. 27 - временная диаграмма исправления ошибки в j-м декодируемом подблоке по полученному j-му синдрому S;
на фиг. 28 - временная диаграмма формирования декодированной последовательности из Y декодируемых подблоков;
на фиг. 29 - вид сформированной функции хеширования последовательностей;
на фиг. 30 - временная диаграмма переданной функции хеширования последовательностей;
на фиг. 31 - временная диаграмма сформированной ИП;
на фиг. 32 - временная диаграмма сформированного КлШД Кb;
на фиг. 33 - временная диаграмма сформированной ДП;
на фиг. 34 - временная диаграмма сформированного КлШД Кa;
на фиг. 35 - временная диаграмма формирования КлШД.

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

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

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

Нарушитель имеет свой канал перехвата, с помощью которого он получает информацию о переданной ПСП по каналу связи с ошибками законных сторон НС (см. фиг. 1). Для формирования КлШД с высокой стойкостью к компрометации необходимо создание условий, при которых качество приема в канале связи с ошибками законных сторон НС (т.е. основного канала) будет превосходить качество приема в канале перехвата, т.е. необходимо создать условия, при которых основной канал будет иметь преимущество (лучшее качество приема) по отношению к каналу перехвата. Для создания вышесказанных условий каждый из символов ПСП, случайно вырабатываемых на ПерСНС (каждый бит ПСП генерируют случайным образом, чтобы увеличить стойкость КлШД к компрометации), повторяют М раз и передают на ПрСНС по основному каналу (по каналу связи с ошибками ЗСНС). На ПрСНС принимают каждое из слов кода повторения, если все его элементы или "1" или "0" и выносят решение об информационном символе, соответствующем принятому кодовому слову. В противном случае на ПрСНС стирают это кодовое слово. Решение о принятых (стертых) кодовых словах передают по обратному каналу связи без ошибок на ПерСНС. ЗСНС сохраняют символы в последовательностях ПрСП на ПрСНС и ПСП на ПерСНС, которые не были стерты. Нарушитель также может удалять символы, которые были стерты законными сторонами НС. Однако символы, сохраняемые нарушителем (т.е. которые сохранили ЗСНС), недостаточно надежны, потому что ошибки, возникающие в основном канале, и ошибки, возникающие в канале перехвата, являются независимыми ошибками. Вместо представленного декодирования с двумя кодовыми словами ЗСНС могут использовать пороговое декодирование. Основное различие при использовании ЗСНС порогового декодирования заключается в том, что на ПрСНС принимают каждое из слов кода повторения, не только когда все его элементы или "1" или "0", но и когда число одинаковых двоичных символов в кодовом слове не менее определенного числа (порога). Это приведет, с одной стороны, к уменьшению вероятности совпадения соответствующих сохраненных символов в ПСП на ПерСНС и в ПрСП на ПрСНС, с другой стороны, ЗСНС будут меньше стирать символов ПСП (ПрСП). Создание условий, при которых основной канал имеет преимущество над каналом перехвата, реализуется в заявленном способе следующей последовательностью действий по одновременному формированию ПрСП на приемной стороне направления связи и ПСП на передающей стороне направления связи. Одновременное формирование ПрСП на приемной стороне направления связи и ПСП на ПерСНС заключается в следующем. На передающей стороне направления связи L раз, где L > 104 - выбранная начальная длина ПСП, генерируют случайный бит (см. фиг. 2). Известные способы генерирования случайных чисел описаны, например, в книге Д. Кнут, "Искусство программирования для ЭВМ", М.: Мир, 1977, т. 2, с. 22. Формируют из случайного бита кодовое слово. Для формирования кодового слова сгенерированный случайный бит кодируют кодом с М-повторениями (см. фиг. 3), где М ≥ 1, М определяется качеством канала связи с ошибками. Известные способы кодирования кодом с повторениями описаны, например, в книге Э. Берлекэмп, "Алгебраическая теория кодирования", М.: Мир, 1971, с. 11, однако при декодировании кодового слова ЗСНС используется обратный канал связи без ошибок, что существенно влияет на увеличение надежности принятых символов. Передают кодовое слово по каналу связи с ошибками на приемную сторону направления связи. Временная диаграмма вектора ошибок в канале связи с ошибками показана на фиг. 4. Под термином "вектор ошибок" понимают поразрядную разность между переданным и принятым кодовыми словами, как описано, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М. : Радио и связь, 1986, с. 93. Принятое кодовое слово показано на фиг. 5. Известные способы передачи последовательностей по каналам связи с ошибками описаны, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М.: Радио и связь, 1986, с. 11. На приемной стороне направления связи из принятого кодового слова формируют принятый бит и бит подтверждения F. Принятому биту присваивают значение первого бита принятого кодового слова (см. фиг. 7). Для формирования бита подтверждения первый бит принятого кодового слова сравнивают с последующими М битами принятого кодового слова. При наличии М совпадений первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения присваивают значение "1", как показано на фиг. 6. При наличии хотя бы одного несовпадения первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения присваивают значение "0". Известные способы сравнения битов описаны, например, в книге П. Хоровец, У. Хил, "Искусство схемотехники", М.: Мир, т. 1, 1983, с. 212. Передают бит подтверждения по обратному каналу без ошибок на передающую сторону направления связи (см. фиг. 8). Известные способы передачи бита по обратному каналу описаны, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М.: Радио и связь, 1986, с. 156. При равенстве бита подтверждения F единице (F = 1) принятый бит и сгенерированный случайный бит запоминают соответственно на приемной и передающей сторонах направления связи в качестве i-x элементов, где i = 1, 2, 3, ..., L-U, ПрСП и ПСП, где U - количество стертых символов при формировании ПрСП и ПСП. На фиг. 9 показан i-й элемент ПрСП, а i-й элемент ПСП показан на фиг. 10. Известные способы хранения бит описаны, например, в книге Л. Мальцев, Э. Фломберг, В. Ямпольский, "Основы цифровой техники", М.: Радио и связь, 1986, с. 79. При равенстве бита подтверждения F нулю (F = 0) сгенерированный случайный бит и принятый бит стирают. Известные способы стирания бит описаны, например, в книге У. Питерсон, Э. Уэлдон, "Коды исправляющие ошибки", М.: Мир, 1976, с. 17. Вид сформированной ПСП показан на фиг. 11, а вид сформированной ПрСП показан на фиг. 12. Затем на приемной стороне направления связи формируют исходную последовательность, причем каждый v-й бит исходной последовательности, где v = 1, 2, 3, ..., L-U, генерируют случайным образом (см. фиг. 13). Каждый бит ИП генерируют случайным образом, чтобы увеличить стойкость формируемого КлШД к компрометации. Известные способы генерирования случайных чисел описаны, например, в книге Д. Кнут, "Искусство программирования для ЭВМ", М.: Мир, 1977, т. 2, с. 22. Формируют зашумленную исходную последовательность длиной L-U двоичных символов путем поразрядного суммирования по модулю 2 исходной и принятой случайной последовательностей на ПрСНС, как показано на фиг. 14. Передают зашумленную исходную последовательность по обратному каналу связи без ошибок на передающую сторону направления связи. Известные способы передачи последовательностей по каналам связи с ошибками описаны, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М.: Радио и связь, 1986, с. 11. На ПерСНС формируют предварительную последовательность (ПРП) длиной L-U двоичных символов (см. фиг. 17) путем поразрядного суммирования зашумленной исходной (см. фиг. 15) и первичной случайной последовательностей (см. фиг. 16). Так, например, если рm - вероятность ошибки на бит в основном канале, то вероятность несовпадения (ошибки) соответствующих двоичных символов в ПСП на ПерСНС и ПрСП на ПрСНС может быть выражена как

где pac - вероятность, с которой принимается блок (длиной М+1 двоичных символов) с М повторениями на ПрСНС, которая определяется с помощью выражения
pac = pM+1m

+(1-pm)M+1. (2)
Вероятность ошибки на двоичный символ (соответствующий сохраненным ЗСНС символам) в версии ПрСП нарушителя будет зависеть от выбранного им правила приема. Так, если рw - вероятность ошибки на бит в канале перехвата и нарушитель декодирует по мажоритарному правилу (мажоритарное правило декодирования - правило, когда решение о информационном символе принятого блока кода с повторениями выносится согласно большего количества одинаковых символов в принятом блоке кода с повторениями), то вероятность ошибки на бит для принятых символов нарушителя относительно переданной от ПерСНС по основному каналу ПСП может быть выражена как

Однако ИП формируется на ПрСНС и относительно ее будут исправляться несовпадающие символы (ошибки) в ПРП на ПерСНС и в дальнейшем будет формироваться КлШД ЗСНС, но ЗИП (т.е. просуммированные по модулю 2 ИП и ПрСП на ПрСНС) передают по обратному каналу связи без ошибок на ПерСНС, чтобы на ПерСНС сформировать ПРП. На ПерСНС ЗИП суммируют по мдулю 2 с ПСП и получают ПРП. Вероятность несовпадения (ошибки) соответствующих сформированных двоичных символов в ПРП на ПерСНС и в ИП на ПрСНС определятся согласно выражения (1), т. к. она прямо определяется вероятностью несовпадения (ошибки) соответствующих двоичных символов в ПСП на ПерСНС и ПрСП на ПрСНС. Из перехваченной ЗИП нарушитель не может извлечь никакой полезной информации о ИП, т. к. ЗИП для него представляет собой случайную последовательность (каждый бит ИП генерируют случайным образом на ПрСНС и каждый бит ПСП генерируют случайным образом на ПерСНС и, следовательно, каждый бит ПрСП на ПрСНС для нарушителя также случаен). В этом случае для нарушителя оптимальной обработкой имеющейся у него информации будет сложение по модулю 2 ЗИП и его версии ПрСП (т.е. удаление случайного зашумления с ИП), как доказано, например, в работе Maurer U. "Secret Key Agreement by Public Discussion Based on Common Information" // IEEE Trans. on IT., Vol. 39, May 1993, pp. 733-742, с. 733-734. Тогда, после такой обработки нарушителя, вероятность ошибки на бит для полученного символа в версии ПРП нарушителя относительно соответствующего сформированного информационного символа ИП на ПрСНС будет зависеть от вероятности несовпадения (ошибки) соответствующих двоичных символов в ПСП на ПерСНС и ПрСП на ПрСНС, равной (см. выражение (1)), и вероятности совпадения соответствующих двоичных символов в ПСП на ПерСНС и ПрСП на ПрСНС, равной (учитывая, что ЗИП - это просуммированные по модулю 2 ИП и ПрСП на ПрСНС, а ПРП - это просуммированные по модулю 2 ЗИП и ПСП на ПерСНС ). Эта вероятность с учетом того, что ошибки возникающие в основном канале и канале перехвата являются независимыми ошибками, может быть выражена как

где определяется согласно выражению (3), причем Это приводит к еще большему ухудшению качества приема канала перехвата, т.к. при сохранении прежнего качества приема основного канала (вероятность несовпадения (ошибки) соответствующих двоичных символов в ПРП на ПерСНС и ИП на ПрСНС равна ).

Пример 1. ЗСНС для формирования ПСП (ПрСП) используют код с М повторениями. Нарушитель декодирует по мажоритарному правилу. Вероятность ошибки на бит в канале перехвата равна рw=0.06, а вероятность ошибки на бит в основном канале равна рw=0.07, т.е. в случай, когда по надежности канал связи с ошибками законных сторон НС хуже, чем канал перехвата нарушителя. При передаче от ПерСНС ПСП начальной длины L=102001 двоичных символов и использовании кода с М повторениями, где М = 3 (рac = 0.748), вероятность несовпадения (ошибки) соответствующих двоичных символов в ПСП на ПерСНС и ПрСП на ПрСНС будет равна а вероятность ошибки на бит для принятых символов в версии ПрСП нарушителя относительно переданной от ПерСНС по основному каналу ПСП будет равна После формирования ИП и ЗИП на ПрСНС и передачи ЗИП по обратному каналу связи без ошибок на ПерСНС и формирования ПРП на ПерСНС, вероятность несовпадения (ошибки) соответствующих двоичных символов в ПРП на ПерСНС и ИП на ПрСНС будет также равна а вероятность ошибки на бит для полученного после обработки информационного символа в версии ПРП нарушителя относительно сформированного информационного символа ИП на ПрСНС будет равна , т.е. число несовпадающих символов (ошибок) в ПРП и ИП законных сторон НС будет меньше, чем в ИП и версии ПРП нарушителя. При этом ЗСНС будет стерто U двоичных символов из ПСП (ПрСП), U = 25697 двоичных символов, и вторичная длина ПСП (ПРП) и ПрСП (ИП) составит величину L-U = 76304 бит, в то время когда по каналу связи с ошибками необходимо будет передать 408004 двоичных символа.

После формирования ЗСНС ИП на ПрСНС и ПРП на ПерСНС в ИП и ПРП остаются несовпадающие символы, что не позволяет ЗСНС приступить к непосредственному формированию КлШД. Устранение этих несовпадений может быть реализовано на основе использования помехоустойчивого кодирования. Однако известные помехоустойчивые коды позволяют кодировать последовательности значительно меньшей длины, чем полученная вторичная длина ИП (ПРП), равная L-U двоичных символов. Для этого применяют последовательное кодирование, т.е. если длина ИП (ПРП) велика, например 105-107 двоичных символов, ее разделяют на Y подблоков длиной по К символов, где

Каждый подблок длиной К символов кодируется линейным систематическим блоковым помехоустойчивым (N, K) двоичным кодом, где К - длина блока информационных символов кода и N - длина кодового блока. Линейным двоичным кодом называется код, который построен на основе использования линейных операций в поле GF (2), как описано, например, в книге Р. Блейхут, "Теория и практика кодов, контролирующих ошибки", М.: Мир, 1986, с. 61. Под термином "блоковый код" понимают код, в котором действия производятся над блоками символов, как описано, например, в книге Р. Блейхут, "Теория и практика кодов, контролирующих ошибки", М.: Мир, 1986, с. 13. Систематическим называется код, в котором кодовое слово начинается с информационных символов, оставшиеся символы кодового слова являются проверочными символами к информационным символам, как описано, например, в книге Р. Блейхут, "Теория и практика кодов, контролирующих ошибки", М.: Мир, 1986, с. 66. Затем формируемые блоки проверочных символов длиной N-К двоичных символов объединяют в единый блок проверочных символов кодированной ИП длиной Y(N-К) двоичных символов и передают его по обратному каналу связи без ошибок на ПерСНС. На ПерСНС используют блок проверочных символов кодированной ИП для устранения несовпадений в ПРП по отношению к ИП и получают ДП. Тогда вероятность ошибочного декодирования ПРП может быть определена по формуле
PE ≤ 1-(1-PEO)Y, (6)
где РE0 - вероятность ошибочного декодирования подблока длиной К двоичных символов, определяемая, как описано, например, в книге Ф. Мак-Вильямс, Н. Слоэн, "Теория кодов, исправляющих ошибки", М.: Связь, 1979, с. 29,

где определяется из выражения (1), а d - минимальное кодовое расстояние (N, K) кода, которое определяется как минимальное число несовпадающих разрядов в двух любых кодовых словах (N, K) кода, как описано, например, в книге Ф. Мак-Вильямс, Н. Слоэн, "Теория кодов исправляющих ошибки", М.: Связь, 1979, с. 20. В качестве помехоустойчивых кодов могут использоваться широкий класс кодов Боуза - Чоудхури - Хоквингема, коды Хемминга, Рида - Малера, Рида - Соломона и другие линейные блоковые коды, характеризующиеся своими параметрами N, K, d. В ходе применения ЗСНС помехоустойчивого кодирования, нарушитель получает дополнительную информацию о КлШД путем перехвата блока проверочных символов кодированной ИП, переданного по обратному каналу связи без ошибок. Используя его, нарушитель также исправляет часть несовпадений в своей версии перехваченной ПРП относительно ИП. Это обстоятельство ЗСНС учитывают при формировании из исходной и декодированной последовательностей КлШД ЗСНС. Устранение несовпадений (ошибок) в ПРП на ПерСНС реализуется в заявленном способе следующей последовательностью действий. Кодирование исходной последовательности на ПрСНС заключается в следующем. Предварительно исходную последовательность разделяют на Y подблоков длиной К двоичных символов, где Y = (L-U)/К, как показано на фиг. 18. Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, "Системы связи", М.: Высшая школа, 1987, с. 208. Последовательно, начиная с 1-го до Y-го, каждый j-й подблок, где j = 1, 2, 3,..., Y, кодируют линейным блоковым систематическим двоичным помехоустойчивым (N, К) кодом (см. фиг. 19). Порождающая матрица кода имеет размерность К х N, причем N > К. Размеры К и N порождающей матрицы линейного блочного систематического двоичного помехоустойчивого (N, К) кода выбирают К = 2m-1-m и N = 2m-1, где m ≥ 3, как описано, например, в книге Р. Блейхуг, "Теория и практика кодов, контролирующих ошибки", М. : Мир, 1986, с. 71. Для кодирования ИП каждый j-й подблок длиной К двоичных символов перемножают на порождающую матрицу кода и получают j-й кодовый блок длиной N двоичных символов, как показано на фиг. 20. Известные способы помехоустойчивого кодирования блоков символов описаны, например, в книге Р. Блейхут, "Теория и практика кодов контролирующих ошибки", М.: Мир, 1986, с. 63. Из j-го кодового блока выделяют j-й подблок проверочных символов длиной N-K двоичных символов (см. фиг. 21). Известные способы выделения блоков фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, "Системы связи", М.: Высшая школа, 1987, с. 208. Запоминают j-й подблок проверочных символов в качестве j-го подблока блока проверочных символов кодированной исходной последовательности. Временная диаграмма формирования блока проверочных символов кодированной ИП показана на фиг. 22. Известные способы хранения последовательности бит описаны, например, в книге Л. Мальцев, Э. Фломберг, В. Ямпольский, "Основы цифровой техники", М.: Радио и связь, 1986, с. 38. Передают блок проверочных символов кодированной ИП по обратному каналу связи без ошибок на передающую сторону направления связи. Известные способы передачи последовательностей по каналам связи описаны, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М. : Радио и связь, 1986, с. 11. Формирование декодированной последовательности на передающей стороне направления связи заключается в следующем. Декодированную последовательность формируют из предварительной последовательности. Предварительную последовательность и блок проверочных символов кодированной исходной последовательности разделяют на Y соответствующих пар декодируемых подблоков (см. фиг. 24) и подблоков проверочных символов (см. фиг. 23), где Y = (L-U)/К. Длины декодируемых подблоков и подблоков проверочных символов выбирают равными соответственно К и N-К двоичных символов. Известные способы разбиения последовательности на блоки фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, "Системы связи", М.: Высшая школа, 1987, с. 208. Формируют Y принятых кодовых блоков длиной N двоичных символов путем конкатенации справа к j-му декодируемому подблоку j-го подблока проверочных символов, где j = 1, 2, 3, ..., Y, как показано на фиг. 25. Каждый из У принятых кодовых блоков декодируют линейным блоковым систематическим двоичным помехоустойчивым (N, К) кодом (см. фиг. 25). Проверочная матрица кода имеет размерность (N-К) х N, причем N > К. Выбирают размеры К и N проверочной матрицы линейного блокового систематического двоичного помехоустойчивого (N, К) кода К = 2m-1-m и N = 2m-1, где m ≥ 3, как описано, например, в книге Р. Блейхут, "Теория и практика кодов, контролирующих ошибки", М. : Мир, 1986, с. 71. Последовательно, начиная с 1-го до Y-го, вычисляют j-й синдром S длины N-K двоичных символов перемножением j-го принятого кодового блока на транспонированную проверочную матрицу. Временная диаграмма вычисления j-го синдрома S длиной N-К двоичных символов показана на фиг. 26. По полученному j-му синдрому S исправляют ошибки в j-м декодируемом подблоке (см. фиг. 27). Известные способы синдромного декодирования блоков символов описаны, например, в книге Р. Блейхут, "Теория и практика кодов, контролирующих ошибки", М.: Мир, 1986, с. 70. Затем j-й декодируемый подблок запоминают в качестве j-го подблока декодированной последовательности, как показано на фиг. 28. Известные способы хранения последовательности бит описаны, например, в книге Л. Мальцев, Э. Фломберг, В. Ямпольский, "Основы цифровой техники", М.: Радио и связь, 1986, с. 38. И получают, таким образом, ДП на ПерСНС.

Пример 2. Исходными данными для примера 2 берут исходные данные и полученные результаты примера 1 (см. выше). При использовании ЗСНС для исправления
несовпадающих символов в ПРП на ПерСНС кода Хемминга с m = 9 получают код с характеристиками: N = 511, K = 502, d = 3. Согласно выражению (5) получают Y - число подблоков длиной по 502 двоичных символа, Y = 152. Согласно выражению (7) получают PE0 - вероятность ошибочного декодирования одного подблока, РE0=1.28•10-4. Используя выражение (6) определяют вероятность РE - вероятность ошибочного декодирования ПРП длиной L-U, РE=1.929•10-2.

После формирования ЗСНС тождественных ИП на ПрСНС и ДП на ПерСНС, ЗСНС должны сформировать КлШД с малым количеством информации нарушителя о КлШД. Для обеспечения малого количества информации нарушителя о КлШД в предлагаемом способе формирования КлШД используют метод "усиления секретности" последовательностей ИП и ДП, основанный на универсальном хешировании, как описано, например, в книге Bennett С. , Brassard G., Crepeau С., Maurer U. "Generalized privacy amplification", IEEE Trans. on IT. vol. 41. no. 6. pp. 1915 - 1923, 1995, с. 1920. Сущность метода "усиления секретности" заключается в следующем. На ПерСНС выбирают случайным образом функцию хеширования из универсального множества функций хеширования. Функцию хеширования передают по прямому каналу связи без ошибок на ПрСНС. Затем хешируют ИП на ПрСНС и ДП на ПерСНС. Результатом хеширования будет сформированный КлШД ЗСНС. С вероятностью, близкой к единице и равной 1-Pε, происходит событие, при котором информация (информация Шеннона) нарушителя о КлШД не превысит определенной малой величины Iо, и с малой вероятностью сбоя Pε возможно событие, при котором информация нарушителя о КлШД будет более Iо. При хешировании ИП (ИП длиной L-U двоичных символов ) отображается в последовательность Kb длиной Т двоичных символов формируемого КлШД на ПрСНС. Аналогично, при хешировании ДП (ДП длиной L-U двоичных символов) отображается в последовательность Кa длиной Т двоичных символов формируемого КлШД на ПерСНС. Предполагается, что нарушитель имеет полную информацию о функции хеширования последовательностей ЗСНС. Функция хеширования последовательностей должна удовлетворять ряду требований, как описано, например, в книге Ю. Романец, П. Тимофеев, В. Шаньгин, "Защита информации в компьютерных системах и сетях", М.: Радио и связь, 1999, с. 156:
функция хеширования должна быть чувствительна к всевозможным изменениям в последовательности, таким как вставки, выбросы, перестановки и т.п.;
функция хеширования должна обладать свойством необратимости, т.е. задача подбора другой последовательности, которая обладала требуемым значением функции хеширования должна быть вычислительно неразрешима;
вероятность коллизии, т. е. вероятность события, при котором значения функции хеширования двух различных последовательностей совпадают, должна быть ничтожно мала.

Кроме этого, функция хеширования должна принадлежать универсальному множеству функций хеширования. Универсальное множество функций хеширования определяется следующим образом. Пусть n и r два положительных целых числа, причем n > r. Множество функций G2, отображающих множество двоичных последовательностей длиной n в множество двоичных последовательностей длиной r называется универсальным, если для любых различных последовательностей x1 и x2 из множества двоичных последовательностей длины n вероятность (коллизии) того, что значение функции хеширования от x1 равно значению функции хеширования от х2(g(x1) = g(x2)), не больше 2-r, при случайном выборе функции хеширования g, в соответствии с равновероятным распределением, из G2, как описано, например, в книге Carter J., Wegman M., "Universal classes of hash functions", Journal of Computer and System Sciences, 1979, Vol. 18, pp. 143 - 154, с. 145. Все линейные функции, отображающие множество двоичных последовательностей длиной n в множество двоичных последовательностей длиной r, принадлежат универсальному множеству, как описано, например, в книге Carter J. , Wegman M., "Universal classes of hash functions", Journal of Computer and System Sciences, 1979, Vol. 18, pp. 143 - 154, с. 150. Линейные функции могут быть описаны двоичными матрицами размерности n x r. Хранение универсального множества G2 функций хеширования последовательностей для ИП и ДП (число функций хеширования последовательностей принадлежащих универсальному множеству G2 велико и составляет величину равную 2T(L-U), причем для хранения каждая функция хеширования последовательностей требует T(L-U) ячеек памяти) труднореализуемо и нецелесообразно. Поэтому случайный равновероятный выбор функции хеширования последовательностей из универсального множества G2 функций хеширования последовательностей на ПерСНС заключается в генерировании случайным образом каждого из элементов двоичной матрицы размерности (L-U) х Т, которая описывает случайно выбранную функцию хеширования последовательностей из универсального множества функций хеширования последовательностей G2. После формирования ЗСНС КлШД путем хеширования ИП и ДП по сформированной случайным образом двоичной матрице размерности (L-U) х Т количество информации Шеннона, получаемое нарушителем о КлШД, сформированном ЗСНС, не больше, чем

где IR - информации Реньи. Информация Реньи IR определяется через выражение для энтропии Реньи на символ (энтропия Реньи на символ зависит от вероятности ошибки на бит рw в канале перехвата), которая характеризует неопределенность нарушителя о КлШД, при знании нарушителем информации, полученной с помощью канала перехвата, полной информации о алгоритме взаимодействия законных сторон НС и их действиям по формированию КлШД, как описано, например, в книге Bennett С., Brassard G., Crepeau С., Maurer U. "Generalized privacy amplification", IEEE Trans. on IT. vol. 41. no. 6. pp. 1915 -1923, 1995, с. 1919. Энтропия Реньи равна
HRДСК = -log2{pw2 + (1-pw)2} (9)
Тогда информация Реньи IR, полученная нарушителем при перехвате последовательности ПСП длиной L-U символов, определяется выражением
IR = (L-U)(1 - log2{pw2 + (1-pw)2}) (10)
При устранении ЗСНС несовпадений (ошибок) в ПРП на ПерСНС, когда от ПрСНС передают по обратному каналу связи без ошибок на ПерСНС блок проверочных символов кодированной ИП длиной Y(N- К) двоичных символов, нарушитель получает дополнительную информацию Реньи о ИП (КлШД). Дополнительная информация Реньи, полученная нарушителем за счет кодирования ИП IRкод, равна IRкод= Y(N - К), как доказано, например, в лемме 5 статьи Maurer U. "Linking Information Reconciliation and Privacy Amplification", J. Cryptology, 1997, no. 10, pp. 97 - 110, с. 105. Тогда общее количество информации Реньи, поступающее к нарушителю, равно
IRобщ=IR+Y(N-K) (11)В
этом случае (8) принимает вид

Количество информации Шеннона, получаемое нарушителем о сформированном ЗСНС КлШД, при использовании ЗСНС метода "усиления секретности", может быть больше ограничения Iо ( определенного в (12)) с малой вероятностью сбоя Pε.
Энтропия Реньи и вероятность Pε, при одновременном формировании ЗСНС первичной случайной и принятой случайной последовательностей, с помощью кода с повторениями и формировании ИП на ПрСНС и ДП на ПерСНС определяются более сложными соотношениями. Определение энтропии Реньи и вероятности Pε, при одновременном формировании ЗСНС первичной случайной и принятой случайной последовательностей, с помощью кода с повторениями и формировании ИП на ПрСНС и ДП на ПерСНС приведено в Приложении 1. Для обеспечения малой величины информации нарушителя о КлШД в предлагаемом способе формирования КлШД (с использованием метода "усиления секретности") реализуется следующая последовательность действий. Формирование КлШД из исходной и декодированной последовательностей заключается в следующем. Формируют на ПерСНС функцию хеширования последовательностей в виде двоичной матрицы G размерности (L-U) x T, где T ≥ 64 - требуемая длина формируемого КлШД. Каждый из элементов двоичной матрицы G генерируют случайным образом (см. фиг. 29). Известные способы генерирования случайных чисел описаны, например, в книге Д. Кнут, "Искусство программирования для ЭВМ", М.: Мир, 1977, т. 2, с. 22. Функцию хеширования последовательностей передают по прямому каналу связи без ошибок на приемную сторону направления связи, последовательно, начиная с 1-й по (L-U)-ю строки двоичной матрицы G, как показано на фиг. 30. Известные способы передачи последовательностей по каналам связи описаны, например, в книге А. Зюко, Д. Кловский, М. Назаров, Л. Финк, "Теория передачи сигналов", М. : Радио и связь, 1986, с. 11. КлШД на приемной стороне направления связи формируют путем хеширования ИП (см. фиг. 31) по сформированной на передающей стороне направления связи функции хеширования последовательностей, как показано на фиг. 32. КлШД на передающей стороне направления связи формируют путем хеширования ДП (см. фиг. 33) по сформированной на передающей стороне направления связи функции хеширования последовательностей, как показано на фиг. 34. При формировании КлШД, предварительно на приемной стороне направления связи двоичную матрицу G и исходную последовательность, а на передающей стороне направления связи двоичную матрицу G и декодированную последовательность разделяют на W соответствующих пар подматриц размерности Р х Т, где P = (L-U)/W, и подблоков исходной и декодированной последовательностей длиной Р двоичных символов. Известные способы разбиения последовательности на подблоки фиксированной длины описаны, например, в книге В. Васильев, В. Свириденко, "Системы связи", М.: Высшая школа, 1987, с. 208. Затем, последовательно, начиная с 1-го до W-й, вычисляют z-й первичный ключ длиной T двоичных символов, где z = 1, 2, 3, ..., W, перемножением z-го подблока исходной последовательности на z-ю подматрицу Gz на приемной стороне направления связи и z-го подблока декодированной последовательности на z-ю подматрицу Gz на передающей стороне направления связи. После чего формируют КлШД путем поразрядного суммирования по модулю два W первичных ключей соответственно на приемной и передающей сторонах направления связи, как показано на фиг. 35. У нарушителя остается возможность получения полной информации о КлШД ЗСНС в результате хищения носителей информации о ИП и ПрСП (ДП, ПРП и ПСП), несанкционированного доступа к информации о ИП и ПрСП (ДП, ПРП и ПСП), разглашения информации о ИП и ПрСП (ДП, ПРП и ПСП) и др. хотя бы одной из законных сторон НС. Для исключения этой возможности ЗСНС после формирования КлШД стирают ИП и ПрСП на приемной стороне направления связи и ДП, ПРП и ПСП на передающей стороне направления связи. Действия по передаче и приему последовательностей по каналу связи с ошибками, прямому и обратному каналам связи без ошибок засинхронизированы. Известные способы синхронизации описаны, например, в книге Е. Мартынов, "Синхронизация в системах передачи дискретных сообщений", М.: Связь, 1972, с. 186.

Пример 3. Исходными данными для примера 3 берут исходные данные и полученные результаты примеров 1 и 2 ( см. выше). ЗСНС формируют КлШД длиной Т = 64 бита. ЗСНС используют сформированную на ПерСНС двоичную матрицу G размерности 76304 х 64. Определяют среднюю энтропию Реньи R0 на принятый блок кода с повторениями длиной М+1 = 4 двоичных символа, равную R0 = 2.15•10-2, ε - величину, определяющую отклонение энтропии Реньи на принятый блок кода с повторениями от R0, ε = 2,562•10-3. Определяют значение вероятности сбоя Pε, Pε = 7,824•10-7 при обеспечении информации нарушителя о сформированном КлШД не более Iо, где Iо = 8.289•10-6 бит. При таком количестве информации о КлШД нарушителю остается лишь использовать перебор КлШД, время на который составит около 86 суток (вероятно, за этот промежуток времени ЗСНС неоднократно сменят действующий КлШД), т.е. время непрерывной работы одной из самых мощных ЭВМ типа INTEL ASCI RED (которая находится в пользовании АНБ США), как описано, например, в журнале "Конфидент. Защита информации", май - июнь, 3, 1998 г., с. 69, статья Ю. Е. Пудовенко "Когда наступит время подбирать ключи".

Метод "усиления секретности", используемый в предлагаемом способе, является более сильным по стойкости к компрометации сформированного ЗСНС КлШД по сравнению с алгоритмом сжатия, используемым способом-прототипом (см. стр. 11 описания способа-прототипа на английском языке). Понятие "более сильный по стойкости к компрометации сформированного ЗСНС КлШД" означает, что при использовании метода "усиления секретности" ограничено сверху максимальное количество информации нарушителя о КлШД (которое не зависит от применяемых нарушителем стратегий обработки информации) с вероятностью, близкой к единице. Это ограничение математически доказано, как показано, например, в книге Bennett С. , Brassard G., Crepeau С., Maurer U. "Generalized privacy amplification", IEEE Trans. on IT. vol. 41, no. 6. pp. 1915 - 1923, 1995, с. 1920. Такое доказательство относительно алгоритма сжатия, используемого способом-прототипом, неизвестно, поэтому трудно прогнозировать максимальное количество информации нарушителя о сформированном ЗСНС КлШД (при использовании алгоритма сжатия способа-прототипа), с учетом реальных возможностей нарушителя, который использует мощные вычислительные средства и современные методы криптоанализа.

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

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

Иллюстрации к изобретению RU 2 180 770 C2

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

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

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

1. Способ формирования ключа шифрования/дешифрования, заключающийся в том что формируют исходную последовательность на приемной стороне направления связи, кодируют ее, выделяют из кодированной исходной последовательности блок проверочных символов, передают его по обратному каналу связи без ошибок на передающую сторону направления связи, где формируют декодированную последовательность, а из исходной и декодированной последовательностей формируют ключ шифрования/дешифрования, отличающийся тем, что предварительно L раз, где L>104 - выбранная начальная длина первичной случайной последовательности, на передающей стороне направления связи генерируют случайный бит, затем из каждого случайного бита первичной случайной последовательности формируют кодовое слово путем повторения случайного бита М раз, где М≥1, и передают кодовое слово по каналу связи с ошибками на приемную сторону направления связи, где из принятого кодового слова формируют принятый бит путем присвоения значения первого бита принятого кодового слова и формируют бит подтверждения F путем сравнения первого бита принятого кодового слова с последующими М битами принятого кодового слова, после чего при наличии М совпадений первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения F присваивают значение единица, а при наличии хотя бы одного несовпадения первого бита принятого кодового слова с М битами принятого кодового слова биту подтверждения F присваивают значение ноль, затем передают бит подтверждения по обратному каналу связи без ошибок на передающую сторону направления связи, при бите подтверждения F, равном нулю, принятый бит и сгенерированный случайный бит стирают, а при бите подтверждения F, равном единице, принятый бит и сгенерированный случайный бит одновременно запоминают соответственно на приемной и передающей сторонах направления связи в качестве i-х элементов, где i= 1, 2, 3, . . . , L-U, принятой случайной и первичной случайной последовательностей, соответственно на приемной и передающей сторонах направления связи, где U - количество стертых символов при формировании принятой случайной и первичной случайной последовательностей, затем на приемной стороне направления связи формируют и запоминают исходную последовательность, причем каждый v-й бит исходной последовательности, где v= 1, 2, 3, . . . , L-U, генерируют случайным образом, формируют зашумленную исходную последовательность длиной L-U двоичных символов путем поразрядного суммирования по модулю 2 исходной и принятой случайной последовательностей, передают зашумленную исходную последовательность по обратному каналу связи без ошибок на передающую сторону направления связи, где формируют и запоминают предварительную последовательность длиной L-U двоичных символов путем поразрядного суммирования зашумленной исходной и первичной случайной последовательностей, причем для формирования декодированной последовательности на передающей стороне направления связи декодируют предварительную последовательность линейным блоковым систематическим двоичным помехоустойчивым (N, K) кодом, проверочная матрица которого имеет размерность (N-K)хN, причем N>K, для чего предварительную последовательность и блок проверочных символов кодированной исходной последовательности разделяют на Y соответствующих пар декодируемых подблоков и подблоков проверочных символов, где Y= (L-U)/K, причем длины декодируемых подблоков и подблоков проверочных символов выбирают равными соответственно К и N-K двоичных символов, затем формируют Y принятых кодовых блоков длиной N двоичных символов путем конкатенации справа к j-му декодируемому подблоку j-го подблока проверочных символов, где j = 1, 2, 3, . . . , Y, затем последовательно, начиная с 1-го до Y-го, вычисляют j-й синдром S длиной N-K двоичных символов перемножением j-го принятого кодового блока на транспонированную проверочную матрицу, а по полученному j-му синдрому S исправляют ошибки в j-м декодируемом подблоке, который затем запоминают в качестве j-го подблока декодированной последовательности, после формирования исходной и декодированной последовательностей на передающей стороне направления связи формируют функцию хеширования последовательностей в виде двоичной матрицы G размерности (L-U)хT, где Т≥64 - длина формируемого ключа шифрования/дешифрования, причем каждый из элементов двоичной матрицы G генерируют случайным образом, затем передают ее по прямому каналу связи без ошибок на приемную сторону направления связи путем последовательной построчной передачи, начиная с 1-й по (L-U)-ю строки двоичной матрицы G, после чего на приемной стороне направления связи двоичную матрицу G и исходную последовательность, а на передающей стороне направления связи двоичную матрицу G и декодированную последовательность разделяют на W соответствующих пар подматриц размерности РхТ, где Р= (L-U)/W, и подблоков исходной и декодированной последовательностей длиной Р двоичных символов, затем начиная с 1-го до W-й, вычисляют z-й первичный ключ длины Т двоичных символов, где z= 1, 2, 3, . . . , W, перемножением z-го подблока исходной последовательности на z-ю подматрицу Gz на приемной стороне направления связи и z-го подблока декодированной последовательности на z-ю подматрицу Gz на передающей стороне направления связи, после чего формируют ключ шифрования/дешифрования путем поразрядного суммирования по модулю 2W первичных ключей на приемной и передающей сторонах направления связи, после чего на приемной стороне направления связи стирают исходную и принятую случайную последовательности, а на передающей стороне направления связи стирают декодированную, предварительную и первичную случайную последовательности. 2. Способ по п. 1, отличающийся тем, что исходную последовательность кодируют на приемной стороне направления связи линейным блоковым систематическим двоичным помехоустойчивым (N, K) кодом, порождающая матрица которого имеет размерность KхN, причем N>K, для чего предварительно исходную последовательность разделяют на Y подблоков длиной К двоичных символов, где Y= (L-U)/K, затем последовательно начиная с 1-го до Y-го из каждого j-го подблока, где j= 1, 2, 3, . . . , Y, формируют j-й кодовый блок длиной N двоичных символов перемножением j-го подблока на порождающую матрицу, затем из j-го кодового блока выделяют j-й подблок проверочных символов длиной N-K двоичных символов, который запоминают в качестве j-го подблока блока проверочных символов кодированной исходной последовательности. 3. Способ по п. 2, отличающийся тем, что размеры K и N порождающей матрицы линейного блокового систематического двоичного помехоустойчивого (N, K) кода выбирают К= 2m-1-m и N= 2m-1, где m≥3. 4. Способ по п. 1, отличающийся тем, что выбирают размеры К и N проверочной матрицы линейного блокового систематического двоичного помехоустойчивого (N, К) кода K= 2m-1-m и N= 2m-1, где m≥3.

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

СПОСОБ ФОРМИРОВАНИЯ КЛЮЧА ШИФРОВАНИЯ-ДЕШИФРОВАНИЯ 1994
  • Коржик В.И.
  • Меринович Ю.В.
RU2090006C1
СПОСОБ ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ СООБЩЕНИЙ ХЭШИРУЮЩЕЙ ФУНКЦИЕЙ И УСТРОЙСТВО, ЕГО РЕАЛИЗУЮЩЕЕ 1998
  • Бурнашев Р.У.
  • Оков И.Н.
  • Туринцев И.В.
  • Царик О.В.
RU2138126C1
Прибор для очистки паром от сажи дымогарных трубок в паровозных котлах 1913
  • Евстафьев Ф.Ф.
SU95A1
US 5416841 A, 16.05.1995
Фронтально-перекидной погрузчик 1975
  • Рубинштейн Федор Ефимович
  • Витолиньш Висвалдис Жанович
  • Паламарчук Виктор Владимирович
SU534419A1

RU 2 180 770 C2

Авторы

Молдовян А.А.

Коржик В.И.

Молдовян Н.А.

Синюк А.Д.

Яковлев В.А.

Даты

2002-03-20Публикация

2000-04-12Подача