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

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

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

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

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

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

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

Однако способ-прототип имеет недостаток. Для корректировки искаженного при приеме символа вводится большая избыточность путем добавления к преобразованному двоичному вектору исходного текста избыточного бита для проверки закодированного символа на четность. При этом количество символов в передаваемом сообщении увеличивается на 13%.

Изобретение направлено на снижение избыточности в передаваемом сообщении и увеличение скорости передачи сообщения.

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

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

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

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

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

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

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

x≡ Δ β · Δ α ^-1(mod p),

где Δ α ^-1≡^{(Δ α )p-2(mоdр)-обратный элемент по отношению к символу Δ α в поле F_p:}

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

α ≡ α +Δ α (mod p).

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

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

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

l₀=К(mod q), если l₀&λτ;_{2, то l0=2,}

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

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

, l30,... ,lk-10 будут различны.

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

x≡ x· x_n(mod p)

Если в процессе вычислений на каком-то i такте работы регистра сдвига, окажется, что x=1, то в этом случае меняется порождающий элемент x_n поля F_p. При этом в качестве нового порождающего элемента х_n принимается элемент, сформированный на данном такте работы регистра сдвига, суммарный символ исходного текста С конечного ноля F_p, х_n=С, если С&λτ; 2, то x_n=2. Сформированные последовательности конечного поля F_p используют в криптографических преобразованиях при преобразовании потока данных в закодированное сообщение:

α · x+у=β (mod р)

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

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

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

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

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

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

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

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

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

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

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

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

λ ⁶+λ ⁵+1

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

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

&λτ; λ ₆, λ ₅, λ ₄, λ ₃, λ ₂, λ₁&γτ;_.

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

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

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

{1110000010000110001010011110100011

100100101101110110011010101111}.

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

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

+2³λ4, то последовательность двоичных чисел в процессе работы регистра можно рассматривать как последовательность у чисел (символов) {0, 1, 2,... , 15} в виде

y={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... }.

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

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

x_n=2³+2⁴+2⁵(mod l7)=5,

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

x=x x_n(mod 17),

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

x 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6.

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

Сα =Сα _-1 α (mod 17)

α =7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

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

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

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

α =7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

x=5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6,

y=8, 0, 0, 1, 2, 4, 8, 0, 1, 3, 6, 12, 8, 1, 2, 5, 10, 4, 9, 3, 7,

β =9, 5, 8, 7, 15, 1, 10, 10, 0, 15, 15, 6, 12, 4, 0, 12, 12, 7, 5, 14, 5.

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

Сβ =9, 14, 5, 12, 10, 11, 4, 14, 14, 12, 10, 16, 11, 15, 15, 10, 5, 12, 0, 14, 2.

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

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

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

β =9, 5, 8, 7, 15, 1, 10, 10, 0, 15, 15, 6, 12, 4, 0, 12, 15, 10, 12, 7, 5, 14, 5,

y* =9, 0, 0, 16, 15, 13, 9, 0, 16, 14, 11, 5, 9, 16, 15, 12, 7, 13, 8, 14, 10,

x^-1=7, 15, 3, 4, 11, 9, 12, 16, 10, 2, 14, 13, 6, 8, 5, 1,, 12, 8, 11, 13, 3,

α =7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,, 7, 7, 7, 7, 7.

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

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

Сα * =7, 14, 4, 11, 1, 8, 15, 5, 12, 9, 16, 6, 13, 3, 10, 0.

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

Δ α ≡ Сα -Cα * (mod p)=10-0≡ 10(mod 17);

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

Сβ * =9, 14, 5, 12, 10, 11, 4, 14, 14, 7, 5, 11, 6, 10, 10, 5,

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

Δ β ≡ Сβ -Cβ * (mod p)=10-5≡ 5(mod 17);

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

x≡ Δ β · Δ α ^-1(mod p)=5· 12=60≡ 9(mod 17),

где Δ α ^-1≡^{(Δ α )p-2(mod p) - обратный элемент по отношению к символу Δ α в поле F_p:}

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

α ≡ α +Δ α (mod p)=14+10=24=7(mod 17).

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

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

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

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

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

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

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

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

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