Способ шифрования блока данных, представленного в виде битовой строки

Способ шифрования блока данных, представленного в виде битовой строки

Реферат

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

Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно, в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования RC5 [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, рр. 344-346]. Способ включает в себя формирование секретного ключа в виде совокупности подключей, разбиение n-битового двоичного блока информации на n/2-битовые информационные подблоки A и B и поочередное преобразование данных подблоков. Подблоки преобразуются путем последовательного выполнения над ними линейных и нелинейных операций, в качестве которых используются операции суммирования по модулю 2^m, где m=n/2=8, 16, 32, 64, поразрядного суммирования по модулю 2 и циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока. Последнее свойство является характерным для способа RC5 и определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Подблок информации, например подблок B, преобразуют путем наложения подблока A на подблок B с помощью операции поразрядного суммирования по модулю 2 B:=B⊕A. После этого над подблоком B выполняют операцию циклического сдвига влево на число бит, равное значению подблока A:B:=B<<<A. Затем над подблоком B и одним из подключей K выполняют операцию суммирования по модулю 2^m, где m - длина подблока в битах: B:=(B+K)mod 2^m. После этого аналогичным образом преобразуется подблок A. В зависимости от размеров ключа выполняется несколько таких итераций преобразования обоих подблоков. Данный способ обеспечивает достаточно высокую скорость шифрования при программной реализации. Недостатком способа шифрования RC5 является невысокая стойкость к дифференциальному и линейному видам криптоанализа [Kaliski B.S., Yin Y.L. On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm. Advances in Cryptology - CRYPTO 95. Proceedings, Springer-Verlag, 1995, pp. 171-184].

Известен способ шифрования n-битовых блоков данных [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, pp. 193-194] путем генерации секретного ключа K, разбиения сообщения M на n-битовые блоки данных M₁, M₂, …, M_k где k - число блоков в сообщении; n≥64 бит, и последующего шифрования блоков данных M₁, M₂, …, M_k, причем процесс шифрования выполняют следующим путем. Шифруют блок M₁ по секретному ключу, получая блок криптограммы C₁, затем, начиная со значения i=2 и до значения i=k, суммируют с помощью операции поразрядного суммирования блок криптограммы C_i-1 и блок M_i, полученный в результате суммирования блок данных, шифруют по секретному ключу, получая в результате текущий блок криптограммы C_i. Совокупность блоков криптограммы C₁, C₂, …, C_k представляет собой криптограмму, содержащую сообщение в скрытом виде. Извлечение сообщения из криптограммы практически возможно только с использованием секретного ключа, использованного при шифровании, за счет чего достигается защита информации, содержащейся в сообщении при его передачи по открытым каналам связи. Данный способ обеспечивает улучшение статистических свойств криптограммы, однако он имеет недостаток, состоящий в том, что теряется возможность независимого расшифрования отдельных блоков криптограммы.

Наиболее близким по своей технической сущности к заявляемому способу шифрования блока данных M, представленного в виде n-битовой строки, является способ, описанный в патенте №2459275 [Молдовян А.А., Молдовян Н.А. Способ блочного шифрования сообщения M, представленного в двоичном виде. Патент №2459275] по п. 2 формулы изобретения указанного патента. Способ-прототип включает в себя формирование секретного ключа, включающего подключи K и Q, формирование вспомогательного n-битового блока двоичных данных T, формирование n-битовой вспомогательной криптограммы C_M путем выполнения над M операции блочного шифрования E в зависимости от K по формуле C_M=E_K(M), формирование n-битовой вспомогательной криптограммы C_T путем выполнения над T операции блочного шифрования E в зависимости от Q по формуле C_T=E_Q(T), формирование криптограммы C в зависимости от секретного ключа и вспомогательных криптограмм C_M и C_T.

Способ-прототип позволяет реализовать защиту информации с использованием механизма обманных ловушек, который состоит в том, что потенциальному злоумышленнику подставляется часть секретного ключа, включающая подключ Q, в качестве ключа расшифрования, а в качестве вспомогательного n-битового блока двоичных данных T используется n-битовый блок фиктивного сообщения. Блок криптограммы C расшифровывается путем его преобразования по дополнительному ключу, приводящего к получению вспомогательной криптограммы C*, представляющей собой конкатенациию двух n-битовых строк C_M и C T : C ∗ = C M ‖ C T . Затем правая n-битовая строка C_T расшифровывается путем выполнения операции блочного преобразования D, обратной к операции блочного шифрования E, т.е. по формуле T=D_Q(C_T). Аналогичная процедура расшифрования выполняется с использованием подключа K и левой n-битовой строки C_M вспомогательной криптограммы C ∗ = C M ‖ C T , а именно данных М, восстанавливается по формуле M=D_K(C_M). Недостатком способа прототипа является то, что различные части вспомогательной криптограммы C* используются при расшифровании блока данных M и блока фиктивного сообщения T. Это демаскирует факт наличия в блоке криптограммы C блока данных M.

Задачей, на решение которой направлено заявляемое техническое решение, является разработка способа шифрования блока данных M, представленного в виде n-битовой строки, обеспечивающего эффективную маскировку факта наличия n-битового блока данных M в 2n-битовом блоке криптограммы C за счет формирования n-битовой вспомогательной криптограммы и использования всех ее битов при выполнении процедур расшифрования как n-битового блока данных M, так и вспомогательной n-битовой строки T.

Техническим результатом нового способа шифрования блока данных, представленного в виде битовой строки, является повышение уровня защищенности информации, шифруемой с его применением. Данный технический результат достигается тем, что в способе шифрования блока данных M, представленного в виде n-битовой строки, заключающемся в формировании секретного ключа в виде подключей K и Q, представляющих собой битовые строки, формировании вспомогательной n-битовой строки T, формировании n-битовой вспомогательной криптограммы C_M путем выполнения над блоком данных M операции блочного шифрования E в зависимости от K по формуле C_M=E_K(M), формировании n-битовой вспомогательной криптограммы C_T путем выполнения над n-битовой строкой T операции блочного шифрования E в зависимости от Q по формуле C_T=E_Q(T), формировании 2n-битовой криптограммы C в зависимости от подключей K и Q и вспомогательных криптограмм C_M и C_T,

новым является то, что подключ K формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-битовых строк k₁ и k₂, подключ Q формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-битовых строк q₁ и q₂, формируют (n+1)-битовую строку m и формируют 2n-битовую криптограмму C в виде конкатенации двух двоичных многочленов степени n-1, являющихся решением системы из двух линейных уравнений k₁C₁+k₂C₂=C_M mod m и q₁C₁+q₂C₂=C_T mod m с двумя неизвестными двоичными многочленами C₁ и C₂, в которой m есть дополнительно сформированный многочлен степени n, а n-битовые строки k₁, k₂, q₁, q₂, C_M, C_T рассматриваются как двоичные многочлены степени n-1 и (n+1)-битовая строка m рассматривается как двоичный многочлен степени n.

Новым также является то, что формируют (n+1)-битовую строку m в виде неприводимого двоичного многочлена степени n.

Формирование (n+1)-битовой строки m в виде неприводимого двоичного многочлена степени n снижает сложность вычисления решения системы линейных уравнений, за счет чего уменьшается время, необходимое для шифрования блока данных M, представленного в виде n-битовой строки.

Благодаря указанной новой совокупности существенных признаков за счет формирования n-битовых вспомогательных криптограмм C_M и C_T обеспечивается использование всех битов вспомогательной криптограммы при выполнении процедуры расшифрования как блока данных M, так и вспомогательной n-битовой строки T, в качестве которой может быть применен n-битовой блок фиктивного сообщения. Это обеспечивает эффективную маскировку факта наличия n-битового блока данных M в 2n-битовом блоке криптограммы C при ее расшифровании потенциальным нарушителем при использовании им элементов ключа Q и m₂ в качестве ключа расшифрования, поскольку процедура расшифрования выполняется по одной и той же формуле при расшифровании блока данных M и блока фиктивного сообщения T.

Корректность заявленного способа шифрования блока данных M, представленного в виде n-битовой строки, состоит в том, что по 2n-битовой криптограмме C = C 1 ‖ C 2 может быть восстановлен n-битовый блока данных M по подключу K = k 1 ‖ k 2 по формуле M=D_K((k₁C₁+k₂C₂)mod m), где D - операция блочного расшифрования, обратная операции блочного шифрования E, и вспомогательная n-битовая строка T по подключу Q = q 1 ‖ q 2 по формуле T=D_Q((q₁C₁+q₂C₂)mod m).

Действительно, при выполнении процедуры расшифрования по подключу K = k 1 ‖ k 2 имеем

.

а при выполнении процедуры расшифрования по подключу Q = q 1 ‖ q 2 имеем

.

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

Пример 1. Шифрование блока данных M, представленного в виде 65-битовой строки. Формируют секретный ключ в виде подключей K и Q, причем подключ K формируют в виде 130-битовой строки, представляющей собой конкатенацию двух 65-битовых строк k₁ и k₂, т.е. K=(k₁, k₂), а подключ Q формируют в виде 130-битовой строки, представляющей собой конкатенацию двух 65-битовых строк q₁ и q₂, т.е. Q=(q₁, q₂). Формируют 66-битовую строку представляющую собой последовательность коэффициентов неприводимого двоичного многочлена степени 65, т.е. двоичного многочлена x⁶⁵+x¹⁸+1 [см. таблицу неприводимых двоичных многочленов на с. 209 в книге Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига, 2006. - 280 с.]. Затем формируют вспомогательную 65-битовую строку T и 65-битовую вспомогательную криптограмму C_M путем выполнения над блоком данных M операции блочного шифрования E в зависимости от подключа K=(k₁, k₂) по формуле C_M=E_K(M), где операция блочного шифрования описывается следующим алгоритмом:

1. Установить значение счетчика i←1 и переменной C_M←M, где знак ← обозначает операцию присваивания.

2. Рассматривая 65-битовые строки k₁ и M как двоичные многочлены, сформировать 65-битовую строку C_M, представляющую собой последовательность коэффициентов двоичного многочлена, вычисленного по формуле C_M←(k₁C_M mod m)^<23<, где (…)^<23< обозначает операцию циклического сдвига битовой строки (…) на 23 бита влево.

3. Рассматривая 65-битовую строку k₂, преобразовать 65-битовую строку C_M по формуле C_M←(k₂C_M mod m)^<17<, где (…)^<17< обозначает операцию циклического сдвига битовой строки (…) на 17 бит влево.

4. Прирастить значение счетчика i: i←i+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение C_M взять в качестве выходного значения операции блочного шифрования E_K, выполненной над 65-битовым блоком данных M.

Затем формируют 65-битовую вспомогательную криптограмму C_T путем выполнения над 65-битовой строкой T операции блочного шифрования E в зависимости от подключа Q=(q₁, q₂) по формуле C_T=E_Q(T) в соответствии со следующим алгоритмом:

1. Установить значение счетчика i←1 и переменной C_T←T.

2. Рассматривая 65-битовые строки k₂ и T как двоичные многочлены, сформировать 65-битовую строку C_T, представляющую собой последовательность коэффициентов двоичного многочлена, вычисленного по формуле C_T←(q₁C_T mod m)^<23<.

3. Преобразовать 65-битовую строку C_T по формуле C_T←(q₂C_T mod m)^<17<.

4. Прирастить значение счетчика i: i←+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение C_M взять в качестве выходного значения операции блочного шифрования E_Q(T), выполненной над 65-битовой строкой T.

После формирования вспомогательных криптограмм C_M и C_T в виде двоичных многочленов, представленных в виде 65-битовых строк, формируют 130-битовую криптограмму C путем решения следующей системы из двух линейных уравнений

.

Решением данной системы являются два двоичных многочлена C₁ и C₂, представленных в виде 65-битовых строк. Объединяя 65-битовые строки C₁ и C₂, получают 130-битовую криптограмму C = C 1 ‖ C 2 , где знак ║ обозначает операцию конкатенации (объединения) битовых строк.

Доказательство корректности данного частного варианта заявленного способа шифрования блока данных M, представленного в виде 65-битовой строки, доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что операция блочного расшифрования D_K(C_M), обратная операции блочного шифрования E_K(M), реализуется следующей процедурой преобразования:

1. Установить значение счетчика i←1 и переменной M←C_M.

2. Преобразовать 65-битовую строку М, выполняя последовательно вычисления по формулам M←M^>17> и M ← M k 2 − 1 mod   m , где (…)^>17>, обозначает операцию циклического сдвига битовой строки (…) на 17 бит вправо.

3. Преобразовать 65-битовую строку М, выполняя последовательно вычисления по формулам M←M^>23> и M ← M k 1 − 1 mod   m , где (…)^>23>, обозначает операцию циклического сдвига битовой строки (…) на 23 бита вправо.

4. Прирастить значение счетчика i: i←i+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение M взять в качестве выходного значения операции D_K, выполненной над 65-битовым блоком данных C_M.

Аналогично записывается процедура для реализации операции блочного расшифрования D_Q(C_T), обратная операции блочного шифрования E_Q(T).

Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрование двух сообщений M и T, каждое из которых, например, имеет размер 65 Кбит. Сообщение M разбивается на 65-битовые блоки данных M₁, M₂, …, M_w, где w=1000. Сообщение T разбивается на на 65-битовые блоки данных T₁, T₂, …, T_w. Поочередно для значений i=1, 2, …, 1000 пары блоков данных (M_i, T_i,) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 130-битовых криптограмм ( C 1 ‖ C 2 ) i , i=1, 2, …, 1000.

Пример 2. Шифрование блока данных M, представленного в виде 52-битовой строки. Формируют секретный ключ в виде подключей K и Q, причем подключ K формируют в виде 104-битовой строки, представляющей собой конкатенацию двух 52-битовых строк k₁ и k₂, т.е. K=(k₁, k₂), а подключ Q формируют в виде 104-битовой строки, представляющей собой конкатенацию двух 52-битовых строк q₁ и q₂, т.е. Q=(q₁, q₂). Формируют 53-битовую строку

представляющую собой последовательность коэффициентов неприводимого двоичного многочлена степени 52, т.е. двоичного многочлена x⁵³+x³+1 [см. таблицу неприводимых двоичных многочленов на с. 209 в книге Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига, 2006. - 280 с.]. Затем формируют вспомогательную 52-битовую строку T и 52-битовую вспомогательную криптограмму C_M путем выполнения над блоком данных M операции блочного шифрования E в зависимости от подключа K=(k₁, k₂) по формуле C_M=E_K(M), где операция блочного шифрования описывается следующим алгоритмом:

1. Установить значение счетчика i←1 и переменной C_M←M, где знак ← обозначает операцию присваивания.

2. Рассматривая 52-битовые строки k₁ и M как двоичные многочлены, сформировать 52-битовую строку C_M, представляющую собой последовательность коэффициентов двоичного многочлена, вычисленного по формуле C_M←(k₁C_M mod m)^<19<, где (…)^<19<, обозначает операцию циклического сдвига битовой строки (…) на 19 бит влево.

3. Рассматривая 52-битовую строку k₂, преобразовать 65-битовую строку C_M по формуле C_M←(k₂C_M mod m)^<11<, где (…)^<11< обозначает операцию циклического сдвига битовой строки (…) на 11 бит влево.

4. Прирастить значение счетчика i: i←i+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение C_M взять в качестве выходного значения операции блочного шифрования E_K, выполненной над 52-битовым блоком данных M.

Затем формируют 52-битовую вспомогательную криптограмму C_T путем выполнения над 52-битовой строкой T операции блочного шифрования E в зависимости от подключа Q=(q₁, q₂) по формуле C_T=E_Q(T) в соответствии со следующим алгоритмом:

1. Установить значение счетчика i←1 и переменной C_T←T.

2. Сформировать 52-битовую строку C_T, представляющую собой последовательность коэффициентов двоичного многочлена, вычисленного по формуле C_T←(q₁C_T mod m)^<19<.

3. Преобразовать 52-битовую строку C_T по формуле C_T←(q₂C_T mod m)^<11<.

4. Прирастить значение счетчика i: i←i+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение C_M взять в качестве выходного значения операции блочного шифрования E_Q(T), выполненной над 65-битовой строкой T.

После формирования вспомогательных криптограмм C_M и C_T в виде двоичных многочленов, представленных в виде 52-битовых строк, формируют 130-битовую криптограмму C путем решения следующей системы из двух линейных уравнений.

Решением данной системы являются два двоичных многочлена C₁ и C₂, представленных в виде 52-битовых строк. Объединяя 52-битовые строки C₁ и C₂, получают 104-битовую криптограмму C = C 1 ‖ C 2 , где знак ║ обозначает операцию конкатенации (объединения) битовых строк.

Доказательство корректность данного частного варианта заявленного способа шифрования блока данных M, представленного в виде 52-битовой строки, доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что операция блочного расшифрования D_K(C_M), обратная операции блочного шифрования E_K(M), реализуется следующей процедурой преобразования:

1. Установить значение счетчика i←1 и переменной M←C_M.

2. Преобразовать 52-битовую строку M, выполняя последовательно вычисления по формулам M←M^>11> и M ← M k 2 − 1 mod   m , где (…)^>11> обозначает операцию циклического сдвига битовой строки (…) на 11 бит влево.

3. Преобразовать 52-битовую строку M, выполняя последовательно вычисления по формулам M←M^>19> и M ← M k 1 − 1 mod   m , где (…)^>19> обозначает операцию циклического сдвига битовой строки (…) на 19 бит влево.

4. Прирастить значение счетчика i: i←i+1. Если i<10, то перейти к шагу 2, в противном случае текущее значение M взять в качестве выходного значения операции D_K, выполненной над 65-битовым блоком данных C_M.

Аналогично записывается процедура для реализации операции блочного расшифрования D_Q(C_T), обратная операции блочного шифрования E_Q(T).

Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрование двух сообщений M и T, каждое из которых, например, имеет размер 520 кбит. Сообщение M разбивается на 52-битовые блоки данных M₁, M₂, …, M_w, где w=10000. Сообщение T разбивается на 52-битовые блоки данных T₁, T₂, …, T_w. Поочередно для значений i=1, 2, …, 10000 пары 52-битовых блоков данных (M_i, T_i) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 130-битовых криптограмм ( C 1 ‖ C 2 ) i , i=1, 2, …, 1000.

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

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

Толкование терминов, используемых в описании изобретения

1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.

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

3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например, число 10011 является 5-разрядным.

4. Битовая строка (БС) - двоичный цифровой электромагнитный сигнал, представляемый в виде конечной последовательности цифр «0» и «1».

5. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».

6. Многоразрядное двоичное число (МДЧ) - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».

7. Многочлен - это упорядоченная последовательность коэффициентов, каждый из которых является одноразрядным или многоразрядным двоичным числом (МДЧ). Над многочленами определены операции сложения многочленов и умножения многочленов, которые сводятся к выполнению действий с коэффициентами многочленов, являющихся операндами. Многочлены и правила действия над ними подробно рассмотрены в книгах [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.]. В вычислительных устройствах многочлены представляются в виде битовой строки, в которой каждый бит или каждая подстрока битов фиксированной длины интерпретируется как один из коэффициентов многочлена, над которыми определены операции сложения и умножения коэффициентов.

8. Двоичный многочлен - это многочлен, коэффициентами которого являются одноразрядными двоичными числами «0» и «1». Двоичный многочлен записывается в виде битовой строки, старший разряд которой равен единичному биту. Степенью многочлена является значение S, равное длине битовой строки, представляющей двоичный многочлен минус единица. В алгебраической форме двоичный многочлен записывается в виде суммы некоторых степеней s_i<S формальной переменной x, например в виде x S + x s 1 + x s 2 + x s 3 + 1 . В алгебраической форме указываются только слагаемые с ненулевыми коэффициентами, так как позиция коэффициента связана однозначно со степенью формальной переменной, при которой он записан.

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

10. Сравнимыми по модулю некоторого многочлена m называются многочлены, разность которых делится на многочлен m без остатка или, что то же самое, многочлены, при делении которых на многочлен m получаются равные остатки.

11. Операция умножения двух многочленов по модулю (по mod) многочлена m выполняется как обычное алгебраическое умножение многочленов с последующим взятием остатка от деления полученного результата на многочлен m.

12. Операция сложения двух многочленов выполняется как сложение всех коэффициентов при одинаковых степенях формальной переменной, как элементов поля, которому принадлежат коэффициенты многочленов (это поле называется полем, над которым заданы многочлены).

13. Алгебраическая структура - это множество математических элементов, некоторой природы. В качестве математических элементов могут выступать, например, многочлены, МДЧ, пары МДЧ, пары многочленов, тройки МДЧ, тройки многочленов, матрицы МДЧ, матрицы многочленов и т.д., над которыми заданы математические действия (операции). Математически алгебраическая структура определяется путем задания конкретного множества математических элементов и одной или нескольких операций, выполняемых над элементами.

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

15. Группа - это алгебраическая структура (т.е. множество элементов различной природы), над элементами которой определена одна операция, и которая при заданной операции обладает заданным набором свойств: операция ассоциативна, результатом выполнения операции над двумя элементами является также элемент этой же структуры, существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Детальное описание групп дано в книгах [А.Г. Курош. Теория групп. - М., изд-во «Наука», 1967. - 648 с.] и [М.И. Каргаполов, Ю.И. Мерзляков. Основы теории групп. - М., изд-во «Наука. Физматлит», 1996. - 287 с.]. Операция, определенная над элементами группы, называется групповой операцией.

16. Кольцо - это алгебраическая структура (т.е. множество математических элементов природы), над элементами которой определены две операции, одна из которых называется сложением, а вторая - умножением. При этом при заданных операциях эта алгебраическая структура обладает заданным набором свойств: операции сложения и умножения ассоциативны и коммутативны, операция умножения является дистрибутивной относительно операции сложения, а результатом выполнения каждой из этих операций над двумя элементами является также элемент этой же структуры. Кроме того, для сложения существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Нейтральный элемент относительно сложения называется нулевым элементом (или просто нулем). Детальное описание колец дано в книгах [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.].

17. Поле - это алгебраическая структура (т.е. множество математических элементов различной природы), над элементами которой определены две операции, одна из которых называется сложением, а вторая - умножением. При этом при заданных операциях эта алгебраическая структура обладает заданным набором свойств: операции сложения и умножения ассоциативны и коммутативны, операция умножения является дистрибутивной относительно операции сложения, а результатом выполнения каждой из этих операций над двумя элементами является также элемент этой же структуры. Причем для каждой из указанных двух операций существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Нейтральный элемент относительно сложения называется нулевым элементом (или просто нулем), а нейтральный элемент относительно умножения называется единичным элементом (или просто единицей). Кроме того, каждому ненулевому элементу а может быть сопоставлен в соответствие единственный элемент а ^-1, называемый обратным элементом по отношению к данному элементу, такой, что произведение a ^-1 a (а значит и aa ^-1) равно единице. Детальное описание полей дано в книгах [А.И. Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.].

18. Операция деления двоичного многочлена A на двоичный многочлен B по модулю двоичного многочлена m выполняется как операция умножения по модулю m двоичного многочлена A на двоичный многочлен B^-1, который является обратным к двоичному многочлену B по модулю двоичного многочлена m.

19. Совокупность всех двоичных многочленов степени, которая не превосходит значения S, вместе с операцией сложения и умножения по модулю неприводимого многочлена степени S+1 образует поле GF(2^S) с числом элементов, равным 2^S. В таком поле, также как и в других полях, системы, включающие два линейно независимых уравнения с двумя неизвестными, имеют единственное решение.

1. Способ шифрования блока данных, представленного в виде битовой строки, заключающийся в формировании секретного ключа в виде подключей K и Q, представляющих собой битовые строки, формировании вспомогательной n-битовой строки T, формировании n-битовой вспомогательной криптограммы C_M путем выполнения над блоком данных M операции блочного шифрования E в зависимости от K по формуле C_M=E_K(M), формировании n-битовой вспомогательной криптограммы C_T путем выполнения над n-битовой строкой T операции блочного шифрования E в зависимости от Q по формуле C_T=E_Q(T), формировании 2n-битовой криптограммы C в зависимости от подключей K и Q и вспомогательных криптограмм C_M и C_T, отличающийся тем, что подключ K формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-битовых строк k₁ и k₂, подключ Q формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-битовых строк q₁ и q₂, формируют (n+1)-битовую строку m и формируют 2n-битовую криптограмму C в виде конкатенации двух двоичных многочленов степени n-1, являющихся решением системы из двух линейных уравнений k₁C₁+k₂C₂=C_M mod m и q₁C₁+q₂C₂=C_T mod m с двумя неизвестными двоичными многочленами C₁ и C₂, в которой m есть дополнительно сформированный многочлен степени n, а n-битовые строки k₁, k₂, q₁, q₂, C_M, C_T рассматриваются как двоичные многочлены степени n-1 и (n+1)-битовая строка m рассматривается как двоичный многочлен степени n.

2. Способ по п.1, отличающийся тем, что формируют (n+1)-битовую строку m в виде неприводимого двоичного многочлена степени n.