Способ шифрования сообщения м, представленного в виде многоразрядного двоичного числа

Способ шифрования сообщения м, представленного в виде многоразрядного двоичного числа

Реферат

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

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

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

Наиболее близким по своей технической сущности к заявляемому способу шифрования сообщения М, представленного в виде многоразрядного двоичного числа (МДЧ), является способ, описанный в патенте США №2103829 [Hellman M.E., Pohlig S.C. Exponentiation Cryptographic Apparatus and Method // U.S. Patent # 4424414. Jan. 3, 1984]. Способ-прототип включает в себя генерацию простого МДЧ р, формирование секретного ключа в виде МДЧ е и формирование криптограммы, зависящей от сообщения М и от секретного ключа е, причем криптограмму формируют в виде МДЧ С, которое удовлетворяет соотношению С=M^e mod p.

Недостатком способа-прототипа является уязвимость к атакам с принуждением, которые предполагают необходимость предоставления атакующему некоторого случайного вспомогательного секретного ключа, по которому криптограмма расшифровывается в некоторое осмысленное сообщение , отличное от сообщения М, зашифрованному по секретному ключу (см. [R.Canetti, С.Dwork, М.Naor, R.Ostrovsky, Deniable Encryption // Advances in cryptology - CRYPTO 1997. / Conference Proceedings, pp.90-104] и [М.H. Ibrahim, A Method for Obtaining Deniable Public-Key Encryption // International Journal of Network Security. 2009. Vol.8. No.1, pp.1-9]). При этом процедура расшифрования криптограммы не зависит от значения предоставляемого ключа, т.е. расшифрование криптограммы (C₁, C₂, …, C_d) по секретному ключу и по вспомогательному секретному ключу осуществляется единообразно. Данный недостаток связан с тем, что в способе-прототипе вычислительно неосуществимо нахождение вспомогательного секретного ключа, по которому криптограмма расшифровывается в осмысленное сообщение , отличное от сообщения М, из-за чего атакующему может быть предоставлен только секретный ключ, который позволяет атакующему получить доступ к секретному сообщению, т.е. не обеспечивается стойкость алгоритма шифрования к атаке с принуждением.

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

Указанная цель достигается тем, что в способе шифрования сообщения М, представленного в виде МДЧ, заключающемся в формировании секретного ключа и формировании криптограммы, зависящей от сообщения М и от секретного ключа

новым является то, что секретный ключ формируют в виде набора подключей К₁, K₂, …, К_h, где h≥1, генерируют вспомогательные МДЧ p, , , …, , , , …, , …, , , …, , R₁, R₂, …, R_u, где 1<d и 1≤u≤d, и формируют криптограмму в виде набора МДЧ C₁, С₂, …, C_d, который удовлетворяет системе уравнений , , …, , где, по крайней мере, одно из МДЧ R₁, R₂, …, R_u зависит от сообщения М и, по крайней мере, одно из МДЧ , , …, , , , …, , …, , , …, зависит от одного из подключей K₁, K₂, …, K_h.

Новым также является то, что секретный ключ формируют в виде набора подключей K₁, K₂, K₃, K₄, генерируют вспомогательные МДЧ р, , , , , , генерируют вспомогательное МДЧ R₂ путем формирования дополнительного сообщения , представленного в виде МДЧ, и генерации R₂ по формуле и формируют криптограмму в виде набора МДЧ С₁, С₂, который удовлетворяет системе уравнений , .

Формирование правой части уравнений по формулам и обеспечивает стойкость заявленного способа шифрования к атакам на основе известных сообщений и М. При этом криптограмма С расшифровывается по секретному ключу в сообщение М, а по вспомогательному секретному ключу - в сообщение . Вспомогательным секретным ключом в данном частном варианте заявленного способа является совокупность подключей К₃ и К₄. (Заметим, что понятие вспомогательного секретного ключа не относится к признакам заявленного способа, а относится к рассмотрению стойкости заявленного способа к атакам с принуждением.)

Новым также является то, что секретный ключ формируют в виде набора подключей K₁, K₂, K₃, K₄, генерируют вспомогательные МДЧ р, , , , , , , , , , , генерируют вспомогательное МДЧ R₂ путем формирования дополнительного сообщения , представленного в виде МДЧ, и генерации R₂ по формуле , генерируют случайное вспомогательное МДЧ R₃<p и формируют криптограмму в виде набора МДЧ С₁, С₂, С₃, который удовлетворяет системе уравнений , , .

Использование в качестве правой части одного из сравнений случайного МДЧ обеспечивает возможность выполнения вероятностного шифрования с помощью заявленного способа, при котором многократное зашифрование одной и той же пары сообщений и М на одном и том же секретном ключе обеспечивает формирование различающихся криптограмм. При этом любая из сформированных криптограмм, представляющих собой набор МДЧ С₁, С₂, …, С_d расшифровывается по секретному ключу в сообщение М, а по вспомогательному секретному ключу - в сообщение . Вспомогательным секретным ключом в данном частном варианте заявленного способа является совокупность подключей K₃ и K₄.

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

Проведенный анализ уровня техники позволил установить, что в известных источниках информации аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного изобретения условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния существенных признаков заявленного изобретения на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Возможность реализации заявленного способа и корректность его работы объясняется тем, что система из u линейных уравнений, заданная над любым полем, с d неизвестными, где d≥u, имеет по крайней мере одно решение. То есть при простом вспомогательном МДЧ p и любых значениях вспомогательных МДЧ , , …, , , , …, , …, , , …, , R₁, R₂, …, R_u криптограмма C=(C₁, C₂, …, C_d), представляющая собой упорядоченный набор МДЧ C₁, С₂, …, C_d, может быть сформирована. При d=u существует единственное значение формируемой криптограммы. При d>u имеет место случай вероятностного шифрования и существует большое число различных криптограмм, расшифрование каждой из которых с использованием секретного ключа приведет к получению сообщения М. Для получения конкретного значения криптограммы в случае вероятностного шифрования формирование криптограммы осуществляется путем генерации d-u линейных уравнений со случайными коэффициентами и случайной правой частью, добавления сгенерированных линейных уравнений к имеющейся системе из u линейных уравнений и решения полученной расширенной системы линейных уравнений. Значение сформированной криптограммы представляет собой решение указанной расширенной системы уравнений. Процедура формирования криптограммы (С₁, С₂, …, C_d) состоит в выполнении некоторой последовательности операций, обеспечивающих нахождение решения указанной системы уравнений. Существуют различные способы решения систем линейных уравнений, каждый из которых определяет конкретный вариант выполнения процедуры формирования криптограммы.

Формирование МДЧ R₁, R₂, …, R_u может быть выполнено различными способами, выбор которых определяется конкретным применением заявленного способа. В частности, для реализации вероятностного шифрования одно из этих МДЧ, например R₁, формируется в зависимости от сообщения М и от подключа К₁ по формуле R₁=МK₁modp₁, а МДЧ R₂, R₃, …, R_u формируются в виде случайных МДЧ. Каждое из сформированных МДЧ R₂, R₃, …, R_u влияет на значение криптограммы (C₁, C₂, …, C_d), однако из всех возможных вариантов значения (C₁, С₂, …, С_d) при расшифровании криптограммы по формуле

будет восстановлено сообщение М. При необходимости обеспечить стойкость к атакам на основе известных или специально подобранных текстов формируются подключ К₁ и МДЧp, имеющие разрядность не менее 256 бит, а МДЧ R₁ формируется по формуле R₁=M^eK₁modp₁, где е - МДЧ, используемое в качестве дополнительного подключа и являющееся взаимно простым с МДЧр-1. В последнем случае расшифрование криптограммы (C₁, C₂, …, C_d) выполняется по формуле

где h=е^-1mod р-1.

Для обеспечения стойкости к атакам с принуждением заявленный способ используется, например, следующим образом. Секретный ключ формируют в виде набора подключей K₁, K₂, K₃, K₄, таких, что значения подключей K₁ и K₃, являются взаимно простыми с МДЧ р-1. Генерируют дополнительное осмысленное сообщение , генерируют вспомогательные МДЧ и .

В случае реализации атаки с принуждением атакующему предоставляется вспомогательный секретный ключ в виде подключей K₃, K₄. Расшифрование криптограммы (C₁, C₂, …, С_d) no вспомогательному секретному ключу, выполненное по формуле

даст атакующему значение дополнительного осмысленного сообщения . Владелец секретного ключа расшифровывает криптограмму по такой же формуле, но с использованием K₁ и K2, что приводит к восстановлению секретного сообщения:

Таким образом, одна и та же процедура расшифрования криптограммы (C₁, C₂, …, C_d) приводит к получению двух различных осмысленных сообщений, в зависимости от используемых параметров, входящих в формулу расшифрования криптограммы (C₁, C₂, …, С_d). При этом без наличия всех элементов секретного ключа доказательство того, что кроме осмысленного сообщения из криптограммы может быть восстановлено другое осмысленное сообщение, является вычислительно невыполнимым.

Рассмотрим конкретные примеры реализации заявленного способа шифрования сообщения М, представленного в виде МДЧ.

Пример 1. Шифрование сообщения, представленного в виде МДЧ М, осуществляют путем формирования секретного ключа в виде набора подключей K₁, K₂, K₃, K₄, генерации вспомогательного простого МДЧ p>М, генерации вспомогательного МДЧ R₁ по формуле , генерации вспомогательного МДЧ R₂ путем формирования дополнительного осмысленного сообщения , и генерации R₂ по формуле , и формирования криптограммы в виде набора МДЧ (C₁, C₂), который является решением системы уравнений, включающей следующие два уравнения и , которую можно записать в виде

В соответствии методом решения систем линейных уравнений, известным как метод определителей [Курош А.Г. Курс высшей алгебры. - М.: Наука, 1971. - 431 с.], решение вычисляется по следующим формулам:

Различные способы реализации вычислений по этой формуле задают различные возможные варианты реализации процедуры формирования криптограммы.

Пример 2. Вероятностное шифрование сообщения, представленного в виде МДЧ М, осуществляют путем формирования секретного ключа в виде набора подключей K₁, K₂, K₃, K₄, генерации простого МДЧр>М, генерации вспомогательных МДЧ генерации случайного вспомогательного МДЧ R₂ путем формирования дополнительного осмысленного сообщения и генерации R₂ по формуле генерации случайного вспомогательного МДЧ R₃<p и формирования криптограммы в виде набора МДЧ (C₁, C₂, С₃), который является решением системы уравнений, включающей следующие три уравнения которую можно записать в виде

Процедура формирования криптограммы (C₁, C₂, С₃) включает выполнение последовательности операций, приводящих к получению решения последней системы уравнений. Конкретный вариант процедуры формирования криптограммы зависит от используемого метода решения этой системы уравнений, например, при использовании метода определителей формирование криптограммы включает следующую последовательность действий:

1. Вычислить главный определитель системы уравнений:

2. Вычислить определитель, получаемый путем замены первого столбца главного определителя столбцом свободных членов:

3. Вычислить определитель, получаемый путем замены второго столбца главного определителя столбцом свободных членов:

4. Вычислить определитель, получаемый путем замены третьего столбца главного определителя столбцом свободных членов:

5. Вычислить значения С₁, С₂, С₃ по следующим формулам:

Формирование криптограммы может также быть осуществлено в виде процедуры решения рассматриваемой системы уравнений методом исключения переменных.

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

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

Приложение

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

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

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

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

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

5. Простое МДЧ - МДЧ, которое не делится нацело ни на какое другое число, кроме единицы и самого себя.

6. Взаимно простые МДЧ - МДЧ, наибольший общий делитель которых равен единице.

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

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

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

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

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

12. Операция возведения числа S в дискретную степень А по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1, 2, …, n-1}, включающем n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю [см. Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. - СПб, БХВ-Петербург, 2002. - с.58-61 или Б.Шнайер. Прикладная криптография. - М.: «Триумф», 2002. - с.278-280] и электронные устройства осуществляющие эту операцию с большой скоростью [У.Диффи. Первые десять лет криптографии с открытым ключом // ТИИЭР. 1988, т.76. №5, с.67-68]; выполнение операции возведения числа S в дискретную степень Z по модулю n обозначается как W=S^z modn, где W - число являющееся результатом выполнения данной операции.

13. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.; Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с].

14. Показатель q по модулю n числа α, являющегося взаимно простым с n - это минимальное из чисел γ, для которых выполняется условие α^γmod n=1, т.е. q=min{γ₁, γ₂, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].

15. Обратный элемент по модулю n к числу α, являющемуся взаимно простым с n, есть натуральное число, обозначаемое как α^-1, для которого выполняется условие α^-1α=1; для любого числа, являющегося взаимно простым с модулем, существует элемент, обратный этому числу. Известны эффективные алгоритмы вычисления обратных элементов [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М.: Радио и связь. - С.308-310].

16. Сравнение - выражение, состоящее из правой и левой частей, такое, что значение левой части сравнимо со значением правой части по заданному модулю n [Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с.].

17. Сравнимость двух заданных значений по модулю некоторого числа m - это равенство остатков от деления заданных значений на m. n [Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с.].

18. Конечное поле - алгебраическая структура, содержащая конечное число элементов, над которым определены операции сложения и умножения, содержащая единицу (нейтральный элемент по умножению) и нуль (нейтральный элемент по сложению). Например, множество МДЧ {0, 1, …, р-1} с операциями сложения и умножения по модулю простого числа p является полем.

1. Способ шифрования сообщения М, представленного в виде многоразрядного двоичного числа, заключающийся в формировании секретного ключа и формировании криптограммы, зависящей от сообщения М и от секретного ключа, отличающийся тем, что секретный ключ формируют в виде набора подключей K₁, K₂,…, K_h, где h≥1, генерируют вспомогательные многоразрядные двоичные числа р, …, …, …, …, R₁, R₂, …, R_u, где 1<d и 1≤u≤d, и формируют криптограмму в виде набора многоразрядных двоичных чисел C₁, C₂,…, С_d, который удовлетворяет системе уравнений …, где, по крайней мере, одно из многоразрядных двоичных чисел R₁, R₂,…, R_u зависит от сообщения М и, по крайней мере, одно из многоразрядных двоичных чисел …, …, …, …, зависит от одного из подключей K₁, K₂,…, K_h.

2. Способ по п.1, отличающийся тем, что секретный ключ формируют в виде набора подключей K₁, K₂, K₃, K₄, генерируют вспомогательные многоразрядные двоичные числа р, генерируют вспомогательное многоразрядное двоичное число R₂ путем формирования дополнительного сообщения , представленного в виде многоразрядного двоичного числа, и генерации R₂ по формуле и формируют криптограмму в виде набора многоразрядных двоичных чисел C₁, C₂, который удовлетворяет системе уравнений

3. Способ по п.1, отличающийся тем, что секретный ключ формируют в виде набора подключей K₁, K₂, K₃, K₄, генерируют вспомогательные многоразрядные двоичные числа p, генерируют вспомогательное многоразрядное двоичное число R₂ путем формирования дополнительного сообщения представленного в виде многоразрядного двоичного числа, и генерации R₂ по формуле генерируют случайное вспомогательное многоразрядное двоичное число R₃<р и формируют криптограмму в виде набора многоразрядных двоичных чисел C₁, C₂, С₃, который удовлетворяет системе уравнений