RU2459276C1

RU2459276C1 - Method for coding of m message represented as multidigit binary number

Info

Publication number: RU2459276C1
Application number: RU2011134131/08A
Authority: RU
Inventors: Николай Андреевич МОЛДОВЯН (RU); Николай Андреевич Молдовян; Александр Андреевич МОЛДОВЯН (RU); Александр Андреевич Молдовян
Original assignee: Николай Андреевич Молдовян
Priority date: 2011-08-12
Filing date: 2011-08-12
Publication date: 2012-08-20

Abstract

FIELD: electricity.

SUBSTANCE: method of unit coding of a message M represented in a binary form includes the following sequence of actions: generation of a secret key in the form of a set of subkeys K₁, K₂, …, K_h, where h≥1, generation of auxiliary multidigit binary numbers (MBN) p, Q₁ ⁽¹⁾,Q₂ ⁽¹⁾,…,Q_d ⁽¹⁾, Q₁ ⁽²⁾, Q₂ ⁽²⁾, …, Q_d ⁽²⁾,…, Q₁ ^(k), Q₂ ^(u),…, Q_d ^(u), R₁, R₂, …, R_u, where 1<d and 1<u<d, generation of a cryptogram in the form of a set of MBN, C₁, C₂, …, C_d, which complies with a system of equations Q₁ ⁽¹⁾, C₁ + Q₂ ⁽¹⁾C₂ +… + Q_d ⁽¹⁾C_d = R₁ mod p, Q₁ ⁽²⁾C₁+Q₂ ⁽²⁾C₂+…+ Q_d ⁽²⁾Cd =R₂ mod p, …,Q₁ ^(u)C₁+Q₂ ^(u)C₂+…+Q_d ^(u)C_d =R_u mod p, where at least one of multidigit binary numbers R₁, R₂,…, R_u depends on an M message, and at least one of multidigit binary numbers Q₂ ⁽¹⁾,…,Q_d ⁽¹⁾, Q₁ ⁽²⁾, Q₂ ⁽¹⁾,…,Q_d ⁽²⁾,…,Q_d ⁽²⁾,…,Q₁ ^(u), Q₂ ^(u),…,Q_d ^(u) depends on one of subkeys K₁ K₂, …, K_h.

EFFECT: increased resistance of a cryptogram.

3 cl, 1 ex

Description

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов и устройств для защиты информации, передаваемой по телекоммуникационным сетям путем шифрования (толкование используемых в описании терминов приведено в приложении) сообщений (информации).The invention relates to the field of telecommunications and computer technology, and more particularly to the field of cryptographic methods and devices for protecting information transmitted over telecommunication networks by encryption (the interpretation of the terms used in the description is given in the appendix) of messages (information).

Известны способы шифрования электронных сообщений, представленных в цифровом виде, а именно в виде двоичных данных, выполняемые по секретному ключу, например способ, реализованный в виде алгоритма блочного шифрования 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].There are known methods of encrypting electronic messages presented in digital form, namely in the form of binary data, performed using a secret key, for example, a method implemented in the form of an RC5 block encryption algorithm [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons , Inc., New York, 1996, pp. 344-346]. The method includes generating a secret key in the form of a set of subkeys, splitting an n-bit binary information block into n / 2-bit information subunits A and B, and sequentially converting these subunits. The subblocks are transformed by sequentially performing linear and nonlinear operations on them, for which summation modulo 2 ^m , where m = n / 2 = 8.16.32.64, bitwise summation modulo 2 and a cyclic shift to the left are used, and the number the bit by which the converted sub-block is shifted depends on the value of the other sub-block. The latter property is characteristic of the RC5 method and determines the dependence of the cyclic shift operation at the current step of the conversion of the subunit on the initial value of the input data block. The information subblock, for example subblock B, is transformed by superimposing subblock A onto subblock B using the bitwise summing operation modulo 2 B: = B⊕A. After that, the operation of cyclic left shift by the number of bits equal to the value of subunit A is performed on subblock B: B: = B <<< A. Then, over the subblock B and one of the subkeys K, the summation operation is performed modulo 2 ^m , where m is the length of the subblock in bits: B: = (B + K) mod 2 ^m . After that, subunit A is similarly converted. Depending on the size of the key, several such iterations of the conversion of both subunits are performed. This method provides a fairly high encryption speed in software implementation. The disadvantage of the RC5 encryption method is its low resistance to differential and linear types of cryptanalysis [Kaliski BS, Yin YL 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 представляет собой криптограмму, содержащую сообщение М в скрытом виде. Извлечение сообщения М из криптограммы практически возможно только с использованием секретного ключа, использованного при шифровании, за счет чего достигается защита информации, содержащейся в сообщении М при его передаче по открытым каналам связи. Данный способ обеспечивает улучшение статистических свойств криптограммы, однако он имеет недостаток, состоящий в том, что теряется возможность независимого расшифрования отдельных блоков криптограммы.A known method of encrypting a message M [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, pp. 193-194], presented as a binary sequence, by generating a secret key K, splitting the message M into blocks M ₁ , M ₂ , ..., M _k , where k is the number of blocks in the message. The binary data blocks M _i , i = 1, 2, ..., k, have a fixed bit width n, where n≥64 bits. The M ₁ block is encrypted with the secret key, obtaining the cryptogram block C ₁ , then, starting from the value i = 2 and up to the value i = k, the cryptogram block C _i-1 and the block M _i obtained by summing are summed using the bitwise summing operation the data block is encrypted with a secret key, resulting in the current cryptogram block C _i . The set of blocks of the cryptogram C ₁ , C ₂ , ..., C _k is a cryptogram containing the message M in a hidden form. Removing the message M from the cryptogram is practically possible only using the secret key used in encryption, which ensures protection of the information contained in the message M when it is transmitted over open communication channels. This method provides an improvement in the statistical properties of the cryptogram, however, it has the disadvantage that the ability to independently decrypt individual blocks of the cryptogram is lost.

Наиболее близким по своей технической сущности к заявляемому способу шифрования сообщения М, представленного в виде многоразрядного двоичного числа (МДЧ), является способ, описанный в патенте США №2103829 [Hellman M.E., Pohlig S.C. Exponentiation Cryptographic Apparatus and Method // U.S. Patent # 4424414. Jan. 3, 1984]. Способ-прототип включает в себя генерацию простого МДЧ р, формирование секретного ключа в виде МДЧ е и формирование криптограммы, зависящей от сообщения М и от секретного ключа е, причем криптограмму формируют в виде МДЧ С, которое удовлетворяет соотношению С=M^emod p.The closest in technical essence to the claimed method of encrypting message M, presented in the form of a multi-bit binary number (MDC), is the method described in US patent No. 2103829 [Hellman ME, Pohlig SC Exponentiation Cryptographic Apparatus and Method // US Patent # 4424414. Jan. 3, 1984]. The prototype method includes the generation of a simple MDC p, the formation of a secret key in the form of MDC e and the formation of a cryptogram depending on the message M and the secret key e, and the cryptogram is formed in the form of MDC C, which satisfies the relation C = 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) по секретному ключу и по вспомогательному секретному ключу осуществляется единообразно. Данный недостаток связан с тем, что в способе-прототипе вычислительно неосуществимо нахождение вспомогательного секретного ключа, по которому криптограмма расшифровывается в осмысленное сообщение

, отличное от сообщения М, из-за чего атакующему может быть предоставлен только секретный ключ, который позволяет атакующему получить доступ к секретному сообщению, т.е. не обеспечивается стойкость алгоритма шифрования к атаке с принуждением.The disadvantage of the prototype method is the vulnerability to coercive attacks, which suggest the need to provide the attacker with some random auxiliary secret key, according to which the cryptogram is decrypted into some meaningful message

different from the message M encrypted with a secret key (see [R. Canetti, C. Work, M. Naor, R. Ostrovsky, Deniable Encryption // Advances in cryptology - CRYPTO 1997. / Conference Proceedings, pp.90-104 ] and [M. H. Ibrahim, A Method for Obtaining Deniable Public-Key Encryption // International Journal of Network Security. 2009. Vol.8. No.1, pp.1-9]). The cryptogram decryption procedure does not depend on the value of the provided key, i.e. decryption of the cryptogram (C ₁ , C ₂ , ..., C _d ) by the secret key and by the auxiliary secret key is carried out in the same way. This drawback is due to the fact that in the prototype method it is computationally impractical to find an auxiliary secret key, by which the cryptogram is decrypted into a meaningful message

different from message M, because of which only the secret key can be provided to the attacker, which allows the attacker to access the secret message, i.e. the encryption algorithm is not resistant to a forced attack.

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

.The purpose of the claimed technical solution is to develop a method for encrypting message M, presented in the form of MDC, which provides resistance to attacks with coercion by generating a cryptogram that depends on the secret key, which includes an auxiliary secret key as its component, and on an additional meaningful message

.

Указанная цель достигается тем, что в способе шифрования сообщения М, представленного в виде МДЧ, заключающемся в формировании секретного ключа и формировании криптограммы, зависящей от сообщения М и от секретного ключаThis goal is achieved by the fact that in the method of encrypting the message M, presented in the form of MDC, which consists in the formation of a secret key and the formation of a cryptogram depending on the message M and the secret key

новым является то, что секретный ключ формируют в виде набора подключей К₁, 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.new is that the secret key is formed in the form of a set of subkeys K ₁ , K ₂ , ..., K _h , where h≥1, generate auxiliary MDC p,

,

, ...,

,

, ...,

,

, ...,

, R ₁ , R ₂ , ..., R _u , where 1 <d and 1≤u≤d, and form a cryptogram in the form of a set of MDC C ₁ , C ₂ , ..., C _d , which satisfies the system of equations

,

, ...,

, where at least one of the MDC R ₁ , R ₂ , ..., R _u depends on the message M and at least one of the MDC

,

, ...,

,

, ...,

,

, ...,

depends on one of the subkeys K ₁ , K ₂ , ..., K _h .

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

,

, генерируют вспомогательное МДЧ R₂ путем формирования дополнительного сообщения

, представленного в виде МДЧ, и генерации R₂ по формуле

и формируют криптограмму в виде набора МДЧ С₁, С₂, который удовлетворяет системе уравнений

,

.New is also that the secret key is formed in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , generate auxiliary MDC p,

,

generate auxiliary MDC R ₂ by forming an additional message

represented in the form of MDC, and the generation of R ₂ according to the formula

and form a cryptogram in the form of a set of MDC C ₁ C ₂ that satisfies the system of equations

,

.

Формирование правой части уравнений по формулам

и

обеспечивает стойкость заявленного способа шифрования к атакам на основе известных сообщений

и М. При этом криптограмма С расшифровывается по секретному ключу в сообщение М, а по вспомогательному секретному ключу - в сообщение

. Вспомогательным секретным ключом в данном частном варианте заявленного способа является совокупность подключей К₃ и К₄. (Заметим, что понятие вспомогательного секретного ключа не относится к признакам заявленного способа, а относится к рассмотрению стойкости заявленного способа к атакам с принуждением.)The formation of the right side of the equations by the formulas

and

provides resistance of the claimed encryption method to attacks based on known messages

and M. In this case, the cryptogram C is decrypted by the secret key into the message M, and by the auxiliary secret key into the message

. Auxiliary secret key in this particular embodiment of the claimed method is a combination of subkeys K ₃ and K ₄ . (Note that the concept of an auxiliary secret key does not apply to the features of the claimed method, but refers to the consideration of the resistance of the claimed method to forced attacks.)

,

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

,

generate auxiliary MDC R ₂ by forming an additional message

generate a random auxiliary MDC R ₃ <p and form a cryptogram in the form of a set of MDC C ₁ , C ₂ , C ₃ that satisfies the system of equations

,

.

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

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

. Вспомогательным секретным ключом в данном частном варианте заявленного способа является совокупность подключей K₃ и K₄.Using as a right part of one of the comparisons a random MDC provides the possibility of performing probabilistic encryption using the claimed method, in which multiple encryption of the same pair of messages

and M on the same secret key ensures the formation of different cryptograms. Moreover, any of the generated cryptograms, which is a set of MDC C ₁ , C ₂ , ..., C _{d is} decrypted by the secret key into message M, and by the auxiliary secret key into the message

. Auxiliary secret key in this particular embodiment of the claimed method is a combination of subkeys K ₃ and K ₄ .

Благодаря указанной новой совокупности существенных признаков за счет возможности совместного шифрования, по крайней мере, двух осмысленных сообщений обеспечивается стойкость к атакам с принуждением, т.е. возможность расшифрования отдельных сообщений путем использования в процедуре расшифрования различных наборов подключей, составляющих секретный ключ.Thanks to this new set of essential features, due to the possibility of joint encryption of at least two meaningful messages, resistance to coercive attacks is ensured, i.e. the ability to decrypt individual messages by using different sets of subkeys that make up the private key in the decryption procedure.

Проведенный анализ уровня техники позволил установить, что в известных источниках информации аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного изобретения условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния существенных признаков заявленного изобретения на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».The analysis of the prior art made it possible to establish that there are no analogues in known sources of information characterized by a combination of features identical to all the features of the claimed technical solution, which indicates the compliance of the claimed invention with the condition of patentability “novelty”. Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the prior art. The prior art also did not reveal the popularity of the influence of the essential features of the claimed invention to achieve the specified technical result. Therefore, the claimed invention meets the condition of patentability "inventive step".

Возможность реализации заявленного способа и корректность его работы объясняется тем, что система из 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) состоит в выполнении некоторой последовательности операций, обеспечивающих нахождение решения указанной системы уравнений. Существуют различные способы решения систем линейных уравнений, каждый из которых определяет конкретный вариант выполнения процедуры формирования криптограммы.The possibility of implementing the claimed method and the correctness of its operation is explained by the fact that a system of u linear equations defined over any field with d unknowns, where d≥u, has at least one solution. That is, with a simple auxiliary MDC p and any values of auxiliary MDC

,

, ...,

,

, ...,

,

, ...,

, R ₁ , R ₂ , ..., R _{u the} cryptogram C = (C ₁ , C ₂ , ..., C _d ), which is an ordered set of MDC C ₁ , C ₂ , ..., C _d , can be formed. For d = u, there is a single value of the generated cryptogram. For d> u, there is a case of probabilistic encryption and there are a large number of different cryptograms, decryption of each of them using a secret key will lead to the receipt of message M. To obtain a specific value of the cryptogram in the case of probabilistic encryption, the cryptogram is generated by generating du linear equations with random coefficients and the random right-hand side, adding the generated linear equations to the existing system of u linear equations and solving the resulting expansion rennoy system of linear equations. The value of the generated cryptogram is a solution to the specified extended system of equations. The procedure for generating a cryptogram (C ₁ , C ₂ , ..., C _d ) consists in performing a certain sequence of operations providing a solution to the indicated system of equations. There are various ways to solve systems of linear equations, each of which determines a specific embodiment of the cryptogram formation procedure.

Формирование МДЧ R₁, R₂, …, R_u может быть выполнено различными способами, выбор которых определяется конкретным применением заявленного способа. В частности, для реализации вероятностного шифрования одно из этих МДЧ, например R₁, формируется в зависимости от сообщения М и от подключа К₁ по формуле R₁=МK₁modp₁, а МДЧ R₂, R₃, …, R_u формируются в виде случайных МДЧ. Каждое из сформированных МДЧ R₂, R₃, …, R_u влияет на значение криптограммы (C₁, C₂, …, C_d), однако из всех возможных вариантов значения (C₁, С₂, …, С_d) при расшифровании криптограммы по формулеThe formation of MDC R ₁ , R ₂ , ..., R _u can be performed in various ways, the choice of which is determined by the specific application of the claimed method. In particular, to implement probabilistic encryption, one of these MDCs, for example, R ₁ , is formed depending on the message M and on the subkey K ₁ according to the formula R ₁ = MK ₁ modp ₁ , and MDC R ₂ , R ₃ , ..., R _u are formed in the form of random FDM. Each of the generated MDCs R ₂ , R ₃ , ..., R _u affects the value of the cryptogram (C ₁ , C ₂ , ..., C _d ), however, out of all possible options, the values (C ₁ , C ₂ , ..., C _d ) at decrypt cryptograms according to the formula

будет восстановлено сообщение М. При необходимости обеспечить стойкость к атакам на основе известных или специально подобранных текстов формируются подключ К₁ и МДЧp, имеющие разрядность не менее 256 бит, а МДЧ R₁ формируется по формуле R₁=M^eK₁modp₁, где е - МДЧ, используемое в качестве дополнительного подключа и являющееся взаимно простым с МДЧр-1. В последнем случае расшифрование криптограммы (C₁, C₂, …, C_d) выполняется по формулеmessage M will be restored. If necessary, to provide resistance to attacks on the basis of known or specially selected texts, subkey K ₁ and MDCp are formed, having a capacity of at least 256 bits, and MDC R ₁ is formed by the formula R ₁ = M ^e K ₁ modp ₁ , where e - MDC, used as an additional subkey and is mutually simple with MDC-1. In the latter case, the decryption of the cryptogram (C ₁ , C ₂ , ..., C _d ) is performed according to the formula

где h=е^-1mod р-1.where h = e ^-1 mod p-1.

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

, генерируют вспомогательные МДЧ

и

.To ensure resistance to attacks with coercion, the claimed method is used, for example, as follows. The secret key is formed in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , such that the values of the subkeys K ₁ and K ₃ are coprime with the MDC p-1. Generate additional meaningful message

generate auxiliary MDC

and

.

В случае реализации атаки с принуждением атакующему предоставляется вспомогательный секретный ключ в виде подключей K₃, K₄. Расшифрование криптограммы (C₁, C₂, …, С_d) no вспомогательному секретному ключу, выполненное по формулеIn the case of an attack with coercion, the attacker is provided with an auxiliary secret key in the form of subkeys K ₃ , K ₄ . Decryption of the cryptogram (C ₁ , C ₂ , ..., C _d ) no auxiliary secret key, performed according to the formula

даст атакующему значение дополнительного осмысленного сообщения

. Владелец секретного ключа расшифровывает криптограмму по такой же формуле, но с использованием K₁ и K2, что приводит к восстановлению секретного сообщения:will give the attacker the value of an additional meaningful message

. The owner of the secret key decrypts the cryptogram using the same formula, but using K ₁ and K2, which leads to the restoration of the secret message:

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

из криптограммы может быть восстановлено другое осмысленное сообщение, является вычислительно невыполнимым.Thus, the same procedure for decrypting a cryptogram (C ₁ , C ₂ , ..., C _d ) leads to two different meaningful messages, depending on the parameters used, which are included in the decryption formula of the cryptogram (C ₁ , C ₂ , ..., C _d ). In this case, without the presence of all elements of the secret key, proof that, in addition to a meaningful message

another meaningful message can be restored from the cryptogram; it is computationally impossible.

Рассмотрим конкретные примеры реализации заявленного способа шифрования сообщения М, представленного в виде МДЧ.Consider specific examples of the implementation of the claimed method of encrypting message M, presented in the form of MDC.

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

, генерации вспомогательного МДЧ R₂ путем формирования дополнительного осмысленного сообщения

, и генерации R₂ по формуле

, и формирования криптограммы в виде набора МДЧ (C₁, C₂), который является решением системы уравнений, включающей следующие два уравнения

и

, которую можно записать в видеExample 1. The encryption of the message presented in the form of MDC M, is carried out by generating a secret key in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , generating an auxiliary simple MDC p> M, generating an auxiliary MDC R ₁ according to the formula

generating auxiliary MDC R ₂ by forming an additional meaningful message

, and generating R ₂ according to the formula

, and forming a cryptogram in the form of a set of MDC (C ₁ , C ₂ ), which is a solution to a system of equations that includes the following two equations

and

which can be written as

В соответствии методом решения систем линейных уравнений, известным как метод определителей [Курош А.Г. Курс высшей алгебры. - М.: Наука, 1971. - 431 с.], решение вычисляется по следующим формулам:In accordance with the method of solving systems of linear equations, known as the method of determinants [Kurosh A.G. Course of higher algebra. - M .: Nauka, 1971. - 431 p.], The solution is calculated by the following formulas:

Различные способы реализации вычислений по этой формуле задают различные возможные варианты реализации процедуры формирования криптограммы.Different ways of implementing calculations using this formula specify various possible options for implementing the cryptogram formation procedure.

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

генерации случайного вспомогательного МДЧ R₂ путем формирования дополнительного осмысленного сообщения

и генерации R₂ по формуле

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

которую можно записать в видеExample 2. Probabilistic encryption of a message presented in the form of MDC M, is carried out by forming a secret key in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , generating a simple FDM> M, generating auxiliary MDC

generating random auxiliary MDC R ₂ by forming an additional meaningful message

and generating R ₂ according to the formula

generating a random auxiliary MDC R ₃ <p and generating a cryptogram in the form of a set of MDC (C ₁ , C ₂ , C ₃ ), which is a solution to a system of equations including the following three equations

which can be written as

Процедура формирования криптограммы (C₁, C₂, С₃) включает выполнение последовательности операций, приводящих к получению решения последней системы уравнений. Конкретный вариант процедуры формирования криптограммы зависит от используемого метода решения этой системы уравнений, например, при использовании метода определителей формирование криптограммы включает следующую последовательность действий:The procedure for generating a cryptogram (C ₁ , C ₂ , C ₃ ) involves performing a sequence of operations leading to the solution of the last system of equations. The specific version of the cryptogram formation procedure depends on the method used to solve this system of equations, for example, when using the determinant method, cryptogram formation includes the following sequence of actions:

1. Вычислить главный определитель системы уравнений:1. Calculate the main determinant of the system of equations:

2. Вычислить определитель, получаемый путем замены первого столбца главного определителя столбцом свободных членов:2. Calculate the determinant obtained by replacing the first column of the main determinant with a column of free members:

3. Вычислить определитель, получаемый путем замены второго столбца главного определителя столбцом свободных членов:3. Calculate the determinant obtained by replacing the second column of the main determinant with a column of free members:

4. Вычислить определитель, получаемый путем замены третьего столбца главного определителя столбцом свободных членов:4. Calculate the determinant obtained by replacing the third column of the main determinant with a column of free members:

5. Вычислить значения С₁, С₂, С₃ по следующим формулам:5. Calculate the values of C ₁ , C ₂ , C ₃ according to the following formulas:

Формирование криптограммы может также быть осуществлено в виде процедуры решения рассматриваемой системы уравнений методом исключения переменных.The formation of a cryptogram can also be carried out in the form of a procedure for solving the considered system of equations by the method of eliminating variables.

Приведенные примеры показывают, что заявляемый способ шифрования сообщения М, представленного в виде МДЧ, функционирует корректно, технически реализуем и позволяет решить поставленную задачу.The above examples show that the claimed method of encrypting the message M, presented in the form of MDC, functions correctly, is technically feasible and allows us to solve the problem.

Заявляемый способ шифрования сообщения М, представленного в виде МДЧ, может быть применен для разработки средств защиты информации от несанкционированного доступа и средств защищенной широковещательной рассылки сообщений с селективным доступом к сообщениям со стороны получателей при обеспечении идентичности процедуры расшифрования одной и той же криптограммы. Такие средства защищенной широковещательной рассылки сообщений решают задачу неотслеживаемости трафика при передаче информации по телекоммуникационным каналам.The inventive method of encrypting message M, presented in the form of MDC, can be used to develop means of protecting information from unauthorized access and means of secure broadcasting of messages with selective access to messages from recipients while ensuring the identity of the decryption process of the same cryptogram. Such means of secure broadcast messaging solve the problem of traffic non-tracking when transmitting information over telecommunication channels.

Приложениеapplication

Толкование терминов, используемых в описании заявкиInterpretation of the terms used in the description of the application

1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.1. Binary digital electromagnetic signal - a sequence of bits in the form of zeros and ones.

2. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.2. Parameters of a binary digital electromagnetic signal: bit depth and order of single and zero bits.

3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например число 10011 является 5-разрядным.3. The bit depth of a binary digital electromagnetic signal is the total number of its single and zero bits, for example, the number 10011 is 5-bit.

4. Многоразрядное двоичное число (МДЧ) - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».4. A multi-bit binary number (MDC) is a binary digital electromagnetic signal, interpreted as a binary number and represented as a sequence of digits “0” and “1”.

5. Простое МДЧ - МДЧ, которое не делится нацело ни на какое другое число, кроме единицы и самого себя.5. Simple MDC - MDC, which is not completely divisible by any other number, except for one and itself.

6. Взаимно простые МДЧ - МДЧ, наибольший общий делитель которых равен единице.6. Mutually simple MDC - MDC, the largest common factor of which is equal to one.

7. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для выполнения криптографических процедур шифрования сообщения и расшифрования криптограммы.7. Secret key - a binary digital electromagnetic signal used to perform cryptographic procedures for encrypting a message and decrypting a cryptogram.

8. Криптограмма - двоичный цифровой электромагнитный сигнал, представленный в виде МДЧ, полученного в результате шифрования сообщения, представленного в виде МДЧ. Криптограмма представляется, например, в двоичном виде как последовательность цифр «0» и «1».8. A cryptogram is a binary digital electromagnetic signal presented in the form of MDC obtained as a result of encrypting a message presented in the form of MDC. A cryptogram is presented, for example, in binary form as a sequence of digits “0” and “1”.

9. Вероятностное шифрование - процедура шифрования сообщения, представленного в виде МДЧ, в которой используются случайные МДЧ. В результате чего при заданном шифруемом сообщении, заданном секретном ключе и заданном алгоритме вероятностного шифрования значение криптограммы недетерминировано, однако расшифрование любой возможной криптограммы по правильному секретному ключу приводит к восстановлению одного и того же исходного сообщения.9. Probabilistic encryption - the procedure for encrypting a message presented in the form of MDC, which uses random MDC. As a result, for a given encrypted message, a given secret key and a given probabilistic encryption algorithm, the value of the cryptogram is non-deterministic, however, decryption of any possible cryptogram with the correct secret key leads to the restoration of the same original message.

10. Расшифрование - процедура преобразования криптограммы по секретному ключу, приводящая к восстановлению зашифрованного сообщения, представленного в виде МДЧ. Для чтения сообщения, представленного в виде МДЧ, оно интерпретируется как последовательность двоичных кодовых слов, которыми закодирован алфавит языка, на котором написано сообщение.10. Decryption - a procedure for converting a cryptogram by a secret key, leading to the restoration of an encrypted message, presented in the form of MDC. To read a message presented in the form of MDC, it is interpreted as a sequence of binary codewords that encoded the alphabet of the language in which the message is written.

11. Осмысленное сообщение - сообщение, представленное в виде МДЧ, интерпретация которого последовательностью двоичных кодовых слов, которыми закодирован алфавит языка, на котором написано сообщение, приводит к получению текста, содержащего слова некоторого известного языка.11. Meaningful message - a message presented in the form of MDC, the interpretation of which is a sequence of binary code words that encoded the alphabet of the language in which the message is written, leads to the receipt of text containing the words of some well-known language.

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 - число являющееся результатом выполнения данной операции.12. The operation of raising a number S to a discrete power A modulo n is an operation performed on a finite set of natural numbers {0, 1, 2, ..., n-1}, including n numbers that are the remainders of dividing all kinds of integers by a number n; the result of the operations of addition, subtraction and multiplication modulo n is a number from the same set [Vinogradov IM Fundamentals of number theory. - M .: Nauka, 1972. - 167 p.]; the operation of raising a number S to a discrete power Z modulo n is defined as a Z-fold sequential multiplication modulo n of the number S by itself, i.e. as a result of this operation, the number W is also obtained that is less than or equal to the number n-1; even for very large numbers S, Z and n, there are effective algorithms for performing the operation of raising to a discrete power modulo [see Moldovyan A.A., Moldovyan N.A., Guts N.D., Izotov B.V. Cryptography: high-speed ciphers. - SPb, BHV-Petersburg, 2002. - p. 58-61 or B. Schneier. Applied cryptography. - M .: "Triumph", 2002. - p.278-280] and electronic devices performing this operation at high speed [W. Diffie. The first ten years of public-key cryptography // TIIER. 1988, vol. 76. No. 5, p. 67-68]; the operation of raising the number S to a discrete power of Z modulo n is denoted as W = S ^z modn, where W is the number resulting from the operation.

13. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.; Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с].13. The Euler function of a natural number n is the number of numbers that are coprime with n and not exceeding n [Vinogradov IM Fundamentals of number theory. - M .: Nauka, 1972. - 167 p .; Buchstab A.A. Number theory - M .: Education, 1966. - 384 s].

14. Показатель q по модулю n числа α, являющегося взаимно простым с n - это минимальное из чисел γ, для которых выполняется условие α^γmod n=1, т.е. q=min{γ₁, γ₂, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].14. The exponent q modulo n of the number α, which is coprime with n, is the minimum of the numbers γ for which the condition α ^γ mod n = 1 holds, that is q = min {γ ₁ , γ ₂ , ...} [I. Vinogradov Fundamentals of number theory. - M .: Nauka, 1972. - 167 p.].

15. Обратный элемент по модулю n к числу α, являющемуся взаимно простым с n, есть натуральное число, обозначаемое как α^-1, для которого выполняется условие α^-1α=1; для любого числа, являющегося взаимно простым с модулем, существует элемент, обратный этому числу. Известны эффективные алгоритмы вычисления обратных элементов [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М.: Радио и связь. - С.308-310].15. The inverse element modulo n to the number α, which is coprime with n, is a natural number, denoted as α ^-1 , for which the condition α ^-1 α = 1; for any number that is coprime with the module, there is an element inverse to this number. Effective algorithms for computing inverse elements are known [Romanets Yu.V., Timofeev P.A., Shangin V.F. Information security in computer systems and networks. - M .: Radio and communication. - S.308-310].

16. Сравнение - выражение, состоящее из правой и левой частей, такое, что значение левой части сравнимо со значением правой части по заданному модулю n [Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с.].16. Comparison - an expression consisting of the right and left parts, such that the value of the left side is comparable to the value of the right side for a given module n [A. Bukhstab. Number theory - M .: Education, 1966. - 384 p.].

17. Сравнимость двух заданных значений по модулю некоторого числа m - это равенство остатков от деления заданных значений на m. n [Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с.].17. The comparability of two given values modulo a certain number m is the equality of the residuals from the division of the given values by m. n [Bukhstab A.A. Number theory - M .: Education, 1966. - 384 p.].

18. Конечное поле - алгебраическая структура, содержащая конечное число элементов, над которым определены операции сложения и умножения, содержащая единицу (нейтральный элемент по умножению) и нуль (нейтральный элемент по сложению). Например, множество МДЧ {0, 1, …, р-1} с операциями сложения и умножения по модулю простого числа p является полем.18. The final field is an algebraic structure containing a finite number of elements, over which the operations of addition and multiplication are defined, containing one (neutral element for multiplication) and zero (neutral element for addition). For example, the set of MDC {0, 1, ..., p-1} with the operations of addition and multiplication modulo a prime p is a field.

Claims

1. The method of encrypting message M, presented in the form of a multi-bit binary number, which consists in generating a secret key and generating a cryptogram depending on the message M and the secret key, characterized in that the secret key is formed as a set of subkeys K ₁ , K ₂ , ... , K _h , where h≥1, generate auxiliary multi-bit binary numbers p,

...

R ₁ , R ₂ , ..., R _u , where 1 <d and 1≤u≤d, and form a cryptogram in the form of a set of multi-bit binary numbers C ₁ , C ₂ , ..., C _d , which satisfies the system of equations

...

where at least one of the multi-bit binary numbers R ₁ , R ₂ , ..., R _u depends on the message M and at least one of the multi-bit binary numbers

...

depends on one of the subkeys K ₁ , K ₂ , ..., K _h .

2. The method according to claim 1, characterized in that the secret key is formed in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , generate auxiliary multi-bit binary numbers p,

generate an auxiliary multi-bit binary number R ₂ by forming an additional message

represented as a multi-bit binary number, and generating R ₂ by the formula

and form a cryptogram in the form of a set of multi-bit binary numbers C ₁ , C ₂ , which satisfies the system of equations

3. The method according to claim 1, characterized in that the secret key is formed in the form of a set of subkeys K ₁ , K ₂ , K ₃ , K ₄ , generate auxiliary multi-bit binary numbers p,

represented as a multi-bit binary number, and generating R ₂ by the formula

generate a random auxiliary multi-bit binary number R ₃ <p and form a cryptogram in the form of a set of multi-bit binary numbers C ₁ , C ₂ , C ₃ that satisfies the system of equations