Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к способам и устройствам криптографического преобразования данных.
Известны способы поточного кодирования дискретной информации (см., например, Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 [1], Британский алгоритм В-Сrурt, являющий дополнением к стандарту США DES [2] стр. 50, 126, а также способ, описанный в [3] стр. 50-51).
В известных способах кодирование дискретной информации осуществляется путем формирования ключа защиты, генерирования псевдослучайной последовательности двоичных символов и преобразования потока данных, включающего операции сложения по модулю два символов потока данных с символами псевдослучайной последовательности.
Известные способы - аналоги поточного кодирования дискретной информации - обеспечивают целостность, но не обеспечивают помехоустойчивость передаваемой информации при активных вторжениях.
Наиболее близким по своей технической сущности к заявленному способу является способ, представленный в [1] стр.126-127 и в [3] стр.50-51.
Способ-прототип включает в себя формирование ключа защиты в виде двоичного вектора длиною n бит, подачу его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов, формирование с использованием регистра сдвига псевдослучайной последовательности максимальной длины, содержащей 2n-1 двоичных символов, преобразование потока данных путем сложения по модулю два символов исходного текста с символами псевдослучайной последовательности и передачу закодированного сообщения по линии связи другому пользователю сети.
Однако способ-прототип имеет недостатки. Несмотря на то, что код, основанный на сложении потока псевдослучайных битов с битами исходного текста по модулю 2 является в общем случае теоретически нераспознаваемым (см. [2], стр.128), сама система кодирования не отличается стойкостью и может быть раскрыта. Если структура регистра сдвига, имеющего n-разрядов, известна, то для нахождения начального состояния регистра сдвига, надо знать n символов известного открытого текста, которые складываются по модулю 2 с соответствующими n символами кодированного текста. Полученные n символов псевдослучайной последовательности определяют состояние регистра сдвига на некоторый момент времени. Моделируя работу регистра сдвига в обратном направлении, можно определить его исходное состояние, а следовательно, и ключи, используемые пользователями сети при кодировании информации.
Если структура регистра сдвига, имеющего n-разрядов, является неизвестной, то достаточно 2•n символов известного открытого текста и им соответствующих 2•n символов кодированного текста, чтобы сравнительно быстро (в течение нескольких секунд работы ЭВМ) определить состояние регистра сдвига и вычислить используемые ключи (см. , например, [4] стр.93). А это приводит к снижению стойкости кода к атакам на основе известных и подобранных исходных текстов, что не обеспечивает конфиденциальности передаваемой информации и приводит к необходимости смены ключа защиты. Ключи защиты могут использоваться только один раз и при очередном сеансе связи должны определяться по новому. Кроме того, при активных вторжениях и при наличии помех в канале связи символы кодированного текста могут быть искажены помехами.
Изобретение направлено на повышение стойкости кода к атакам на основе известных и подобранных исходных текстов, а также повышению помехоустойчивости передаваемой информации.
Это достигается тем, что в известном способе кодирования дискретной информации, заключающемся в формировании ключа защиты в виде двоичного вектора длиною n бит, подаче его для начального заполнения регистра сдвига с обратной связью, имеющего n разрядов, формировании с использованием регистра сдвига псевдослучайной последовательности максимальной длины, содержащей 2n-1 символов, преобразовании потока данных исходного текста в закодированное сообщение и передаче его по линии связи, согласно изобретению псевдослучайную последовательность формируют как псевдослучайную последовательность символов конечного поля Fp с характеристикой р=257 в виде двоичных векторов длиною 8 бит путем снятия информации с восьми различных разрядов регистра сдвига, дополнительно формируют в виде двоичных векторов перебирающую последовательность за счет возведения в степень порождающего элемента в конечном поле Fp, разбивают поток данных на блоки-символы исходного текста в виде двоичных векторов длиною 8 бит, формируют суммарный символ исходного текста в виде двоичного вектора путем сложения в конечном поле Fр символа исходного текста со всеми предыдущими символами исходного текста и поочередно преобразуют двоичные векторы символов исходного текста путем умножения их на символы перебирающей последовательности и сложении в конечном поле Fр полученного результата с символами псевдослучайной последовательности, добавляют к преобразованному двоичному вектору исходного текста избыточный бит для проверки закодированного символа на четность, меняют порождающий элемент перебирающей последовательности при появлении в ее составе символа 1 на символ суммарного исходного текста, кодируют новый пораждающий элемент и передают по линии связи.
В совокупности признаков заявляемого способа под двоичным вектором понимается сигнал в виде последовательности нулевых и единичных битов, соответствующей представлению числа в двоичной системе исчисления.
Перечисленная совокупность существенных признаков исключает возможность определения ключей защиты при использовании метода криптоанализа с известным открытым текстом и повышает стойкость кода к атакам на основе известных и подобранных исходных текстов. В этом случае сформированная псевдослучайная последовательность символов в виде двоичных векторов длиною 8 бит является псевдослучайной последовательностью символов {0, 1, 2, ..., 255} конечного поля F257, имеет тот же период N=2n-1, что и псевдослучайные последовательности двоичных чисел, и обеспечивает статистическую равномерность использованных символов. Сформированная перебирающая последовательность является последовательностью символов мультипликативной группы конечного поля F257{1, 2, ..., 255}. Использование двух последовательностей позволяет формировать в поле F257 функцию для кодирования символа исходного текста α, включающую операцию умножение по модулю р символа исходного текста на символ перебирающей последовательности и операцию сложения по модулю р полученного результата с символом псевдослучайной последовательности.
Поскольку символы перебирающей последовательности х являются элементами мультипликативной группы конечного поля Fp, то могут быть вычислены обратные величины
x-1≡xp-2(mod p),
а для символов псевдослучайной последовательности у, которые составляют аддитивную группу конечного поля Fр, могут быть вычислены сопряженные элементы
y*=p-y,
которые позволяют реализовать обратные преобразования для декодирования символов исходного текста
(β+y*)x-1≡α(mod p).
Выбор в качестве характеристики конечного поля числа р=257 обусловлен тем, что для воспроизведения мультимедийных данных современные вычислительные машины используют 256 символов и ближайшим простым числом к числу 256 является 257.
Поскольку псевдослучайная последовательность символов конечного поля Fp снимается с восьми разрядов регистра сдвига, то не воспроизводится один символ конечного поля Fp, так как максимальное число, представленное 8 двоичными разрядами, составляет 255, поэтому снимаемые псевдослучайные последовательности не являются псевдослучайными последовательностями максимальной длины в конечном поле Fp, а представляют нелинейные псевдослучайные последовательности. Общее число возможных псевдослучайных последовательностей символов конечного поля будет определяться числом возможных комбинаций из восьми разрядов регистра сдвига, с которых может сниматься информация, и числом перестановок в рамках одной комбинации, каждая из которых определяет порядок считывания информации, и для регистра сдвига, состоящего из n=256 разрядов, число различных псевдослучайных последовательностей символов конечного поля F257 будет составлять Q=8!C256 8≈1019, в то время как для поля F2, с каких бы точек регистра сдвига не снимали бы информацию, псевдослучайная последовательность двоичных чисел будет лишь циклически сдвинутой относительно других псевдослучайных последовательностей двоичных чисел, снимаемых с других разрядов регистра сдвига.
Так как в криптографических преобразованиях используются две последовательности символов конечного поля F257, то при наличии сколь угодно символов исходного и им соответствующих символов шифрованного текста исключается возможность определения символов псевдослучайной последовательности, так как для ее определения число уравнений всегда будет в два раза меньше числа неизвестных. При этом обеспечивается стойкость кода к атакам на основе известных и подобранных исходных текстов, так как вскрытие состояния регистра сдвига в этом случае может быть обеспечено только путем тотального перебора всего множества возможных состояний регистра сдвига. Поскольку стандарт США DES предусматривает использование регистра сдвига, имеющего 128 разрядов (длина ключа 128 бит), мощность множества возможных состояний регистра сдвига будет составлять 1038. Если вскрытие состояния регистра сдвига будет осуществляться с помощью ЭВМ, имеющей тактовую частоту 10 ГГц, то число операций, выполняемых этой ЭВМ в течение года, будет составлять 3•1019, а время вскрытия составляет 1018 лет.
В соответствии с Российским стандартом ГОСТ 28147-89 для регистра сдвига, имеющего 256 разрядов (длина ключа 256 бит), время вскрытия состояния регистра сдвига будет составлять 1057 лет.
Поскольку добавляют избыточный бит для проверки закодированного символа на четность, то на приемной стороне может быть обнаружена одиночная ошибка в переданном символе исходного текста.
Если одна ошибка будет обнаружена на интервале, соответствующем смене порождающих элементов перебирающей последовательности, то обнаруженная ошибка будет скорректирована. Для чего вычисляют расхождение r в суммарных символах переданного исходного текста С и вычисленного С0 на приемной стороне и корректируют искаженный символ α0 по формуле
α0+r = α(mod p),
где С-С0=r(mod p).
Помехоустойчивость способа может быть усилена, если кодируют и передают суммарный символ исходного текста через определенное число тактов работы регистра сдвига после смены порождающего элемента перебирающей последовательности и(или) добавляют несколько избыточных битов к закодированному двоичному вектору исходного текста.
Возможность обнаружения и корректировки символов исходного текста на приемной стороне приводит к повышению помехоустойчивости передаваемой информации.
Возможность технической реализации заявленного способа поясняется следующим образом. Формирование ключа защиты можно осуществить путем ввода пароля с клавиатуры или с магнитного носителя информации в генератор псевдослучайных чисел, получая на выходе ключ защиты необходимого размера.
Формирование псевдослучайной последовательности максимальной длины, содержащей 2n-1 символов, можно осуществлять путем использования линейного регистра сдвига, имеющего n разрядов, обратную связь которого определяют по виду выбранного примитивного полинома степени n. Нахождение примитивных полиномов степени n изложено в [4] на стр.74-75.
Формирование псевдослучайной последовательности символов конечного поля F257 в виде двоичных векторов длиною 8 бит можно осуществить путем снятия информации с восьми различных разрядов регистра сдвига, номера которых могут быть определены по значению вводимого ключа защиты К. Например, путем определения порождающего элемента
l0≡K(mod q),
если l0<2, то l0=2,
и вычисления номера разряда регистра сдвига по формуле
Значение q выбирается из простых чисел и для регистра сдвига, имеющего 256 разрядов, q= 257, для регистра сдвига, имеющего 128 разрядов, q=127. В этом случае за счет возведения в степень порождающего числа l0 мы будем переходить от одного элемента поля Fq к другому. При этом, как показано в [4] стр.44, если l0 - элемент порядка k, то все элементы l0, l0 2, l0 3, ..., l0 k-1 будут различны.
Формирование псевдослучайной последовательности символов конечного поля Fp можно осуществить также по типу "сжимающего генератора" путем снятия информации с восьми разрядов регистра сдвига и пропуска тех тактов работы регистра сдвига, для которых символы псевдослучайной последовательности принимают значение "0" или совпадают с символами перебирающей последовательности.
Формирование символов х перебирающей последовательности в виде двоичных векторов на каждом такте работы регистра сдвига можно определить как порожденные элементы поля Fp путем умножения предыдущего символа этой последовательности на порождающий элемент xn
x≡x•xn(mod p).
Если в процессе вычислений на каком-то i такте работы регистра сдвига окажется, что х=1, то в этом случае меняется порождающий элемент xn поля Fp. При этом в качестве нового порождающего элемента xn принимается элемент, сформированный на данном такте работы регистра сдвига суммарный символ исходного текста С конечного поля Fp, xn=С, если С<2, то xn=2. Сформированные последовательности конечного поля Fp используют в криптографических преобразованиях при преобразовании потока данных в закодированное сообщение
α•x+y≡β(mod p).
Поскольку в перебирающей последовательности конечного поля элементы формируются за счет возведения в степень порождающего элемента xn, имеющего порядок k, то все элементы xn, xn 2, xn 3, ..., xn k будут различны на интервале k тактов работы регистра сдвига. Поскольку порождающие элементы xn могут быть разного порядка в конечном поле Fp, то смена порождающих элементов будет осуществляться по псевдослучайному закону. При этом обеспечивается статистическая равномерность символов закодированного текста на интервале, равном р-1 тактам работы регистра сдвига, что исключает применение статистических методов криптоанализа для определения состояния регистра сдвига.
Могут быть использованы еще три варианта формирования псевдослучайных последовательностей символов конечного поля в виде двоичных векторов.
1. Формируют дополнительный ключ защиты и для каждого сеанса связи генерируют случайный двоичный вектор длиною n бит и используют его для формирования начального порождающего элемента перебирающей последовательности, формируют двоичный вектор для начального заполнения регистра сдвига путем сложения по модулю два битов случайного двоичного вектора с битами основного ключа защиты, а дополнительный ключ защиты используют для кодирования и передачи на приемный конец радиолинии случайного двоичного вектора путем сложения их битов по модулю два.
В этом случае если и будет определено начальное состояние регистра сдвига, то для определения ключей защиты требуется знание случайного двоичного вектора, который выбирается для каждого сеанса связи случайным образом. Поскольку статистические методы криптоанализа в этом случае неприемлемы, то ключи защиты могут быть вскрыты только путем тотального перебора всего множества возможных ключей. При этом отпадает необходимость в назначении ключей защиты для новых сеансов связи и обеспечивается стойкость кода к атакам на вскрытие ключей защиты на основе определения состояния регистра сдвига при кодировании информации.
2. Изменяют номера разрядов регистра сдвига, с которых снимается информация для псевдослучайной последовательности символов конечного поля, в соответствии с изменением начального заполнения регистра сдвига.
3. Изменяют порядок считывания информации для псевдослучайной последовательности символов конечного поля в соответствии с изменением начального заполнения регистра сдвига.
Формирование псевдослучайной последовательности символов конечного поля по п. 2 и 3 повышает стойкость кода к атакам на основе известных и подобранных исходных текстов при формировании ключа защиты малой длины.
Преобразование потока данных в закодированное сообщение можно осуществить путем разбиения исходных данных на блоки в виде символов α двоичных векторов длиною 8 бит, вычисления в конечном поле Fp (р=257) значений символов β закодированного текста в соответствии с выбранной функцией кодирования, например α•x+y≡β(mod p), преобразования полученного числа β в двоичный вектор, добавления к нему избыточного бита и передачи его по линии связи.
Предлагаемый способ может быть реализован с помощью ЭВМ или устройства. На фиг.1 представлена структурная схема устройства, где
блок 1 - устройство формирования ключа защиты и исходного сигнала;
блок 2 - регистр сдвига;
блок 3 - формирователь перебирающей последовательности;
блок 4 - кодирующее устройство;
блок 5 - передающее устройство.
Для регистра сдвига на фиг.2 блоки 6-11 - разряды 1-6 регистра сдвига, а блок 12 - сумматор по модулю два.
Для простоты описания работы устройства будем пользоваться малыми числами. Будем считать, что регистр сдвига имеет 6 разрядов (длина ключа 6 бит), а весь алфавит исходного текста содержит 16 символов, тогда для передачи одного символа может быть использован двоичный вектор длиною 4 бита, а в качестве характеристики конечного поля Fp может быть выбрано число р=17.
Для определения структуры регистра сдвига выбирают примитивный многочлен шестой степени, например
λ6+λ5+1.
Для выбранного примитивного многочлена структурная схема регистра сдвига с обратной связью представлена на фиг.2.
Сформированный в блоке 1 фиг.1 с помощью генератора случайных чисел ключ защиты длиною 6 бит
<λ6, λ5, λ4, λ3, λ2, λ1>,
где 
поступает в регистр сдвига и используется для начального заполнения разрядов регистра сдвига. Двоичные символы с 5 и 6 разряда регистра сдвига поступают в каждом такте работы на вход сумматора 12 по модулю два, а с выхода сумматора по модулю два символы ε поступают на вход первого разряда регистра сдвига (блок 6, фиг.2). При этом состояния разрядов для каждого такта в процессе работы регистра сдвига определяются выражением
.
Если символы будут сниматься с шестого разряда λ6 регистра сдвига (блок 11, фиг. 2), то двоичная псевдослучайная последовательность максимального периода будет иметь вид
{1110000010000110001010011110100011
100100101101110110011010101111}.
Заметим, что на периоде этой последовательности любой ненулевой набор из шести знаков 0 и 1 встречается и только один раз.
Если двоичные числа будем снимать с 1, 2, 3 и 4 разряда регистра сдвига (блоки 6, 7, 8, 9, фиг.2) и на каждом такте работы регистра сдвига с набором <λ1, λ2, λ3, λ4> будем сопоставлять двоичный вектор (число) y = λ1+2λ2+22λ3+23λ4, то последовательность двоичных чисел в процессе работы регистра можно рассматривать как последовательность у чисел (символов) {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, ...}.
Анализ сформированной последовательности у показывает, что на интервале, соответствующем периоду, равному 63 тактам работы регистра сдвига, каждый из символов { 1, 2, ..., 15} встречается ровно четыре раза. Символ, соответствующий нулю встречается ровно три раза, при этом в последовательности y отсутствуют скрытые периодичности и обеспечивается статистическая равномерность используемых символов.
Сформированный в блоке 1 фиг.2 ключ защиты 1 1 1 0 0 0 вместе с сигналом исходного текста поступает в блок 3 фиг.1. В этом блоке формируют порождающий элемент xn путем приведения числа, соответствующего ключу защиты, в конечное множество поля F17
xn=23+24+25(mod 17)=5,
и вычисляют для каждого такта работы регистра сдвига элементы конечного поля F17
х=х xn(mod 17),
которые являются символами перебирающей последовательности:
х= 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6, а также вычисляют суммарные символы исходного текста
Ci+1=Ci+α(mod 17)
α= 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
С=7, 14, 4, 11, 1, 8, 15, 5, 12, 2, 9, 16, 6, 13, 3, 10 0, 7, 14, 4, 11.
Если символ перебирающей последовательности принимает значение "1", то изменяют порождающий элемент xn в соответствии со значением суммарного символа исходного текста. Для приведенного примера новый порождающий элемент равен "10". Этот элемент кодируют в устройстве 4 фиг.1 и передают с использованием устройства 5 фиг.1 на приемный конец радиолинии.
Сформированные последовательности символов конечного поля х и у в виде двоичных векторов поступают в кодирующее устройство 4 фиг.1, где преобразуют поступающий поток данных α в закодированное сообщение β в соответствии с выбранным криптографическим преобразованием в конечном поле F17, например
α=7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
х= 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6,
у=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.
Для полученных значений β формируют двоичный вектор и добавляют к нему избыточный бит для проверки на четность и передают с помощью устройства 5 фиг.1 на приемный конец радиолинии.
На приемном конце радиолинии осуществляют декодирование принятой последовательности символов β в соответствии с установленным криптографическим преобразованием в конечном поле F17, например
β= 9, 5, 8, 7, 15, 1, 10, 10, 0, 15, 15, 6, 12, 4, 0, 12, 12, 7, 5, 14, 5,
у*= 9, 0, 0, 16, 15, 13, 9, 0, 16, 14, 11, 5, 9, 16, 15, 12, 7, 13, 8, 14, 10,
x-1= 5, 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,
проверяют на четность двоичные вектора символов закодированного сообщения и при обнаружении ошибки корректируют искаженный символ (например, если исказился третий символ последовательности и вместо символа "7" принят символ "5", тогда вычисленный суммарный символ исходного текста на 16 такте работы регистра сдвига будет равен 8 и отличаться от переданного суммарного символа исходного текста на 2).
Реализация предлагаемого способа не вызывает затруднений, так как все блоки и узлы, входящие в устройство, реализующее способ, общеизвестны и широко описаны в технической литературе.
Источники информации
1. Российский стандарт шифрования стандарт СССР ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.
2. С. Мафтик. Механизмы защиты в сетях ЭВМ, М., 1993 г.
3. В.И. Нечаев. Элементы криптографии. Основы теории защиты информации, М.: Высшая школа, 1999 г.
4. Б.Н. Воронков, В.И. Тупота. Методическое пособие по разработке средств защиты информации в вычислительных сетях, Воронеж, Воронежский Государственный Университет, 2000.4
Изобретение относится к области электросвязи и вычислительной техники. Технический результат заключается в повышении стойкости кода к атакам на основе известных и подобранных текстов, а также повышении помехоустойчивости передаваемой информации. Сущность изобретения заключается в формировании ключа защиты в виде двоичного вектора длиной n бит, подаче его для начального заполнения регистра сдвига, вырабатывающего псевдослучайную последовательность максимальной длины, формировании псевдослучайной последовательности символов, преобразовании потока данных в закодированное сообщение и передаче его по линии связи. 5 з.п. ф-лы, 2 ил.
| СПОСОБ ШИФРОВАНИЯ ДВОИЧНОЙ ИНФОРМАЦИИ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ | 1993 |
|
RU2091983C1 |
| WO 00/77972 А1, 09.06.2000 | |||
| US 4641128 А1, 02.03.1987 | |||
| US 4316055 A1, 16.02.1982. | |||
