СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ СООБЩЕНИЯ М, ПРЕДСТАВЛЕННОГО В ДВОИЧНОМ ВИДЕ
METHOD FOR UNIT CODING OF M MESSAGE REPRESENTED IN BINARY FORM

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов и устройств для защиты информации, передаваемой по телекоммуникационным сетям путем шифрования (Толкование используемых в описании терминов приведено в Приложении) сообщений (информации).
m
m
m
Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования RC5 [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, p.344-346]. Способ включает в себя формирование секретного ключа в виде совокупности подключей, разбиение n-битового двоичного блока информации на n/2-битовые информационные подблоки А и В и поочередное преобразование данных подблоков. Подблоки преобразуются путем последовательного выполнения над ними линейных и нелинейных операций, в качестве которых используются операции суммирования по модулю 2, где m=n/2=8, 16, 32, 64, поразрядного суммирования по модулю 2 и циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока. Последнее свойство является характерным для способа RC5 и определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Подблок информации, например подблок В, преобразуют путем наложения подблока А на подблок В с помощью операции поразрядного суммирования по модулю 2 В:=В⊕А. После этого над подблоком В выполняют операцию циклического сдвига влево на число бит, равное значению подблока А: В:=В<<<А. Затем над подблоком В и одним из подключей К выполняют операцию суммирования по модулю 2, где m - длина подблока в битах: В:=(В+К)mod2. После этого аналогичным образом преобразуется подблок А. В зависимости от размеров ключа выполняется несколько таких итераций преобразования обоих подблоков. Данный способ обеспечивает достаточно высокую скорость шифрования при программной реализации. Недостатком способа шифрования 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].
1
2
k
i
1
1
i-1
i
i
1
2
k
Известен способ шифрования сообщения М [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, p.193-194], представленного в виде двоичной последовательности, путем генерации секретного ключа К, разбиения сообщения М на блоки M, М,…, М, где k - число блоков в сообщении. Блоки двоичных данных М, i=1, 2,…, k, имеют фиксированную разрядность n, где n≥64 бит. Шифруют блок M по секретному ключу, получая блок криптограммы C, затем, начиная со значения i=2 и до значения i=k, суммируют с помощью операции поразрядного суммирования блок криптограммы С и блок М, полученный в результате суммирования блока данных, шифруют по секретному ключу, получая в результате текущий блок криптограммы С. Совокупность блоков криптограммы C, C,…, C представляет собой криптограмму, содержащую сообщение М в скрытом виде. Извлечение сообщения М из криптограммы практически возможно только с использованием секретного ключа, использованного при шифровании, за счет чего достигается защита информации, содержащейся в сообщении М при его передаче по открытым каналам связи. Данный способ обеспечивает улучшение статистических свойств криптограммы, однако он имеет недостаток, состоящий в том, что теряется возможность независимого расшифрования отдельных блоков криптограммы.
6
1
2
u
u+1
u+2
2u
iu+1
iu+2
(i+1)u
(w-1)u+1
wu
1
2
D
1
2
w
1
2
u
u+1
u+2
2u
iu+1
iu+2
(i+1)u
(w-1)u+1
wu
1
2
D
1
2
w
Наиболее близким по своей технической сущности к заявляемому способу блочного шифрования сообщения М, представленного в двоичном виде, является способ, описанный в патенте РФ №2103829 [Молдовян А.А., Молдовян Н.А., Молдовян П.А. Способ шифрования информации, представленной двоичным кодом. Патент РФ №2103829. МПК Н04L 9/20. Бюл. №3 от 27.01.1998]. Способ-прототип включает в себя формирование секретного ключа, разбиение сообщения М на подблоки M, M,…, M; M, M,…, M;…; M, M,…, M;…; M,…, M, где i=1, 2,…, w, u≥1 и w≥1, генерацию двоичных векторов V, V,…, V, где D≥1, формирование блоков данных В, В,…, В, каждый из которых включает, по крайне мере, один из подблоков M, M,…, M; M, M,…, M;…; M, M,…, M;…; M,…, M и один из двоичных векторов V, V,…, V, и шифрование блоков данных В, В,…, В в зависимости от секретного ключа.
Недостатком способа-прототипа является снижение информационной емкости криптограммы за счет того, что двоичные вектора генерируются по случайному закону и после расшифрования не несут в себе полезной информации.
1
2
w
Целью заявляемого технического решения является разработка способа блочного шифрования сообщения М, представленного в двоичном виде, обеспечивающего повышение информационной емкости криптограммы за счет формирования шифруемых блоков В, В,…, В путем объединения подблоков данных, принадлежащих сообщению М и, по крайней мере, одному дополнительному сообщению Т.
1
2
u
u+1
u+2
2u
iu+1
iu+2
(i+1)u
(w-1)u+1
wu
1
2
w
1
2
u
u+1
u+2
2u
iu+1
iu+2
(i+1)u
(w-1)u+1
wu
1
2
w
Указанная цель достигается тем, что в способе блочного шифрования сообщения М, представленного в двоичном виде, заключающемся в формировании секретного ключа, разбиении сообщения на подблоки M, M,…, M; M, M,…, M;…; M, M,…, M;…; M,…, M, где i=1, 2,…, w, u≥1 и w≥1, формировании блоков данных В, В,…, В, каждый из которых включает, по крайне мере, один из подблоков M, M,…, M; M, M,…, M;…; M, M,…, M;…; M,…, M, и шифровании блоков данных В, В,…, В в зависимости от секретного ключа,
1
2
u
1
2
h
i
1
2
w
(i-1)u+1
(i-1)u+2
iu
1
2
u
i
i
i
1
2
h
(i-1)u+1
(i-1)u+2
iu
i
i
i
i
(1)
(2)
(h)
(j)
(j)
(j)
(j)
(1)
(2)
(h)
(1)
(2)
(h)
новым является то, что секретный ключ формируют в виде набора подключей K, Q, Q,…, Q, R, R,…, R, где h≥1, формирование блоков данных В, где i=1, 2,…, w, осуществляют путем дополнительного формирования сообщений T, T,…, T, разбиения сообщений Т, где j=1, 2,…, h, на подблоки Т , Т ,…, T , шифрования подблоков М, М,…, М в зависимости от подключей Q, Q,…, Q, шифрования подблоков Т , Т ,…, Т  в зависимости от подключей R, R,…, R и объединения преобразованных подблоков М, М,…, M, T , T ,…, T , а шифрование блоков данных В выполняют в зависимости от подключа K.
Новым также является то, что используют значения u=1 и h=1.
Уменьшение числа одновременно шифруемых сообщений упрощает реализацию заявленного способа.
Новым также является то, что используют значения u=1 и h=1 и подключ R, равный подключу K.
Уменьшение числа различных подключей секретного ключа упрощает процедуру генерации секретного ключа, благодаря чему достигается упрощение аппаратной реализации заявленного способа.
1
2
u
j
1
2
h
(j)
(1)
(2)
(h)
Благодаря указанной новой совокупности существенных признаков за счет совместного шифрования двух и более сообщений обеспечивается повышение информационной емкости криптограммы и возможности независимого извлечения из криптограммы каждого из совместно шифруемых сообщений, т.е. возможность расшифрования отдельных сообщений путем использования в процедуре расшифрования подключа K и подключей, относящихся к сообщениям, которые требуется извлечь из криптограммы. Например, при необходимости извлечь сообщение М из криптограммы путем ее расшифрования используются подключи K, Q, Q,…, Q, при необходимости извлечь сообщение Т - подключи K и R, где j=1, 2,…, h, при необходимости извлечь сообщения T, T,…, T - подключи K и R, R,…, R и т.д. То есть выбором подключей, используемых для расшифрования, можно извлечь из криптограммы любой набор из совместно преобразованных сообщений, оставляя остальные сообщения защищенными от несанкционированного ознакомления.
Проведенный анализ уровня техники позволил установить, что в известных источниках информации аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного изобретения условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
i
(i-1)u+1
(i-1)u+2
iu
i
i
i
(i-1)u+1
(i-1)u+2
iu
Q
i
i
i
i
(1)
(2)
(h)
(z)
(1)
(2)
(h)
(j)
Возможность реализации заявленного способа и корректность его работы объясняется тем, что каждый блок данных В, где i=1, 2,…, h, представляет собой конкатенацию преобразованных подблоков М, М,…, М и преобразованных подблоков Т , Т ,…, T . Подблоки M, M,…, M могут быть преобразованы с помощью одной и той же процедуры блочного шифрования E, где нижний индекс обозначает значение ключа шифрования для используемой процедуры блочного шифрования, или в общем случае с помощью различных процедур шифрования E, где i=1, 2,…, u. Преобразованные значения этих подблоков равны , ,…, . Подблоки Т , T ,…, Т  могут быть преобразованы с помощью одной и той же процедуры блочного шифрования F или в общем случае с помощью различных процедур шифрования F, где j=1, 2,…, h. Преобразованные значения этих подблоков равны , ,…, . Таким образом, блоки данных B имеют вид следующей конкатенации преобразованных подблоков:
i
К
i
i
Блоки данных В шифруются с помощью некоторой процедуры блочного шифрования Ф по подключу K. Преобразованное значение В является i-тым блоком криптограммы, который обозначим как С:
i
K
i
i
(i-1)u+1
(i-1)u+2
iu
i
i
i
(1)
(2)
(h)
(1)
(2)
(h)
Совокупность блоков криптограммы С, где i=1, 2,…, w, составляет криптограмму, полученную в результате шифрования сообщения М. Процедура блочного шифрования Ф легко обратима при известном значении К, поэтому для всех значений i=1, 2,…, w при расшифровании блока криптограммы С по ключу К восстанавливается значение блока данных В, который содержит значения преобразованных подблоков М, М,…, М и подблоков T , T ,…, T , причем преобразование этих подблоков было выполнено с помощью процедур блочного шифрования, каждая из которых обратима при известном ключе, использованном при шифровании. Поэтому, используя соответствующие подключи для выполнения процедуры расшифрования, можно расшифровать подблоки, относящиеся к произвольному набору из сообщений М и T, T,…, T. Это соответствует тому, что из одной и той же криптограммы извлекаются только сообщения, соответствующие использованному набору подключей.
1
2
w
1
2
w
i
i
i
i
i
i
Q
i
R
i
i
i
K
i
K
Q
i
R
i
i
i
i
Q
i
R
i
Q
i
R
i
i
-1
-1
Пример 1. Совместное шифрование двух сообщений М и Т, каждое из которых имеет размер 64 кбайт, осуществляется с помощью процедуры блочного шифрования Е, реализуемой по американскому стандарту блочного шифрования DES [Menezes A.J., Vanstone S.A. Handbook of Applied Cryptography. - CRC Press, 1996, p.250-256], и процедуры блочного шифрования F, реализуемой по алгоритму блочного шифрования IDEA [Menezes A.J., Vanstone S.A. Handbook of Applied Cryptography. - CRC Press, 1996, p.263-266]. Сообщение М разбивается на подблоки M, М,…, М, где w=8192. Сообщение T разбивается на подблоки T, Т,…, T, где w=8192. Генерируют секретный ключ в виде набора подключей K, Q (Q≠К) и R (R≠К; R≠Q), где Q и R - 64-битовые подключи; К - 128-битовый подключ. Блоки данных В, где i=1, 2,…, 8192, формируют путем шифрования подблока М с помощью процедуры блочного шифрования Е по подключу Q, шифрования подблока T с помощью процедуры блочного шифрования Е по подключу R и объединения преобразованных подблоков M и Т в единый блок данных B=E(M)||E(T). После формирования блока данных В он шифруется с помощью процедуры блочного шифрования F по подключу K: С=F(B)=F(E(M)||E(T)). Совокупность преобразованных блоков данных В, т.е. последовательность 128-битовых блоков С, где i=1, 2,…, 8192, образуют криптограмму размером 128 кбайт, в которой содержатся два сообщения размером по 64 кбайт. При вводе в процедуру расшифрования подключей К и Q каждый блок криптограммы С, где i=1, 2,…, 8192, расшифровывается следующим образом. Выполняется процедура расшифрования, специфицированная алгоритмом блочного шифрования IDEA и обозначаемая как F, по подключу К, в результате чего формируется 128-битовый блок данных . Блок данных E(M)||Е(Т) разбивается на два 64-битовых подблока данных E(M) и E(T). Каждый из последних двух подблоков расшифровывается с использованием процедуры расшифрования, специфицируемой стандартом блочного шифрования DES и обозначаемой как E, по подключу Q, в результате чего формируются два 64-битовых подблока следующего вида:  и  причем второй подблок данных представляет собой псевдослучайную последовательность битов, поскольку подключи шифрования и расшифрования не одинаковы (R≠Q). Расшифрованные блоки М, где i=1, 2,…, 8192, объединяются в единое расшифрованное сообщение М. При этом отличить совокупность всех подблоков  от случайной последовательности битов вычислительно невозможно, поэтому без знания подключа R ознакомление с сообщением T вычислительно невозможно.
i
i
Аналогично легко показать, что при выполнении процедуры расшифрования по подключам К и R 128-битовый блок криптограммы С, где i=1, 2,…, 8192, преобразуется в два 64-битовых подблока  и  причем первый подблок данных представляет собой псевдослучайную последовательность битов, поскольку подключи шифрования и расшифрования не одинаковы (R≠Q). Расшифрованные блоки T, где i=1, 2,…, 8192, объединяются в единое расшифрованное сообщение Т. При этом отличить совокупность всех подблоков  от случайной последовательности битов вычислительно невозможно, поэтому без знания подключа Q ознакомление с сообщением М вычислительно невозможно.
Таким образом, пример 1 показывает, что осуществление расшифрования одной и той же криптограммы размером 128 кбайт с различным набором подключей приводит к получению двух различных сообщений размером по 64 кбайт.
(1)
(2)
(1)
(2)
(1)
(2)
(1)
(1)
(1)
(2)
(2)
(2)
1
2
2i-1
2i
2w-1
2w
1
2
w
1
2
w
1
2
1
2
1
2
1
2
i
Пример 2. Совместное шифрование трех сообщений М, Т и T. Сообщение М имеет размер 32 кбайт. Сообщения T и T имеют одинаковый размер, равный 16 кбайт. Сообщение М разбивается на 32-битовые подблоки M, М,…, M, M,…, M, M, где i=1, 2,..., w; w=4096 (u=2). Сообщения T и T разбиваются на 32-битовые подблоки Т , Т ,…, Т  и T , T ,…, T , где w=4096. Секретный ключ генерируется в виде набора подключей К, Q, Q, R и R, где K - 128-битовый подключ, а подключи Q, Q, R и R представляют собой 32-битовые двоичные вектора, имеющие нечетное значение при их интерпретации в виде двоичных чисел. Блоки данных В, где i=1, 2,…, 4096, формируют путем выполнения следующих шагов:
2i-1
Q
1
1) шифрование подблока М с помощью процедуры блочного шифрования E по подключу Q, описываемой формулой ;
2i
2
2) шифрование подблока М с помощью процедуры блочного шифрования  по подключу Q, описываемой формулой ;
i
1
(1)
3) шифрование подблока Т  с помощью процедуры блочного шифрования  по подключу R, описываемой формулой ;
i
2
(2)
4) шифрование подблока T  с помощью процедуры блочного шифрования  по подключу R, описываемой формулой
2i
2i-1
i
i
(1)
(2)
5) объединение преобразованных подблоков М, М, Т  и Т  в единый 128-битовый блок данных
i
После формирования блока данных В он шифруется с помощью процедуры блочного шифрования F, описанной в примере 1, по подключу K:
i
i
(1)
(2)
Совокупность преобразованных блоков данных В, т.е. последовательность 128-битовых блоков С, где i=1, 2,…, 4096, образуют криптограмму размером 64 кбайт, в которой содержатся в преобразованном виде три сообщения М, Tи Т с общим размером, равным размеру криптограммы. Равенство общего размера шифруемых сообщений и размера криптограммы имеет место для произвольных шифруемых сообщений. Это означает, что рассмотренный в примере 2 частный вариант реализации заявленного способа обеспечивает максимально возможную информационную емкость криптограммы.
1
i
i
i
2
1
2
1
2
Q
Q
Q
(1)
(1)
(1)
(2)
(1)
(2)
(1)
(2)
Q
16
16
-1
-1
Легко показать, что при выполнении процедуры расшифрования по подключам К и R из 128-битового блока криптограммы С, где i=1, 2,…, 4096, извлекается подблок Т . Совокупность расшифрованных блоков Т  где i=1, 2,…, 4096, образует восстановленное сообщение Т. При выполнении процедуры расшифрования по подключам К и R восстанавливается сообщение Т. При выполнении процедуры расшифрования по подключам К, Q, Q, R и R восстанавливаются все три совместно преобразованных сообщения М, Т и Т. Корректность расшифрования сообщений М, T и T основана на применении процедур шифрования, которые обратимы при известном ключе шифрования. Обратимость процедуры блочного шифрования F показана в книге [Menezes A.J., Vanstone S.A. Handbook of Applied Cryptography. - CRC Press, 1996, p.263-266]. Обратимость процедуры блочного шифрования E по подключу Q, описываемой формулой E(M')=M'Qmodp=C' (где р=2+1; М' - 32-битовый подблок, интерпретируемый как двоичное число) при использовании подключа Q, имеющего нечетное значение, показывается в общем случае следующим путем. Поскольку число р-1=2 является взаимно простым с любым нечетным числом, то для любого нечетного подключа Q существует и легко вычисляется (по расширенному алгоритму Евклида [Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. - СПб.: БХВ - Петербург, 2010. - 304 с.]) мультипликативно обратное по модулю р-1 целое число Q. Поскольку число р - простое и Q<р, то для любого нечетного подключа Q существует и легко вычисляется (по расширенному алгоритму Евклида) мультипликативно обратное по модулю р целое число Q'. Процедура расшифрования , обратная процедуре блочного шифрования E, описывается формулой . Действительно процедура расшифрования по этой формуле восстанавливает значение 32-битового подблока:
.
Приведенные примеры показывают, что заявляемый способ блочного шифрования сообщения М, представленного в двоичном виде, функционирует корректно, технически реализуем и позволяет решить поставленную задачу.
Заявляемый способ блочного шифрования сообщения М, представленного в двоичном виде, может быть применен для разработки средств защищенной широковещательной рассылки сообщений с управлением доступа к сообщениям со стороны получателей при обеспечении идентичности процедуры расшифрования одной и той же криптограммы. Такие средства защищенной широковещательной рассылки сообщений решают задачу неотслеживаемости трафика при передаче информации по телекоммуникационным каналам.
ТОЛКОВАНИЕ ТЕРМИНОВ, ИСПОЛЬЗУЕМЫХ В ОПИСАНИИ ЗАЯВКИ
1. Электронное сообщение (сообщение), представленное в двоичном виде, - это двоичный цифровой электромагнитный сигнал, параметры которого зависят от исходного сообщения и способа его преобразования к электронному виду.
2. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.
3. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.
4. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например, число 10011 является 5-разрядным.
5. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».
Z
6. Операция возведения числа S в дискретную степень А по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1,…, n-1}, включающем n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю [см. Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. - СПб.: БХВ - Петербург, 2002. - с.58-61]; выполнение операции возведения числа S в дискретную степень Z по модулю n обозначается как W=S mod n, где многоразрядное двоичное число W есть результат выполнения данной операции.
7. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
γ
1
2
8. Порядок q числа а по модулю n - это минимальное из чисел γ, для которых выполняется условие a mod n=1, т.е. q=min{γ, γ,…} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
-1
9. Операция деления целого числа А на целое число В по модулю n выполняется как операция умножения по модулю n числа А на целое число B, которое является обратным к В по модулю n.
-1
-1
10. Вычисление значения B, которое является обратным к В по модулю n, выполняется как возведение числа В в степень, равную q-1, где q - порядок числа В по модулю n. Более быстрым способом вычисления значения В является выполнение расширенного алгоритма Евклида [Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. - СПб.: БХВ - Петербург, 2010. - 304 с.].
11. Шифрование - это криптографическое преобразование цифровой информации, которое выполняется по секретному ключу (в зависимости от секретного ключа) и обеспечивает влияние одного бита исходных данных на многие биты выходных данных, например, с целью защиты информации от несанкционированного чтения.
12. Расшифрование есть процесс, обратный процедуре шифрования, обеспечивающий восстановление информации по криптограмме при знании секретного ключа.
13. Шифр (или алгоритм шифрования) - это алгоритм преобразования входных данных с использованием секретного ключа.
14. Двоичный вектор - это некоторая последовательность нулевых и единичных битов. Сообщение, представленное в двоичном виде, представляет собой двоичный вектор.
15. Выполнение арифметических операций над двоичными векторами и сообщениями, представленными в двоичном виде, осуществляется путем интерпретации двоичного вектора как числа, записанного в двоичной форме, и выполнения арифметической операции над этим числом.
16. Криптограмма - двоичная последовательность, получаемая в результате шифрования исходного сообщения по секретному ключу.
17. Блок криптограммы - двоичная последовательность, получаемая в результате шифрования исходного блока данных.