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

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

Реферат

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

Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования 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], представленного в виде двоичной последовательности, путем генерации секретного ключа К, разбиения сообщения М на блоки М₁, М₂,…, М_k, где k - число блоков в сообщении. Блоки двоичных данных М_i, i=1, 2,…, k имеют фиксированную разрядность n, где n≥64 бит. Шифруют блок М₁ по секретному ключу, получая блок криптограммы С₁, затем, начиная со значения i=2 и до значения i=k, суммируют с помощью операции поразрядного суммирования блок криптограммы С_i-1 и блок М_i, полученный в результате суммирования блок данных шифруют по секретному ключу, получая в результате текущий блок криптограммы С_i. Совокупность блоков криптограммы C₁, C₂,…, С_k представляет собой криптограмму, содержащую сообщение М в скрытом виде. Извлечение сообщения М из криптограммы практически возможно только с использованием секретного ключа, использованного при шифровании, за счет чего достигается защита информации, содержащейся в сообщении М при его передаче по открытым каналам связи. Данный способ обеспечивает улучшение статистических свойств криптограммы, однако он имеет недостаток, состоящий в том, что теряется возможность независимого расшифрования отдельных блоков криптограммы.

Наиболее близким по своей технической сущности к заявляемому способу шифрования сообщения М, представленного в виде многоразрядного двоичного числа (МДЧ), является способ, описанный в патенте США №2103829 [Hellman M.E., Pohlig S.C. Exponentiation Cryptographic Apparatus and Method // U.S. Patent # 4,424,414. 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]). При этом процедура расшифрования криптограммы не зависит от значения предоставляемого ключа, т.е. расшифрование криптограммы С по секретному ключу и по вспомогательному секретному ключу осуществляется единообразно. Данный недостаток связан с тем, что в способе прототипе вычислительно неосуществимо нахождение вспомогательного секретного ключа, по которому криптограмма расшифровывается в осмысленное сообщение , отличное от сообщения М, из-за чего атакующему может быть предоставлен только секретный ключ, который позволяет атакующему получить доступ к секретному сообщению, т.е. не обеспечивается стойкость алгоритма шифрования к атаке с принуждением.

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

Указанная цель достигается тем, что в способе шифрования сообщения М, представленного в виде МДЧ, заключающемся в формировании секретного ключа и формировании криптограммы, зависящей от сообщения М и от секретного ключа, новым является то, что секретный ключ формируют в виде набора подключей К₁, К₂,…, К_h, где h≥1, и вспомогательных МДЧ p₁, p₂,…, p_u, p_u+1, где u≥1, генерируют вспомогательные МДЧ R₁, R₂,…, R_u, D и формируют криптограмму в виде МДЧ С, которое удовлетворяет системе сравнений C≡R₁ mod р₁, C≡R₂ mod р₂,…, C≡R_u mod p_u, C≡D mod p_u+1, где, по крайней мере, одно из МДЧ R₁, R₂,…, R_u зависит от сообщения М и от одного из подключей К₁, К₂,…, К_h.

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

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

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

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

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

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

Возможность реализации заявленного способа и корректность его работы объясняется тем, что согласно китайской теореме об остатках (см. с. в книге [Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. - Санкт-Петербург, БХВ-Петербург, 2010. - 304 с.]) при выборе взаимно простых МДЧ p₁, р₂,…, p_u, p_u+1 для любых значений МДЧ R₁, R₂,…, R_u и D существует и легко вычисляется единственное МДЧ С, которое удовлетворяет системе сравнений C≡R₁ mod р₁, С≡R₂ mod p₂,…, C≡R_u mod p_u, C≡D mod p_u+1, такое, что выполняется соотношение С<p₁,p₂,…, p_up_u+1. То есть криптограмма С представляет собой решение указанной системы сравнений. Процедура формирования криптограммы С состоит в выполнении некоторой последовательности операций, обеспечивающих нахождение решения указанной системы сравнений. Конкретный вариант процедуры формирования криптограммы С зависит от конкретного варианта очередности выполняемых операций. В формулировке утверждения китайской теоремы об остатках содержится формула, по которой легко вычисляется решение системы сравнений. Формирование МДЧ R₁, R₂,…, R_u и D может быть выполнено различными способами, выбор которых определяется конкретным применением заявленного способа шифрования сообщения М, представленного в виде МДЧ. В частности, для реализации вероятностного шифрования одно из этих МДЧ, например R₁, формируется в зависимости от сообщения М и от подключа К₁ и МДЧ р₁ по формуле R₁=MK₁ mod p₁, а МДЧ R₂,…, R_u и D формируются в виде случайных МДЧ. Каждое из сформированных МДЧ R₁, R₂,…, R_u и D влияет на значение криптограммы С, однако из всех возможных вариантов значения С при расшифровании криптограммы по формуле будет восстановлено сообщение М. При необходимости обеспечить стойкость к атакам на основе известных или специально подобранных текстов формируются подключ К₁ и МДЧ р₁, имеющие разрядность не менее 256 бит, а МДЧ R₁ генерируется по формуле R₁=M^eK₁ mod p₁, где е - МДЧ, используемое в качестве дополнительного подключа и являющееся взаимно простым с МДЧ р₁-1. В последнем случае расшифрование криптограммы выполняется по формуле , где d=e^-1 mod p₁-1.

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

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

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

.

В соответствии с китайской теоремой об остатках решение вычисляется по следующей формуле:

.

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

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

.

В соответствии с китайской теоремой об остатках решение этой системы сравнений вычисляется по следующей формуле:

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

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

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

Приложение

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

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 mod n, где W - число, являющееся результатом выполнения данной операции.

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

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

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

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

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

1. Способ блочного шифрования сообщения М, представленного в виде многоразрядного двоичного числа, заключающийся в формировании секретного ключа и формировании криптограммы, зависящей от сообщения М и от секретного ключа, отличающийся тем, что секретный ключ формируют в виде набора подключей К₁, К₂,…,K_h, где h≥1, и вспомогательных многоразрядных двоичных чисел p₁, p₂,…,p_u, p_u+1, где u≥1, генерируют вспомогательные многоразрядные двоичные числа R₁, R₂,…,R_u, D и формируют криптограмму в виде многоразрядного двоичного числа С, которое удовлетворяет системе сравнений C≡R₁ mod p₁, C≡R₂ mod p₂,…, C≡R_u mod p_u, C≡D mod p_u+1, где по крайней мере одно из чисел R₁, R₂,…,R_u зависит от сообщения М и от одного из подключей К₁, К₂,…,К_h.

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

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