способ шлифования n-битового блока данных м

Формула изобретения

1. Способ шифрования n-битового блока данных М, заключающийся в формировании секретного ключа путем генерации подключей Q и R, формировании вспомогательного n-битового блока данных T, формировании n-битовой вспомогательной криптограммы C_M путем выполнения над М операции блочного шифрования Е в зависимости от Q по формуле C_M=E_Q(М), формировании n-битовой вспомогательной криптограммы C_Т путем выполнения над Т операции блочного шифрования Е в зависимости от R по формуле C_T=E _R(t), формировании криптограммы С в зависимости от секретного ключа и вспомогательных криптограмм C_M и C_T , отличающийся тем, что при формировании секретного ключа дополнительно генерируют вспомогательные подключи в виде взаимно простых многоразрядных двоичных чисел m₁ и m₂, а криптограмму С формируют в виде решения системы двух сравнений С C_Mmodm₁ и С C_Tmodm₂ с неизвестным С.

2. Способ по п.1, отличающийся тем, что, по крайней мере, одно из многоразрядных двоичных чисел m₁ и m₂ является простым.

Описание изобретения к патенту

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

Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно, в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования RC5 [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, 758 p.; см. C.344-346]. Способ включает в себя формирование секретного ключа в виде совокупности подключей, разбиение n-битового двоичного блока информации на n/2-битовые информационные подблоки А и В и поочередное преобразование этих подблоков. Подблоки преобразуются путем последовательного выполнения над ними линейных и нелинейных операций, в качестве которых используются операции суммирования по модулю 2^m, где m=n/2=8, 16, 32, 64, поразрядного суммирования по модулю 2 и циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока. Последнее свойство является характерным для способа RC5 и определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Подблок информации, например подблок В, преобразуют путем наложения подблока А на подблок В с помощью операции поразрядного суммирования по модулю 2 В:=В А. После этого над подблоком В выполняют операцию циклического сдвига влево на число бит, равное значению подблока А: В:=В А. Затем над подблоком В и одним из подключей К выполняют операцию суммирования по модулю 2^m, где m - длина подблока в битах: В:=(В+К)mod2^m. После этого аналогичным образом преобразуется подблок А. В зависимости от размеров ключа выполняется несколько таких итераций преобразования обоих подблоков. Данный способ обеспечивает достаточно высокую скорость шифрования при программной реализации. Недостатком способа шифрования 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. P.171-184].

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

Близким аналогом к заявляемому способу шифрования n-битового блока двоичных данных М является способ, описанный в патенте № 2459275 [Молдовян А.А., Молдовян Н.А. Способ блочного шифрования сообщения М, представленного в двоичном виде. Патент № 2459275. Опубл. 20.08.2012].

Наиболее близким по своей технической сущности к заявляемому способу шифрования n-битового блока двоичных данных М является частный вариант реализации способа по патенту № 2459275, приведенный в примере 1 описания этого патента. В указанном частном способе шифрование 64-битового блока данных M_i осуществляют, выполняя следующую последовательность действий:

1. Формируют секретный ключ путем генерации подключей K, Q (Q К) и R (R К; R Q), где Q и R - 64-битовые подключи; К - 128-битовый подключ.

2. Формируют вспомогательный 64-битовый блок данных T_i.

3. Шифруют 64-битовый блок данных M_i с помощью процедуры блочного шифрования Е по подключу Q, в результате чего получают блок данных E_Q(M _i), который представляет собой вспомогательную криптограмму C_M, т.е. на этом шаге осуществляется формирование 64-битовой вспомогательной криптограммы C_M=eq (M _i).

4. Шифруют вспомогательный 64-битовый блок данных T_i с помощью процедуры блочного шифрования Е по подключу R, в результате чего получают блок данных E _R(T_i), который представляет собой вспомогательную криптограмму C_T, т.е. на этом шаге осуществляется формирование 64-битовой вспомогательной криптограммы C_T =E_r(T_i).

5. Формируют 128-битовый блок данных B_i путем объединения вспомогательных криптограмм C_M и C_T (т.е. путем объединения преобразованных 64-битовых блоков M_i и T_i) в единый 128-битовый блок данных B_i=C_M||C_T=E _Q(M_i)||E_R(T_i).

6. Шифруют 128-битовый блок данных B_i с помощью процедуры блочного шифрования F по подключу К:

C_i =F_K(B_i)=F_K(E_Q(M _i)||E_R(T_i)).

Таким образом, способ-прототип включает в себя формирование секретного ключа, включающего подключи Q и R, формирование вспомогательного n-битового блока двоичных данных Т, формирование n-битовой вспомогательной криптограммы C_M путем выполнения над М операции блочного шифрования Е в зависимости от Q по формуле C_M=E _Q(M), формирование n-битовой вспомогательной криптограммы C_T путем выполнения над Т операции блочного шифрования Е в зависимости от R по формуле C_T=E_R(T), формирование криптограммы С в зависимости от секретного ключа и вспомогательных криптограмм C_M и C_T .

Способ-прототип позволяет реализовать защиту информации с использованием механизма обманных ловушек, который состоит в том, что потенциальному злоумышленнику подставляется часть секретного ключа, включающая подключ R, в качестве ключа расшифрования, а в качестве вспомогательного n-битового блока двоичных данных Т используется n-битовый блок фиктивного сообщения. Блок криптограммы С расшифровывается путем его преобразования по дополнительному ключу, приводящего к получению промежуточной 2n-битовой криптограммы С*, представляющей собой конкатенациию двух n-битовых вспомогательных криптограмм C_M и C _T: С*=C_M||C_T. Вспомогательные криптограммы C_M и C_T составляют правую и левую половины промежуточной 2n-битовой криптограммы С*. По подключу R выполняется расшифрование правой n-битовой вспомогательной криптограммы C _T путем выполнения операции блочного преобразования D, обратной к операции блочного шифрования Е, т.е. по формуле Т=D _R(C_T). Аналогичная процедура расшифрования выполняется с использованием подключа К и левой n-битовой строки C_M промежуточной 2n-битовой криптограммы С*=C_M||C _T. Недостатком способа прототипа является то, что различные части промежуточной 2n-битовой криптограммы С* используются при восстановлении блока данных М и блока фиктивного сообщения Т. Это демаскирует факт наличия в блоке криптограммы С блока данных М, что снижает уровень защищенности информации, шифруемой с использованием способа-прототипа.

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

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

Указанный технический результат достигается тем, что в способе шифрования n-битового блока данных М, заключающемся в формировании секретного ключа путем генерации подключей Q и R, формировании вспомогательного n-битового блока данных Т, формировании n-битовой вспомогательной криптограммы C_M путем выполнения над М операции блочного шифрования Е в зависимости от Q по формуле C_M=E _Q(М), формировании n-битовой вспомогательной криптограммы C_T путем выполнения над Т операции блочного шифрования Е в зависимости от R по формуле C_T=E_R(T), формировании криптограммы С в зависимости от секретного ключа и вспомогательных криптограмм C_M и C_T, кроме того, при формировании секретного ключа дополнительно генерируют вспомогательные подключи в виде взаимно простых многоразрядных двоичных чисел m₁ и m₂, а криптограмму С формируют в виде решения системы двух сравнений С C_M mod m₁ и С C_T mod m₂ с неизвестным С.

Новым также является то, что, по крайней мере, одно из многоразрядных двоичных чисел m₁ и m₂ является простым.

Использование простых чисел в качестве модулей системы сравнений упрощает процедуру формирования секретного ключа, поскольку устраняется необходимость выполнения алгоритма Евклида для проверки условия взаимной простоты МДЧ m₁ и m₂.

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

Корректность заявленного способа шифрования n-битового блока двоичных данных М состоит в том, что по криптограмме С может быть восстановлен n-битовый блок двоичных данных М по подключам Q и m₁ по формуле M=D_Q(C mod m₁), где D - операция блочного расшифрования, обратная операции блочного шифрования Е, и вспомогательный n-битовый блок данных Т по подключам R и m₂ по формуле Т=D_R (Cmodm₂).

Действительно, при выполнении процедуры расшифрования по подключам Q и m₁ имеем

,

а при выполнении процедуры расшифрования по подключам R и m₂ имеем

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

Пример 1. Шифрование 64-битового блока двоичных данных М (n=64). Формируют секретный ключ в виде подключей Q, R, m₁ и m₂, причем подключ Q формируют в виде 128-битовой строки, представляющей собой конкатенацию двух нечетных 64-разрядных двоичных чисел q₁ и q₂, т.е. Q=q₁ ||q₂, где знак || обозначает операцию конкатенации, подключ R формируют в виде 128-битовой строки, представляющей собой конкатенацию двух нечетных 64-битовых двоичных чисел r ₁ и r₂, т.е. R=r₁||r, подключи m ₁ и m₂ формируют в виде двух случайных 65-битовых двоичных чисел, удовлетворяющих условию взаимной простоты, т.е. их наибольший общий делитель равен единице. Затем формируют вспомогательный 64-битовый блок данных Т и 64-битовую вспомогательную криптограмму C_M путем выполнения над блоком данных М операции блочного шифрования Е в зависимости от подключа Q=q₁||q ₂ по формуле C_M=E_Q(M), где операция блочного шифрования описывается следующим алгоритмом:

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

2. Сформировать 64-битовую строку C_M в виде МДЧ, вычисленного по формуле C_M (q₁(C_M q₂)mod2⁶⁴)^<29<, где ( )^<29< обозначает операцию циклического сдвига битовой строки (...) на 29 бит влево; знак обозначает операцию поразрядного суммирования по модулю 2.

3. Преобразовать 64-битовую строку C_M по формуле C_M (q₂(C_M q₁)mod2⁶⁴)^<17<, где ( )^<17< обозначает операцию циклического сдвига битовой строки ( ) на 17 бит влево.

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

Затем формируют 64-битовую вспомогательную криптограмму C_T путем выполнения над вспомогательным 64-битовым блоком двоичных данных Т операции блочного шифрования Е в зависимости от подключа R=r₁ ||r₂ no формуле C_T=E_R(T) в соответствии со следующим алгоритмом:

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

2. Сформировать 64-битовую строку C _T в виде МДЧ, вычисленного по формуле C_T (r₁(C_T r₂)mod2⁶⁴)^<29<.

3. Преобразовать 64-битовую строку C_T по формуле C_T (r₂(C_T r₁)mod2⁶⁴)^<17<.

4. Прирастить значение счетчика i: i i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение C_T взять в качестве выходного значения операции блочного шифрования E_R, выполненной над вспомогательным 64-битовым блоком данных Т.

После формирования вспомогательных криптограмм C_M и C_T, рассматривая их как 64-битовые МДЧ, формируют криптограмму С в виде решения следующей системы из двух линейных сравнений с неизвестным значением С:

.

Поскольку m₁ и m₂ представляют собой 65-битовые взаимно простые числа, то m ₁>C_M; m₂>C_T и в соответствии с китайской теоремой об остатках указанная система имеет единственное решение С<m₁m₂. Данное решение берется в качестве криптограммы С и вычисляется по следующей формуле [Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. СПб., БХВ-Петербург, 2010. - 304 с.; см. С.15-16]:

.

Доказательство корректности данного частного варианта реализации заявленного способа шифрования n-битового блока двоичных данных М доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что для нечетных МДЧ q₁, q₂, r ₁, r₂ по модулю 2 существуют и легко вычисляются по расширенному алгоритму Евклида соответствующие обратные значения , , , , а операция блочного расшифрования D_Q(C _M), обратная операции блочного шифрования E_Q (M), реализуется следующей процедурой преобразования:

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

2. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М M^>17>, и M M q₁ , где ( )^>17> обозначает операцию циклического сдвига битовой строки ( ) на 17 бит вправо.

3. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М<-M ^>29>, M<-Mqmod 2 и M<-M+***q₂, где (...)^>29>обозначает операцию циклического сдвига битовой строки (...) на 29 бит вправо.

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

Аналогично записывается процедура для реализации операции блочного расшифрования D_R(C _T), обратная операции блочного шифрования E_R (Т).

Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрования двух сообщений Message и Text, каждое из которых, например, имеет размер 64 кбит. Сообщение Message разбивается на 64-битовые блоки данных M₁, M₂, , M_w, где w=1000. Сообщение Text разбивается на 64-битовые блоки данных Т₁, Т₂, , T_w. Поочередно для значений i=1, 2, , 1000 пары блоков данных (M_l, T_i ) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 128-битовых криптограмм (C₁ ||C₂)_i, i=1, 2, , 1000.

Пример 2. Шифрование 128-битового блока двоичных данных М (n=128). Формируют секретный ключ в виде подключей Q, R, m₁ и m₂, причем подключ Q формируют в виде 256-битовой строки, представляющей собой конкатенацию двух нечетных 128-разрядных двоичных чисел q₁ и q ₂, т.е. Q=q₁||q₂, где знак || обозначает операцию конкатенации, подключ R формируют в виде 256-битовой строки, представляющей собой конкатенацию двух нечетных 64-битовых двоичных чисел r₁ и r₂, т.е. R=r₁ ||r, подключи m₁ и m₂ формируют в виде двух случайных простых 129-битовых двоичных чисел, удовлетворяющих условию m₁ m₂ (в силу последнего условия m₁ и m₂ являются взаимно простыми МДЧ). Затем формируют вспомогательный 128-битовый блок данных Т и 128-битовую вспомогательную криптограмму C_M путем выполнения над блоком данных М операции блочного шифрования Е в зависимости от подключа Q=q ₁||q₂ по формуле C_M=E_Q (M), где операция блочного шифрования описывается следующим алгоритмом:

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

2. Сформировать 128-битовую строку C_M в виде МДЧ, вычисленного по формуле C_M (q₁(C_M q₂)mod2¹²⁸)^<80<, где ( )^<80< обозначает операцию циклического сдвига битовой строки ( ) на 80 бит влево.

3. Преобразовать 128-битовую строку C_M по формуле C_M (q₂(C_M q₁)mod2¹²⁸)^<40<, где ( )^<40< обозначает операцию циклического сдвига битовой строки ( ) на 40 бит влево.

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

Затем формируют 128-битовую вспомогательную криптограмму C_T путем выполнения над вспомогательным 128-битовым блоком двоичных данных Т операции блочного шифрования Е в зависимости от подключа R=r₁ ||r₂ по формуле C_T=E_R(T) в соответствии со следующим алгоритмом:

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

2. Сформировать 128-битовую строку C _T в виде МДЧ, вычисленного по формуле C_T (r₁(C_T r₂)mod2¹²⁸)^<80<.

3. Преобразовать 128-битовую строку C_T по формуле C_T (r₂(C_T r₁)mod2¹²⁸)^<40<.

4. Прирастить значение счетчика i: i i+1. Если i<20, то перейти к шагу 2, в противном случае текущее значение C_T взять в качестве выходного значения операции блочного шифрования E_R, выполненной над вспомогательным 128-битовым блоком данных Т.

После формирования вспомогательных криптограмм C_M и C_T, рассматривая их как 64-битовые МДЧ, формируют криптограмму С в виде решения следующей системы из двух линейных сравнений с неизвестным значением С:

Поскольку m₁ и m₂ (m₂ m₁) представляют собой 129-битовые простые числа, то m₁>C_M, m₂>C_T и в соответствии с китайской теоремой об остатках указанная система имеет единственное решение С<m₁m₂ . Данное решение берется в качестве криптограммы С и вычисляется по следующей формуле

Доказательство корректности данного частного варианта реализации заявленного способа шифрования n-битового блока двоичных данных М доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что для нечетных МДЧ q₁, q₂, r ₁, r₂ по модулю 2 существуют и легко вычисляются по расширенному алгоритму Евклида соответствующие обратные значения , , , , а операция блочного расшифрования d_q(c _m), обратная операции блочного шифрования E_Q (M), реализуется следующей процедурой преобразования:

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

2. Преобразовать 128-битовую строку М, выполняя последовательно вычисления по формулам M M^<40< и М M *q₁ , где ( )^>40> обозначает операцию циклического сдвига битовой строки ( ) на 40 бит вправо.

3. Преобразовать 128-битовую строку М, выполняя последовательно вычисления по формулам М M^>80> и M M q₂, где ( )^>80> обозначает операцию циклического сдвига битовой строки ( ) на 80 бит вправо.

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

Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрования двух сообщений Message и Text, каждое из которых, например, имеет размер 128 кбайт. Сообщение Message разбивается на 128-битовые блоки данных М₁, M₂, , M_w, где w=8000. Сообщение Text разбивается на 128-битовые блоки данных Т₁, Т₂, , T_w. Поочередно для значений i=1, 2, , 8000 пары блоков данных (M_l, T_l ) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 256-битовых криптограмм (C₁ ||C₂)_l, i=1, 2, , 8000.

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

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

Приложение 1

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

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

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

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

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

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

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

7. Сравнимыми по модулю некоторого числа m называются числа, разность которых делится на число m без остатка или, что то же самое, числа, при делении которых на число m получаются равные остатки. Сравнимость двух МДЧ а и b по модулю m обозначается как а bmodm или а b(modm), а также как равенство по модулю, т.е. а=bmodm или а=b(modm).

8. Операция умножения двух МДЧ по модулю m выполняется как обычное алгебраическое умножение МДЧ с последующим взятием остатка от деления полученного результата на модуль m.

9. Операция сложения двух МДЧ по модулю m выполняется как обычное алгебраическое сложение МДЧ с последующим взятием остатка от деления полученного результата на модуль m.

10. Каждому МДЧ а, взаимно простому с модулем m, может быть сопоставлен в соответствие единственный элемент а^-1, называемый обратным элементом по отношению к данному элементу, такой, что произведение a^-1a (а значит и аа^-1) сравнимо с единицей по модулю m. Для вычисления обратных значений а^-1 по модулю m используется расширенный алгоритм Евклида, детально описанный в книге [Молдовян Н.А. Молдовян А.А. Введение в криптосистемы с открытым ключом. СПб., БХВ - Петербург, 2005. - 288 с.; см. С.78-79].

11. Операция деления МДЧ а на МДЧ b по модулю m выполняется как операция умножения по модулю m МДЧ а на МДЧ b^-1, которое является обратным к МДЧ b по модулю m.

12. Операции сложения и умножения по модулю m являются ассоциативными и коммутативными, а также операция умножения по модулю m по отношению к умножению по модулю m является дистрибутивной.

13. Система из двух линейных уравнений по модулю m с двумя неизвестными имеет единственное решение, если выполняется условие взаимной простоты коэффициентов и модуля m и условие взаимной простоты главного определителя системы и модуля m.