СПОСОБ ПЕРЕДАЧИ ДИСКРЕТНОЙ ИНФОРМАЦИИ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ Российский патент 2004 года по МПК H04L9/00 H04L9/14 

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

Известны способы передачи дискретной информации в вычислительной сети (см. например, Заявка на изобретение №99123808/09 от 10.11.1999-МПК Н 04 В 1/713 [1], Британский алгоритм B-Grypt, являющий дополнением к стандарту США DES [2], стр.50, 126-128, а также способ, описанный в [3], стр.50-51)

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

Известные способы передачи дискретной информации обеспечивают целостность и высокое быстродействие процессов преобразования передаваемой информации в вычислительной сети.

Наиболее близким по своей технической сущности к заявленному способу является способ, представленный в [2] стр.126-128 и в [3] стр.50-51.

Способ-прототип включает в себя на передающем конце деление входного сигнала на блоки длиною n бит, сформирование ключа защиты в виде двоичного вектора длиною k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащей 2^k-1 двоичных символов, сформирование двоичного вектора псевдослучайной последовательности путем одновременного параллельного снятия информации с различных разрядов регистра сдвига, при этом длину двоичного вектора псевдослучайной последовательности выбирают равной длине двоичного вектора, блока входного сигнала, кодирование блока входного сигнала путем сложения по модулю два битов двоичного вектора псевдослучайной последовательности с битами двоичного вектора блока входного сигнала и последующую передачу закодированного блока, входного сигнала по линии связи, прием сигнала на приемном конце линии связи, формирование ключа защиты в виде двоичного вектора, длиною k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов, а также сформирование аналогично как и на передающей стороне двоичного вектора псевдослучайной последовательности длиною n бит, осуществление декодирования закодированного блока входного сигнала путем сложения по модулю два его битов с битами двоичного вектора, псевдослучайной последовательности и подачу входного сигнала на оконечное устройство.

Однако способ-прототип имеет недостатки. Несмотря на то, что код, основанный на сложении потока псевдослучайных битов с битами исходного текста, по модулю два, является в общем случае теоретически нераспознаваемым (см. [2], стр.126) сама система кодирования не отличается стойкостью и может быть раскрыта. Если структура регистра сдвига, имеющего k разрядов известна, то для нахождения начального состояния регистра сдвига надо знать k символов известного открытого текста, которые складываются по модулю два с соответствующими k символами кодированного текста. Полученные k символов псевдослучайной последовательности определяют состояние регистра сдвига на некоторый момент времени. Моделируя работу регистра сдвига в обратном направлении, можно определить его исходное состояние, а следовательно и ключи, используемые пользователями сети при кодировании информации.

Если структура регистра сдвига, имеющего k-разрядов, является неизвестной, то достаточно 2· k-символов известного открытого текста и им соответствующих 2· k-символов кодированного текста, чтобы сравнительно быстро (в течении нескольких секунд работы ЭВМ) определить состояние регистра сдвига и вычислить используемые ключи (см., например, [4], стр.93). А это приводит к снижению стойкости кода к атакам на основе известных и подобранных исходных текстов, что не обеспечивает конфиденциальности передаваемой информации и приводит к необходимости смены ключа защиты. Ключи защиты могут использоваться только один раз и при очередном сеансе связи должны определяться по-новому.

Изобретение направлено на повышение стойкости кода к атакам на основе известных и подобранных исходных текстов.

Это достигается тем, что в известном способе передачи дискретной информации, заключающемся в делении входного сигнала на блоки длиною n бит, формировании ключа защиты в виде двоичного вектора длиною k бит, подаче его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащей 2^k-1 двоичных символов, формировании двоичного вектора псевдослучайной последовательности путем одновременного параллельного снятия информации с различных разрядов регистра сдвига, при этом длину двоичного вектора псевдослучайной последовательности выбирают равной длине двоичного вектора-блока входного сигнала, кодировании блока входного сигнала путем сложения по модулю два битов двоичного вектора псевдослучайной последовательности с битами двоичного вектора блока входного сигнала и последующей передаче закодированного блока входного сигнала по линии связи, приеме сигнала на приемном конце линии связи, формировании ключа защиты в виде двоичного вектора длиною k бит, подаче его для начального заполнения регистра, сдвига с обратной связью, имеющего k разрядов, а также формировании аналогично как и на передающей стороне двоичного вектора псевдослучайной последовательности длиною n бит, осуществлении декодирования закодированного блока, входного сигнала путем сложения по модулю два его битов с битами двоичного вектора псевдослучайной последовательности и подаче входного сигнала на оконечное устройство согласно изобретению на передающей стороне дополнительно формируют второй двоичный вектор псевдослучайной последовательности путем одновременного параллельного снятия информации с других n различных разрядов регистра сдвига и преобразуют кодированный блок входного сигнала путем сложения по модулю Р=2ⁿ числа, соответствующего двоичному вектору кодированного блока входного сигнала с числом, соответствующим второму двоичному вектору псевдослучайной последовательности, а на приемной стороне дополнительно формируют аналогично, как и на передающей стороне, второй двоичный вектор псевдослучайной последовательности, преобразуют его в сопряженный двоичный вектор путем вычитания из числа Р число, соответствующее второму двоичному вектору псевдослучайной последовательности, и восстанавливают кодированный блок путем сложения по модулю Р числа, соответствующего сопряженному двоичному вектору псевдослучайной последовательности, с числом, соответствующем двоичному вектору закодированного блока входного сигнала.

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

Перечисленная совокупность существенных признаков исключает возможность определения ключей защиты и повышает стойкость кода к атакам на основе известных и подобранных исходных текстов. В этом случае сформированная псевдослучайная последовательность символов в виде двоичных векторов длиною n бит являются псевдослучайной последовательностью символов 0, 1, 2,... , n-1 имеют тот же период N=2^k-1, что и псевдослучайные последовательности двоичных чисел, и обеспечивают статистическую равномерность использованных символов.

Так как в криптографических преобразованиях используется две псевдослучайные последовательности символов и две разные операции сложение символов по модулю два и сложение чисел по модулю Р=2ⁿ, то при наличии сколь угодно символов исходного и им соответствующих символов шифрованного текста исключается возможность определения символов псевдослучайных последовательностей, так как для их определения число уравнений всегда будет меньше числа неизвестных. При этом обеспечивается стойкость кода к атакам на основе известных и подобранных исходных текстов, так как вскрытие состояния регистра сдвига в этом случае может быть обеспечено только путем тотального перебора всего множества возможных состояний регистра сдвига. Поскольку стандарт США DES предусматривает использование регистра сдвига, имеющего 128 разрядов (длина ключа 128 бит), мощность множества возможных состояний регистра сдвига будет составлять 10³⁸. Если вскрытие состояния регистра сдвига будет осуществляться с помощью ЭВМ, имеющей тактовую частоту 100 ГГц, то число операций выполняемой этой ЭВМ в течении года будет составлять 3· 10²⁰, а время вскрытия составляет 10¹⁷ лет.

Возможность технической реализации заявленного способа поясняется следующим образом.

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

Формирование псевдослучайной последовательности максимальной длины, содержащей 2^k-1 символов, осуществляют путем использования линейного регистра сдвига, имеющего k разрядов, обратную связь которого определяют по виду выбранного примитивного полинома степени k. Нахождение примитивных полиномов степени k изложено в [4] на стр.74-75.

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

l₀ ≡ К[mod q), если l₀<2, то l₀=2,

и вычисления номера разряда регистра сдвига по формуле

l₁=l₀, l_i ≡ l₀l_i-1(modq), .

Значение q выбирается из простых чисел и для регистра сдвига, имеющего 256 разрядов, q=257, для регистра сдвига, имеющего 128 разрядов, q=127.

В этом случае за счет возведения в степень порождающего числа l₀ мы будем переходить от одного элемента поля F_q к другому. При этом, как показано в [4] стр.44, если l₀ - элемент порядка k, то все элементы l₀, , ,... , будут различны.

Используют еще четыре варианта формирования псевдослучайных последовательностей символов в виде двоичных векторов.

1. Формируют дополнительный ключ защиты и для каждого сеанса связи, генерируют случайный двоичный вектор длиною k бит, создают двоичный вектор для начального заполнения регистра сдвига путем сложения по модулю два битов случайного двоичного вектора с битами основного ключа защиты, а дополнительный ключ защиты используют для кодирования и передачи на приемный конец линии связи случайного двоичного вектора путем сложения их битов по модулю два.

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

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

3. Изменяют порядок считывания информации для псевдослучайной последовательности символов конечного поля в соответствии с изменением начального заполнения регистра сдвига.

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

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

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

Предлагаемый способ может быть реализован с помощью устройств. представленных блок-схемой на фиг.1, где: блок 1 - источник сигнала; блок 2 - первый формирователь ключа защиты; блок 3 - первый регистр сдвига; блок 4 - кодирующее устройство; блок 5 - передатчик; блок 6 - приемник; блок 7 - второй формирователь ключа защиты; блок 8 - второй регистр сдвига; блок 9 - декодирующее устройство; блок 10 - оконечное устройство, и блок-схемой на фиг.2, где блоки 11-16 разряды 1-6 регистра, сдвига, а блок 17 - сумматор по модулю два.

Для простоты описания работы устройства будем пользоваться малыми числами. Будем считать, что регистр сдвига имеет 6 разрядов (длина ключа защиты 6 бит), а блок входного сигнала имеет длину 4 бита. Для определения структуры регистра сдвига выбирают примитивный многочлен шестой степени; например

λ ⁶+λ ⁵+1.

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

Сформированный в блоке 2 фиг.1 с помощью генератора случайных чисел ключ защиты длиною 6 бит

<λ ₆, λ ₅, λ ₄, λ ₃, λ ₂, λ ₁>,

где λ ₁=0, λ ₂=0, λ ₃=0, λ ₄=1, λ ₅=1, λ ₆=1;

поступает в регистр сдвига и используется для начального заполнения разрядов регистра сдвига. Двоичные символы с 5 и б разряда регистра сдвига поступают в каждом такте работы на вход сумматора 17 по модулю два, а с выхода сумматора по модулю два символы ε поступают на вход первого разряда регистра сдвига (блок 11, фиг.2). При этом состояния разрядов для каждого такта в процессе работы регистра сдвига определяются выражением

λ _i=λ _i-1 для , λ ₁=ε .

Если символы будут сниматься с шестого разряда λ ₆ регистра сдвига (блок 16, фиг.2), то двоичная псевдослучайная последовательность максимального периода будет иметь вид

{1110000010000110001010011110100011

100100101101110110011010101111}.

Заметим, что на периоде этой последовательности любой ненулевой набор из шести знаков 0 и 1 встречается и только один раз.

Если двоичные числа будем снимать с 1, 2, 3 и 4 разряда регистра сдвига (блоки 11, 12, 13, 14, фиг.2) и на каждом такте работы регистра сдвига с набором <λ ₁, λ ₃, λ ₃, λ ₄> будем сопоставлять двоичный вектор (число) х=λ ₁+2λ ₂+2²λ ₃+2³λ ₄, то последовательность двоичных чисел в процессе работы регистра можно рассматривать как последовательность х чисел (символов) {0, 1, 2,... ,15} в виде

х=8, 0, 0, 1, 2, 4, 8, 0, 1, 3, 6, 12, 8, 1, 2, 5, 10, 4, 9, 3, 7, 15, 14, 13, 10, 4, 8, 1, 3, 7, 14, 12, 9, 2, 4, 9, 2, 5, 11, 6, 13, 11, 7, 14, 13, 11, 6, 12, 9, 3, 6, 13, 10, 5, 10, 5, 11, 7, 15, 15, 15, 14, 12, ... .

Если двоичные числа будем снимать одновременно с 1, 2, 5, 6 разрядов регистра сдвига (блоки 11, 12, 15, 16) на каждом такте его работы с набором <λ ₆, λ ₅, λ ₂, λ ₁> будем сопоставлять двоичный вектор (число) у=λ ₆+2λ ₅+2²λ ₂+2³λ ₁, тo последовательность двоичных чисел в процессе работы регистра сдвига можно рассматривать как последовательность символов у 0, 1, 2,..., 15 в виде

у=3, 3, 1, 8, 4, 0, 0, 2, 9, 12, 4, 0, 2, 11, 5, 8, 4, 2, 9, 14, 13, 12, 6, 11, 7, 3, 1, 10, 13, 12, 4, 2, 11, 7, 1, 8, 6, 9, 12, 6, 9, 14, 15, 5, 10, 15, 7, 1, 10, 15, 5, 8, 6, 11, 5, 10, 13, 14, 13, 14, 15, 7, 3, ... .

Анализ сформированных последовательностей х и у показывает, что на интервале, соответствующему периоду, равному 63 тактам работы регистра сдвига; каждый из символов {1, 2,... , 15} встречается ровно четыре раза. Символ, соответствующий нулю, в обеих последовательностях встречается ровно три раза, при этом последовательности х и у не могут быть получены друг из друга в результате циклического сдвига. В последовательностях х и у отсутствуют скрытые периодичности и обеспечивается статистическая равномерность используемых символов.

Сформированные псевдослучайные последовательности символов х и у в виде двоичных векторов поступают в кодирующее устройство 4, где кодируют блок входного сигнала 0111⇒ 7 путем сложения по модулю два его битов с битами двоичного вектора псевдослучайной последовательности х=8⇒ 1000. Полученный двоичный вектор 1111⇒ 15 складывают по модулю Р=2⁴=16 с символами псевдослучайной последовательности у=3⇒ 0011 и передают закодированное сообщение в виде двоичного вектора 0010⇒ 2.

При этом декодирование сообщения осуществляют в блоке 9 в следующем порядке. Принятый блок 0010⇒ 2 складывают по модулю 16 с сопряженным символом псевдослучайной последовательности у* =Р-у=16-3=13⇒ 1101. Из полученного числа 13+2=15 (mod 16)⇒ 1111 формируют двоичный вектор 1111 и складывают его биты по модулю два с битами двоичного вектора псевдослучайной последовательности х=8⇒ 1000, в результате получают двоичный вектор 0111⇒ 7, соответствующий двоичному вектору входного сигнала.

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

Источники информации

1. Способ передачи дискретной информации в радиолинии с псевдослучайной перестройкой рабочей частоты и устройство для его осуществления. Заявка на изобретение №99123808/09 от 10.11.1999 - МПК7 Н 04 В 1/713.

2. С.Мафтик. Механизмы защиты в сетях ЭВМ. - М., 1993 г.

3. В.И.Нечаев. Элементы криптографии. Основы теории защиты информации. - М.: Высшая школа, 1999 г.

4. Б.Н.Воронков, В.И.Тупота. Методическое пособие по разработке средств защиты информации в вычислительных сетях. - Воронеж: Воронежский Государственный Университет, 2000.

Изобретение относится к области электросвязи и вычислительной технике, в частности, к способам и устройствам криптографической обработки данных. Техническим результатом является повышение стойкости кода к атакам на основе известных и подобранных исходных текстов. Технический результат достигается тем, что способ передачи дискретной информации в вычислительной сети, включает на передающей стороне деление входного сигнала на блоки длиною n бит, формирование ключа защиты в виде двоичного вектора длиною k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащей 2^k-1 двоичных символов, формирование двоичного вектора псевдослучайной последовательности путем одновременного параллельного снятия информации с различных разрядов регистра сдвига, при этом длину двоичного вектора псевдослучайной последовательности выбирают равной длине двоичного вектора блока входного сигнала, кодирование блока входного сигнала путем сложения по модулю два битов двоичного вектора псевдослучайной последовательности с битами двоичного вектора блока входного сигнала и последующую передачу закодированного блока входного сигнала по линии связи, прием сигнала на приемном конце линии связи, формирование ключа защиты в виде двоичного вектора длиною k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов, а также формирование аналогично как и на передающей стороне двоичного вектора псевдослучайной последовательности длиной n бит, осуществление декодирования закодированного блока входного сигнала путем сложения по модулю два его битов с битами двоичного вектора псевдослучайной последовательности и подачу входного сигнала на оконечное устройство, отличаюется тем, что на передающей стороне дополнительно формируют второй двоичный вектор псевдослучайной последовательности путем одновременного параллельного снятия информации с других n различных разрядов регистра сдвига и преобразуют кодированный блок входного сигнала путем сложения по модулю Р=2ⁿ числа, соответствующего двоичному вектору закодированного блока входного сигнала с числом, соответствующим второму двоичному вектору псевдослучайной последовательности, а на приемной стороне дополнительно формируют аналогично как и на передающей стороне второй двоичный вектор псевдослучайной последовательности, преобразуют его в сопряженный двоичный вектор путем вычитания из числа Р число, соответствующее второму двоичному вектору псевдослучайной последовательности, и восстанавливают кодированный блок входного сигнала путем сложения по модулю Р числа, соответствующего сопряженному двоичному вектору псевдослучайной последовательности с числом, соответствующим двоичному вектору закодированного блока входного сигнала. 4 з.п. ф-лы, 2 ил.

1. Способ передачи дискретной информации в вычислительной сети, включающий на передающей стороне деление входного сигнала на блоки длиной n бит, формирование ключа защиты в виде двоичного вектора длиной k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов и вырабатывающего псевдослучайную последовательность максимальной длины, содержащей 2^k-1 двоичных символов, формирование двоичного вектора псевдослучайной последовательности путем одновременного параллельного снятия информации с различных разрядов регистра сдвига, при этом длину двоичного вектора псевдослучайной последовательности выбирают равной длине двоичного вектора блока входного сигнала, кодирование блока входного сигнала путем сложения по модулю два битов двоичного вектора псевдослучайной последовательности с битами двоичного вектора блока входного сигнала и последующую передачу закодированного блока входного сигнала по линии связи, прием сигнала на приемном конце линии связи, формирование ключа защиты в виде двоичного вектора длиной k бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего k разрядов, а также формирование аналогично как и на передающей стороне двоичного вектора псевдослучайной последовательности длиной n бит, осуществление декодирования закодированного блока входного сигнала путем сложения по модулю два его битов с битами двоичного вектора псевдослучайной последовательности и подачу входного сигнала на оконечное устройство, отличающийся тем, что на передающей стороне дополнительно формируют второй двоичный вектор псевдослучайной последовательности путем одновременного параллельного снятия информации с других n различных разрядов регистра сдвига и преобразуют кодированный блок входного сигнала путем сложения по модулю P=2ⁿ числа, соответствующего двоичному вектору закодированного блока входного сигнала, с числом, соответствующим второму двоичному вектору псевдослучайной последовательности, а на приемной стороне дополнительно формируют аналогично как и на передающей стороне второй двоичный вектор псевдослучайной последовательности, преобразуют его в сопряженный двоичный вектор путем вычитания из числа Р числа, соответствующего второму двоичному вектору псевдослучайной последовательности, и восстанавливают кодированный блок входного сигнала путем сложения по модулю Р числа, соответствующего сопряженному двоичному вектору псевдослучайной последовательности, с числом, соответствующим двоичному вектору закодированного блока входного сигнала.2. Способ по п.1, отличающийся тем, что формируют дополнительный ключ защиты и для каждого сеанса связи генерируют случайный двоичный вектор длиной k бит, создают двоичный вектор для начального заполнения регистра сдвига путем сложения по модулю два битов случайного двоичного вектора с битами ключа защиты, а дополнительный ключ защиты используют для кодирования и передачи на приемный конец линии связи случайного двоичного вектора.3. Способ по любому из пп.1 и 2, отличающийся тем, что пропускают те такты работы регистра сдвига, для которых символы формируемых двоичных векторов псевдослучайных последовательностей совпадают во всех или нескольких выбранных разрядах.4. Способ по любому из пп.1-3, отличающийся тем, что при каждом сеансе связи изменяют номера разрядов регистра сдвига, с которых снимается информация для формирования двоичных векторов псевдослучайных последовательностей в зависимости от сформированного двоичного вектора начального заполнения регистра сдвига.5. Способ по любому из пп.1-4, отличающийся тем, что при каждом сеансе связи изменяют порядок считывания информации с выделенных разрядов регистра сдвига для формирования двоичных векторов псевдослучайных последовательностей в зависимости от сформированного двоичного вектора начального заполнения регистра сдвига.