СПОСОБ ШИФРОВАНИЯ БЛОКА ДВОИЧНЫХ ДАННЫХ
METHOD OF ENCRYPTING BINARY DATA UNIT

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов и устройств для защиты информации, передаваемой по телекоммуникационным сетям путем шифрования  сообщений (информации).
m
m
m
Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования RC5 [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, рр. 344-346]. Способ включает в себя формирование секретного ключа в виде совокупности подключей, разбиение n-битового двоичного блока информации на n/2-битовые информационные подблоки А и В и поочередное преобразование этих подблоков. Подблоки преобразуются путем последовательного выполнения над ними линейных и нелинейных операций, в качестве которых используются операции суммирования по модулю 2, где m=n/2=8,16,32,64, поразрядного суммирования по модулю 2 и циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока. Последнее свойство является характерным для способа RC5 и определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Подблок информации, например подблок В, преобразуют путем наложения подблока А на подблок В с помощью операции поразрядного суммирования по модулю 2 В:=В⊕А. После этого над подблоком В выполняют операцию циклического сдвига влево на число бит, равное значению подблока А:В:=В<<<А. Затем над подблоком В и одним из подключей К выполняют операцию суммирования по модулю 2, где m - длина подблока в битах: B:=(B+K)mod 2. После этого аналогичным образом преобразуется подблок А. В зависимости от размеров ключа выполняется несколько таких итераций преобразования обоих подблоков. Данный способ обеспечивает достаточно высокую скорость шифрования при программной реализации. Недостатком способа шифрования 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].
1
2
k
1
2
k
1
1
i-1
i
i
1
2
k
Известен способ шифрования n-битовых блоков данных [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, pp. 193-194] путем генерации секретного ключа К, разбиения сообщения М на n-битовые блоки данных М, М,…,М, где k - число блоков в сообщении; n≥64 бит, и последующего шифрования блоков данных М, М,…М, причем процесс шифрования выполняют следующим путем. Шифруют блок М по секретному ключу, получая блок криптограммы C, затем, начиная со значения i-2 и до значения i=k, суммируют с помощью операции поразрядного суммирования блок криптограммы C и блок M, полученный в результате суммирования блок данных шифруют по секретному ключу, получая в результате текущий блок криптограммы С. Совокупность блоков криптограммы C, C,…, C представляет собой криптограмму, содержащую сообщение М в скрытом виде. Извлечение сообщения М из криптограммы практически возможно только с использованием секретного ключа, использованного при шифровании, за счет чего достигается защита информации, содержащейся в сообщении М, при его передаче по открытым каналам связи. Данный способ обеспечивает улучшение статистических свойств криптограммы, однако он имеет недостаток, состоящий в том, что теряется возможность независимого расшифрования отдельных блоков криптограммы.
M
M
Q
T
T
R
M
T
Наиболее близким по своей технической сущности к заявляемому способу шифрования n-битового блока двоичных данных М является способ, описанный в патенте №2459275 [Молдовян А.А., Молдовян Н.А. Способ блочного шифрования сообщения М, представленного в двоичном виде. Патент №2459275] по п.2 формулы изобретения указанного патента. Способ прототип включает в себя формирование секретного ключа, включающего подключи Q и R, формирование вспомогательного n-битового блока двоичных данных Т, формирование n-битовой вспомогательной криптограммы С путем выполнения над М операции блочного шифрования E в зависимости от Q по формуле С=E(M), формирование n-битовой вспомогательной криптограммы C путем выполнения над Т операции блочного шифрования E в зависимости от R по формуле C=E(T), формирование криптограммы С в зависимости от секретного ключа и вспомогательных криптограмм C и C.
M
T
M
T
T
R
T
M
M
T
Способ-прототип позволяет реализовать защиту информации с использованием механизма обманных ловушек, который состоит в том, что потенциальному злоумышленнику подставляется часть секретного ключа, включающая подключ R, в качестве ключа расшифрования, а в качестве вспомогательного n-битового блока двоичных данных Т используется n-битовый блок фиктивного сообщения. Блок криптограммы С расшифровывается путем его преобразования по дополнительному ключу, приводящего к получению вспомогательной криптограммы С∗, представляющей собой конкатенациию двух n-битовых строк C и C:С∗=C||C. Затем правая n-битовая строка C расшифровывается путем выполнения операции блочного преобразования D, обратной к операции блочного шифрования Е, т.е. по формуле Т=D(C). Аналогичная процедура расшифрования выполняется с использованием подключа К и левой n-битовой строки C вспомогательной криптограммы C∗=C||C. Недостатком способа прототипа является то, что различные части вспомогательной криптограммы C∗ используются при расшифровании блока данных М и блока фиктивного сообщения Т. Это демаскирует факт наличия в блоке криптограммы С блока данных М.
Задачей заявленного нового технического решения является разработка способа шифрования блока двоичных данных, представленного в виде n-битовой строки, обеспечивающего эффективную маскировку факта наличия n-битового блока данных М в блоке криптограммы С за счет того, что при выполнении процедуры расшифрования осуществляется преобразование С в n-битовую вспомогательную криптограмму и использование всех битов вспомогательной криптограммы при выполнении процедур расшифрования как n-битового блока данных М, так и вспомогательной n-битовой строки Т.
Техническим результатом нового способа шифрования блока двоичных данных М является повышение уровня защищенности информации, шифруемой с его применением.
M
M
Q
T
T
R
M
T
Указанный технический результат достигается тем, что в способе шифрования блока двоичных данных М, заключающемся в формировании секретного ключа, включающего подключи Q и R, формировании вспомогательного n-битового блока двоичных данных T, формировании n-битовой вспомогательной криптограммы C путем выполнения над М операции блочного шифрования Е в зависимости от Q по формуле C=E(M), формировании n-битовой вспомогательной криптограммы C путем выполнения над Т операции блочного шифрования Е в зависимости от R по формуле C=E(T), формировании криптограммы С в зависимости от секретного ключа и вспомогательных криптограмм C и C,
1
2
1
2
1
2
1
1
2
2
M
1
1
2
2
T
1
2
новым является то, что подключ Q формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-разрядных двоичных чисел q и q, подключ R формируют в виде 2n-битовой строки, представляющей собой конкатенацию двух n-разрядных двоичных чисел r и r, формируют (n+1)-разрядное двоичное число p и формируют криптограмму С в виде конкатенации двух многоразрядных двоичных чисел C и C, являющихся решением системы из двух линейных уравнений kC+kC=C mod p и qC+qC=C mod р с двумя неизвестными C и C.
Новым также является то, что формируют (n+1)-разрядное двоичное число p, которое является простым.
Формирование и использование простого (n+1)-разрядного двоичного числа p упрощает процедуру генерации подключей Q и R.
n
Новым является и то, что формируют (n+1)-разрядное двоичное число p, которое представимо в виде 2+1.
n
Использование в качестве (n+1)-разрядного двоичного числа р МДЧ вида 2+1 обеспечивает формирование криптограммы, имеющей размер 2n бит, что упрощает программную и аппаратную реализацию заявленного способа шифрования n-битового блока двоичных данных М.
M
T
Благодаря указанной новой совокупности существенных признаков за счет формирования n-битовых вспомогательных криптограмм C и C обеспечивается использование всех битов вспомогательной криптограммы при выполнении процедуры расшифрования как блока данных М, так и вспомогательного n-битового блока двоичных данных Т, в качестве которой может быть применен n-битовой блок некоторого фиктивного сообщения. Это обеспечивает эффективную маскировку факта наличия n-битового блока данных М в блоке криптограммы С при ее расшифровании потенциальным нарушителем при использовании им подключа Q при расшифровании криптограммы С, поскольку процедура расшифрования выполняется по одной и той же формуле как при расшифровании блока данных M, так и при расшифровании блока фиктивного сообщения Т.
1
2
1
2
Q
1
1
2
2
1
2
R
1
1
2
2
Корректность заявленного способа шифрования n-битового блока двоичных данных М состоит в том, что по криптограмме С=С||C, где знак || обозначает операцию конкатенации (объединения битовых строк), может быть восстановлен «-битовый блок двоичных данных М по подключу Q=q||q по формуле M=D((qC+qC)mod p), где D - операция блочного расшифрования, обратная операции блочного шифрования Е, и вспомогательный n-битовый блок двоичных данных Т по подключу R=r||r по формуле T=D((rC+rC)mod р).
1
2
Действительно, при выполнении процедуры расшифрования по подключу Q=q||q имеем
1
2
а при выполнении процедуры расшифрования по подключа R=r||r имеем
Далее реализуемость и корректность заявленного способа шифрования n-битового блока двоичных данных М иллюстрируется частными примерами его реализации.
10
64
3
2
Пример 1. Шифрование 64-битового блока двоичных данных М. Формируют простое МДЧ р=18446744073709551629=2+2+2+1=
2
1
2
1
2
1
2
1
2
=10000000000000000000000000000000000000000000000000000000000001101, , где индекс 10 (индекс 2) обозначает то, что число записано с использованием десятичной (двоичной) системы записи чисел, формируют секретный ключ в виде подключей Q и R, причем подключ Q формируют в виде 128-битовой строки, представляющей собой конкатенацию двух 64-разрядных двоичных чисел q и q, т.е. Q=q||q, а подключ R формируют в виде 128-битовой строки, представляющей собой конкатенацию двух 64-битовых строк r и r (т.е. R=r||r), которые удовлетворяют условиям
1
2
1
2
1
2
1
2
q≡q≡r≡r≡1 mod 2 (условие нечетности чисел q, q, r, r), а именно формируют следующие МДЧ:
1
10
2
10
q=15344089324516380789; q=12571778644096321013;
1
10
2
10
r=15608185472029694193; r=15369129295277581477.
1
2
1
2
1
2
2
1
M
1
2
M
Q
Проверка показывает, что сформированные нечетные МДЧ q, q, r и r удовлетворяют условию qr-qr=812714980881351227≠0 mod p. Затем формируют вспомогательный 64-битовый блок двоичных данных Т и 64-битовую вспомогательную криптограмму Спутем выполнения над блоком данных М операции блочного шифрования Е в зависимости от подключа Q=q||q по формуле C=E(M), где операция блочного шифрования описывается следующим алгоритмом:
M
1. Установить значение счетчика i←0 и переменной C←М, где знак ← обозначает операцию присваивания.
M
M
1
M
64
<29<
<29<
2. Сформировать 64-битовую строку C в виде МДЧ, вычисленного по формуле C←(qC mod2), где (…) обозначает операцию циклического сдвига битовой строки (…) на 29 бит влево.
M
M
1
M
64
<17<
<17<
3. Преобразовать 64-битовую строку C по формуле C←(qC mod2), где (…) обозначает операцию циклического сдвига битовой строки (…) на 17 бит влево.
M
Q
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение C взять в качестве выходного значения операции блочного шифрования E, выполненной над 64-битовым блоком двоичных данных М.
T
1
2
T
R
Затем формируют 64-битовую вспомогательную криптограмму C путем выполнения над вспомогательным 64-битовым блоком двоичных данных Т операции блочного шифрования Е в зависимости от подключа R=r||r по формуле C=E(T) в соответствии со следующим алгоритмом:
T
1. Установить значение счетчика i←0 и переменной C←Т.
T
T
1
T
64
<29<
2. Сформировать 64-битовую строку C в виде МДЧ, вычисленного по формуле C←(rC mod2).
T
T
2
T
64
<17<
3. Преобразовать 64-битовую строку C по формуле C←(rC mod2).
T
R
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение C взять в качестве выходного значения операции блочного шифрования E, выполненной над вспомогательным 64-битовым блоком двоичных данных Т.
M
T
2
1
2
После формирования вспомогательных криптограмм C и C, рассматривая их как 64-битовые МДЧ, формируют криптограмму C=C1||C путем решения следующей системы из двух линейных уравнений с неизвестными C и C.
1
2
1
2
Решением данной системы являются два МДЧ C и C, которые объединяются в криптограмму C=C||C.
1,
2
1
2
Q
M
Q
64
<mrow><msubsup><mi>q</mi><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>q</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>r</mi><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>r</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup></mrow>
Доказательство корректности данного частного варианта реализации заявленного способа шифрования n-битового блока двоичных данных М доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что для нечетных МДЧ q q, r, r по модулю 2 существуют и легко вычисляются по расширенному алгоритму Евклида соответствующие обратные значения
а операция блочного расшифрования D(C), обратная операции блочного шифрования E(M), реализуется следующей процедурой преобразования:
M
1. Установить значение счетчика i←0 и переменной M←C.
>17>
>17>
<mrow><mi>M</mi><mo>←</mo><mi>M</mi><msubsup><mi>q</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mtext> </mtext><mi>mod</mi><msup><mn>2</mn><mrow><mn>64</mn></mrow></msup><mo>,</mo></mrow>
2. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М←М и
где (…) обозначает операцию циклического сдвига битовой строки (…) на 17 бит вправо.
>29>
>29>
<mrow><mi>M</mi><mo>←</mo><mi>M</mi><msubsup><mi>q</mi><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mtext> </mtext><mi>mod</mi><msup><mn>2</mn><mrow><mn>64</mn></mrow></msup><mo>,</mo></mrow>
3. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М←М и
, где (…) обозначает операцию циклического сдвига битовой строки (…) на 29 бит вправо.
Q
M
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение М взять в качестве выходного значения операции D, выполненной над 64-битовой вспомогательной криптограммой C.
R
T
R
Аналогично записывается процедура для реализации операции блочного расшифрования D(C), обратная операции блочного шифрования E(T).
1
2
w
1
2
w
i
i
1
2
i
Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрования двух сообщений Message и Text, каждое из которых, например, имеет размер 64 Кбит. Сообщение Message разбивается на 64-битовые блоки данных M, M,…,M, где w=1000. Сообщение Text разбивается на 64-битовые блоки данных T, T,…,T. Поочередно для значений i=1, 2,…, 1000 пары блоков данных (M, T) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 128-битовых криптограмм (C||C), i=1, 2,…,1000.
Пример 2. Шифрование 128-битового блока двоичных данных М.
128
Формируют МДЧ p вида 2+1:
128
10
р=2+1=340282366920938463463374607431768211457, где индекс 10 обозначает то, что число записано с использованием десятичной системы записи чисел. В виде двоичного числа (т.е. при использовании двоичной системы записи чисел) р имеет вид
2
р=1000000000000000000000000000000000000000000000000000000000000 00\\0000000000000000000000000000000000000000000000000000000000000 00001,
1
2
1
2
1
2
1
2
где знак «\\» означает перенос записи на следующую строку. Затем формируют секретный ключ в виде подключей Q и R, причем подключ Q формируют в виде 256-битовой строки, представляющей собой конкатенацию двух 128-разрядных двоичных чисел q и q, т.е. Q=q||q, а подключ R формируют в виде 256-битовой строки, представляющей собой конкатенацию двух 128-битовых строк r и r (т.е. R=r||r), которые удовлетворяют условию
1
2
1
2
1
2
1
2
q≡q≡r≡r≡1 mod 2 (условие нечетности чисел q, q, r, r), а именно формируют следующие МДЧ:
1
10
q=321909040675575663770595377008565615669;
2
10
q=286307205067618230636306150613625759003;
1
10
r=290440427634195645156881834450918186151;
2
10
r=294266926927583280559101629113993987661.
1
2
1
2
Проверка показывает, что сформированные нечетные МДЧ q, q, r, и r удовлетворяют условию
1
2
2
1
qr-qr=75227762587413192201808942155507758598≠0 mod р.
M
1
2
M
Q
Затем формируют вспомогательный 64-битовый блок двоичных данных Т и 128-битовую вспомогательную криптограмму C путем выполнения над блоком данных М операции блочного шифрования Е в зависимости от подключа Q=q||q по формуле C=E(M), где операция блочного шифрования описывается следующим алгоритмом:
M
1. Установить значение счетчика i←0 и переменной C←М.
M
M
1
M
128
<32<
<32<
2. Сформировать 64-битовую строку C в виде МДЧ, вычисленного по формуле C←(qC mod2), где (…) обозначает операцию циклического сдвига битовой строки (…) на 32 бита влево.
M
M
2
M
128
<40<
<40<
3. Преобразовать 64-битовую строку C по формуле C←(qC mod2), где (…) обозначает операцию циклического сдвига битовой строки (…) на 40 бит влево.
M
Q
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение C взять в качестве выходного значения операции блочного шифрования E, выполненной над 64-битовым блоком двоичных данных М.
T
1
2
T
R
Затем формируют 64-битовую вспомогательную криптограмму C путем выполнения над вспомогательным 64-битовым блоком двоичных данных Т операции блочного шифрования Е в зависимости от подключа R=r||r по формуле C=E(T) в соответствии со следующим алгоритмом:
T
1. Установить значение счетчика i←0 и переменной C←Т.
T
T
1
T
128
<32<
2. Сформировать 64-битовую строку C в виде МДЧ, вычисленного по формуле C←(rC mod2).
T
T
2
T
128
<40<
3. Преобразовать 64-битовую строку C по формуле C←(rCmod2).
T
R
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение C взять в качестве выходного значения операции блочного шифрования E, выполненной над вспомогательным 64-битовым блоком двоичных данных Т.
M
T
1
2
1
2
После формирования вспомогательных криптограмм C и C, рассматривая их как 64-битовые МДЧ, формируют криптограмму C=C||C путем решения следующей системы из двух линейных уравнений с неизвестными C и C:
1
2
1
2
Решением данной системы являются два МДЧ C и C, которые объединяются в криптограмму C=C||C.
1
2
1
2
Q
M
Q
128
<mrow><msubsup><mi>q</mi><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><mtext> </mtext><msubsup><mi>q</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><mtext> </mtext><msubsup><mi>r</mi><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><mtext> </mtext><msubsup><mi>r</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo></mrow>
Доказательство корректности данного частного варианта реализации заявленного способа шифрования n-битового блока двоичных данных М доказывается аналогично описанному ранее общему доказательству корректности заявленного способа с учетом того, что для нечетных МДЧ q, q, r, r по модулю 2 существуют и легко вычисляются по расширенному алгоритму Евклида соответствующие обратные значения
операция блочного расшифрования D(C), обратная операции блочного шифрования E(M), реализуется следующей процедурой преобразования:
M
1. Установить значение счетчика i←0 и переменной M←C.
>40>
>40>
<mrow><mi>M</mi><mo>←</mo><mi>M</mi><msubsup><mi>q</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mtext> </mtext><mi>mod</mi><msup><mn>2</mn><mrow><mn>128</mn></mrow></msup><mo>,</mo></mrow>
2. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М←М и
где (…) обозначает операцию циклического сдвига битовой строки (…) на 40 бит вправо.
>32>
>32>
<mrow><mi>M</mi><mo>←</mo><mi>M</mi><msubsup><mi>q</mi><mn>2</mn><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mtext> </mtext><mi>mod</mi><msup><mn>2</mn><mrow><mn>128</mn></mrow></msup><mo>,</mo></mrow>
3. Преобразовать 64-битовую строку М, выполняя последовательно вычисления по формулам М←М и
где (…) обозначает операцию циклического сдвига битовой строки (…) на 32 бита вправо.
Q
M
4. Прирастить значение счетчика i:i←i+1. Если i<16, то перейти к шагу 2, в противном случае текущее значение М взять в качестве выходного значения операции D, выполненной над 64-битовой вспомогательной криптограммой C.
R
T
R
Аналогично записывается процедура для реализации операции блочного расшифрования D(C), обратная операции блочного шифрования E(T).
1
2
w
1
2
w
i
i
1
2
i
Рассмотренная частная реализация заявленного способа может быть применена для совместного шифрование двух сообщений Message и Text, каждое из которых, например, имеет размер 128 Кбайт. Сообщение Message разбивается на 128-битовые блоки данных M, M,…, M, где w=8000. Сообщение Text разбивается на 128-битовые блоки данных T, T,…, T. Поочередно для значений i=1, 2,…, 8000 пары блоков данных (M, T) совместно шифруются в соответствии с описанным примером реализации заявленного способа, в результате чего формируется шифртекст в виде последовательности 256-битовых криптограмм (C||C), i=1, 2,…, 8000.
Приведенные примеры показывают, что заявляемый способ шифрования блока данных М, представленного в виде n-битовой строки, функционирует корректно, технически реализуем и позволяет решить поставленную задачу.
Заявляемый способ шифрования блока данных М, представленного в виде n-битовой строки, может быть применен для разработки средств комплексной защиты информации от несанкционированного доступа, обеспечивающих дополнительную защищенность информации за счет навязывания потенциальным злоумышленникам ложных сообщений. Данный способ также может быть применен для защищенной широковещательной рассылки сообщений с управлением доступа к сообщениям со стороны получателей при обеспечении идентичности процедуры расшифрования одной и той же криптограммы. Такие средства защищенной широковещательной рассылки сообщений решают задачу неотслеживаемости трафика при передаче информации по телекоммуникационным каналам.