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

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

Известны способы поточного кодирования дискретной информации (см. например, Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 [1], Британский алгоритм B-Grypt, являющий дополнением к стандарту США DES [2] стр.50, 126, а также способ, описанный в [3] стр.50-51).

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

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

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

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

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

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

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

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

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

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

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

За счет пропуска тактов работы регистра сдвига, для которых символы псевдослучайной последовательности принимают четные значения будет сформирована псевдослучайная последовательность символов х из нечетных чисел 1,3,5,7,... ,р-2, которую используют для кодирования символов исходного текста α за счет возведения их в степень, соответствующую символам псевдослучайной последовательности х. При этом закодированное сообщение будет представлять последовательность символов β , определяемых по формуле

β ≡ α ^x(modp).

Поскольку число р=2^k+1 является простым, то функция Эйлера ϕ (р)=(р-1) и в соответствии с теоремой Эйлера-Ферма будет иметь следующее тождество

α ^{1+mϕ (р)}=α ^1+m(р-1) ≡^{α (modp).}

Так как x· x^-1=1+m(р-1)≡ 1(mod(p-1)),

где m - произвольное целое положительное число,

x^-1 - символ, обратный символу х в кольце класса вычетов по модулю

p-1,

то справедливо соотношение В этом случае вычисленные на приемной стороне значения символов x^-1 в кольце класса вычетов по модулю р-1 позволяют реализовать обратные преобразования для декодирования исходного текста

Поскольку псевдослучайная последовательность х включает только нечетные символы 1,3,5,... ,р-2, то все они являются элементами мультипликативной группы кольца классов вычетов по модулю р-1 и будут иметь обратные величины x^-1, которые могут быть определены по формуле

где ϕ (р-1) - функция Эйлера для числа р-1. Поскольку р-1=2^k, то ϕ (р-1)=2^k-1. В этом случае х^-1 можно рассчитать по формуле

где q=2^(k-1)-1. При этом для вычисления х^-1 может быть использован алгоритм быстрого возведения чисел по модулю, представленный в [4] на стр.39.

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

В соответствии с Российским стандартом ГОСТ 28147-89 для регистра сдвига, имеющего 256 разрядов (длина ключа 256 бит), время вскрытия состояния регистра сдвига будет составлять 10⁵⁷ лет.

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

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

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

если l₀<2, то l₀=2,

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

l₁=l₀,

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

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

Поскольку р должно быть простым числом, равным р=2^k+1 то, в качестве k выбирают один из членов геометрической прогрессии 2, 4, 8, 16, 32, 64,... , со знаменателем, равным двум.

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

α ^x ≡^{β(mod p)}

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

1. Изменяют число разрядов k, c которых снимается информация для псевдослучайной последовательности символов конечного поля F_p, p=2^k+1 в соответствии с изменением начального заполнения регистра сдвига.

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

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

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

Преобразование потока данных в закодированное сообщение можно осуществить путем разбиения исходных данных на блоки в виде символов α двоичных векторов длиною k бит, вычислении в конечном поле F_p, (p=2^k+1) значений символов β закодированного текста в соответствии с выбранной функцией кодирования, α ^x ≡ β (mod p), преобразовании полученного числа β в двоичный вектор, и передачу его по линии связи. При этом может быть использован алгоритм быстрого возведения числа в степень в конечном поле F_p, представленный в [4] на стр.39.

Предлагаемый способ может быть реализован с помощью устройства. На фиг.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). При этом состояние разрядов для каждого такта в процессе работы регистра сдвига определяются выражением

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

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

{1110000010000110001010011110100011

100100101101110110011010101111}.

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

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

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, 3, 5, 7, 9,... , 15 в виде:

х=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,11,9,3,3,13,5,5,11,7,15

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

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

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

х=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,

β =7,7,3,7,11,10,3,12,5,6,7,3,12,10,10,11,14,6,14,12,6.

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

На приемном конце радиолинии осуществляют декодирование принятой последовательности символов β в соответствии с установленным криптографическим преобразованием α ≡ β ^х-1(modl7) в конечном поле F₁₇. Так как р=17, k=4, то расчет х^-1 осуществляется по формуле х^-1 ≡^{x7(mod16). Тогда для рассмотренного примера значения соответствующих символов при декодировании сообщения будут иметь вид:}

β =7,7,3,7,11,10,3,12,5,6,7,3,12,10,10,11,14,6,14,12,6,

х=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,

х^-1=1,1,11,1,13,9,11,7,15,5,1,11,7,9,9,13,3,5,3,7,5,

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

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

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

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

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

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

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

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

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