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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как в качестве модуля сравнения используют числа вида р=2^k, то функция Эйлера ϕ(р)=2^(k-1), где k - целое число большее двух. В этом случае по отношению к числу х в кольце класса вычетов по модулю р существуют обратные элементы х^-1 только для нечетных чисел. Эти числа являются элементами мультипликативной группы кольца класса вычетов по модулю р. При этом могут быть вычислены обратные элементы для декодирования сообщения:

х^-1≡x^q(mod p), где q=2^(k-1)-1.

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

х≡х·x_n{mod p)

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

α·х≡β(mod p)

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

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

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

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

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

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

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

Для простоты описания работы устройства будем считать, что длина ключа составляет 6 бит, а передаваемое сообщение в виде последовательности нулевых и единичных бит представлено в виде:

011101110111011101110111011101110111011101110111011101110111

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

0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111

Сформированный в блоке 1 ключ защиты 100101 вместе с сигналом исходного текста подают в блок 2 (см. чертеж). В этом блоке формируют порождающий элемент x_n путем приведения числа, соответствующего ключу защиты, по модулю р=16

x_n≡2⁰+2²+2⁵(mod16)≡5,

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

С_α≡C_α-1+α(mod16)

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

С_α=7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9,

а также вычисляют элементы х=х x_n (mod16), которые являются символами перебирающей последовательности:

х=5, 9, 13, 1, 13, 9, 5, 1, 9, 1, 7, 1, 5, 9, 13.

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

Сформированные символы перебирающей последовательности х в виде двоичных векторов подают в кодирующее устройство 3, где преобразуют исходный текст α в закодированное сообщение β в соответствии с выбранным криптографическим преобразованием, например

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

х=5, 9, 13, 1, 13, 9, 5, 1, 9, 1, 7, 1, 5, 9, 13,

β=3, 15, 11, 7, 11, 15, 3, 7, 15, 7, 1, 7, 3, 13, 11.

С учетом передачи новых порождающих элементов перебирающей последовательности закодированное сообщение будет иметь следующий вид:

β*=3, 15, 11, 7, 12, 11, 15, 3, 7, 8, 15, 7, 6, 1, 7, 4, 3, 13, 11.

Для полученных значений β* формируют двоичный вектор, добавляют к нему избыточный бит для проверки на четность и передают с помощью устройства 4 (см.чертеж) на приемный конец радиолинии.

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

х^-1≡x⁷(mod 16)=13, 9, 5, 1, 5, 9, 13, 1, 9, 1, 7, 1, 5, 9, 5,

например:

β=3, 15, 11, 7, 11, 15, 3, 7, 15, 7, 1, 7, 3, 13, 11,

x^-1=13, 9, 5, 1, 5, 9, 13, 1, 9, 1, 7, 1, 5, 9, 5,

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

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

Для уменьшения вводимой избыточности передаваемое дискретное сообщение

011101110111011101110111011101110111011101110111011101110111

разбивают на блоки и представляют его в виде 12 символов, которым соответствует двоичный вектор длиною 5 бит, а в качестве модуля сравнения используют число р=32.

01110 11101 11011 01110 11101 11011 01110 11101 11011 01110 11101 11011

Сформированный в блоке 1 ключ защиты 100101 вместе с сигналом исходного текста подают в блок 2 (см. чертеж). В этом блоке формируют порождающий элемент x_n путем приведения числа, соответствующего ключу защиты, по модулю р=32

x_n≡2⁰+2²+2⁵(mod32)≡5,

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

Сα≡С_α-1+α(mod32)

α=14, 29, 27, 14, 29, 27, 14, 29, 27, 14, 29, 27,

C_α=14, 11, 6, 20, 17, 12, 26, 23, 18, 0, 29, 24,

а также вычисляют элементы х=х x_n (mod32), которые являются символами перебирающей последовательности:

х=5, 25, 29, 17, 21, 9, 13, 1, 23, 17, 7, 1.

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

Сформированные символы перебирающей последовательности х в виде двоичных векторов поступают в кодирующее устройство 3 (см. чертеж), где преобразуют исходный текст α в закодированное сообщение β в соответствии с выбранным криптографическим преобразованием, например

α=14, 29, 27, 14, 29, 27, 14, 29, 27, 14, 29, 27,

x=5, 25, 29, 17, 21, 9, 13, 1, 23, 17, 7, 1,

β=6, 21, 15, 14, 1, 19, 22, 29, 13, 14, 11, 27.

С учетом передачи новых порождающих элементов перебирающей последовательности закодированное сообщение будет иметь следующий вид:

β*=6, 21, 15, 14, 1, 19, 22, 29, 23, 13, 14, 11, 27, 24.

Для полученных значений β* формируют двоичный вектор, добавляют к нему избыточный бит для проверки на четность и передают с помощью устройства 4 (см. чертеж) на приемный конец радиолинии.

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

х^-1≡x⁷(mod 32)=13, 9, 21, 17, 29, 25, 5, 1, 7, 17, 23, 1, 9, 17, 25,

например:

β=6, 21, 15, 14, 1, 19, 22, 29, 13, 14, 11, 27,

x^-1=13, 9, 21, 17, 29, 25, 5, 1, 7, 17, 23, 1,

α=14, 29, 27, 14, 29, 27, 14, 29, 27, 14, 29, 27,

проверяют на четность двоичные вектора символов закодированного сообщения и при обнаружении ошибки корректируют искаженный символ (например, если исказился третий символ последовательности и вместо символа "27" принят символ "21", тогда вычисленный суммарный символ исходного текста на 8 такте работы устройства будет равен 17 и отличаться от переданного суммарного символа исходного текста 23 на 6).

Таким образом, с увеличением n с 4 до 5 вводимая избыточность уменьшается, что приводит к увеличению скорости передачи информации в условиях снижения уровня помех в линии связи, искажающих не более двух символов в сообщении.

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

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

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

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

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

4. Способ поточного кодирования дискретной информации. Патент на изобретение №2205516 по заявке №2002104639 от 20.02.2002.

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

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

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