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

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

Известны способы поточного кодирования дискретной информации (см. например, Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 [1], Британский алгоритм В-Grypt, являющий дополнением к стандарту США DES [2] стр.50, 126, [3] стр.50-51, а также способ, описанный в патенте на изобретение 2002104639/09, МПК 7 H 04 L 9/00 [4]).

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

Известные способы - аналоги поточного кодирования дискретной информации обеспечивают ее целостность. Способы, описанные в [1-3], уязвимы к атакам на основе известных или подобранных исходных текстов, способ, описанный в [4], обеспечивает помехоустойчивость передаваемой информации при активных вторжениях.

Наиболее близким по своей технической сущности к заявленному способу является способ, представленный в [4].

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

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

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

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

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

Перечисленная совокупность существенных признаков повышает корректирующие возможности способа поточного кадирования дискретной информации за счет возможности корректировки двух искаженных при приеме символов на интервале, соответствующем смене порождающих элементов перебирающей последовательности. При этом для исправления двух искаженных символов передают по линии связи суммарный символ кодированного текста в момент изменения порождающего элемента перебирающей последовательности, когда ее символ принимает значение, равное "1". Поскольку смена порождающих элементов перебирающей последовательности конечного поля F₂₅₇ в среднем осуществляется через 256 символов, то один суммарный символ кодированного текста будет передаваться двоичным вектором длиною 8 бит в среднем через 256 символов.

Если две ошибки произойдут на интервале, соответствующем смене порождающих элементов перебирающей последовательности, то эти ошибки будут исправлены. Для этого:

- вычисляют расхождение Δα в суммарных символах переданного исходного текста C_α и вычисленного C_α* на приемной стороне

- вычисляют расхождение Δ_β в суммарных символах переданного кодированного текста С С_β и вычисленного С_β* на приемной стороне

- вычисляют корректирующую поправку Δα_i для искаженного символа исходного текста на приемной стороне

где x_i, x_j-i-й и j-й символы перебирающей последовательности, соответствующие i-му и j-му ошибочно принятым закодированным символам. (x_i-x_j ^-1≡(x_i-x_j)^p-2(modp) - обратный элемент в поле F_p;

- вычисляют корректирующую поправку Δx_j для искаженного символа исходного текста на приемной стороне

- корректируют искаженный на приемной стороне символ исходного текста α_i по формуле

- корректируют искаженный на приемной стороне символ исходного текста α_j по формуле

Выражение для корректирующих поправок Δα_i,_{Δαj получено в результате решения системы уравнений:}

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

Формирование псевдослучайной последовательности максимальной длины, содержащей 2ⁿ-1 символов, можно осуществлять путем использования линейного регистра сдвига, имеющего n разрядов, обратную связь которого определяют по виду выбранного примитивного полинома степени n. Нахождение примитивных полиномов степени n изложено в [5] на стр.106-110.

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

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

Значение q выбирают из простых чисел и для регистра сдвига, имеющего 256 разрядов, q=257, для регистра сдвига, имеющего 128 разрядов, q=127. В этом случае за счет возведения в степень порождающего числа l₀ мы будем переходить от одного элемента поля F_q к другому. При этом, как показано в [5] стр.9, если l₀ - элемент порядка k то все элементы l₀, l₀ ², l₀ ³, ..., l₀ ^k-1 будут различны.

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

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

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

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

Формирование символов х перебирающей последовательности в виде двоичных векторов на каждом такте работы регистра сдвига можно определить как порожденные элементы поля F_p путем умножения предыдущего символа этой последовательности на порождающий элемент x_n:

Если в процессе вычислений на каком-то i такте работы регистра сдвига окажется, что х=1, то в этом случае меняется порождающий элемент x_n поля F_p. При этом в качестве нового порождающего элемента x_n принимается элемент, сформированный на данном такте работы регистра сдвига суммарный символ исходного текста C_α конечного поля F_p, x_n=С_α, если С_α<2, то x_n=2. Сформированные последовательности конечного поля Fp используют в криптографических преобразованиях при преобразовании потока данных в кодирований текст:

Поскольку в перебирающей последовательности конечного поля элементы формируются за счет возведения в степень порождающего элемента x_n, имеющего порядок k, то все элементы x_n, x_n ², x_n ³, ..., x_n ^k будут различны на интервале k тактов работы регистра сдвига. Поскольку порождающие элементы x_n могут быть разного порядка в конечном поле F_p, то смена порождающих элементов будет осуществляться по псевдослучайному закону. При этом обеспечивается статистическая равномерность символов закодированного текста на интервале, равном р-1 тактам работы регистра сдвига, что исключает применение статистических методов криптоанализа для определения состояния регистра сдвига.

Преобразование потока данных в кодированный текст осуществляют путем разбиения исходных данных на блоки в виде символов α-двоичных векторов длиною 8 бит, вычисляют в конечном поле F_p, (р=257) значения символов (закодированного текста в соответствии с выбранной функцией кодирования α·x+y≡β(modp), преобразуют полученные числа (в двоичные вектора, добавляют к ним по избыточному биту и передают их по линии связи.

Предлагаемый способ может быть реализован с помощью ЭВМ или устройства. На фиг.1 представлена структурная схема устройства; где

блок 1 - устройство формирования ключа защиты и исходного сигнала;

блок 2 - регистр сдвига;

блок 3 - формирователь перебирающей последовательности;

блок 4 - кодирующее устройство;

блок 5 - передающее устройство.

Для регистра сдвига на фиг.2 блоки 6-11 - разряды 1-6 регистра сдвига; а блок 12 - сумматор по модулю два.

Для простоты описания работы устройства будем пользоваться малыми числами. Будем считать, что регистр сдвига имеет 6 разрядов (длина ключа 6 бит), а весь алфавит исходного текста содержит 16 символов, тогда для передачи одного символа может быть использован двоичный вектор длиною 4 бита, а в качестве характеристики конечного поля F_p может быть выбрано число р=17.

Для определения структуры регистра сдвига выбирают примитивный многочлен шестой степени, например

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

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

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

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

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

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

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

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

Сформированный в блоке 1 фиг.1 ключ защиты 111000 вместе с сигналом исходного текста поступает в блок 3 фиг.1. В этом блоке формируют порождающий элемент x_n путем приведения числа, соответствующего ключу защиты, в конечное множество поля F₁₇

и вычисляют для каждого такта работы регистра сдвига элементы конечного поля F₁₇

которые являются символами перебирающей последовательности:

а также вычисляют суммарные символы исходного текста

Если символ перебирающей последовательности принимает значение "1", то изменяют пораждающий элемент x_n в соответствии со значением суммарного символа исходного текста. Для приведенного примера новый пораждающий элемент равен "10". Этот элемент кодируют в устройстве 4 фиг.1 и передают с использованием устройства 5 фиг.1 на приемный конец радиолинии закодированным символом 12.

Сформированные последовательности символов конечного поля х и y в виде двоичных векторов поступают в кодирующее устройство 4 фиг.1, где преобразуют поступающий поток данных а в кодированный текст β в соответствии с выбранным криптографическим преобразованием в конечном поле F₁₇, например

Для полученных значений β формируют суммарный символ кодированного текста С_β≡C_β-1+β(mod17)

Если символ перебирающей последовательности принимает значение "1",то суммарный символ кодированного текста (в нашем случае символ 10) в виде двоичного вектора передают по линии связи после передачи порождающего элемента.

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

На приемном конце радиолинии осуществляют декодирование принятой последовательности символов β в соответствии с установленным криптографическим преобразованием α≡(β+y*)·x^-1(mod17) в конечном поле F₁₇, например:

проверяют на четность двоичные вектора символов кодированного текста и при обнаружении ошибок корректируют искаженные символы.

Если при приеме сообщения произошла ошибка, например, при приеме десятого символа вместо символа 15 принят символ 10, то при декодировании сообщения этому символу будет соответствовать символ 14 (вместо символа 7), а при приеме тринадцатого символа вместо символа 12 принят символ 11, то при декодировании сообщения этому символу будет соответствовать символ 1 (вместо символа 7). Эти ошибки исправляются следующим образом:

- вычисляют суммарный символ исходного текста

- вычисляют расхождение Δα в суммарных символах переданного исходного текста С_α и вычисленного C_α* на приемной стороне

- вычисляют суммарный символ кодированного текста

- вычисляют расхождение Δβ в суммарных символах переданного кодированного текста С_β и вычисленного C_β* на приемной стороне

- вычисляют корректирующую поправку Δα₁₀ для искаженного символа исходного текста на приемной стороне

где x₁₀=9, x₁₃=3 - символы перебирающей последовательности, соответствующие 10-му и 13-му ошибочно принятым закодированным символам.

- вычисляют корректирующую поправку Δα₁₃ для искаженного символа исходного текста на приемной стороне

- корректируют искаженный на приемной стороне символ исходного текста α₁₀ по формуле

- корректируют искаженный на приемной стороне символ исходного текста α_j по формуле

Криптостойкость предлагаемого способа может быть усилена путем кодирования передаваемого суммарного символа кодированного текста.

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

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

1. Российский стандарт шифрования - стандарт СССР ГОСТ 28147-89. Системы обработки информции. Защита криптографическая. Алгоритм криптографического преобразования.

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

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

4. Способ поточного кодирования дискретной информации. Патент на изобретение №2002104639/09, МПК 7 H 04 L 9/00.

5. В.И.Тупота. Адаптивные средства защиты информации в вычислительных сетях, М.: Радио и связь, 2002 г.

Изобретение относится к области электросвязи и вычислительной техники. Технический результат - повышение помехоустойчивости передаваемой информации. Сущность изобретения заключается в формировании ключа защиты в виде двоичного вектора длиною n бит, подачи его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов, формировании псевдослучайной последовательности символов конечного поля F_p с характеристикой р=257 в виде двоичных векторов, формировании в виде двоичных векторов символов перебирающей последовательности за счет возведения в степень порождающего элемента в конечном поле F_p, разбиении потока данных на блоки-символы исходного текста в виде двоичных векторов длиною 8 бит, формировании суммарного символа исходного текста в виде двоичного вектора путем сложения в конечном поле F_p символа исходного текста со всеми предыдущими символами исходного текста и поочередном преобразовании двоичных векторов символов исходного текста путем умножения их на символы перебирающей последовательности и сложении в конечном поле F_p полученного результата с символами псевдослучайной последовательности, замене порождающего элемента перебирающей последовательности при появлении в ее составе символа "1" на суммарный символ исходного текста, кодировании нового порождающего элемента, преобразовании потока данных исходного текста в кодированный текст и передачи кодированного текста и нового порождающего элемента по линии связи. Отличительной особенностью данного способа является то, что формируют суммарный символ кодированного текста в виде двоичного вектора путем сложения в конечном поле F_p очередного символа кодированного текста со всеми предыдущими символами кодированного текста и передачи суммарного символа кодированного текста по линии связи после замены и передачи порождающего элемента перебирающей последовательности. 3 з.п. ф-лы, 2 ил.

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